Cantor's first uncountability proof

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" [cite journal|last=Cantor|first=Georg|journal=Journal für die Reine und Angewandte Mathematik|title=Über eine Eigenschaft des Inbegriffes aller reelen algebraischen Zahlen|volume=77|pages=258–262] , 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.

Publication

Cantor published the paper under what noted Cantor biographer Joseph W. Dauben [cite journal|last=Dauben|first=Joseph W|title=Georg Cantor and the Battle for Transfinite Set Theory|journal= Proceedings of the 9th ACMS Conference (Westmont College, Santa Barbara, CA)|pages=4|year=1993,2004|url=http://math.boisestate.edu/~tconklin/MATH124/Main/Notes/6%20Set%20Theory/PDFs/Cantor.pdf|accessdate=2008-01-14|format=PDF] 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." [Dauben, "op. cit.", p. 6]

The theorem

Suppose a set "R"

#is linearly ordered, and
#contains at least two members, and
#is densely ordered, i.e., between any two members there is another, and
#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.

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.

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.

ee also

* Dedekind cut

References