Cantor's diagonal argument

**Cantor's diagonal argument** is a mathematical method to prove that two infinite sets have the same cardinality. Cantor  published articles on it in 1877, 1891 and 1899. His first proof of the diagonal argument was published in 1890 in the journal of the German Mathematical Society (Deutsche Mathematiker-Vereinigung).  According to Cantor, two sets have the same cardinality, _if it is possible to associate an element from the second set to each element of the first set, and to associate an element of the first set to each element of the second set_.

## Cantor's first diagonal argument

The example below uses two of the simplest infinite sets, that of natural numbers, and that of positive fractions. The idea is to show that both of these sets,   and   have the same cardinality.

First, the fractions are aligned in an array, as follows:

Next, the numbers are counted, as shown. Fractions which can be simplified are left out:

That way, the fractions are counted:

By omitting fractions that can still be simplified, there is a bijection which associates each element of the natural numbers, to one element of the fractions:

To show that all natural numbers and the fractions have the same cardinality, the element 0 needs to be added; after each fraction its negative  is added;

That way, there is a complete bijection, which associates a fraction to each natural number. In other words: both sets have the same cardinality. Today, sets that have the same number of elements than the set of natural numbers are called countable. Sets which have fewer elements than the natural numbers are called at most countable. With that definition, the set of rational numbers / fractions is countable.

Infinite sets often have properties which go against intuition: David Hilbert showed this in an experiment which is called Hilbert's paradox of the Grand Hotel.

## Real numbers

The set of real numbers does not have the same cardinality than those of the natural numbers;  there are more real numbers than natural numbers. The idea outlined above influenced his proof. In his 1891 article, Cantor considered the set _T_ of all infinite sequences of binary digits (i.e. each digit is zero or one).

He begins with a constructive proof of the following theorem:
- If _s_<sub>1</sub>, _s_<sub>2</sub>, … , _s_<sub>_n_</sub>, … is any enumeration of elements from _T_, then there is always an element _s_ of _T_ which corresponds to no _s_<sub>_n_</sub> in the enumeration.
To prove this, given an enumeration of elements from _T_, like e.g.
- {|
|-
| _s_<sub>1</sub> = || (0, || 0, || 0, || 0, || 0, || 0, || 0, || ...)
|-
| _s_<sub>2</sub> = || (1, || 1, || 1, || 1, || 1, || 1, || 1, || ...)
|-
| _s_<sub>3</sub> = || (0, || 1, || 0, || 1, || 0, || 1, || 0, || ...)
|-
| _s_<sub>4</sub> = || (1, || 0, || 1, || 0, || 1, || 0, || 1, || ...)
|-
| _s_<sub>5</sub> = || (1, || 1, || 0, || 1, || 0, || 1, || 1, || ...)
|-
| _s_<sub>6</sub> = || (0, || 0, || 1, || 1, || 0, || 1, || 1, || ...)
|-
| _s_<sub>7</sub> = || (1, || 0, || 0, || 0, || 1, || 0, || 0, || ...)
|-
| ...
|}
The sequence _s_ is constructed by choosing the 1st digit as complementary to the 1st digit of _s_<sub>_1_</sub> (swapping **0**s for **1**s and vice versa), the 2nd digit as complementary to the 2nd digit of _s_<sub>_2_</sub>, the 3rd digit as complementary to the 3rd digit of _s_<sub>_3_</sub>, and generally for every _n_, the _n_<sup>th</sup> digit as complementary to the _n_<sup>th</sup> digit of _s_<sub>_n_</sub>. In the example, this yields:

- {|
|-
| _s_<sub>1</sub> || = || (**0**, || 0, || 0, || 0, || 0, || 0, || 0, || ...)
|-
| _s_<sub>2</sub> || = || (1, || **1**, || 1, || 1, || 1, || 1, || 1, || ...)
|-
| _s_<sub>3</sub> || = || (0, || 1, || **0**, || 1, || 0, || 1, || 0, || ...)
|-
| _s_<sub>4</sub> || = || (1, || 0, || 1, || **0**, || 1, || 0, || 1, || ...)
|-
| _s_<sub>5</sub> || = || (1, || 1, || 0, || 1, || **0**, || 1, || 1, || ...)
|-
| _s_<sub>6</sub> || = || (0, || 0, || 1, || 1, || 0, || **1**, || 1, || ...)
|-
| _s_<sub>7</sub> || = || (1, || 0, || 0, || 0, || 1, || 0, || **0**, || ...)
|-
| ...
|-
|
|-
| _s_ || = || (**1**, || **0**, || **1**, || **1**, || **1**, || **0**, || **1**, || ...)
|}
By construction, _s_ differs from each _s_<sub>_n_</sub>, since their _n_<sup>th</sup> digits differ (highlighted in the example).
Hence, _s_ cannot occur in the enumeration.

Based on this theorem, Cantor then uses a proof by contradiction to show that:
- The set _T_ is uncountable.
He assumes for contradiction that _T_ was countable. In that case, all its elements could be written as an enumeration _s_<sub>1</sub>, _s_<sub>2</sub>, … , _s_<sub>_n_</sub>, … .
Applying the previous theorem to this enumeration would produce a sequence _s_ not belonging to the enumeration.
However, _s_ was an element of _T_ and should therefore be in the enumeration.
This contradicts the original assumption, so _T_ must be uncountable.