# Two Types of Infinity


_This is the third post inspired by my current read-through of
[Gödel, Escher, Bach](https://www.goodreads.com/book/show/24113.G_del_Escher_Bach)_.
See also
"[A Hand-wavy Proof for the Infinitude of Prime Numbers](/blog/2021/02/11/A-Hand-wavy-Proof-for-the-Infinitude-of-Prime-Numbers/)"
and
"[Three Layers of Information](/blog/2021/02/21/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](https://en.wikipedia.org/wiki/Natural_number) is a non-negative
integer (e.g. 0, 1, 2, 3), and a
[real number](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Countable_set)", whereas the
real numbers are
"[uncountably infinite](https://en.wikipedia.org/wiki/Uncountable_set)". 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](https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument),
which is structured as a
[proof by contradiction](https://en.wikipedia.org/wiki/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:

![](https://benjamincongdon.me/blog/2021/03/07/Two-Types-of-Infinity/diagonals1.png)

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:

![](https://benjamincongdon.me/blog/2021/03/07/Two-Types-of-Infinity/diagonals2.png)

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](https://unsplash.com/photos/57iTv1_5ef8)_