Cantor's first uncountability proof
Georg Cantor's first proof of uncountability demonstrates that the set of all real numbers is uncountably, rather than countably, infinite. This proof differs from the more familiar proof that uses his diagonal argument. 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, and a proof of the existence of transcendental numbers.
Two points about which not all authors writing about Cantor's article have agreed are these:
- Is Cantor's proof of the existence of transcendental numbers constructive or non-constructive?
- 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, 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 and theoretical computer science, while Cantor's first uncountability proof can be generalized to any ordered set with the same order properties as the real numbers.
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.
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.
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, which 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.
Cantor's second theorem is constructive and thereby separates the constructive content of his work from the proof by contradiction needed to establish uncountability.
To prove that the set of real algebraic numbers is countable, Cantor starts by defining the height of a polynomial of degree n to be: n − 1 + |a0| + |a1| + … + |an|, where a0, a1, …, an are the (integer) coefficients 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 of [aN, bN] 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.
Constructive or non-constructive nature of Cantor's proof of the existence of transcendentals
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 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.)
Other mathematicians claim that Cantor's proof is non-constructive. According to Ian Stewart:
- … 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.
The above quotations show that 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 numbers (as long as one starts with a computable sequence of computable numbers). 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 produce 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 the sequence. We choose the n-th digit of x so that it differs from the n-th digit of the n-th member of the 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 the sequence. Also, x is between 0 and 1, and its decimal representation does not contain the digit 9. Hence, x is irrational.
|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 such that every rational number is excluded from the interior of some interval. Cantor's construction starts by finding the first two numbers in the sequence that belong to the interior of the 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 the 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 the table, the first column contains the interval, and the last column lists the rationals excluded in the search for the first two rationals belonging to this interval's interior. These excluded rationals are in the same order as the 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.
|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. 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
- (I) ω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 Cantor's article emphasizes the countability of the algebraic numbers
- 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 to be considered for the Journal für Math [Crelle's Journal].
In a letter to Philip Jourdain, 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 argues that "local circumstances" refers to the influence of Leopold Kronecker, 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.
- Cantor 1874. English translation: Ewald 1996, pp. 840–843.
- Gray 1994.
- Dauben 1979, pp. 66–70; Ferreirós 2007, pp. 183–186.
- Cantor 1891. English translation: Ewald 1996, pp. 920–922.
- The diagonal argument cannot be applied to sets that only have an ordering. Applying the diagonal argument to the real numbers requires a numeral system—such as the decimal representation system—and a numeral system uses the addition and multiplication properties of the real numbers.
- Cantor 1874. English translation: Ewald 1996, pp. 840–843.
- The notation [a, b] denotes the set of real numbers that are ≥ a and ≤ b.
- Liouville proved this theorem by constructing what are now known as Liouville numbers, and then proving that these numbers are transcendental.
- Cantor 1874, p. 259. English translation: Gray 1994, p. 820.
- Gray 1994, p. 823.
- Using this ordering and placing only the first occurrence of a real algebraic number in the sequence produces a sequence without duplicates. Cantor obtains the same sequence by using irreducible polynomials:
Cantor's enumeration of algebraic numbers Height 1: 1x +0 = 0 x1 = 0 Height 2: 2x +0 = 0 reducible 1x +1 = 0 x2 = −1 1x −1 = 0 x3 = +1 1x2 +0x +0 = 0 reducible Height 3: 3x +0 = 0 reducible 2x +1 = 0 x5 = −1/2 2x −1 = 0 x6 = +1/2 1x +2 = 0 x4 = −2 1x −2 = 0 x7 = +2 2x2 +0x +0 = 0 reducible 1x2 +1x +0 = 0 reducible 1x2 −1x +0 = 0 reducible 1x2 +0x +1 = 0 no real root 1x2 +0x −1 = 0 reducible 1x3 +0x2 +0x +0 = 0 reducible Height 4: 4x +0 = 0 reducible 3x +1 = 0 x13 = −1/3 3x −1 = 0 x14 = +1/3 2x +2 = 0 reducible 2x −2 = 0 reducible 1x +3 = 0 x8 = −3 1x −3 = 0 x19 = +3 3x2 +0x +0 = 0 reducible 2x2 +1x +0 = 0 reducible 2x2 −1x +0 = 0 reducible 2x2 +0x +1 = 0 no real root 2x2 +0x −1 = 0 x16, x11 = ±1/√2 1x2 +2x +0 = 0 reducible 1x2 −2x +0 = 0 reducible 1x2 +1x +1 = 0 no real root 1x2 +1x −1 = 0 x15, x9 = (−1 ± √5) / 2 1x2 −1x +1 = 0 no real root 1x2 −1x −1 = 0 x18, x12 = (+1 ± √5) / 2 1x2 +0x +2 = 0 no real root 1x2 +0x −2 = 0 x17, x10 = ±√2 2x3 +0x2 +0x +0 = 0 reducible 1x3 +1x2 +0x +0 = 0 reducible 1x3 −1x2 +0x +0 = 0 reducible 1x3 +0x2 +1x +0 = 0 reducible 1x3 +0x2 −1x +0 = 0 reducible 1x3 +0x2 +0x +1 = 0 reducible 1x3 +0x2 +0x −1 = 0 reducible 1x4 +0x3 +0x2 +0x +0 = 0 reducible Height 5: 5x +0 = 0 reducible :
- Although Cantor's proof determines a single number, he states: "and consequently infinitely many such numbers … can be determined." (Cantor 1874, p. 260. English translation: Ewald 1996, p. 841.) To see this, consider (for example) the interval [0, 1]. By dividing it into the subintervals [0, 1/2], [1/2, 3/4], [3/4, 7/8], … and then applying the construction in Cantor's proof to each subinterval, we obtain infinitely many numbers that are not contained in the given sequence.
- The interior of the interval [a, b] consists of all numbers in the interval except the endpoints a and b.
- Cantor does not state why this limit exists. It exists because the completeness property of the real numbers implies that every increasing sequence that is bounded above has a limit. The sequence an is increasing and it is bounded above by b (that is, for all n, an < b). The easiest proof that such a sequence has a limit uses the least upper bound property: Every nonempty set of real numbers that has an upper bound also has a least upper bound. The least upper bound property is one of several equivalent ways to express completeness (see the article "Real number").
- Cantor states (without proof) that xn does not belong to the interior of [an, bn]. To prove this, we use an inductive proof to prove the stronger result: x1, x2, …, x2n do not belong to the interior of [an, bn]. By Cantor's construction, a1 and b1 are the first two numbers in the given sequence xn that belong to the interior of [a, b]. If x1 is one of these numbers, then it does not belong to the interior of [a1, b1]. However, if x1 is not one of these numbers, then it does not even belong to the interior of the larger interval [a, b]. Similarly, x2 does not belong to the interior of [a1, b1]. For the inductive step of the proof, assume that x1, x2, …, x2k do not belong to the interior of [ak, bk]. By Cantor's construction, ak + 1 and bk + 1 are the first numbers in the given sequence that belong to the interior of [ak, bk]. By assumption, x1, x2, …, x2k do not belong to the interior of this interval, so ak + 1 and bk + 1 are chosen from the subsequence x2k + 1, x2k + 2, …. Using the same reasoning we used to prove that x1 and x2 do not belong to the interior of [a1, b1], we see that x2k + 1 and x2k + 2 do not belong to the interior of [ak + 1, bk + 1]. Therefore, x1, x2, …, x2k, x2k + 1, x2k + 2 do not belong to the interior of [ak + 1, bk + 1].
- Cantor does not state why this limit exists. It exists because the completeness property of the real numbers implies that every decreasing sequence that is bounded below has a limit. The sequence bn is decreasing and it is bounded below.
- Cantor 1874, p. 261. English translation: Ewald 1996, p. 842.
- Kaplansky 1977, p. 25. For other examples, see: Akihiro Kanamori 2009, p. 398 (also located at Set Theory from Cantor to Cohen, p. 4); Boas and Boas 1996, pp. 12–14; and Fraenkel 1930, p. 237 (English translation: Gray 1994, p. 823).
- Stewart 1987, pp. 92–93. Cantor's proof is also mentioned on page 292: "Cantor's existence proof, mentioned in chapter 7, exhibits not a single transcendental." For other examples, see: Howie 2006, p. 61; Bell 1937, p. 569; and Perron 1921, p. 162 (English translation: Gray 1994, p. 828).
- Gray 1994, pp. 821–824, 830–831.
- Gray 1994, pp. 822–823.
- Avoiding the digit 9 is needed because some rational numbers, such as 1/4, have two representations (0.2500… and 0.2499…). The table contains only one decimal representation for 1/4, namely 0.2500… The diagonal argument prevents x from having this representation; avoiding the digit 9 prevents x from having the representation 0.2499…
- For example, take the midpoint of the interval and the point halfway between the interval's left endpoint and this midpoint. If the interval is [a, b], these are the points (a + b) / 2 and (3a + b) / 4.
- In fact, there is only one such real number when Cantor's construction is applied to the rational numbers (or to any dense subset of the real numbers). Looking back at The proofs, Cantor lets a∞ be the limit of the left endpoints, and b∞ be the limit of the right endpoints. Then either a∞ = b∞ or a∞ < b∞. If the latter case were true, then a rational would lie between these limits since the set of rational numbers is dense in the set of real numbers. But this rational would belong to the interior of all the intervals, which is impossible by the construction. Hence, a∞ is the only real number belonging to the interior of every interval.
- The real number constructed by the table is √2 − 1. To prove this, we use Farey sequences and continued fractions. The Farey sequence Fn is the increasing sequence of completely reduced fractions whose denominators are ≤ n. If a/b and c/d are adjacent in a Farey sequence, the lowest denominator fraction between them is their mediant (a + c)/(b + d). This mediant is adjacent to both a/b and c/d in the Farey sequence Fb + d . (LeVeque 2002, pp. 154–155.) Cantor's construction produces mediants because we sequenced rational numbers by increasing denominator. The first interval in the table is [1/3, 1/2]. Since 1/3 and 1/2 are adjacent in F3, their mediant 2/5 is the first rational in the sequence between 1/3 and 1/2. Since 2/5 is adjacent to both 1/3 and 1/2 in F5, the next fraction is 3/7, the mediant of 2/5 and 1/2. Since we use mediants, we have: 1/3 < 2/5 < 3/7 < 1/2. So the second interval is [2/5, 3/7]. Now we prove that the endpoints of the intervals converge to the continued fraction [0, 2, 2,…]. This continued fraction is the limit of its convergents pn/qn = [0, 2,… 2] (n 2's). The pn and qn sequences satisfy the equations: p0 = 0, p1 = 1; q0 = 1, q1 = 2; pn + 1 = 2pn + pn − 1 and qn + 1 = 2qn + qn − 1 for n ≥ 1. (LeVeque 2002, pp. 174–175.) We prove by induction that the n-th interval in the table is [(pn + pn − 1)/(qn + qn − 1), pn/qn] for odd n. For even n, the endpoints are reversed. This is true for the first interval since [1/3, 1/2] = [(p1 + p0)/(q1 + q0), p1/q1]. Assume that the inductive hypothesis is true for the k-th interval. If k is odd, this interval is [(pk + pk − 1)/(qk + qk − 1), pk/qk]. The mediant of its endpoints, (2pk + pk − 1)/(2qk + qk − 1) = pk + 1/qk + 1, is the first fraction between these endpoints. The second fraction is (pk + 1 + pk)/(qk + 1 + qk), the mediant of pk + 1/qk + 1 and pk/qk. Since we use mediants, we have: (pk + pk − 1)/(qk + qk − 1) < pk + 1/qk + 1 < (pk + 1 + pk)/(qk + 1 + qk) < pk/qk. So the (k + 1)-st interval is [pk + 1/qk + 1, (pk + 1 + pk)/(qk + 1 + qk)]. Note that pk + 1/qk + 1 is the left endpoint, which is required since k + 1 is even. Thus, the inductive hypothesis is true for the (k + 1)-st interval. For even k, the proof is similar. Since the left endpoints of the intervals are increasing and every other endpoint is p2n/q2n, their limit equals limn → ∞ pn/qn. Similarly, the right endpoints have the same limit. As mentioned above, this limit is the continued fraction [0, 2, 2,…], which equals √2 − 1. (Weisstein 2003, p. 541.)
- Noether and Cavaillès 1937, pp. 12–20.
- Noether and Cavaillès 1937, p. 12. English translation: Gray 1994, p. 827. The second result is equivalent to the theorem that the set of all finite n-tuples of positive integers is countable. In his article and in his 1873 letters, Cantor only considered sets of numbers. So it was natural for him to state a theorem about indexed numbers, which are common in mathematics—for example, a matrix is a set of indexed numbers.
- Noether and Cavaillès 1937, p. 18. English translation: Ewald 1994, p. 848. A weaker version of this theorem appears as the first theorem in Cantor's article. Cantor weakened the theorem by restricting it to the set of real algebraic numbers. See Ferreirós 2007 (p. 179–180) for a discussion on who should get credit for this theorem, and how it is related to Cantor's earlier theorem about finite n-tuples of positive integers.
- Noether and Cavaillès 1937, p. 13. English translation: Gray 1994, p. 827.
- Noether and Cavaillès 1937, pp. 14–15. English translation: Ewald 1996, pp. 845–846.
- Noether and Cavaillès 1937, p. 16. English translation: Gray 1994, p. 827.
- The editor of Crelle's Journal, which was called Borchardt's Journal at the time.
- Noether and Cavaillès 1937, p. 17. English translation: Ewald 1996, pp. 847–848.
- Grattan-Guinness 1971, p. 124. (The letter was written in 1905.)
- Cantor realized that his fellow mathematicians might be initially surprised by this result. In his article, he states: "The real algebraic numbers form in their totality a set of numbers, which shall be designated by (ω); as is readily seen, (ω) has the property that in every neighbourhood of any given number α there are infinitely many numbers from (ω). So it ought at first glance to be all the more striking that one can correlate the set (ω) one-to-one with the set … of all positive integers …" (Cantor 1874, p. 258, Ewald 1996, p. 840).
- The submission date, December 23, 1873, appears at the end of the article—see Cantor 1874, p. 262.
- Dugac 1976, p. 226. Cantor's article was published within weeks after its submission (Dauben 1993, p. 5).
- Noether and Cavaillès 1937, p. 20. English translation: Ewald 1996, p. 850.
- Dauben 1993 (p. 5) states: "By the early 1870s, Kronecker was already vocal in his opposition to the Bolzano-Weierstrass theorem, upper and lower limits, and to irrational numbers in general." For more on Kronecker's views: see Dauben 1979, pp. 66–70, and Dauben 1993, p. 5–7.
- Cantor's colleague, Eduard Heine, had recently experienced a publication delay because of Kronecker. (Dauben 1979, p. 67; Dauben 1993, p. 5.)
- Dauben 1979, pp. 66–70. Gray 1994 (p. 828) also gives an example: "… [Cantor's] theorems only deal with sequences that are ordered by a 'law.'" Gray states that "Cantor may have inserted this restriction to avoid problems with Kronecker." However, Ferreirós 2007 (p. 263) corrects Gray: "Like all other authors in the early period of the history of sets, he [Cantor] tended to think of them [sets] as given by a concept or a law, indeed he emphasized this aspect more than other contemporaries." Ferreirós provides examples from Cantor's articles dating from 1872 to 1883.
- These are the limits: a∞ = limn → ∞ an and b∞ = limn → ∞ bn (see "The proofs").
- Dauben 1979, p. 67. Dedekind's principle of continuity appears in his 1872 construction of the real numbers, which uses Dedekind cuts of rational numbers. The principle of continuity states: For every cut in the real numbers, there is a unique real number that produces this cut. (A cut separates the real numbers into two sets A and B such that every member A is less than every member of B. A real number produces a cut if it is either the greatest member of A or the least member of B.) Dedekind's principle of continuity is equivalent to the least upper bound property: Every set of real numbers that is bounded above has a least upper bound. (Dedekind 1901, p. 9.)
- Dauben 1979, p. 69.
- For example, Weierstrass used it to build a function that is continuous everywhere but differentiable only at transcendental numbers. Ferreirós 2007, p. 184.
- Ferreirós 2007, p. 184, footnote 3. However, by the mid-1880s, Weierstrass accepted Cantor's discovery that infinite sets can have different cardinalities. (Ferreirós 2007, p. 185.)
- Ferreirós 2007, p. 184.
- Dugac 1976, p. 226; Ferreirós 2007, p. 184. Cantor did add his remark during proofreading.
- Ferreirós 2007, p. 185.
- Ferreirós 2007 (p. 185–186) mentions this subject as one possible reason why Cantor did not acknowledge Dedekind's help in his article. Cantor acknowledged the help of Kronecker, Weierstrass, Schwarz, and Heine in earlier articles. He did thank Dedekind privately in his December 25 letter: "… your comments (which I value highly) and your manner of putting some of the points were of great assistance to me." Dedekind's private notes on his correspondence reveal how great this assistance was. Dedekind wrote: "… [I] stated and fully proved the theorem that even the totality of all algebraic numbers can be correlated in the stated manner with the totality (n) of all natural numbers. (Shortly thereafter, this theorem and proof appeared almost word-for-word in Cantor's paper in Crelle, Vol. 77, …)" Dedekind's proof of Cantor's second theorem also appears in the article (see quotation above in discussion of Dauben's views). Ferreirós suspects that one reason for Cantor not acknowledging Dedekind's help was his desire to maintain good relations with the Berlin mathematicians. Two of these mathematicians—Kronecker and Kummer—were angry with Dedekind for publishing his theory of algebraic integers before Kronecker published his equivalent theory. Dedekind published his theory in 1871. Kronecker's theory dates back to 1858, but he published it in 1883. For more details on Dedekind's contributions to Cantor's article, see Ferreirós 2007, pp. 177–186. The quotations above are from: Noether and Cavaillès 1937, pp. 17–19; English translation: Ewald 1996, pp. 847–849.
- In his December 27 letter, Cantor mentions Weierstrass' interests when he states "it is important to apply my ideas at first to a single case (such as that of the real algebraic numbers)." His desire to avoid antagonizing Kronecker appears in Dauben's analysis, and in Ferreirós' statement "that Kronecker and Weierstrass would have reacted negatively" if Cantor had emphasized his uncountability result.
- Bell, Eric Temple (1937), Men of Mathematics, New York: Simon & Schuster, ISBN 0-671-62818-6.
- Boas, Ralph P., Jr.; Boas, Harold P. (1996), A Primer of Real Functions (4th ed.), Mathematical Association of America, ISBN 978-0-88385-029-9.
- Cantor, Georg (1874), "Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen", Journal für die Reine und Angewandte Mathematik 77: 258–262, doi:10.1515/crll.1874.77.258, retrieved 2010-01-15.
- Cantor, Georg (1891), "Über eine elementare Frage der Mannigfaltigskeitslehre", Jahresbericht der Deutschen Mathematiker-Vereinigung 1: 75–78.
- Dauben, Joseph (1979), Georg Cantor: His Mathematics and Philosophy of the Infinite, Boston: Harvard University Press, ISBN 0-674-34871-0.
- Dauben, Joseph (1993), "Georg Cantor and the Battle for Transfinite Set Theory" (PDF), 9th ACMS Conference Proceedings, retrieved 2010-01-15.
- Dedekind, Richard (1901), Essays on the Theory of Numbers (PDF), Chicago: Open Court Publishing Company. (Reprinted by Dover Publications, 1963.)
- Dugac, Pierre (1976), Richard Dedekind et les Fondements des Mathématiques, Paris: Vrin.
- Ewald, William B. (ed.) (1996), From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, New York: Oxford University Press, ISBN 978-0-19-853271-2.
- Ferreirós, José (2007), Labyrinth of Thought: A History of Set Theory and Its Role in Mathematical Thought (2nd revised ed.), Basel, Switzerland: Birkhäuser, ISBN 3-7643-8349-6.
- Fraenkel, Abraham (1930), "Georg Cantor", Jahresbericht der Deutschen Mathematiker-Vereinigung 39: 189–266, retrieved 2010-01-15.
- Grattan-Guinness, Ivor (1971), "The Correspondence between Georg Cantor and Philip Jourdain", Jahresbericht der Deutschen Mathematiker-Vereinigung 73: 111–130, retrieved 2010-01-15.
- Gray, Robert (1994), "Georg Cantor and Transcendental Numbers", American Mathematical Monthly 101: 819–832, doi:10.2307/2975129, retrieved 2010-01-15.
- Howie, John Mackintosh (2006), Fields and Galois Theory, London: Springer, ISBN 1-85233-986-1.
- Kanamori, Akihiro (2009), "Set Theory from Cantor to Cohen" (PDF), Philosophy of Mathematics, North Holland, pp. 395–460, ISBN 978-0-444-51555-1.
- Kaplansky, Irving (1977), Set Theory and Metric Spaces (2nd ed.), New York: Chelsea, ISBN 0-8284-0298-1.
- LeVeque, William J. (2002) , Topics in Number Theory, Volumes I and II, Dover Publications: New York, ISBN 978-0-486-42539-9.
- Noether, Emmy; Cavaillès, Jean (eds.) (1937), Briefwechsel Cantor-Dedekind, Paris: Hermann.
- Perron, Oskar (1921), Irrationalzahlen, Berlin: de Gruyter.
- Stewart, Ian (1992), The Problems of Mathematics (2nd ed.), Oxford: Oxford University Press, ISBN 0-19-286148-4.
- Weisstein, Eric W., ed. (2003), "Continued Fraction", CRC Concise Encyclopedia of Mathematics, Boca Raton: Chapman & Hall/CRC, ISBN 1-58488-347-2.