# Cantor’s diagonal argument

One of the starting points in
Cantor’s development of set theory^{} was his discovery that there are
different degrees of infinity^{}. The rational numbers^{}, for example, are
countably infinite^{}; it is *possible* to enumerate all the rational
numbers by means of an infinite^{} list. By contrast, the real numbers
are uncountable. it is *impossible* to enumerate them by means of an
infinite list. These discoveries underlie the idea of cardinality,
which is expressed by saying that two sets have the same cardinality
if there exists a bijective^{} correspondence between them.

In essence, Cantor discovered two theorems: first, that the set of
real numbers has the same cardinality as the power set^{} of the
naturals; and second, that a set and its power set have a different
cardinality (see Cantor’s theorem). The proof of the second result
is based on the celebrated diagonalization argument.

Cantor showed that for every given infinite sequence^{} of real numbers
${x}_{1},{x}_{2},{x}_{3},\mathrm{\dots}$ it is possible to construct a real number $x$
that is not on that list. Consequently, it is impossible to enumerate
the real numbers; they are uncountable. No generality is lost if we
suppose that all the numbers on the list are between $0$ and $1$.
Certainly, if this subset of the real numbers in uncountable, then the
full set is uncountable as well.

Let us write our sequence as a table of decimal expansions:

$$\begin{array}{cccccc}\hfill 0.& {d}_{11}\hfill & {d}_{12}\hfill & {d}_{13}\hfill & {d}_{14}\hfill & \mathrm{\dots}\hfill \\ \hfill 0.& {d}_{21}\hfill & {d}_{22}\hfill & {d}_{23}\hfill & {d}_{24}\hfill & \mathrm{\dots}\hfill \\ \hfill 0.& {d}_{31}\hfill & {d}_{32}\hfill & {d}_{33}\hfill & {d}_{34}\hfill & \mathrm{\dots}\hfill \\ \hfill 0.& {d}_{41}\hfill & {d}_{42}\hfill & {d}_{43}\hfill & {d}_{44}\hfill & \mathrm{\dots}\hfill \\ \hfill \mathrm{\vdots}& \mathrm{\vdots}\hfill & \mathrm{\vdots}\hfill & \mathrm{\vdots}\hfill & \mathrm{\vdots}\hfill & \mathrm{\ddots}\hfill \end{array}$$ |

where

$${x}_{n}=0.{d}_{n1}{d}_{n2}{d}_{n3}{d}_{n4}\mathrm{\dots},$$ |

and the expansion avoids an infinite trailing string of the digit $9$.

For each $n=1,2,\mathrm{\dots}$ we choose a digit ${c}_{n}$ that is different from ${d}_{nn}$ and not equal to $9$, and consider the real number $x$ with decimal expansion

$$0.{c}_{1}{c}_{2}{c}_{3}\mathrm{\dots}$$ |

By construction, this number $x$ is different from every member of the given sequence. After all, for every $n$, the number $x$ differs from the number ${x}_{n}$ in the ${n}^{\text{th}}$ decimal digit. The claim is proven.

Title | Cantor’s diagonal argument |
---|---|

Canonical name | CantorsDiagonalArgument |

Date of creation | 2013-03-22 12:22:03 |

Last modified on | 2013-03-22 12:22:03 |

Owner | rmilson (146) |

Last modified by | rmilson (146) |

Numerical id | 9 |

Author | rmilson (146) |

Entry type | Topic |

Classification | msc 03E10 |

Synonym | Cantor’s diagonalization |

Related topic | CantorsTheorem |