Cantor's diagonal argument

:Note: in order to fully understand this article you may want to refer to the set theory portion of the table of mathematical symbols.

Real numbers

Cantor's original proof shows that the interval is not countably infinite.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The proof by contradiction proceeds as follows:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• Assume (for the sake of argument) that the interval is countably infinite.
• We may then enumerate all numbers in this interval as a sequence, ( r₁, r₂, r₃, ... )
• We already know that each of these numbers may be represented as a decimal expansion.
• We arrange the numbers in a list (they do not need to be in order). In the case of numbers with two decimal expansions, like 0.499 ... = 0.500 ..., we pick the one ending in nines. Assume, for example, that the decimal expansions of the beginning of the sequence are as follows:
• : r₁ = 0 . 5 1 0 5 1 1 0 ...
• : r₂ = 0 . 4 1 3 2 0 4 3 ...
• : r₃ = 0 . 8 2 4 5 0 2 6 ...
• : r₄ = 0 . 2 3 3 0 1 2 6 ...
• : r₅ = 0 . 4 1 0 7 2 4 6 ...
• : r₆ = 0 . 9 9 3 7 8 3 8 ...
• : r₇ = 0 . 0 1 0 5 1 3 5 ...
• : ...
• We shall now construct a real number x in by considering the k^th digit after the decimal point of the decimal expansion of r_k. The digits we will consider are underlined and in bold face, illustrating why this is called the diagonal proof.
• : r₁ = 0 . 5 1 0 5 1 1 0 ...
• : r₂ = 0 . 4 1 3 2 0 4 3 ...
• : r₃ = 0 . 8 2 4 5 0 2 6 ...
• : r₄ = 0 . 2 3 3 0 1 2 6 ...
• : r₅ = 0 . 4 1 0 7 2 4 6 ...
• : r₆ = 0 . 9 9 3 7 8 3 8 ...
• : r₇ = 0 . 0 1 0 5 1 3 5 ...
• : ...
• From these digits we define the digits of x as follows.
• * if the k^th digit of r_k is 5 then the k^th digit of x is 4
• * if the k^th digit of r_k is not 5 then the k^th digit of x is 5
• The number x is clearly a real number (since all decimal expansions represent real numbers) in . For the above sequence, for example, we obtain the following decimal expansion:
• : x = 0 . 4 5 5 5 5 5 4 ...
• Hence we must have r_n = x for some n, since we have assumed that ( r₁, r₂, r₃, ... ) enumerates all real numbers in .
• However, because of the way we have chosen 4's and 5's as digits in step (6), x differs in the n^th decimal place from r_n, so x is not in the sequence ( r₁, r₂, r₃, ... ).
• This sequence is therefore not an enumeration of the set of all reals in the interval . This is a contradiction.
• Hence the assumption (1) that the interval is countably infinite must be false.

It is a direct corollary of this result that the set R of all real numbers is uncountable. If R were countable, we could enumerate all of the real numbers in a sequence, and then get a sequence enumerating by removing all of the real numbers outside this interval. But we have just shown that this latter list cannot exist.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Alternatively, we could show that and R are the same size by constructing a bijection between them. This is slightly awkward to do, though possible, for the closed interval ; for the open interval (0,1) we might use fcolon (0,1) ightarrowmathbb{R}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

defined by f(x) = anleft(pileft(x-rac{1}{2} ight) ight).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~