From Wikipedia, the free encyclopedia

Georg Cantor's first uncountability proof demonstrates that the set of all real numbers is uncountable. Cantor formulated the proof in December 1873 and published it in 1874 in Crelle's Journal, more formally known as the Journal für die Reine und Angewandte Mathematik (Journal for Pure and Applied Mathematics). The proof does not rely on decimal expansions or any other numeral system in order to prove the uncountability of the reals, but instead splits the real number line into countable sequences.

Cantor later formulated his second uncountability proof in 1877, known as Cantor's diagonal argument, which proved the same thing but employed a method generally regarded as simpler and more elegant than the first.

Contents 1 The theorem 2 The proof 3 Real algebraic numbers and real transcendental numbers 4 See also 5 Reference

Suppose a set R is

1. linearly ordered, and
2. contains at least two members, and
3. is densely ordered, i.e., between any two members there is another, and
4. is complete, i.e., if it is partitioned into two nonempty sets A and B in such a way that every member of A is less than every member of B, then there is a boundary point c (in R), so that every point less than c is in A and every point greater than c is in B.

Then R is not countable.

The set of real numbers with its usual ordering is a typical example of such an ordered set R. The set of rational numbers (which is countable) has properties 1-3 but does not have property 4.

The proof is by contradiction. It begins by assuming R is countable and thus that some sequence x₁, x₂, x₃, ... has all of R as its range. Define two other sequences (a_n) and (b_n) as follows:

Pick a₁ < b₁ in R (possible because of property 2).

Let a_n+1 be the first element in the sequence x which is strictly between a_n and b_n (possible because of property 3).

Let b_n+1 be the first element in the sequence x which is strictly between a_n+1 and b_n.

The two monotone sequences a and b move toward each other. By the completeness of R, some point c must lie between them. (Define A to be the set of all elements in R that are smaller than some member of the sequence a, and let B be the complement of A; then every member of A is smaller than every member of B, and so property 4 yields the point c.) Since c is an element of R and the sequence x represents all of R, we must have c = x_i for some index i (i.e., there must exist an x_i in the sequence x, corresponding to c.) But, when that index was reached in the process of defining the sequences a and b, c would have been added as the next member of one or the other sequence, contrary to the fact that c lies strictly between the two sequences. This contradiction finishes the proof.

In the same paper, published in 1874, Cantor showed that the set of all real algebraic numbers is countable, and inferred the existence of transcendental numbers as a corollary. That corollary had earlier been proved by quite different methods by Joseph Liouville.

• Dedekind cut

• Georg Cantor, 1874, "Über eine Eigenschaft des Inbegriffes aller reelen algebraischen Zahlen", Journal für die Reine und Angewandte Mathematik, volume 77, pages 258-262.