Why there’s always a larger infinity
This post is about one formal notion of infinity in mathematics. Using that notion, we’ll see that there are infinitely many different infinities and that for every infinity there exists a larger infinity.
Sets and infinity
A set is one of the most important concepts in mathematics. It describes our classification of certain objects. And it does that without caring about the order of its elements or their repetitions. For example
{2, 5, 9, 1}, {x, y, z}, {{1, 2}, {x}}, {0.123, 2.3, π} and {}
are all sets and
{2, 5, 5, 5, 3, 3} = {2, 5, 3} = {5, 3, 2} = {5, 2, 2, 3}.
We say that A is a subset of B if B contains all elements of A. For example, given the set X = {0,1,2}, we have the set of all its subsets
𝒫(X) = {{}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.
Here, 𝒫(X) is called the power set of X. Note that we also include the empty set {}, as the empty set is a subset of every set.
All of the above sets are finite. An example of an infinite set would be
ℕ = {0, 1, 2, 3, 4, 5, 6, …}.
This is called the set of natural numbers. Its existence is not proved but axiomatized (by the axiom of infinity). In other words, infinity doesn’t necessarily exist, we have to believe it does.
Why should we believe? Well, it’s an incredibly useful concept. Without it, embarrassingly little mathematics could be done. More or less, every contribution of maths to physics depends on this axiom. So, for the sake of physics, let’s believe.
How to compare set sizes?
We are used to counting the number of elements in a given set and then comparing the numbers themselves. That is not a useful definition in our case, as we want to compare infinite sets. Luckily, there exists a more natural definition for set comparison.
We should be able to say that the set {0,1} is smaller than {0,1,2}. That’s obvious as {0,1} is a subset of {0,1,2}. Can we just define “smaller” by “is a subset”?
What about {5,6} and {0,1,2}. Again we want to say that {5,6} is a smaller set than {0,1,2}, but now we can’t use the previous definition.
What we do is rename 5 ↦ 0 (5 to 0) and 6 ↦ 1 (6 to 1). Formally, this is a one-to-one mapping from {5,6} to {0,1,2}. One-to-one means it assigns a unique value (name) to each element.
We say that set A is smaller than set B if there exists a one-to-one function, mapping elements in A to elements in B. Why is this a good definition? Because it’s also defined for infinite sets.
We also have to define the equality of set sizes. This is done by requiring a function to be more than just one-to-one. It should also reach every value in the corresponding set. A function satisfying those two properties is called a bijection.
We say that sets A and B are of equal size when there exists a bijection from A to B. Intuitively this means that every element a in A has exactly one corresponding element b in B, and vice-versa (as in the above picture).
To convince you of the naturalness of this definition, we have to look at how our brains count things. Let’s say I ask you to count the number of the following intervals.
[0, 1], [1, 2], [2, 3], … , [n-1, n].
Chances are, you’ll map i ↦ [i-1, i] and see that sending i from 1 to n generates all the intervals, encountering each one exactly once. So, you have constructed a bijection between the set {1, 2, 3, …, n} and those intervals. Our brain chooses this set because it’s the most natural representation of a number n.
Counting infinities using our definition is not always entirely intuitive. For example, even numbers form a strict subset of natural numbers. But according to our definition, they are of the same size, as
x ↦ x / 2
is a bijection, mapping even numbers to natural numbers.
There are more extreme cases though. It turns out the set of rational numbers (fractions) is the same size as the set of natural numbers.
Given sets A and B, you may have thought about defining their size-equality by requiring A to be smaller than B and B to be smaller than A. That means requiring the existence of two one-to-one functions: one from A to B and another from B to A. That’s also a natural definition and it turns out to be equivalent to ours. This is not a trivial result though.
Every set is strictly smaller than its power set
Let’s pick any set X. Immediately it is obvious that X is smaller than 𝒫(X), as
x ↦ {x}
is a one-to-one function, mapping from X to 𝒫(X). To show that X is strictly smaller than 𝒫(X), we need to prove that they are not of equal size. So we should prove that there are no bijections between X and 𝒫(X).
Proving this was a great mathematical achievement (done by Georg Cantor in 1891) and we’re going to show how it was done.
What if such a bijection was to exist? Let’s assume it does! So, we have a bijection e, mapping from X to 𝒫(X). We define the set of elements x inside X, for which it holds that x does not belong to the set e(x)
Because this is a subset of X (so a member of the power set 𝒫(X)), we need to have S = e(s) for some s, as e is a bijection between X and 𝒫(X). Now we ask if s is in S:
- if s ∈ S, then by definition s ∉ e(s) = S,
- if s ∉ S, then again by definition s ∈ e(s) = S.
What? How could this happen? That’s a contradiction! Exactly! We are in contradiction with our only assumption, that being the existence of a bijection e. This means we can’t have any bijection between X and 𝒫(X). End of proof.
The self-referential nature of this argument may have been hard to follow. If you want to know more about this argument and how it’s used in math, here is a post on its generalization.
Aleph numbers
We have identified an infinite number of infinities
ℕ, 𝒫(ℕ), 𝒫(𝒫(ℕ)), 𝒫(𝒫(𝒫(ℕ))), …
Aleph numbers are a naming convention for infinite sizes. They are denoted by
- ℵ0 represents the smallest infinity (it turns out this is the size of ℕ),
- ℵ1 represents the smallest infinity that is larger than ℵ0,
- ℵ2 represents the smallest infinity that is larger than ℵ1,
- …
It was conjectured that ℵ1 is the size of the set 𝒫(ℕ) but later proven that standard mathematics is not strong enough to prove or disprove this (using the axioms of set theory).
From our previous enumeration of aleph numbers, you might have concluded them to be enumerated by natural numbers. The truth is, they are way more complex. They can even enumerate themselves.
So the fun never ends!
Usages of our result
When I was 8, we argued in simple ways. The one who expressed his argument’s strength with a higher number, won. A way to circumvent this was to use infinity. But I’m an adult now and I use math in my arguments.
