Cantor's Diagonal Argument and Uncountability

Hello! Welcome back to our exploration of the foundations of mathematics.

In our last lesson, we examined the Axiom of Choice, a principle that guarantees our ability to make selections from infinite collections of sets. This raised fundamental questions about what can be said to exist in the mathematical universe, even when we can't explicitly construct it. Today, we continue our journey into the strange world of the infinite by tackling the question of "size".

We've seen that some infinite sets, like the even numbers, can be put into a one-to-one correspondence with the entire set of natural numbers, meaning they have the same "size" or cardinality. This might lead one to suspect that all infinite sets are the same size. Today, you will learn the tool that demolished this intuition: Georg Cantor's diagonal argument. Your learning outcome is to construct Cantor's diagonal argument to prove the uncountability of the real numbers. This is one of the most elegant and profound proofs in mathematics, with deep implications for logic and philosophy.

1. Countable and Uncountable Infinities

Before we can prove that some infinities are "bigger" than others, we need to be precise about what "size" means for infinite sets. As a math student, you'll be familiar with the idea of using functions to compare sets. The core concept, formalized by Cantor, is that two sets have the same cardinality if there exists a bijection (a one-to-one and onto mapping) between them.

A set is called countable if it is either finite or has the same cardinality as the set of natural numbers, $\mathbb{N}=\{0,1,2,...\}$. A set that has the same cardinality as $\mathbb{N}$ is called denumerably infinite. Essentially, a set is countable if you can "list" all its elements in a sequence, even if that sequence is infinite (e.g., $x_0,x_1,x_2,...$). It might be surprising, but the set of integers ($\mathbb{Z}$) and the set of rational numbers ($\mathbb{Q}$) are both countable.

A set that is not countable is called uncountable. An uncountable set is an infinite set whose elements cannot be listed in a sequence. It represents a "larger" size of infinity.

To solidify these foundational concepts, let's turn to a formal text.

2. Constructing the Diagonal Argument

Now, we'll turn to the central question: Is the set of real numbers, $\mathbb{R}$, countable? Cantor's diagonal argument shows that it is not. To make the proof as clean as possible, we'll focus on the set of real numbers in the interval $[0,1)$. If we can show that this subset of $\mathbb{R}$ is uncountable, then the larger set $\mathbb{R}$ must also be uncountable.

The proof is a classic reductio ad absurdum (proof by contradiction):

1. Assume for the sake of argument that the set of real numbers in $[0,1)$ is countable.
2. If it's countable, we can list all of its elements in a sequence: $r_1,r_2,r_3,\dots$.
3. We will then use this list to construct a new real number that is in $[0,1)$ but is guaranteed not to be on the list.
4. This shows that our list was never complete to begin with, which contradicts our initial assumption.
5. Therefore, the assumption must be false, and the set is uncountable.

The following short video provides a brilliant and clear execution of this proof. It uses a clever simplification to avoid a minor technicality with decimal representations (the fact that $0.5=\mathrm{0.499...}$).

The Argument Step-by-Step

Let's walk through the logic you just saw. We assume we can list all real numbers in $[0,1)$. Let's visualize this list, writing out the decimal expansions:

Our list looks something like this:
$r_1=0.d_{11}{d}_{12}{d}_{13}{d}_{14}\dots$
$r_2=0.d_{21}{d}_{22}{d}_{23}{d}_{24}\dots$
$r_3=0.d_{31}{d}_{32}{d}_{33}{d}_{34}\dots$
$r_4=0.d_{41}{d}_{42}{d}_{43}{d}_{44}\dots$
$⋮$

Here, $d_{ij}$ is the $j$-th digit of the $i$-th number on the list. The "diagonal" consists of the digits $d_{11},d_{22},d_{33},\dots$.

Now, we construct a new number, let's call it $d_{new}$, according to a specific rule. For each digit $d_{nn}$ on the diagonal, we'll choose the corresponding digit of $d_{new}$ to be different. A simple rule could be:

Let the $n$-th digit of $d_{new}$, let's call it $c_n$, be defined as:

So, our new number is $d_{new}=0.c_1{c}_2{c}_3{c}_4\dots$

By its construction, $d_{new}$ is a real number in $[0,1)$. According to our initial assumption, it must appear somewhere on our "complete" list. Let's say it's the $k$-th number, so $d_{new}=r_k$.

But is this possible?

• By our rule, the 1st digit of $d_{new}$ ($c_1$) is different from the 1st digit of $r_1$ ($d_{11}$). So $d_{new}\ne r_1$.
• The 2nd digit of $d_{new}$ ($c_2$) is different from the 2nd digit of $r_2$ ($d_{22}$). So $d_{new}\ne r_2$.
• For any $k$, the $k$-th digit of $d_{new}$ ($c_k$) is, by construction, different from the $k$-th digit of $r_k$ ($d_{kk}$). So $d_{new}\ne r_k$.

This is a contradiction. Our new number $d_{new}$ cannot be equal to any number on the list. Therefore, the list was not complete. Since this procedure can be applied to any attempted list of the real numbers, no such list can ever be complete.

The set of real numbers in $[0,1)$ is uncountable.

3. Implications and Connections

Cantor's proof was revolutionary. It formally established that there are different "sizes" of infinity. The cardinality of the natural numbers, $|\mathbb{N}|$, is denoted ${\aleph }_0$ (aleph-nought). The cardinality of the real numbers, $|\mathbb{R}|$, is denoted $\mathfrak{c}$ (the cardinality of the continuum). We have just proven that ${\aleph }_0<\mathfrak{c}$.

This discovery opened up a "paradise" of transfinite arithmetic, but it also posed deep philosophical questions that are central to your interests:

• What is the nature of these higher infinities? Do they exist as Platonic objects, or are they merely consequences of our axiomatic system?
• How many sizes of infinity are there? Cantor also proved that for any set $S$, the cardinality of its power set $\mathcal{P}(S)$ is strictly greater than the cardinality of $S$ itself. This implies an infinite hierarchy of infinities: $|S|<|\mathcal{P}(S)|<|\mathcal{P}(\mathcal{P}(S))|<\dots$.
• The Continuum Hypothesis: Cantor conjectured that there is no set whose cardinality is strictly between ${\aleph }_0$ and $\mathfrak{c}$. This hypothesis, like the Axiom of Choice, was later proven to be independent of the standard axioms of ZFC set theory.

Furthermore, the method of diagonalization is a powerful proof technique that you will see again. It is the engine behind some of the most profound limitative results in logic and computer science, including Gödel's Incompleteness Theorems and Turing's proof of the unsolvability of the Halting Problem. In each case, a self-referential "diagonal" entity is constructed that cannot fit into an assumed complete system, thereby proving the system's incompleteness.

The video below briefly situates Cantor's argument in this broader context, which will be valuable as we move toward Gödel's theorems.

Conclusion

In this lesson, we have used a powerful and elegant proof to uncover a fundamental truth about the structure of the mathematical universe.

Key Takeaways:

• A set is countable if its elements can be put into a one-to-one correspondence with the natural numbers. Otherwise, it is uncountable.
• Cantor's diagonal argument is a proof by contradiction showing that the set of real numbers is uncountable.
• The argument proceeds by assuming the reals can be listed, and then constructing a new real number (the "diagonal" number) that is guaranteed to differ from every number on the list, thus proving the list is incomplete.
• This proves that there are different sizes of infinity; specifically, the cardinality of the natural numbers is strictly less than the cardinality of the real numbers (${\aleph }_0<\mathfrak{c}$).

Preview of the Next Lesson:
The diagonal argument works by showing a mismatch between a list (a syntactic object) and the set it purports to describe (a semantic object). To fully appreciate Gödel's work, which uses a similar trick, we must first become very clear about this distinction. In our next lesson, we will do just that, as we move to the next learning outcome: Explain the distinction between syntax and semantics in the context of formal systems.