This is the third post inspired by my current read-through of Gödel, Escher, Bach. See also “A Hand-wavy Proof for the Infinitude of Prime Numbers” and “Three Layers of Information”.
One of the most interesting concepts I remember from my Introduction to Number Theory course in college was the notion that there are different “types” of infinity. Intuitively, you’d think that all infinities are equivalent – it’s just, well, a non-finite quantity; you can always have more! In mathematics, there are provable properties of different types of infinities that become useful in many fields, from number theory to complexity theory, which rely on the unintuitive notion that there is more than one sort of “infinity”.
One of the simplest cases of multiple classes of infinity is in proving that there are “more” real numbers than natural numbers. A natural number is a non-negative integer (e.g. 0, 1, 2, 3), and a real number is a continuous quantity (e.g. 1.23, $\pi$, $\frac{1}{3}$) that can have a non-terminating number of digits (such as in the case of irrational numbers like $\pi$).
The natural numbers are “countably infinite”, whereas the real numbers are “uncountably infinite”. The practical implication of this is that while the natural numbers are infinite, you can – at least in theory – enumerate them all. The real numbers are more slippery. As we’ll see in a second, no matter how many real numbers you can find, there’s always more that you haven’t counted.
A Hand-wavey Proof
This proof is a simplification of Cantor’s diagonal argument, which is structured as a proof by contradiction. We will show that assuming that there are the same number of natural and real numbers eventually leads to a logical contradiction, implying that there aren’t the same number of natural and real numbers.
To begin: Assume that there are the same number of real numbers as natural numbers. For this to be the case, we could setup a one-to-one correspondence between each real number and natural number. The “ordering” or mechanism of this correspondence doesn’t matter, so for simplicity we can assume that we have a table that maps each natural number to some real number:
We want to show that there can’t be a table like this, where each real number corresponds to a natural number. One way of doing this is by showing that even if there did exist a table like this, we could find another real number that doesn’t exist in the table.
The technique we’ll employ is called “diagnonalization”, which will allow us to create a distinct number that doesn’t exist in our table. The process is simple: to determine the $i$-th digit of our new number, we take the $i$-th digit of the $i$-th number in the table, and add one (wrapping around to 0 when the $i$-th digit is 9).
Graphically, it looks something like this:
That is, Table(0)’s first digit is 6, so our new number’s first digit will be
7; Table(1)’s second digit is 4, so our new number’s second digit will be 5;
and so on.
This process ensures that our new number is totally unique amongst the existing numbers in the table: since we force the new number to differ in at least one digit from all the existing numbers, this new number cannot already exist in the table.
But, here we come to the contradiction: We assumed that the table contained all the real numbers, but we have found a real number that doesn’t exist in the table. Thus, since the size of the table is the same size as the number of natural numbers, there must exist more real numbers than natural numbers.
Notes:
- What about “shorter” numbers like 0.5, 0.23, etc.?
We can still diagonalize using these numbers by padding the end with zeros. (e.g $0.5 = 0.50 = 0.500 = …$ ).
- But why doesn’t diagonalization work with Natural Numbers?
Consider all the numbers of length $X$. There are a countable number of numbers with this length: ~$10^X$. If we tried to perform the diagonal trick on a natural number of length $X$, no matter how we decide to shift the digits, the new number is always already in the table. If we try to get around this by appending another digit, we just increase our search space to numbers with $X+1$ digits, and run into the same inability to come up with a number that isn’t already in the table.
Furthermore, our table is indexed on the natural numbers, so by definition each entry in the table is indexed by exactly one natural number. This one-to-one correspondence breaks diagonalization.
- I’m not convinced that there are actually more real numbers than natural numbers.
In my example, I used $N$ and $N+1$ to hint at the size of the table and the “new” real number you found. In reality for this proof to work, we really are talking about a table with infinite size – $Table(\infty)$. The mental trick is this: assume you (somehow) have a table that contains all of the natural numbers, with a corresponding real number. Even if (somehow) you were able to achieve this feat, you can still always find a real number that you don’t have in your table.
Here’s another way of looking at it: If you were to perform this trick with the natural numbers against the natural numbers, you can’t make up a new number to add to the table. If I have all the natural numbers in the table, then by definition if I were to summon some natural number, it’d either have to (1) already be in the table, or (2) not be in the table, in which case my table wasn’t complete, and adding it would just lead us back to (1). Thus, we have (somewhat tautologically) proven that the number of natural numbers is the same as the number of natural numbers.
Since this diagonalization trick works with real numbers but not with natural numbers, you have to concede that something is going on here – and that something is that there are more real numbers than natural numbers.
Cover Photo: Unsplash