Cantor's diagonal argumentCantorsDiagonalArgument2002-02-18 15:27:062003-01-09 07:05:44Topic\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\natnums}{\mathbb{N}}
\newcommand{\cnums}{\mathbb{C}}
\newcommand{\znums}{\mathbb{Z}}
\newcommand{\lp}{\left(}
\newcommand{\rp}{\right)}
\newcommand{\lb}{\left[}
\newcommand{\rb}{\right]}
\newcommand{\supth}{^{\text{th}}}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}[proposition]{Definition}
\newtheorem{theorem}[proposition]{Theorem}\PMlinkescapeword{diagonalization} 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 \emph{possible} to enumerate all the rational
numbers by means of an infinite list. By contrast, the real numbers
are uncountable. it is \emph{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, \ldots$ 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}{rlllll}
0\;.&d_{11}&d_{12}&d_{13}&d_{14}&\ldots\\
0\;.&d_{21}&d_{22}&d_{23}&d_{24}&\ldots\\
0\;.&d_{31}&d_{32}&d_{33}&d_{34}&\ldots\\
0\;.&d_{41}&d_{42}&d_{43}&d_{44}&\ldots\\
\vdots\; & \;\vdots&\;\vdots&\;\vdots\;&\vdots&\ddots
\end{array}
$$
where
$$x_n = 0.d_{n1} d_{n2} d_{n3} d_{n4}\ldots,$$
and the expansion avoids an infinite trailing string of
the digit $9$.
For each $n=1,2,\ldots$ 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_1c_2c_3\ldots$$
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^{\scriptscriptstyle \text{th}}$ decimal
digit.
The claim is proven.