Infinite Sets
Brody Reid —
Updated on
One result from set theory that has always bothered me is that certain infinite sets have the same number of elements. Never ending sets of the same size?! I don’t believe you, Brody! I know… but as counterintuitive as it may seem, we can mathematically show that this is the case.
Let’s build some intuition with a finite example first. Suppose we are hosting a dinner party with $8$ seats at the table and we invite $7$ guests. In set notation we can represent our guests as the set $G$ and the seats as the set $S$:
$$ G = \{ \, g_1, g_2, g_3, g_4, g_5, g_6, g_7, g_8 \, \} \\ S = \{ \, s_1, s_2, s_3, s_4, s_5, s_6, s_7, s_8 \, \} $$Since there are $8$ people ($7$ guests plus ourselves) and $8$ seats, we can easily pair each person with exactly one seat, with none left over. A simple way to assign everyone a seat is to pair the first guest to the first seat, the second guest to the second seat, and so on. So for our $8$ guests, the map from $G$ to $S$ would look like
$$ \begin{array}{ccc} g_1 & \mapsto & s_1 \\ g_2 & \mapsto & s_2 \\ g_3 & \mapsto & s_3 \\ g_4 & \mapsto & s_4 \\ g_5 & \mapsto & s_5 \\ g_6 & \mapsto & s_6 \\ g_7 & \mapsto & s_7 \\ g_8 & \mapsto & s_8 \end{array} $$Mathematically, we can write this as the function
$$ f(g_i) = s_i \quad \text{for } i = 1, \dots, 8 $$We call this function $f$ a one-to-one correspondence because every seat is occupied and no two guests share the same seat.
This matters because whenever a one-to-one correspondence exists between two sets, the sets must have the same cardinality (i.e., the same size). We write this as $|G| = |S| = 8$, where the vertical bars denote cardinality. But of course, we already knew that since we could just count the number of elements in each. But that’s the point! We took an obvious fact and created a mathematical way to determine the size of two sets without counting the elements. This is helpful if we want to determine the size of sets that are too large to count 👀.
Let’s use our new concept of one-to-one correspondences to tackle some infinite sets!
Consider two infinite sets: the integers, which we denote by $\mathbb{Z}$, and the positive integers (also called the natural numbers), which we denote by $\mathbb{N}$. The integers are all the whole numbers from $- \infty$ to $+ \infty$ and the naturals are the positive subset of these. That is,
$$ \mathbb{Z} = \{ \, \dots, -2, -1, 0, 1, 2, \dots \, \} \ \text{and} \ \mathbb{N} = \{ \, 1,2,3,4,\dots \, \} $$Just like our dinner party example, let’s try pairing each natural number with an integer. Firstly, notice that we can rewrite the integers without needing to extend all the way back to negative infinity:
$$ \mathbb{Z} = \{ \, 0, -1, 1, -2, 2, -3, \dots \, \} $$Now create a map between the naturals and the integers
$$ \begin{array}{ccc} 1 & \mapsto & 0 \\ 2 & \mapsto & -1 \\ 3 & \mapsto & 1 \\ 4 & \mapsto & -2 \\ 5 & \mapsto & 2 \\ 6 & \mapsto & -3 \\ \vdots & & \vdots \end{array} $$This pattern will continue forever since the sets are infinite. And just like at our dinner party, we can cleanly pair up every element from each set, with none left over. We can write the above map as the function
$$ f(n) = \begin{cases} \dfrac{n-1}{2} &\text{if $n$ is odd} \\[6pt] -\dfrac{n}{2} &\text{if $n$ is even} \end{cases} $$We won’t verify this rigorously, but we can see from the mapping diagram that every natural number will appear exactly once in the left column, and each integer will appear exactly once in the right column. So $f$ is a one-to-one correspondence between $\mathbb{N}$ and $\mathbb{Z}$, and therefore
$$\boxed{|\mathbb{N}| = |\mathbb{Z}|}$$Feels wrong? It should!
We have just shown that the integers are no “bigger” than the naturals, even though $\mathbb{Z}$ clearly seems to contain more numbers. This is one of those results that feels wrong no matter how many times you see it… but the logic is airtight! That’s something I love about math: it doesn’t care about our intuitions 🥲
A natural follow-up question to this result is: are all infinite sets the same size? Well, let’s try the same technique we’ve been using and see if we are able to construct a one-to-one correspondence between $\mathbb{N}$ and other infinite sets.
Consider the real numbers, which we denote by $\mathbb{R}$. The real numbers are all positive numbers, negative numbers, fractions, decimals… and well, basically everything. So is the set of real numbers also the same size as the set of natural numbers?
We can think of the natural numbers as being “orderly” insofar as there is always a “next” number. For example, in the naturals there is no number between, say, $4$ and $5$. It is just $4$ then $5$. The naturals are discrete, i.e., there is a clean gap between any natural number and its neighbour. Now take two real numbers, say $0.1$ and $0.2$. What’s between them? Well, $0.15$ is. And between $0.1$ and $0.15$? There’s $0.12$. And between $0.1$ and $0.12$? There’s $0.11$… This never stops. No matter which real numbers you choose, you can always find another one hiding in between. Unlike the naturals, the reals are continuous: there is never a “next” number.
To see the problem this creates, consider what would happen if we tried to match the naturals up with the reals. We have to start somewhere, so let’s map $1 \mapsto 0$. Great! But then what would $2$ map to? It should be the next real number after $0$, right? Maybe $0.01$? No, because $0.001$ would be a smaller first step. What about $0.0001$ or $0.00001$ or $0.000001$? You see the problem, right? Any number we pick leaves infinitely many numbers between it and $0$. Since there is no “next” real number, we can’t list them in order to create a one-to-one correspondence ☹️
Ok, so we can’t list the reals in order, but our correspondence between $\mathbb{N}$ and $\mathbb{Z}$ wasn’t in order either! To truly rule out a one-to-one correspondence, we need to show that no listing of the reals works, in any order. To do this, we only need to look at the interval $(0, 1)$. Since $(0, 1)$ is a subset of $\mathbb{R}$, if we can’t list every real number in $(0, 1)$ then we certainly can’t list all of $\mathbb{R}$.
So suppose we could list every real number in $(0, 1)$. Then our map would look like
$$ \begin{array}{ccc} 1 & \mapsto & 0.2519012 \dots \\ 2 & \mapsto & 0.9431434 \dots \\ 3 & \mapsto & 0.7811852 \dots \\ 4 & \mapsto & 0.3141591 \dots \\ 5 & \mapsto & 0.7071067 \dots \\ 6 & \mapsto & 0.1414293 \dots \\ 7 & \mapsto & 0.2718281 \dots \\ \vdots & & \vdots \end{array} $$Our assumption is that this list contains every real number in $(0, 1)$. So if we can find even one number that is not on the list, then our assumption must be wrong.
Look at the blue digits along the diagonal of the grid below: $2, 4, 1, 1, 0, 9, 1, \dots$ Now let’s use these digits to build a new number. The rule is simple: take each diagonal digit and add $1$ (if the digit is $9$, wrap it to $0$). So $2$ becomes $3$, $4$ becomes $5$, $1$ becomes $2$, and so on, giving us a new number $0.3522102\dots$
$$ \begin{array}{c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c} 0. & {\color{blue}2} & 5 & 1 & 9 & 0 & 1 & 2 & \cdots \\ 0. & 9 & {\color{blue}4} & 3 & 1 & 4 & 3 & 4 & \cdots \\ 0. & 7 & 8 & {\color{blue}1} & 1 & 8 & 5 & 2 & \cdots \\ 0. & 3 & 1 & 4 & {\color{blue}1} & 5 & 9 & 1 & \cdots \\ 0. & 7 & 0 & 7 & 1 & {\color{blue}0} & 6 & 7 & \cdots \\ 0. & 1 & 4 & 1 & 4 & 2 & {\color{blue}9} & 3 & \cdots \\ 0. & 2 & 7 & 1 & 8 & 2 & 8 & {\color{blue}1} & \cdots \\ &&&&\vdots&&&& \end{array} $$Why can’t this number be on our list? Because we built it to disagree with every entry. It differs from the first number at the first decimal place, from the second number at the second decimal place, from the third at the third, and so on. No matter how far down the list we go, our new number is guaranteed to differ from that entry at the corresponding digit.
So our new number is not on the list, but it is clearly in the interval $(0,1)$. This contradicts our assumption that our list contains every real number in $(0,1)$. Therefore, no one-to-one correspondence between $\mathbb{N}$ and $\mathbb{R}$ can exist, which means
$$ \boxed{|\mathbb{N}| \lt |\mathbb{R}|} $$Unlike the naturals, which had clean gaps between elements, the reals are so densely packed that they cannot be listed one by one, no matter how cleverly we try. Even though both sets are infinite, one is genuinely bigger than the other! This result is known as Cantor’s diagonal argument, and it was the first proof that there are different sizes of infinity 😳 And it’s one of my favourite results in all of math.
Earlier we showed that $|\mathbb{N}| = |\mathbb{Z}|$, so the naturals and the integers are the “same size of infinity.” But the reals are strictly larger… Not all infinities are created equal!