Why Some Infinities are Larger than Others
∞ > ∞?
“There are as many fractions as there are whole numbers.”
When I first was told that, it took me a while to understand what my math teacher was talking about.
Surely, since there are an infinite number of fractional numbers in between 2 whole numbers, there have to be more fractions than whole numbers, right?
A set is a collection of objects —it is defined solely by the objects in the set, not by the order in which they are in.
Sets serve an important function in classifying objects or elements in mathematics. Determining if two sets are equal requires a one-to-one correspondence to be achieved between two sets.
A one-to-one correspondence is a connection between the elements in two sets in which each element in one set is uniquely matched with one element in the other set.
If you can match each element of one set to the elements in another set without having any elements left over, then the one-to-one correspondence can be achieved.
If you can pair up two sets, they are the same size.
This method of proving that two sets are equal sometimes results in some unintuitive outcomes, for example, that the integer and the natural number sets are of the same size.
Infinities can either be countable or uncountable. Countable infinities have a one-to-one correspondence with the set of natural numbers (1, 2, 3, etc) — for example, the set of integers.
This seems impossible at first — after all, the integers include all positive and negative numbers, while the natural numbers only include the positive integers.
Since we can achieve a pairing (or one-to-one correspondence) between the integers and the natural numbers, the sets are said to be equal in size.
The two infinites are of the same size, and so, the set of integers is countable.
Uncountable infinities are infinitely larger than countable infinities and cannot be put into a one-to-one correspondence with the natural numbers e.g. real numbers.
Even though there are an infinitely many of both natural numbers and real numbers, the sets are not equal in size. Infinity itself is not a number — rather, it is a concept. Just because there are infinitely many objects in two sets, it doesn’t imply that the two sets are equal.
This can be shown by the fact that we cannot pair up the elements of the natural number set and the real number set.
German mathematician Georg Cantor demonstrated in the late 19th century, there exists a variety of infinities — and some are simply larger than others — using his diagonal argument.
Suppose you have an infinitely long list of real numbers, each one with infinitely many decimal places.
You can create a new number by taking the first digit from the first number, the second digit from the second number, and so on — the nth digit in the new number will be the same as the nth digit as the nth real number in the set.
Then, switch every digit of the new number to its complementary: for example, 2 → 1, 3 → 2, etc.
This way, you ensure that the new number has at least one digit which is different from every number in the set, creating a unique number.
This process can be repeated infinitely many times, proving that you can always generate a unique real number from a pre-existing set.
We cannot pair up numbers in the real numbers and the natural numbers — the infinity of the real numbers is larger than the infinity of the natural numbers.
Hilbert’s Hotel
In 1924, German mathematician David Hilbert introduced the idea of a hotel with infinite rooms — a thought experiment designed to illustrate some counterintuitive properties of infinite sets.
In this experiment, you were the manager of the hotel, tasked with assigning each guest a room.
If all the rooms were occupied, you could still make room for a new guest by instructing each preexisting guest to move from their current room n to the room n+1.
By repeating this procedure, we can see that it is possible to make room for any number of finite guests.
If k new guests are looking for a room, we can move each preexisting guest to the room n + k.
This shows that
∞ + k = ∞
so the sets are of the same size.
What if we had an infinite number of new guests searching for a room? At first, this seems more complicated — we cannot move each preexisting guest to move down an infinite number of rooms.
However, we can move each guest from their room n to the room 2n.
All the preexisting guests will be in even-numbered rooms, leaving all the odd numbered rooms for new guests, proving that
∞ + ∞ = ∞
This is similar to the proof above showing that the set of integers and the set of natural numbers are of the same size, even though intuitively, the integers should be twice the size of the natural numbers.
Let’s add a step to the problem. Suppose an infinite number of buses arrive, each with an infinite number of new guests. How do you accommodate each new guest?
We can utilise a property of primes to give every new guest a room.
Each preexisting guest in room n moves to the room 2^n.
Then, we send the guests in the first bus to the room 3^i, where i is their position on the bus, and the guests in the second bus to the room 5^i.
For the members of bus number j we allocate the rooms c^i where c is the (j+1)th prime number (since we already used the powers of 2 as the room numbers for the pre-existing guests).
Of course, this leaves a lot of rooms empty (all of the rooms which are not powers of a prime number), so there is a lot of waste e.g. room 15 or 33.
The characteristics of infinite collections of objects differ significantly from those of finite collections, so Cantor’s theory of infinite numbers can be used to understand the math behind Hilbert’s Hotel.
There are an infinite number of infinites with different sizes. Mathematically, we can represent the cardinality of the natural numbers using ℵ0, and for a long time, ℵ0 was thought to be the size of every infinite set.
Cantor proved that different infinite sets can have different cardinalities, and some are larger than others. The infinity of the real numbers is known as ℵ1, which is larger than the cardinality of the natural numbers, as shown previously.
Beyond ℵ0 and ℵ1 exist an infinite number of infinities with different sizes, (represented by ℵ2, ℵ3, etc, each one with an increasing cardinality). Even though they all are infinite, they are not the same.
