Cantor's first uncountability proof

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.


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=|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"1, "x"2, "x"3, ... has all of "R" as its range. Define two other sequences ("a""n") and ("b""n") as follows:

:Pick "a"1 < "b"1 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


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Cantor's diagonal argument — An illustration of Cantor s diagonal argument for the existence of uncountable sets. The sequence at the bottom cannot occur anywhere in the list of sequences above. Cantor s diagonal argument, also called the diagonalisation argument, the… …   Wikipedia

  • Cantor's theorem — Note: in order to fully understand this article you may want to refer to the set theory portion of the table of mathematical symbols. In elementary set theory, Cantor s theorem states that, for any set A , the set of all subsets of A (the power… …   Wikipedia

  • First-order logic — is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic (a less… …   Wikipedia

  • Controversy over Cantor's theory — In mathematical logic, the theory of infinite sets was first developed by Georg Cantor. Although this work has found wide acceptance in the mathematics community, it has been criticized in several areas by mathematicians and philosophers. Cantor… …   Wikipedia

  • Countable set — Countable redirects here. For the linguistic concept, see Count noun. Not to be confused with (recursively) enumerable sets. In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of… …   Wikipedia

  • List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic …   Wikipedia

  • Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

  • Real number — For the real numbers used in descriptive set theory, see Baire space (set theory). For the computing datatype, see Floating point number. A symbol of the set of real numbers …   Wikipedia

  • Cardinality of the continuum — In mathematics, the cardinality of the continuum, sometimes also called the power of the continuum, is the size (cardinality) of the set of real numbers mathbb R (sometimes called the continuum). The cardinality of mathbb R is often denoted by… …   Wikipedia

  • Continuum hypothesis — This article is about the hypothesis in set theory. For the assumption in fluid mechanics, see Fluid mechanics. In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis, advanced by Georg Cantor in 1877[citation needed], about… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.