Cantor's first uncountability proof

From Free net encyclopedia

Contrary to what most mathematicians believe, Georg Cantor's first proof that the set of all real numbers is uncountable was not his famous diagonal argument, and did not mention decimal expansions or any other numeral system. The theorem and proof below were found by Cantor in December 1873, and published in 1874 in Crelle's Journal, more formally known as Journal für die Reine und Angewandte Mathematik (German for Journal for Pure and Applied Mathematics). Cantor discovered the diagonal argument in 1877.

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

The theorem

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. The set of rational numbers (which is countable) has properties 1-3 but does not have property 4.

The proof

The proof begins by assuming 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 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 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.) The claim is that c cannot be in the range of the sequence x, and that is the contradiction. If c were in the range, then we would have c = x_i for some index i. But then, when that index was reached in the process of defining a and b, then c would have been added as the next member of one or the other of those two sequences, contrary to the assumption that it lies between their ranges.

Real algebraic numbers and real transcendental numbers

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.

See also

• Dedekind cut

Reference

• 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.de:Cantors erster Überabzählbarkeitsbeweis