Written by: Sahana Vijayaraj

Some infinities are greater than others. You might have heard this statement before, but it’s probably never been explained. Some infinities are greater than others— but please, please don’t ask why. So, while many are content to remain satisfied with it, this factoid becomes infinitely more fun when you begin to consider why it is, and Cantor’s Diagonalisation Argument is one of the most widely known proofs used to illustrate the basic concept.

Introduction to the Argument

The Diagonalisation Argument begins with two sets of numbers— the set of the real numbers, denoted ℝ and the set of the natural numbers, denoted ℕ. First consider the set of natural numbers, or the countable numbers. ℕ is the set of numbers that you would think of when you’re counting, or all the integers greater than zero. We can say ℕ = {1, 2, 3, 4, 5…} and so on until infinity— ℕ is an infinite set, because you can count forever. ℕ is an infinity, but it’s an infinity you can count, so to describe the size, or cardinality of ℕ, we say it’s a countably infinite set.

Our argument focuses on one thing— proving that the cardinality of ℕ and the cardinality of ℝ are are different, which would mean that there are at least two different sizes of infinity. To prove this, we have to prove that there is no bijection between ℝ and ℕ. However, the concept of a bijection, and how it proves this, requires some explaining.

Defining A Bijection

First, a function can be thought of as a way to match two sets together- a first set and a second set, which we can call set A and set B. There are other definitions of functions, but this one is the most useful for this case. From this definition of a function, two other concepts are required to understand a bijection- surjection and injection. Before, though, it’s important to note that the definition of a function does not allow for multiple elements of the second set to map onto the same element in the first set! You always match from the first to the second, so that is not possible.

Moving forward, a surjection is a way to match the first set (A) to the second set (B) so that every element in B corresponds to some member of A. More simply, no elements in B are left unmatched. However, a surjection can still have multiple elements in A correspond to the same member of B. An injection, on the other hand, matches A to B so that no members of A correspond to the same member of B, but there can still be some unmatched members of B. A bijection is both a surjection and an injection- so there are no unmatched members of B, and no members of A correspond to the same member of B. Informally, this is just a one to one correspondence between A and B. So, for every element of A, there is a singular corresponding element of B and vice versa. These definitions are all a little confusing, though, so the diagram below might help:

Now that a bijection is defined, we can see why a bijection between two sets means that the two sets will always have the same size- all the elements will be in a one-to-one correspondence, or a one-to-one ratio. Then, a bijection between the sets ℝ and ℕ means that both sets are the same size. So, by proving that there is no bijection between ℝ and ℕ, we prove that they do not have the same cardinality (are not the same size).

Mapping A Bijection

So, consider the hypothetical mapping function between ℝ and ℕ. To make the argument simpler, we can shorten our proof to the subset of ℝ between 0 and 1, and if we show this subset is bigger than ℕ,  ℝ is definitely bigger than ℕ since it contains this subset. For the interested, this function is—

This looks like a terrifying thing at first, but it’s easily explained. This function returns an ordered pair of one element which we call x from the input set ℕ and its corresponding element which we call y in the output set, ℝ, represented as (x, yx). To get yx from x, you first have an infinite summation that gives you an infinitely long decimal; for example, yxi=5 for all i is 0.5555… where the digit 5 repeats forever. yxi is a function that gives you a random number between 0 and 10, while the (0.1)i part of the equation just makes it so that the element returned by yxi is the ith element to the right of the decimal point. A summation just sums all of the terms as i increases— (0.1)1yxi +(0.1)2yxi +(0.1)3yxi … assigning a random integer yxi for to every decimal place to make an infinite decimal. This will be our mapping function.

Proof by Contradiction

Using the mapping function, we can make a table of just a couple example values to illustrate our proof.

Now that we have our mapping between ℝ and ℕ, we can get started. To make things easier, we can imagine every number mapped onto ℝ from ℕ as something like 0.d11d12d13d14d15…, where din is a single digit, with the subscript i representing the index of the number the digit is in and n representing the place of the digit to the right of the decimal point. Table 1 is a hypothetical mapping with numbers in place for the digits to make the idea easier to understand, while Table 2 is a universal mapping using the din notation for each digit. This is a great starting point for our goal of proving that this bijection cannot exist.

To prove it doesn’t exist, you can take the diagonal of the numbers in this table (the numbers highlighted in red) and construct a new number from them, with an extra one added to each digit. For example, in the first table, the number constructed would be 0.69979… and in the second, it would be the expression below.

0.(d11+1)(d22+1)(d33+1)(d44+1)…

Now, we prove that this number is not included in our mapping. It can’t be equal to the number mapped to 1, because the digit in red, 5 is now 6, and similarly, d11 is d11 + 1. It also can’t be equal to the number mapped to 2, because the digit in red, 8, is now 9, and similarly, d22 is d22 + 1, and so on. For the nth number, the nth digit will always differ, so they can’t be the same. Repeat this argument forever, and congrats— your number isn’t in the mapping! For any mapping like this, we can use this same diagonal argument to forever construct a number that isn’t in the mapping but is in ℝ, meaning there is no bijection between the sets.

Conclusion

That’s Cantor’s Diagonalisation Argument. Some readers might notice a flaw, though— can’t we just add this constructed number to the mapping, then add the next constructed number, and the next, and the next, and have a full mapping? However, since the argument works for all mappings, you will always be able to create a new number not in the current mapping. Even if we continually add the diagonal number we construct to the mapping, we can always construct another number not in it, so you end up adding numbers forever and never creating a true bijection. To truly disprove the Diagonalisation Argument, you need to prove that you can never create a new number not in the mapping, which is impossible, because you can always create a new number not in the mapping- the diagonal number. So, this is why the infinity of the real numbers is bigger than the infinity of the natural numbers, perfectly illustrating the point so aptly made by that simple statement— some infinities really are bigger than others.

Sources:

Google, Translate & Tm, Deepl & Jones, Peter. (2019). A Translation of G. Cantor’s “Ueber eine elementare Frage der Mannigfaltigkeitslehre”. https://www.researchgate.net/publication/335364685_A_Translation_of_G_Cantor’s_Ueber_eine_elementare_Frage_der_Mannigfaltigkeitslehre/citation/download

Oxford College. (n.d.). Cantor’s Diagonal Argument. Cantor’s diagonal argument. https://mathcenter.oxford.emory.edu/site/math125/cantorsDiagonalArgument/

University of Kansas. (n.d.-b). Cantor’s diagonal argument. https://jlmartin.ku.edu/courses/math410-S09/cantor.pdf