View source for Cantor's diagonal argument

{{complex|2=The article needs more making-it-easy-to-understand or it doesn't need to be here.|date=September 2016}}
'''Cantor's diagonal argument''' is a mathematical method to prove that two infinite sets have the same [[cardinality]].{{efn|The cardinality of a set means the number of its elements.<ref>{{cite web |url=http://www.cs.utexas.edu/~eberlein/cs336/cardinality.html |title=Finite and Infinite Sets |author= |date= |website=Computer Science |publisher=University of Texas at Austin |accessdate=28 August 2016}}</ref>}} [[Georg Cantor|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).<ref>{{cite web |url=http://www.logicmuseum.com/cantor/diagarg.htm |title=Uber ein elementare Frage der Mannigfaltigkeitslehre |author= |date= |website= |publisher=The Logic Museum |accessdate=28 August 2016}}</ref>  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''. This statement works well for sets with a [[Finite set|finite]] number of elements. It is less intuitive for sets with an infinite number of elements. 

== Cantor's first diagonal argument ==

The example below uses two of the simplest infinite sets, that of [[natural number]]s, and that of positive [[fraction (mathematics)|fractions]]. The idea is to show that both of these sets, <math>\mathbb{N}</math>  and  <math>\mathbb{Q^+}</math> have the same cardinality. 

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

:<math>\begin{array}{cccccccccc}
\tfrac 11 & & \tfrac 12 & & \tfrac 13 & & \tfrac 14 & & \tfrac 15 & \cdots \\
          & &           & &           & &           & &           &        \\
\tfrac 21 & & \tfrac 22 & & \tfrac 23 & & \tfrac 24 & & \tfrac 25 & \cdots \\
          & &           & &           & &           & &           &        \\
\tfrac 31 & & \tfrac 32 & & \tfrac 33 & & \tfrac 34 & & \tfrac 35 & \cdots \\
          & &           & &           & &           & &           &        \\
\tfrac 41 & & \tfrac 42 & & \tfrac 43 & & \tfrac 44 & & \tfrac 45 & \cdots \\
          & &           & &           & &           & &           &        \\
\tfrac 51 & & \tfrac 52 & & \tfrac 53 & & \tfrac 54 & & \tfrac 55 & \cdots \\
\vdots    & & \vdots    & & \vdots    & & \vdots    & & \vdots    &        \\
\end{array}</math>

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

:<math>\begin{array}{lclclclclc}
\tfrac 11\ _{\color{Blue} (1)}    & {\color{MidnightBlue}\rightarrow} & \tfrac 12\ _{\color{Blue} (2)}     &                                & \tfrac 13\ _{\color{Blue} (5)}     & {\color{MidnightBlue}\rightarrow}  & \tfrac 14\ _{\color{Blue} (6)}     &                                & \tfrac 15\ _{\color{Blue} (11)} & {\color{MidnightBlue}\rightarrow} \\
                                  & {\color{MidnightBlue}\swarrow}    &                                    & {\color{MidnightBlue}\nearrow} &                                    & {\color{MidnightBlue}\swarrow}     &                                    & {\color{MidnightBlue}\nearrow} &                                 &                                   \\
\tfrac 21\ _{\color{Blue} (3)}    &                                   & \tfrac 22\ _{\color{Blue} (\cdot)} &                                & \tfrac 23\ _{\color{Blue} (7)}     &                                    & \tfrac 24\ _{\color{Blue} (\cdot)} &                                & \tfrac 25                       & \cdots                            \\
{\color{MidnightBlue}\downarrow}  & {\color{MidnightBlue}\nearrow}    &                                    & {\color{MidnightBlue}\swarrow} &                                    & {\color{MidnightBlue}\nearrow}     &                                    &                                &                                 &                                   \\
\tfrac 31\ _{\color{Blue} (4)}    &                                   & \tfrac 32\ _{\color{Blue} (8)}     &                                & \tfrac 33\ _{\color{Blue} (\cdot)} &                                    & \tfrac 34                          &                                & \tfrac 35                       & \cdots                            \\
                                  & {\color{MidnightBlue}\swarrow}    &                                    & {\color{MidnightBlue}\nearrow} &                                    &                                    &                                    &                                &                                 &                                   \\
\tfrac 41\ _{\color{Blue} (9)}    &                                   & \tfrac 42\ _{\color{Blue} (\cdot)} &                                & \tfrac 43                          &                                    & \tfrac 44                          &                                & \tfrac 45                       & \cdots                            \\
{\color{MidnightBlue}\downarrow}  & {\color{MidnightBlue}\nearrow}    &                                    &                                &                                    &                                    &                                    &                                &                                 &                                   \\
\tfrac 51\ _{\color{Blue} (10)}   &                                   & \tfrac 52                          &                                & \tfrac 53                          &                                    & \tfrac 54                          &                                & \tfrac 55                       & \cdots                            \\
\vdots                            &                                   & \vdots                             &                                & \vdots                             &                                    & \vdots                             &                                & \vdots                          &                                   \\
\end{array}</math>

That way, the fractions are counted:

:<math>\begin{array}{cccccccccccccccc}
{\color{Blue} 1} & {\color{Blue} 2} & {\color{Blue} 3} & {\color{Blue} 4} & {\color{Blue} 5} & {\color{Blue} 6} & {\color{Blue} 7} & {\color{Blue} 8} & {\color{Blue} 9} & {\color{Blue} 10} & {\color{Blue} 11} & {\color{Blue} \cdots} \\[3pt]
{\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} \\[3pt]
1 & \tfrac 12 & 2 & 3 & \tfrac 13 & \tfrac 14 & \tfrac 23 & \tfrac 32 & 4 & 5 & \tfrac 15 & \cdots \\
\end{array}</math>
By omitting fractions that can still be simplified, there is a [[Bijective function|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;

:<math>\begin{array}{cccccccccccccccc}
{\color{Blue} 1} & {\color{Blue} 2} & {\color{Blue} 3} & {\color{Blue} 4} & {\color{Blue} 5} & {\color{Blue} 6} & {\color{Blue} 7} & {\color{Blue} 8} & {\color{Blue} 9} & {\color{Blue} 10} & {\color{Blue} 11} & {\color{Blue} 12} & {\color{Blue} 13} & {\color{Blue} 14} & {\color{Blue} 15} & {\color{Blue} \cdots} \\[3pt]
{\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} & {\color{MidnightBlue}\downarrow} \\[3pt]
0 & 1 & -1 & \tfrac 12 & -\tfrac 12 & 2 & -2 & 3 & -3 & \tfrac 13 & -\tfrac 13 & \tfrac 14 & -\tfrac 14 & \tfrac 23 & -\tfrac 23 & \cdots \\
\end{array}</math>

That way, there is a complete [[Bijective function|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 set|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 number|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 [[Ones' complement|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> || = || (<u>'''0'''</u>, || 0, || 0, || 0, || 0, || 0, || 0, || ...)
|-
| ''s''<sub>2</sub> || = || (1, || <u>'''1'''</u>, || 1, || 1, || 1, || 1, || 1, || ...)
|-
| ''s''<sub>3</sub> || = || (0, || 1, || <u>'''0'''</u>, || 1, || 0, || 1, || 0, || ...)
|-
| ''s''<sub>4</sub> || = || (1, || 0, || 1, || <u>'''0'''</u>, || 1, || 0, || 1, || ...)
|-
| ''s''<sub>5</sub> || = || (1, || 1, || 0, || 1, || <u>'''0'''</u>, || 1, || 1, || ...)
|-
| ''s''<sub>6</sub> || = || (0, || 0, || 1, || 1, || 0, || <u>'''1'''</u>, || 1, || ...)
|-
| ''s''<sub>7</sub> || = || (1, || 0, || 0, || 0, || 1, || 0, || <u>'''0'''</u>, || ...)
|-
| ...
|-
|
|-
| ''s'' || = || (<u>'''1'''</u>, || <u>'''0'''</u>, || <u>'''1'''</u>, || <u>'''1'''</u>, || <u>'''1'''</u>, || <u>'''0'''</u>, || <u>'''1'''</u>, || ...)
|}
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.

== Notes ==
{{notelist}}

== References ==
{{reflist}}

[[Category:Set theory]]