Cantor's first uncountability proof

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^[1], 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 Publication 2 The theorem 3 The proof 4 Real algebraic numbers and real transcendental numbers 5 See also 6 References

[edit] Publication

Cantor published the paper under what noted Cantor biographer Joseph W. Dauben ^[2] calls a "very strange" and "deliberately misleading" title, namely "On a Property of the Collection of All Real Algebraic Numbers" (German:Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen). The strange thing about the title is that the property Cantor proves about the collection of all real algebraic numbers, namely that they form a countable set, is not particularly surprising; the revolutionary import of the paper is that it demonstrates that the collection of all real numbers is not countable.

Dauben argues that the title was specifically intended to avoid attracting the hostile attentions of Leopold Kronecker, a member of the editorial board of Crelle's Journal, who was antagonistic to the very notions Cantor was studying:

Had Cantor been more direct with a title like "The set of real numbers is non-denumerably infinite" or "A new and independent proof of the existence of transcendental numbers," he could have counted on a strongly negative reaction from Kronecker. After all, when Lindemann later established the transcendence of π in 1882, Kronecker asked what value the result could possibly have, since irrational numbers did not exist.^[3]

[edit] The theorem

Suppose a set R

1. is 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. has the following least upper bound property. If R 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; other examples are real intervals of non-zero width (possibly with half-open gaps) and surreal numbers. The set of rational numbers (which is countable) has properties 1, 2, and 3 but does not have property 4.

[edit] The proof

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 that 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 that 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.

[edit] 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.

[edit] See also

• Dedekind cut

[edit] References