- Cantor's first uncountability proof
demonstrates that the set of allGeorg Cantor 's first uncountability proofreal number s 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 othernumeral system in order to prove the uncountability of the reals, but instead splits the real number line into countablesequence s.Cantor later formulated his second uncountability proof in 1877, known as

, which proved the same thing but employed a method generally regarded as simpler and more elegant than the first.Cantor's diagonal argument **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 realalgebraic number s, namely that they form acountable set , is not particularly surprising; the revolutionary import of the paper is that it demonstrates that the collection of allreal number s 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 oftranscendental number s," 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, sinceirrational number s 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 followingleast 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) andsurreal numbers . The set ofrational 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 number s is countable, and inferred the existence oftranscendental number s as a corollary. That corollary had earlier been proved by quite different methods byJoseph Liouville .**ee also***

Dedekind cut **References**

*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