Cantor's first uncountability proof
Encyclopedia
Georg Cantor
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...

's first uncountability proof
demonstrates that the set of all real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s is uncountable
Uncountable set
In mathematics, an uncountable set is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than that of the set of all natural numbers.-Characterizations:There...

. This proof differs from the more familiar proof that uses his diagonal argument
Cantor's diagonal argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...

. Cantor's first uncountability proof was published in 1874, in an article that also contains a proof that the set of real algebraic numbers is countable
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...

, and a proof of the existence of transcendental numbers.

Two controversies have developed about this article:
  • Is Cantor's proof of the existence of transcendental numbers constructive
    Constructive proof
    In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object with certain properties by creating or providing a method for creating such an object...

     or non-constructive
    Constructive proof
    In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object with certain properties by creating or providing a method for creating such an object...

    ?
  • Why did Cantor emphasize the countability of the real algebraic numbers rather than the uncountability of the real numbers?


In 1891 Cantor published his diagonal argument
Cantor's diagonal argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...

, which produces an uncountability proof that is generally considered simpler and more elegant than his first proof. Both uncountability proofs contain ideas that can be used elsewhere. The diagonal argument is a general technique that is useful in mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

 and theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

,
while Cantor's first uncountability proof can be generalized to any infinite ordered set with the same order properties as the real numbers.

The article

Cantor's article begins with a discussion of the real algebraic numbers, and a statement of his first theorem: The collection of real algebraic numbers can be put into one-to-one correspondence with the collection of positive integers. Cantor restates this theorem in terms more familiar to mathematicians of his time: The collection of real algebraic numbers can be written as an infinite sequence in which each number appears only once.

Next Cantor states his second theorem: Given any sequence of real numbers x1, x2, x3, … and any interval
Interval (mathematics)
In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...

 [a, b], one can determine numbers in [a, b] that are not contained in the given sequence.

Cantor observes that combining his two theorems yields a new proof of the theorem: Every interval [a, b] contains infinitely many transcendental numbers. This theorem was first proved by Joseph Liouville
Joseph Liouville
- Life and work :Liouville graduated from the École Polytechnique in 1827. After some years as an assistant at various institutions including the Ecole Centrale Paris, he was appointed as professor at the École Polytechnique in 1838...

.

He then remarks that his second theorem is:
the reason why collections of real numbers forming a so-called continuum (such as, all real numbers which are ≥ 0 and ≤ 1) cannot correspond one-to-one with the collection (ν) [the collection of all positive integers]; thus I have found the clear difference between a so-called continuum and a collection like the totality of real algebraic numbers.


The first half of this remark is Cantor's uncountability theorem. Cantor does not explicitly prove this theorem, probably because it follows easily from his second theorem. To prove it, use proof by contradiction. Assume that the interval [a, b] can be put into one-to-one correspondence with the set of positive integers, or equivalently: The real numbers in [a, b] can be written as a sequence in which each real number appears only once. Applying Cantor's second theorem to this sequence and [a, b] produces a real number in [a, b] that does not belong to the sequence. This contradicts our original assumption, and proves the uncountability theorem.

Note how Cantor's second theorem separates the constructive content of his work from the proof by contradiction needed to establish uncountability.

The proofs

To prove that the set of real algebraic numbers is countable, Cantor starts by defining the height of a polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

 of degree
Degree of a polynomial
The degree of a polynomial represents the highest degree of a polynominal's terms , should the polynomial be expressed in canonical form . The degree of an individual term is the sum of the exponents acting on the term's variables...

 n to be: n − 1 + |a0| + |a1| + … + |an|, where a0, a1, …, an are the coefficient
Coefficient
In mathematics, a coefficient is a multiplicative factor in some term of an expression ; it is usually a number, but in any case does not involve any variables of the expression...

s of the polynomial. Then Cantor orders the polynomials by their height, and orders the real roots of polynomials of the same height by numeric order. Since there are only a finite number of roots of polynomials of a given height, Cantor's orderings put the real algebraic numbers into a sequence.

Next Cantor proves his second theorem: Given any sequence of real numbers x1, x2, x3, … and any interval [a, b], one can determine a number in [a, b] that is not contained in the given sequence.

To find such a number, Cantor builds two sequences of real numbers as follows: Find the first two numbers of the given sequence x1, x2, x3, … that belong to the interior of the interval [a, b]. Designate the smaller of these two numbers by a1, and the larger by b1. Similarly, find the first two numbers of the given sequence belonging to the interior of the interval [a1, b1].
Designate the smaller by a2 and the larger by b2. Continuing this procedure generates a sequence of intervals [a1, b1], [a2, b2], … such that each interval in the sequence contains all succeeding intervals. This implies the sequence a1, a2, a3, … is increasing, the sequence b1, b2, b3, … is decreasing, and every member of the first sequence is smaller than every member of the second sequence.

Cantor now breaks the proof into two cases: Either the number of intervals generated is finite or infinite. If finite, let [aN, bN] be the last interval. Since at most one xn can belong to the interior of [aN, bN], any number belonging to the interior besides xn is not contained in the given sequence.

If the number of intervals is infinite, let a =  limn → ∞ an.
At this point, Cantor could finish his proof by noting that a is not contained in the given sequence since for every n, a belongs to the interior of [an, bn] but xn does not.

Instead Cantor analyzes the situation further. He lets b = limn → ∞ bn, and then breaks the proof into two cases: a = b and a < b. In the first case, as mentioned above, a is not contained in the given sequence. In the second case, any real number in [a, b] is not contained in the given sequence. Cantor observes that the sequence of real algebraic numbers falls into the first case, thus indicating how his proof handles this particular sequence.

Is Cantor’s proof of the existence of transcendentals constructive or non-constructive?

Some mathematicians claim that Cantor’s proof of the existence of transcendental numbers is constructive—that is, it provides a method of constructing a transcendental number. For example, Irving Kaplansky
Irving Kaplansky
Irving Kaplansky was a Canadian mathematician.-Biography:He was born in Toronto, Ontario, Canada, after his parents emigrated from Poland and attended the University of Toronto as an undergraduate. After receiving his Ph.D...

 writes:
It is often said that Cantor's proof is not "constructive," and so does not yield a tangible transcendental number. This remark is not justified. If we set up a definite listing of all algebraic numbers … and then apply the diagonal procedure …, we get a perfectly definite transcendental number (it could be computed to any number of decimal places) … (I owe these remarks to R. M. Robinson
Raphael M. Robinson
Raphael Mitchel Robinson was an American mathematician.Born in National City, California, Robinson was the youngest of four children of a lawyer and a teacher. He was awarded the BA , MA , and Ph.D. , all in mathematics, and all from the University of California, Berkeley. His Ph.D...

.)


Other mathematicians claim that Cantor's proof is non-constructive. According to Ian Stewart
Ian Stewart (mathematician)
Ian Nicholas Stewart FRS is a professor of mathematics at the University of Warwick, England, and a widely known popular-science and science-fiction writer. He is the first recipient of the , awarded jointly by the LMS and the IMA for his work on promoting mathematics.-Biography:Stewart was born...

:
… The set of real numbers is uncountable. There is an infinity bigger than the infinity of natural numbers! The proof is highly original. Roughly, the idea is to assume that the reals are countable, and argue for a contradiction. … Building on this, Cantor was able to give a dramatic proof that transcendental numbers must exist. … Cantor showed that the set of algebraic numbers is countable. Since the full set of reals is uncountable, there must exist numbers that are not algebraic. End of proof (which is basically a triviality); collapse of audience in incredulity. In fact Cantor's argument shows more: it shows that there must be uncountably many transcendentals! There are more transcendental numbers than algebraic ones; and you can prove it without ever exhibiting a single example of either.


As the above examples show, these two groups of mathematicians are discussing different but related proofs—one proof is constructive while the other is non-constructive. Both proofs use a construction that takes a sequence of real numbers and produces a real number not belonging to this sequence. This construction is either the one in Cantor's 1874 article, or it uses his diagonal method. The proofs differ in how they use this construction.

The constructive proof applies it to the sequence of real algebraic numbers, thus producing a transcendental number. Cantor gave this proof in his article (see "The article").

The non-constructive proof starts by assuming that the set of real numbers is countable, or equivalently: the real numbers can be written as a sequence. Applying the construction to this sequence produces a real number not in the sequence, which contradicts the assumption that this sequence contains all real numbers. Hence, the set of real numbers is uncountable. Since the set of algebraic numbers is countable, transcendental numbers must exist. This proof does not construct a single transcendental number.

Cantor's constructions have been used to write computer programs that generate transcendental numbers. These programs show that his constructions produce computable number
Computable number
In mathematics, particularly theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers or the computable reals, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm...

s. The program that uses Cantor's diagonal method computes the digits of a transcendental number in polynomial time, while the program that uses his 1874 construction requires at least sub-exponential time.

The constructive nature of Cantor's work is easily demonstrated by using his two methods to construct irrational numbers. Both constructions start with the same sequence of rational numbers between 0 and 1. This sequence is formed by ordering these rational numbers by increasing denominators, and ordering those with the same denominator by increasing numerators.

The table below constructs an irrational number x by using Cantor's diagonal method. The strategy is to construct the decimal representation of a number that differs from the decimal representation of every rational number in our sequence. We choose the n-th digit of x so that it differs from the n-th digit of the n-th member of our sequence. If the latter digit is between 0 and 7, add 1 to obtain the n-th digit of x; otherwise, let the n-th digit of x be 0. So the decimal representation for x differs from every decimal in our sequence. Also, x is between 0 and 1, and its decimal representation does not contain the digit 9. Hence, x is irrational.
Generating an Irrational x
1/2 = 0.5 . . .
1/3 = 0.33 . . .
2/3 = 0.666 . . .
1/4 = 0.2500 . . .
3/4 = 0.75000 . . .
• • •
x = 0.64711 . . .


The next table constructs an irrational number by using Cantor's 1874 construction. The strategy is to construct a sequence of nested intervals
Nested intervals
In mathematics, a sequence of nested intervals is understood as a collection of sets of real numberssuch that each set In is an interval of the real line, for n = 1, 2, 3, ... , and that furtherfor all n...

 such that every rational number is excluded from the interior of some interval. Cantor's construction starts by finding the first two numbers in our sequence that belong to the interior of our starting interval [0, 1]. These numbers are 1/2 and 1/3, and they form the interval [1/3, 1/2]. Next we find the next two numbers in our sequence that belong to the interior of [1/3, 1/2]. Continuing this process generates a sequence of nested intervals. This sequence does not terminate since we can always find two rational numbers belonging to the interior of an interval.

In our table, the first column contains the interval, and the last column lists the rationals excluded in our search for the first two rationals belonging to this interval's interior. These excluded rationals are in the same order as our original sequence with one exception—namely, one of the endpoints of the next interval. For example, the exception in the first row is 2/5, and it is the first number excluded in the next row. Every rational number is excluded from some interval's interior because the sequence of intervals does not terminate and the interior of every interval excludes at least two rational numbers (the interval's endpoints). Thus, a real number belonging to the interior of every interval is irrational. In his proof, Cantor constructs such a real number by taking the limits of the endpoints of the intervals.
Generating an irrational using Cantor's 1874 construction
Interval Interval (decimal) Rational numbers outside interval's interior
[1/3, 1/2] [0.33…,    0.50…] 1/2, 1/3; 2/3, 1/4, 3/4, 1/5, 3/5, 4/5, 1/6, 5/6, 1/7, 2/7
[2/5, 3/7] [0.40…,    0.42…] 2/5, 3/7; 4/7, …, 1/12, 7/12, …, 6/17
[7/17, 5/12] [0.4117…, 0.4166…] 5/12, 7/17; 8/17, …, 11/29, 13/29, …, 16/41
[12/29, 17/41] [0.4137…, 0.4146…] 12/29, 17/41; 18/41, …, 27/70, 31/70, …,40/99
[41/99, 29/70] [0.4141…, 0.4142…] 29/70, 41/99; 43/99, …, 69/169, 71/169, …, 98/239

The development of Cantor's ideas

The development leading to Cantor’s article appears in the correspondence between Cantor and his fellow mathematician Richard Dedekind
Richard Dedekind
Julius Wilhelm Richard Dedekind was a German mathematician who did important work in abstract algebra , algebraic number theory and the foundations of the real numbers.-Life:...

. On November 29, 1873, Cantor asked Dedekind whether the collection of positive integers and the collection of positive real numbers "can be corresponded so that each individual of one collection corresponds to one and only one of the other?" Cantor added that
collections having such a correspondence include the collection of positive rational numbers, and collections of the form (an1, n2, …, nν) where n1, n2,…, nν, and ν are positive integers.

Dedekind replied that he was unable to answer Cantor's question, and said that it "did not deserve too much effort because it has no particular practical interest." Dedekind also sent Cantor a proof that the set of algebraic numbers is countable.

On December 2, Cantor pointed out that his question does have interest: "It would be nice if it could be answered; for example, provided that it could be answered no, one would have a new proof of Liouville's theorem that there are transcendental numbers."

On December 7, Cantor sent Dedekind an intricate proof by contradiction that the set of real numbers is uncountable. This proof uses infinitely many sequences of real numbers while the published proof uses only two sequences. Taken together, the letters of December 2 and 7 provide a non-constructive proof of the existence of transcendental numbers.

On December 9, Cantor announced the theorem that allows him to construct transcendental numbers as well as prove the uncountability of the set of real numbers:
I show directly that if I start with a sequence  ω1, ω2, … , ωn, …
I can determine, in every given interval [α, β], a number η that is not included in (I).

This theorem is the second theorem in Cantor's article.

Why does Cantor's article emphasize the countability of the algebraic numbers?

During the Christmas holidays, Cantor visited Berlin and showed his work to his former professor Karl Weierstrass
Karl Weierstrass
Karl Theodor Wilhelm Weierstrass was a German mathematician who is often cited as the "father of modern analysis".- Biography :Weierstrass was born in Ostenfelde, part of Ennigerloh, Province of Westphalia....

. On December 25, Cantor wrote Dedekind about his decision to publish:
Although I did not yet wish to publish the subject I recently for the first time discussed with you, I have nevertheless unexpectedly been caused to do so. I communicated my results to Mr. Weierstrass on the 22nd; … on the 23rd I had the pleasure of a visit from him, at which I could communicate the proofs to him. He was of the opinion that I must publish the thing at least in so far as it concerns the algebraic numbers. So I wrote a short paper with the title: "On a property of the set of real algebraic numbers," and sent it to Professor Borchardt
Carl Wilhelm Borchardt
Carl Wilhelm Borchardt was a German mathematician.Borchardt was born to a Jewish family in Berlin. His father, Moritz, was a respected merchant, and his mother was Emma Heilborn. Borchardt studied under a number of tutors, including Julius Plücker and Jakob Steiner...

' to be considered for the Journal für Math [Crelle's Journal
Crelle's Journal
Crelle's Journal, or just Crelle, is the common name for a mathematics journal, the Journal für die reine und angewandte Mathematik .- History :...

].


In a letter to Philip Jourdain
Philip Jourdain
Philip Edward Bertrand Jourdain was a British logician and follower of Bertrand Russell.He was born in Ashbourne in Derbyshire one of a large family belonging to Emily Clay and his father Francis Jourdain . He was partly disabled by Friedreich's ataxia...

, Cantor provided more details of Weierstrass' reaction:
With Mr. Weierstrass I had good relations. … Of the conception of enumerability [countability] of which he heard from me at Berlin on Christmas holydays 1873, he became at first quite amazed, but [after] one or two days passed over, it became his own and helped him to an unexpected development of his wonderful theory of functions.


Weierstrass probably urged Cantor to publish because he found the countability of the set of algebraic numbers both surprising and useful. On December 27, Cantor told Dedekind more about his article, and mentioned its quick acceptance (only four days after submission):
The restriction which I have imposed on the published version of my investigations is caused in part by local [Berlin] circumstances (about which I shall perhaps later speak with you orally) and in part because I believe that it is important to apply my ideas at first to a single case (such as that of the real algebraic numbers) …

As Mr. Borchardt has already responded to me today, he will have the kindness to include this article soon in the Math. Journal.


Cantor gave two reasons for restricting his article: "local circumstances" and the importance of applying "my ideas at first to a single case." Cantor never told Dedekind what the "local circumstances" were. This has led to a controversy: Who influenced Cantor so that his article emphasizes the countability of the set of algebraic numbers rather than the uncountability of the set of real numbers? This controversy is also fueled by Cantor's earlier letters, which indicate that he was most interested in the set of real numbers.

Cantor biographer Joseph Dauben
Joseph Dauben
Joseph W. Dauben is a Herbert H. Lehman Distinguished Professor of History at the Graduate Center of the City University of New York. He obtained his Ph.D...

 argues that "local circumstances" refers to the influence of Leopold Kronecker
Leopold Kronecker
Leopold Kronecker was a German mathematician who worked on number theory and algebra.He criticized Cantor's work on set theory, and was quoted by as having said, "God made integers; all else is the work of man"...

, Weierstrass' colleague at the University of Berlin. Dauben states that publishing in Crelle's Journal could be difficult because Kronecker, a member of the journal's editorial board, had a restricted view of what was acceptable in mathematics. Dauben argues that to avoid publication problems, Cantor wrote his article to emphasize the countability of the set of real algebraic numbers.

Dauben uses examples from Cantor's article to show Kronecker's influence. For example, Cantor did not prove the existence of the limits used in the proof of his second theorem. Cantor did this despite using Dedekind's version of the proof. In his private notes, Dedekind wrote:
… [my] version is carried over almost word-for-word in Cantor's article (Crelle's Journal, 77); of course my use of "the principle of continuity" is avoided at the relevant place …


The "principle of continuity" requires a general theory of the irrationals, such as Cantor's or Dedekind's construction of the real numbers from the rationals. Kronecker accepted neither theory.

In his history of set theory, José Ferreirós analyzes the situation in Berlin and arrives at a different conclusion. Ferreirós emphasizes Weierstrass' influence: Weierstrass was interested in the countability of the set of real algebraic numbers because he could use it to build interesting functions. Also, Ferreirós suspects that in 1873 Weierstrass might not have accepted the idea that infinite sets can have different sizes. The following year, Weierstrass "stated that two 'infinitely great magnitudes' are not comparable and can always be regarded as equal." Weierstrass' opinion on infinite sets may have led him to advise Cantor to omit his remark on the essential difference between the collections of real numbers and real algebraic numbers. (This remark appears above in "The article.") Cantor mentions Weierstrass' advice in his December 27 letter:
The remark on the essential difference of the collections, which I could have very well included, was omitted on the advice of Mr. Weierstrass; but [he also advised that I] could add it later as a marginal note during proofreading.


Ferreirós' strongest statement about the "local circumstances" mentions both Kronecker and Weierstrass: "Had Cantor emphasized it [the uncountability result], as he had in the correspondence with Dedekind, there is no doubt that Kronecker and Weierstrass would have reacted negatively." Ferreirós also mentions another aspect of the local situation: Cantor, thinking of his future career in mathematics, desired to maintain good relations with the Berlin mathematicians. This desire could have motivated Cantor to create an article that appealed to Weierstrass' interests, and did not antagonize Kronecker.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK