User:RJGray/Cantor draft1

Cantor's first uncountability proof 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. Georg Cantor's first 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.

Georg Cantor, ca. 1870.

As early as 1930, some mathematicians have disagreed on whether Cantor's proof of the existence of transcendentals is constructive or non-constructive. Books as recent as 2014 and 2015 indicate that this disagreement has not been resolved. A careful study of Cantor's article and its proofs will determine the nature of his proof. Cantor's correspondence shows the development of his ideas and reveals that he had a choice between two proofs: one uses the uncountability of the real numbers; the other does not. These proofs play an important role in the disagreement about his proof.

The title of Cantor's article is "On a Property of the Collection of All Real Algebraic Numbers." Historians of mathematics have studied the reasons why Cantor's article emphasizes the countability of the real algebraic numbers rather than the uncountability of the real numbers. They have discovered interesting facts about the article—for example, Cantor left out his uncountability theorem in the article he submitted, then added it during proofreading. They have also studied Richard Dedekind's contributions to the article.

The article

Cantor's article is short, just ⁠4+1/3⁠ pages. It 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's second theorem works with a closed interval [a, b], which is the set of real numbers ≥ a and ≤ b. This theorem states: Given any sequence of real numbers x₁, x₂, x₃, … and any interval [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.

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.

This remark contains Cantor's uncountability theorem, which only states that an interval [a, b] cannot be put into one-to-one correspondence with the set of positive integers. It does not say that this interval is an infinite set of larger cardinality than the set of positive integers. Cardinality and how to compare the cardinality of sets will appear in his next article, which was published in 1878.

Cantor does not explicitly prove his uncountability theorem, which follows easily from his second theorem. To prove it, we 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 the original assumption, and proves the uncountability theorem.

Cantor's second theorem is constructive and separates the constructive content of his work from the proof by contradiction needed to establish uncountability. Cantor's uncountability theorem is just stated; it is not used in any proofs.

The proofs

Algebraic numbers on the complex plane colored by polynomial degree. (red = 1, green = 2, blue = 3, yellow = 4). Points becomes smaller as the integer polynomial coefficients become larger.

For Cantor's article to be constructive, it is also necessary that his proofs be constructive.

To prove that the set of real algebraic numbers is countable, Cantor defines the height of a polynomial of degree n with integer coefficients as: n − 1 + |a₀| + |a₁| + … + |a_n|, where a₀, a₁, …, a_n are the coefficients of the polynomial. Then he 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, these orderings put the real algebraic numbers into a sequence.

Cantor's method of sequencing the real algebraic numbers is constructive. In fact, since these numbers are computable, his method can be used to write a computer program that computes the k-th digit of the n-th number of the sequence for all k and n. This implies that Cantor's method produces a computable sequence of computable numbers.

Next Cantor proves his second theorem: Given any sequence of real numbers x₁, x₂, x₃, … and any interval [a, b], one can determine a number in [a, b] that is not contained in the given sequence. We simplify Cantor's proof by using open intervals. The open interval (a, b) is the set of real numbers > a and < b.

To find a number in [a, b] that is not contained in the given sequence, construct two sequences of real numbers as follows: Find the first two numbers of the given sequence that are in (a, b). Designate the smaller of these two numbers by a₁, and the larger by b₁. Similarly, find the first two numbers of the given sequence that are in (a₁, b₁). Designate the smaller by a₂ and the larger by b₂. Continuing this procedure generates a sequence of intervals (a₁, b₁), (a₂, b₂), … such that each interval in the sequence contains all succeeding intervals—that is, it generates a sequence of nested intervals. This implies the sequence a₁, a₂, a₃, … is increasing, the sequence b₁, b₂, b₃, … is decreasing, and every member of the first sequence is smaller than every member of the second sequence.

Case 1: Last interval (a_N, b_N)

Either the number of intervals generated is finite or infinite. Case 1: if finite, let (a_N, b_N) be the last interval. Since a_N < b_N and at most one x_n can be in (a_N, b_N), every y in this interval except x_n (if it exists) is not contained in the given sequence.

Case 2: a_∞ = b_∞

Case 3: a_∞ < b_∞

If the number of intervals is infinite, let a_∞ =  lim_n → ∞ a_n and b_∞ = lim_{n → ∞} b_n. Now either a_∞ = b_∞ or a_∞ < b_∞. Case 2: if a_∞ = b_∞, a_∞ is not contained in the given sequence since for all n, a_∞ belongs to (a_n, b_n) but x_n does not. Cantor states without proof that x_n does not belong to (a_n, b_n); this will be proved below. Case 3: if a_∞ < b_∞, every y in [a_∞, b_∞] is not contained in the given sequence since for all n, y belongs to (a_n, b_n) but x_n does not. The proof is complete since in all cases, at least one real number in [a, b] has been found that is not contained in the given sequence.

In his proof, Cantor observes that a_∞ = b_∞ when his construction is applied to the sequence of real algebraic numbers, which is the sequence he uses to construct transcendental numbers. More generally, a_∞ = b_∞ for any sequence that is dense in [a, b], which means that every subinterval (y, z) of [a, b] contains a term of the sequence.

We prove the contrapositive: if a_∞ = b_∞ is not true, then the sequence is not dense. If a_∞ = b_∞ is not true, then either there is a last interval (a_N, b_N) or a_∞ < b_∞. We use the same case numbering as the proof above. Case 1: if there is a last interval, then at most one x_n can be in it. If there is such an x_n, then the interval (a_N, x_n) contains no terms of the sequence. Otherwise, the interval (a_N, b_N) contains no terms of the sequence. Hence, the sequence is not dense. Case 3: if a_∞ < b_∞, then (a_∞, b_∞) contains no terms of the sequence, so the sequence is not dense. Therefore, if a sequence is dense, case 2 must be true, so a_∞ = b_∞. The converse is not true: the sequence −⁠1/2⁠, ⁠1/2⁠, −⁠1/3⁠, ⁠1/3⁠, … is not dense in [−1, 1]. However, a_n = −⁠1/n + 1⁠ and b_n = ⁠1/n + 1⁠, so a_∞ = b_∞ = 0.

Since Cantor's construction uses only the order properties of the real numbers, his second theorem can be generalized to any ordered set with the same order properties as the real numbers. Hence, such an ordered set is uncountable.

Cantor's construction is constructive, and when it is applied to a computable sequence of computable numbers, it produces a computable number. A computer program has been written that generates the digits of a transcendental number by applying the construction to a sequence containing all the real algebraic numbers between 0 and 1. The article that discusses this program gives some of its output, which shows how the construction generates a transcendental. However, this article does not show which algebraic numbers are excluded from each interval.

To analyze how Cantor's construction excludes the terms of a sequence, we use a simpler example that applies the construction to the rational numbers between 0 and 1 to produce an irrational number. By ordering these rational numbers by increasing denominators, and ordering those with the same denominator by increasing numerators, we obtain the sequence: ⁠1/2⁠, ⁠1/3⁠, ⁠2/3⁠, ⁠1/4⁠, ⁠3/4⁠, ⁠1/5⁠, ⁠2/5⁠, ⁠3/5⁠, ⁠4/5⁠, …. The table below shows the first five steps of the construction. Because this sequence of rational numbers is dense in [0, 1], a non-terminating sequence of intervals is generated.

We start by finding the first two terms in the sequence belonging to (0, 1). These numbers are ⁠1/2⁠ and ⁠1/3⁠, and they form the interval (⁠1/3⁠, ⁠1/2⁠). Next we find the first two terms belonging to this interval, which are ⁠2/5⁠ and ⁠3/7⁠. The leading terms ⁠1/3⁠, ⁠1/2⁠ …, ⁠3/7⁠ except for ⁠2/5⁠ and ⁠3/7⁠ are excluded by the interval (⁠1/3⁠, ⁠1/2⁠). However, these two terms are the first terms excluded by the next interval (⁠2/5⁠, ⁠3/7⁠). So if the construction is stopped after ⁠2/5⁠ and ⁠3/7⁠ are excluded, then the interval (⁠2/5⁠, ⁠3/7⁠) only excludes leading terms up to ⁠3/7⁠. This stopping point is marked by a semicolon in the table. In general, a non-terminating construction builds intervals (a_n, b_n) that exclude some leading terms of the sequence, and each interval excludes at least two more leading terms than the preceding interval. This leads to the following lemma: For a non-terminating construction, there is a function g(n) such that for all n ≥ 1, g(n) ≥ 2n and x₁, …, x_g(n) ∉ (a_n, b_n). Since n < 2n, this lemma implies Cantor's statement that x_n does not belong to (a_n, b_n).

Proof of lemma

The proof uses mathematical induction. It starts with the construction finding the first two terms x_j and x_k that belong to (a, b), setting a₁ to the smaller of these terms, and setting b₁ to the larger. Let g(1) = k. Then g(1) ≥ 2 and x₁, …, x_g(1) ∉ (a₁, b₁) since each of these x_i either equals a₁ or b₁ or does not belong to the larger interval (a, b).

Assume the inductive hypothesis that there is a g(n) ≥ 2n and x₁, …, x_g(n) ∉  a_n, b_n). The construction then finds the first two terms x_j and x_k that belong to (a_n, b_n), sets a_n + 1 to the smaller of these terms, and sets b_n + 1 to the larger. Let g(n + 1) = k. Then g(n + 1) ≥ g(n) + 2 ≥ 2n + 2 = 2(n + 1) and x₁, …, x_g(n + 1) ∉ (a_n + 1, b_n + 1) since each of these x_i either equals a_n + 1 or b_n + 1 or does not belong to the larger interval (a_n, b_n).

Notes:

1. In our example, g(1) = 2. There are cases where g(1) > 2. For example, if the construction is applied to the sequence of rational numbers in (0, 3) having the same ordering as our example, then the interval (0, 1) excludes ⁠1/1⁠, ⁠2/1⁠, ⁠3/2⁠, and ⁠5/2⁠, so g(1) = 6.
2. For an example where g(n) = 2n for all n: apply the construction to any sequence that produces a non-terminating construction on an interval [a, b]. This produces the intervals (a_n, b_n). Applying the construction to the sequence a₁, b₁, a₂, b₂, … and the interval [a, b] produces the same intervals as before, but this time the only additional terms that (a_n, b_n) excludes are its two endpoints. So g(n) = 2n.
3. This lemma and note 2 can be extended to terminating constructions. If a construction terminates at (a_N, b_N), then g(n) is defined only for n ≤ N.

Generating an irrational using Cantor's construction

Interval	Rational numbers outside interval	Interval (decimal)
$\left(\;{\frac {1}{3}},\;\;\!{\frac {1}{2}}\;\right)$	$\;{\frac {1}{2}},\;\;{\frac {1}{3}};\;\;\;\;\,{\frac {2}{3}},{\frac {1}{4}},{\frac {3}{4}},{\frac {1}{5}},\;\;\;\;\;\,{\frac {3}{5}},{\frac {4}{5}},{\frac {1}{6}},{\frac {5}{6}},{\frac {1}{7}},{\frac {2}{7}}$	$\left(0.3333\dots ,\;0.5000\dots \right)$
$\left(\;{\frac {2}{5}},\;\;\!{\frac {3}{7}}\;\right)$	$\;{\frac {2}{5}},\;\;{\frac {3}{7}};\;\;\;\;\,{\frac {4}{7}},\;\dots ,\;{\frac {1}{12}},\;\;\;\;{\frac {7}{12}},\;\dots ,\;{\frac {6}{17}}$	$\left(0.4000\dots ,\;0.4285\dots \right)$
$\left({\frac {7}{17}},{\frac {5}{12}}\right)$	${\frac {5}{12}},{\frac {7}{17}};\;\;\;\,{\frac {8}{17}},\;\!\dots ,\;\!{\frac {11}{29}},\;\;\;\;{\frac {13}{29}},\;\dots ,\;{\frac {16}{41}}$	$\left(0.4117\dots ,\;0.4166\dots \right)$
$\left({\frac {12}{29}},{\frac {17}{41}}\right)$	${\frac {12}{29}},{\frac {17}{41}};\;\;\;\,{\frac {18}{41}},\;\!\dots ,\;\!{\frac {27}{70}},\;\;\;\;{\frac {31}{70}},\;\dots ,\;{\frac {40}{99}}$	$\left(0.4137\dots ,\;0.4146\dots \right)$
$\left({\frac {41}{99}},{\frac {29}{70}}\right)$	${\frac {29}{70}},{\frac {41}{99}};\;\;\;\,{\frac {43}{99}},\dots ,{\frac {69}{169}},\;\;{\frac {71}{169}},\,\dots ,{\frac {98}{239}}$	$\left(0.4141\dots ,\;0.4142\dots \right)$

The irrational number constructed by the table is √2 − 1.

Proof

The proof uses Farey sequences and continued fractions. The Farey sequence $F_{n}$ is the increasing sequence of completely reduced fractions whose denominators are ≤ n. If ${\tfrac {a}{b}}$ and ${\tfrac {c}{d}}$ are adjacent in a Farey sequence, the lowest denominator fraction between them is their mediant ${\tfrac {a+c}{b+d}}.$ This mediant is adjacent to both ${\tfrac {a}{b}}$ and ${\tfrac {c}{d}}$ in the Farey sequence $F_{b+d}.$

Cantor's construction produces mediants because we sequenced rational numbers by increasing denominator. The first interval in the table is $({\tfrac {1}{3}},{\tfrac {1}{2}})$. Since ${\tfrac {1}{3}}$ and ${\tfrac {1}{2}}$ are adjacent in $F_{3},$ their mediant ${\tfrac {2}{5}}$ is the first rational in the sequence between ${\tfrac {1}{3}}$ and ${\tfrac {1}{2}}$. Since ${\tfrac {2}{5}}$ is adjacent to both ${\tfrac {1}{3}}$ and ${\tfrac {1}{2}}$ in $F_{5},$ the next fraction is ${\tfrac {3}{7}}$, the mediant of ${\tfrac {2}{5}}$ and ${\tfrac {1}{2}}.$ Since we use mediants, we have: ${\tfrac {1}{3}}<{\tfrac {2}{5}}<{\tfrac {3}{7}}<{\tfrac {1}{2}}.$ So the second interval is $({\tfrac {2}{5}},{\tfrac {3}{7}}).$

We will prove that the endpoints of the intervals converge to the continued fraction $[0,2,2,\dots ].\,$ This continued fraction is the limit of its convergents:

${\frac {p_{n}}{q_{n}}}=[0,2,\dots 2](n\;2{\text{'s}}).\;$

The $p_{n}$ and $q_{n}$ sequences satisfy the equations:

$p_{0}=0\;\;\;\;\;\;\;p_{1}=1\;\;\;\;\;\;\;p_{n+1}=2p_{n}+p_{n-1}{\text{ for }}n\geq 1$

$q_{0}=1\;\;\;\;\;\;\;q_{1}=2\;\;\;\;\;\;\;q_{n+1}=2q_{n}+q_{n-1}{\text{ for }}n\geq 1$

First, we prove by induction that for odd n the n-th interval in the table is:

$\left({\frac {p_{n}+p_{n-1}}{q_{n}+q_{n-1}}},{\frac {p_{n}}{q_{n}}}\right)\!.$

For even n, the endpoints are reversed.

This is true for the first interval since:

$\left({\frac {p_{1}+p_{0}}{q_{1}+q_{0}}},{\frac {p_{1}}{q_{1}}}\right)=\left({\frac {1}{3}},{\frac {1}{2}}\right)\!.$

Assume that the inductive hypothesis is true for the k-th interval. If k is odd, this interval is:

$\left({\frac {p_{k}+p_{k-1}}{q_{k}+q_{k-1}}},{\frac {p_{k}}{q_{k}}}\right)\!.$

The mediant of its endpoints: ${\frac {2p_{k}+p_{k-1}}{2q_{k}+q_{k-1}}}={\frac {p_{k+1}}{q_{k+1}}}$ is the first fraction between these endpoints.

The second fraction is $\;{\frac {p_{k+1}+p_{k}}{p_{k+1}+q_{k}}},\;$ the mediant of $\;{\frac {p_{k+1}}{q_{k+1}}}\;$ and $\;{\frac {p_{k}}{q_{k}}}.$

Since we use mediants, we have:

${\frac {p_{k}+p_{k-1}}{q_{k}+q_{k-1}}}<{\frac {p_{k+1}}{q_{k+1}}}<{\frac {p_{k+1}+p_{k}}{p_{k+1}+q_{k}}}<{\frac {p_{k}}{q_{k}}}.$

So the (k + 1)-st interval is:

$\left({\frac {p_{k+1}}{q_{k+1}}},{\frac {p_{k+1}+p_{k}}{p_{k+1}+q_{k}}}\right)\!.$

Note that ${\frac {p_{k+1}}{q_{k+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 ${\frac {p_{2n}}{q_{2n}}},$ their limit equals $\lim _{n\to \infty }{\frac {p_{n}}{q_{n}}}.$ The right endpoints have the same limit because they are decreasing and every other endpoint is ${\frac {p_{2n-1}}{q_{2n-1}}}.$ As mentioned above, this limit is the continued fraction $[0,2,2,\dots ]$, which equals √2 − 1.

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 (a_{n1, n2, …, nν}) where n₁, n₂,…, 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 a proof by contradiction that the set of real numbers is uncountable. Cantor starts by assuming the real numbers can be written as a sequence. Then he applies a construction to this sequence to produce a real not in the sequence, thus contradicting his original assumption. The letters of December 2 and 7 lead to 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)  ω₁, ω₂, … , ω_n, …

I can determine, in every given interval [α, β], a number η that is not included in (I).

This is the second theorem in Cantor's article. It comes from realizing that his construction can be applied to any sequence, not just to sequences that supposedly enumerate the real numbers. So Cantor had a choice between two proofs that demonstrate the existence of transcendental numbers: one proof is constructive and the other is not. We now compare the proofs assuming that we have a sequence consisting of all the real algebraic numbers.

The constructive proof applies Cantor's construction to this sequence and the interval [a, b] to produce a transcendental number in this interval.

The non-constructive proof uses two proofs-by-contradiction:

1. Assume that the real numbers in [a, b] can be written as a sequence. Applying Cantor's construction to this sequence and [a, b] produces a real number in [a, b] that does not belong to the sequence. This contradicts the original assumption. Therefore, the real numbers in [a, b] cannot be written as a sequence.
2. Assume that there are no transcendental numbers in [a, b]. This implies that all the real numbers in [a, b] are algebraic, which implies that they form a subsequence of the sequence of all real algebraic numbers. This contradicts what was proved in 1. Thus the assumption that there are no transcendental numbers in [a, b] is false. Therefore, there are transcendental numbers in this interval.

Cantor chose to publish the constructive proof, which not only constructs a transcendental number but also is shorter and avoids two proofs-by-contradiction.

The disagreement about Cantor's proof

Cantor never published the non-constructive reasoning found in his December 2 and 7 letters—it only appears in his correspondence, which was published in 1937. By that time, other mathematicians had rediscovered his reasoning and used it to produce the non-constructive proof discussed above. As early as 1921, this non-constructive proof was attributed to Cantor and criticized as a pure existence proof. In that year, Oskar Perron stated: "… Cantor's proof for the existence of transcendental numbers has, along with its simplicity and elegance, the great disadvantage that it is only an existence proof; it does not enable us to actually specify even a single transcendental number."

Some mathematicians have attempted to correct this misunderstanding of Cantor's work. In 1930, the set theorist Abraham Fraenkel stated that Cantor's method is "… a method that incidentally, contrary to a widespread interpretation, is fundamentally constructive and not merely existential." In 1977, Irving Kaplansky wrote: "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)."

Cantor's diagonal argument has often replaced his 1874 construction in expositions of his proof. It is as constructive as his earlier construction, and it produces a more efficient computer program. Using the diagonal argument, a computer program has been written that computes the digits of a transcendental number in polynomial time. The program that uses his 1874 construction requires at least sub-exponential time.

The disagreement about Cantor's proof occurs because two groups of mathematicians are talking about different proofs: the constructive one that Cantor published and the non-constructive one that was rediscovered. The view that Cantor's proof is non-constructive appears in some books that were very successful as measured by the length of time new editions or reprints appeared—for example: Eric Temple Bell's Men of Mathematics (1937; still being reprinted), Godfrey Hardy and E. M. Wright's An Introduction to the Theory of Numbers (1938; 2008 6th edition), Garrett Birkhoff and Saunders Mac Lane's A Survey of Modern Algebra (1941; 1997 5th edition), and Michael Spivak's Calculus (1967; 2008 4th edition). None of these books mention that there is a constructive proof. On the other hand, the quotations above from Fraenkel and Kaplansky show that they knew both proofs. This disagreement about Cantor's proof shows no sign of being resolved: since 2014, at least two books appeared stating that Cantor's proof is constructive, and at least four appeared stating that his proof does not construct any (or a single) transcendental.

The non-constructive proof may appear in some books because it is a simple example of the power of non-constructive reasoning. In The Problems of Mathematics, Ian Stewart dramatizes the power of this reasoning:

… 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.

However, Steward does not tell the full story about non-constructive proofs. Most mathematicians prefer constructive proofs over non-constructive ones. Also, some mathematicians have used non-constructive arguments to discover new proofs or theorems, but then find and publish constructive proofs. Cantor did this and so did Kurt Gödel. Cantor proved that the sets of algebraic numbers and real numbers have different properties (one is countable, the other is not), and hence there are real numbers that are not algebraic. Gödel proved that, in a sufficiently strong theory, the sets of provable statements and true statements have different properties (provability is expressible in the theory, but truth is not), and hence there are true statements that are not provable. Like Cantor, Gödel used a key idea from his non-constructive proof (in this case, the liar paradox) to produce the constructive proof that he published.

Asserting that Cantor proof gave a non-constructive proof can lead to erroneous statements about the history of mathematics. In their influential textbook A Survey of Modern Algebra, Birkhoff and Mac Lane state: "Cantor's argument for this result [Not every real number is algebraic] was at first rejected by many mathematicians, since it did not exhibit any transcendental number." Birkhoff and Mac Lane are talking about the non-constructive proof that Cantor never published. There was no reason to reject Cantor's published proof, which is constructive. Even Leopold Kronecker, who had strict views on what is acceptable in mathematics and who could have delayed publication of Cantor's article, did not delay it.

Cantor's article, which introduced countability, and countable unions of sets (introduced in 1878), led to interesting results in mathematics. In 1874, Karl Weierstrass used the countability of the real algebraic numbers to build a function that is continuous everywhere but differentiable only at transcendental numbers. In 1885, Axel Harnack proved that a countable set can be covered by countable union of intervals whose total length is arbitrarily small. In the 1890s, Harnack's result and countable unions led Émile Borel to his concept of measure zero and then to his theory of measure. Borel measure helped to lead Henri Lebesgue to his theory of measure and integration. Lebesgue was also aided by René Baire's hierarchy of functions, which uses the transfinite ordinal numbers that Cantor introduced in 1883.

Why Cantor's article emphasizes the countability of the real algebraic numbers

Historians of mathematics have discovered several interesting facts about Cantor's article "On a Property of the Collection of All Real Algebraic Numbers":

1. Cantor's uncountability theorem was left out of the submitted article. He added it during proofreading.
2. The article's title refers to set of real algebraic numbers. The main topic in Cantor's correspondence was the set of real numbers.
3. Cantor restricted his first theorem to the set of real algebraic numbers. The proof he was using demonstrates the countability of the set of all algebraic numbers.
4. The proof of Cantor's second theorem does not state why some limits exist. The proof he was using does.

To explain these facts, historians have pointed to the influence of Cantor's former professors, Weierstrass and Kronecker. Cantor sent his results to Weierstrass on December 22, 1874. Weierstrass was first amazed by the concept of countability, but then found the countability of the set of real algebraic numbers useful. Cantor did not want to publish yet, but Weierstrass felt that he must publish at least his results concerning the algebraic numbers.

Cantor wanted his article to include his uncountability theorem, but followed Weierstrass' advice to leave it out. Weierstrass also said that he could add it during proofreading, which he did. It appears in a remark at the end of the article's introduction. Without the uncountability theorem, the article's most significant result is the theorem stating that the set of real algebraic numbers is countable. The article's title refers to this theorem.

Weierstrass probably convinced Cantor of the importance of applying his "ideas at first to a single case (such as that of the real algebraic numbers) …" This lead Cantor to restrict his first theorem to real algebraic numbers. This restriction produces a pedagogically simpler article: since Cantor constructs transcendental numbers by using his second theorem (which works with sequences of real numbers), the article is simpler if his first theorem produces a real sequence rather than a complex sequence.

From his correspondence, it appears that Cantor only discussed his article with Weierstrass. However, he wrote to Dedekind: "The restriction which I have imposed on the published version of my investigations is caused in part by local circumstances …" Cantor biographer Joseph Dauben believes that "local circumstances" refers to Kronecker who was a member of the editorial board of Crelle's Journal. Kronecker had delayed publication of a 1870 article by Eduard Heine, and Cantor would send his article to this journal.

Kronecker's influence appears in Cantor's proof of his second theorem. Cantor used Dedekind's version of the proof except he did not state why the limits a_∞ =  lim_n → ∞ a_n and b_∞ =  lim_n → ∞ b_n exist. 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 …". Dedekind's principle of continuity (which is equivalent to the completeness of the real numbers) is the reason why these limits exist. However, this principle comes from Dedekind's construction of the real numbers, a construction that Kronecker did not accept.

Kronecker's influence also appears in Weierstrass' advising Cantor to leave out his uncountability theorem. In his history of set theory, José Ferreirós states: "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."

Dedekind's contributions to Cantor's article

Dedekind's previous work enabled him to understand and contribute quickly to Cantor's work. Since 1856, Dedekind had developed theories involving infinitely many infinite sets—for example: ideals, which he used in algebraic number theory, and Dedekind cuts, which he used to construct the real numbers.

Richard Dedekind

One of Dedekind's contributions has already been mentioned: in his article, Cantor gives Dedekind's proof of his second theorem. In his December 7th letter, Cantor sent Dedekind a complicated proof (involving infinitely many sequences) that the interval [a, b] is uncountable. Dedekind replied with a simpler proof. Before Dedekind's letter arrived, Cantor wrote that he had found a simpler proof that did not use infinitely many sequences. So Cantor had two proofs, but preferred Dedekind's.

Dedekind's second contribution concerns the theorem that the set of real algebraic numbers is countable. In his November 29th letter, Cantor states that he can prove the countability of the set of positive rational numbers and sets of the form (a_{n1, n2, …, nν}) where n₁, n₂, …, n_ν, and ν are positive integers. Cantor's second result uses indexed numbers: each set consists of the ranges of n_ν functions where each function maps k positive integer arguments to the real numbers for some k ≤ n_ν. His second result implies his first: let ν = 2, a_n1 = n₁, and a_n1, n2 = ⁠n₁/n₂⁠. The functions can be quite general—for example, a_{n1, n2, n3, n4, n5} = (⁠n₁/n₂⁠)^⁠1/n₃⁠ + tan(⁠n₄/n₅⁠).

Dedekind quickly replied, sending Cantor a proof of the theorem: the set of algebraic numbers is countable. To obtain this result from Cantor's theorem about indexed numbers, Dedekind removed Cantor's restriction to positive integer indices and realized that the ordering produced can order the polynomials. Since each polynomial has finitely many roots, the algebraic numbers can be ordered. Because of his extensive work with algebraic numbers, it was natural for Dedekind to see that Cantor's work can be extended to these numbers.

In his reply to Dedekind's letter, Cantor does not claim to have proved Dedekind's result. He states: "Your proof that (n) [the set of positive integers] can be correlated one-to-one with the field of all algebraic numbers is approximately the same as the way I prove my contention in the last letter. I take n₁² + n₁² + ··· + n_ν² ... and order the elements accordingly." Cantor's ordering cannot handle indices that are 0.

Cantor is usually given credit for the theorem on the countability of the algebraic numbers, but the mathematical historian Ferreirós calls it "Dedekind's theorem." The question of whether it should be called Cantor's theorem, Dedekind's theorem, or the Cantor-Dedekind theorem belongs to mathematicians and historians of mathematics.

In his private notes, 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 its proof appeared almost word-for-word in Cantor's paper in Crelle, vol. 77, even with the use of the artificial expression height [Höhe] …)." Cantor did not ask permission to use this material.

Cantor did thank Dedekind privately for his help: "… your comments (which I value highly) and your manner of putting some of the points were of great assistance to me." However, in his article, he did not acknowledge Dedekind's help. In previous articles, he had acknowledged help received from Kronecker, Weierstrass, Heine, and Hermann Schwarz. Cantor's handling of Dedekind's contributions adversely affected his relationship with Dedekind—for example, Dedekind stopped replying to his letters and did not resume the correspondence until October 1876. Their correspondence ended up following "a pattern of short but intense outbursts, followed by long periods without contact."

See also

• Cantor's theorem

Bibliography

• Bell, Eric Temple (1937), Men of Mathematics, New York: Simon & Schuster, ISBN 0-671-62818-6.
• Birkhoff, Garrett; Mac Lane, Saunders (1941), A Survey of Modern Algebra, New York: Macmillan, ISBN 978-1-56881-068-3.
• 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.
• Cantor, Georg (1878), "Ein Beitrag zur Mannigfaltigkeitslehre", Journal für die Reine und Angewandte Mathematik, 84: 242–248.
• Cantor, Georg (1883), "Ueber unendliche, lineare Punktmannichfaltigkeiten. 5.", Mathematische Annalen, 21: 569–591. Published separately as: Grundlagen einer allgemeinen Mannigfaltigkeitslehre.
• Cantor, Georg (1883a), "Sur une propriété du système de tous les nombres réels algébriques", Acta Mathematica, 2: 305–310. French translation of Cantor 1874 that was reviewed and corrected by Cantor.
• Cantor, Georg (1883b), "Une contribution à la théorie des ensembles", Acta Mathematica, 2: 311–328. French translation of Cantor 1878 that was reviewed and corrected by Cantor.
• Chowdhary, K. R. (2015), Fundamentals of Discrete Mathematical Structures (3rd ed.), Delhi: PHI Learning, ISBN 978-81-203-5074-8.
• Dasgupta, Abhijit (2014), Set Theory: With an Introduction to Real Point Sets, Springer, ISBN 978-1-4614-8853-8.
• Dauben, Joseph (1979), Georg Cantor: His Mathematics and Philosophy of the Infinite, Boston: Harvard University Press, ISBN 0-674-34871-0.
• Dedekind, Richard (1901), Essays on the Theory of Numbers (PDF), Chicago: Open Court Publishing Company. (Reprinted by Dover Publications, 1963.)
• Dieudonné, Jean (1992), Mathematics — The Music of Reason, Springer, ISBN 3-540-53346-X.
• Dugac, Pierre (1976), Richard Dedekind et les Fondements des Mathématiques, Paris: Vrin.
• Edwards, Harold M. (1989), "Kronecker's Views on the Foundations of Mathematics", in Rowe, David E.; McCleary, John (eds.) (eds.), The History of Modern Mathematics, Volume 1, Academic Press, pp. 67–77, ISBN 0-12-599662-4 {{citation}}: |editor-first2= has generic name (help).
• Edwards, Harold M. (2005), Essays in Constructive Mathematics, Springer, ISBN 0-387-21978-1.
• Ewald, William B. (ed.) (1996), From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2, Oxford University Press, ISBN 0-19-850536-1 {{citation}}: |first= has generic name (help).
• Ferreirós, José (1993), "On the relations between Georg Cantor and Richard Dedekind", Historia Mathematica, 20: 343–363, doi:10.1006/hmat.1993.1030.
• 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.
• Gray, Robert (1994), "Georg Cantor and Transcendental Numbers", American Mathematical Monthly, 101: 819–832, doi:10.2307/2975129.
• Jarvis, Frazer (2014), Algebraic Number Theory, Springer, ISBN 978-3-319-07544-0.
• Hardy, Godfrey; Wright, E. M. (1938), An Introduction to the Theory of Numbers, Clarendon Press, ISBN 978-0-19-921985-8.
• Hawkins, Thomas (1970), Lebesgue's Theory of Integration, University of Wisconsin Press, ISBN 0-299-05550-7.
• Kaplansky, Irving (1977), Set Theory and Metric Spaces (2nd ed.), New York: Chelsea, ISBN 0-8284-0298-1.
• LeVeque, William J. (2002) [1956], 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 {{citation}}: |first2= has generic name (help).
• Perron, Oskar (1921), Irrationalzahlen, Berlin: de Gruyter.
• Sheppard, Barnaby (2014), The Logic of Infinity, Cambridge University Press, ISBN 978-1-107-67866-8.
• Spivak, Michael (1967), Calculus (PDF), W. A. Benjamin, ISBN 978-0914098911.
• Stewart, Ian (1987), The Problems of Mathematics, Oxford University Press, ISBN 0-19-286148-4.
• Stewart, Ian (2015), Galois Theory (4th ed.), CRC Press, ISBN 978-1-4822-4582-0.
• Stewart, Ian; Tall, David (2015), The Foundations of Mathematics (2nd ed.), Oxford University Press, ISBN 978-0-19-870644-1.
• Weisstein, Eric W., ed. (2003), "Continued Fraction", CRC Concise Encyclopedia of Mathematics, Chapman & Hall/CRC, ISBN 1-58488-347-2.

Category:History of mathematics Category:Set theory Category:Real analysis Category:Georg Cantor