User:RJGray/Sandbox5

Georg Cantor, c. 1870.

Georg Cantor published his first set theory article in 1874, and it contains the first theorems of transfinite set theory, which studies infinite sets and their properties. One of these theorems is "Cantor's revolutionary discovery" that the set of all real numbers is uncountably, rather than countably, infinite. This theorem is proved using Cantor's first uncountability proof, which differs from the more familiar proof using his diagonal argument. The title of the article, "On a Property of the Collection of All Real Algebraic Numbers" ("Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen"), refers to its first theorem: the set of real algebraic numbers is countable.

Cantor's article also contains a proof of the existence of transcendental numbers. As early as 1930, mathematicians have disagreed on whether this proof is constructive or non-constructive. Books as recent as 2014 and 2015 indicate that this disagreement has not been resolved. Since Cantor's proof either constructs transcendental numbers or does not, an analysis of his article can determine whether his proof is constructive or non-constructive. Cantor's correspondence with Richard Dedekind shows the development of his ideas and reveals that he had a choice between two proofs, one that uses the uncountability of the real numbers and one that does not.

Historians of mathematics have examined Cantor's article and the circumstances in which it was written. For example, they have discovered that Cantor was advised to leave out his uncountability theorem in the article he submitted; he added it during proofreading. They have traced this and other facts about the article to the influence of Karl Weierstrass and Leopold Kronecker. Historians have also studied Dedekind's contributions to the article, including his contributions to the theorem on the countability of the real algebraic numbers. In addition, they have looked at the article's legacy, which includes the impact that the uncountability theorem and the concept of countability have had on mathematics.

The article

Cantor's article is short, less than four and a half pages. It begins with a discussion of the real algebraic numbers and a statement of his first theorem: The set of real algebraic numbers can be put into one-to-one correspondence with the set of positive integers. Cantor restates this theorem in terms more familiar to mathematicians of his time: The set 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. The theorem states: Given any sequence of real numbers x₁, x₂, x₃, … and any interval [a, b], there is a number in [a, b] that is not contained in the given sequence. Hence, there are infinitely many such numbers.

The first part of this theorem implies the "Hence" part. For example, let [0, 1] be the interval, and consider its pairwise disjoint subintervals [0, 1/2], [3/4, 7/8], [15/16, 31/32], …. Applying the first part of the theorem to each subinterval produces infinitely many numbers in [0, 1] that are not contained in the given sequence.

Cantor observes that combining his two theorems yields a new proof of Liouville's theorem that every interval [a, b] contains infinitely many transcendental numbers.

Cantor 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 state that this interval is an infinite set of larger cardinality than the set of positive integers. Cardinality is defined in Cantor's next article, which was published in 1878.

Proof of Cantor's uncountability theorem

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 only states his uncountability theorem. He does not use it in any proofs.

The proofs

First theorem

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

To prove that the set of real algebraic numbers is countable, define 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. Order the polynomials by their height, and order 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 went a step further and produced a sequence in which each real algebraic number appears just once. He did this by only using polynomials that are irreducible over the integers. The table below contains the beginning of Cantor's enumeration.

Cantor's enumeration of the real algebraic numbers
Real algebraic number	Polynomial	Height of polynomial
x1 = 0	x	1
x2 = −1	x + 1	2
x3 = 1	x − 1	2
x4 = −2	x + 2	3
x5 = −1/2	2x + 1	3
x6 = 1/2	2x − 1	3
x7 = 2	x − 2	3
x8 = −3	x + 3	4
x9 = −1 − √5/2	x2 + x − 1	4
x10 = −√2	x2 − 2	4
x11 = −1/√2	2x2 − 1	4
x12 = 1 − √5/2	x2 − x − 1	4
x13 = −1/3	3x + 1	4
x14 = 1/3	3x − 1	4
x15 = −1 + √5/2	x2 + x − 1	4
x16 = 1/√2	2x2 − 1	4
x17 = √2	x2 − 2	4
x18 = 1 + √5/2	x2 − x − 1	4
x19 = 3	x − 3	4

Second theorem

Only the first part of Cantor's second theorem needs to be proved. It states: Given any sequence of real numbers x₁, x₂, x₃, … and any interval [a, b], there is 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). Denote 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₁). Denote the smaller by a₂ and the larger by b₂. Continuing this procedure generates a sequence of intervals (a₁, b₁), (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 that the sequence a₁, a₂, a₃, … is increasing and the sequence b₁, b₂, b₃, … is decreasing.

Either the number of intervals generated is finite or infinite. If finite, let (a_N, b_N) be the last interval. If infinite, take the limits a_∞ = lim_n → ∞ a_n and b_∞ = lim_n → ∞ b_n. Since a_n < b_n for all n, either a_∞ = b_∞ or a_∞ < b_∞. Thus, there are three cases to consider:

Case 1: Last interval (a_N, b_N)

Case 2: a_∞ = b_∞

Case 3: a_∞ < b_∞

• Case 1: There is a last interval (a_N, b_N). Since at most one x_n can be in this interval, every y in this interval except x_n (if it exists) is not contained in the given sequence.
• Case 2: a_∞ = b_∞. Then a_∞ is not contained in the given sequence since for all n : a_∞ belongs to the interval (a_n, b_n), but as Cantor observes, x_n does not. This observation is implied by the following proof.

Proof that for all n :  (an, bn) excludes x1, … , x2n

Proof by induction. Basis step: If a1 = xj, b1 = xk, and E1 = max(j, k), then (a1, b1) excludes x1, … , xE1. Also, E1 ≥ 2 since the interval (a1, b1) excludes its two endpoints. Inductive step: Assume that (an, bn) excludes x1, … , xEn and En ≥ 2n. If an+1 = xj, bn+1 = xk, and En+1 = max(j, k), then (an+1, bn+1) excludes x1, … , xEn+1. Also, En+1 ≥ En + 2 ≥ 2n + 2 = 2(n + 1) since the interval (an+1, bn+1) excludes the numbers that (an, bn) excludes plus the two endpoints an+1 and bn+1. Therefore, for all n : (an, bn) excludes x1, … , x2n.

• Case 3: a_∞ < b_∞. Then 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.

Cantor's proofs are constructive and have been used to write a computer program that generates the digits of a transcendental number. This program applies Cantor's 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.

Dense sequences

Cantor observes that a_∞ = b_∞ when his construction is applied to the sequence of real algebraic numbers. This sequence is dense in [a, b], which means that every open subinterval (y, z) of [a, b] contains a term of the sequence. Cantor's observation follows from the lemma: If the sequence is dense in [a, b], then a_∞ = b_∞.

We prove the contrapositive: If a_∞ ≠ b_∞, then the sequence is not dense in [a, b]. If a_∞ ≠ b_∞, then case 2 does not occur. Hence, there are two cases to consider:

• Case 1: There is a last interval (a_N, b_N), so at most one x_n can be in this interval. 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.
• Case 3: a_∞ < b_∞. The interval (a_∞, b_∞) contains no terms of the sequence.

In both cases, an open subinterval of [a, b] has been found that contains no terms of the sequence, which implies that the sequence is not dense in [a, b]. Therefore, the contrapositive of the lemma is true, which implies that the lemma is true.

Example of Cantor's construction

An example illustrates how Cantor's construction works. Consider the sequence: 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, … This sequence is obtained by ordering the rational numbers in (0, 1) by increasing denominators, ordering those with the same denominator by increasing numerators, and omitting reducible fractions. Since this sequence is dense in [0, 1], the construction generates infinitely many intervals. The table below shows the first five steps of the construction. The table's first column contains the intervals (a_n, b_n). The second column lists the terms visited during the search for the first two terms in (a_n, b_n). These two terms are in red.

Generating a number using Cantor's construction

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

Since the sequence contains all the rational numbers in (0, 1), the construction generates an irrational number, which turns out to be √2 − 1.

Proof that the number generated is √2 − 1

The proof uses Farey sequences and continued fractions. The Farey sequence $F_{n}$ is the increasing sequence of completely reduced fractions whose denominators are $\leq n.$ If ${\frac {a}{b}}$ and ${\frac {c}{d}}$ are adjacent in a Farey sequence, the lowest denominator fraction between them is their mediant ${\frac {a+c}{b+d}}.$ This mediant is adjacent to both ${\frac {a}{b}}$ and ${\frac {c}{d}}$ in the Farey sequence $F_{b+d}.$ Cantor's construction produces mediants because the rational numbers were sequenced by increasing denominator. The first interval in the table is $({\frac {1}{3}},{\frac {1}{2}}).$ Since ${\frac {1}{3}}$ and ${\frac {1}{2}}$ are adjacent in $F_{3},$ their mediant ${\frac {2}{5}}$ is the first fraction in the sequence between ${\frac {1}{3}}$ and ${\frac {1}{2}}.$ Hence, ${\frac {1}{3}}<{\frac {2}{5}}<{\frac {1}{2}}.$ In this inequality, ${\frac {1}{2}}$ has the smallest denominator, so the second fraction is the mediant of ${\frac {2}{5}}$ and ${\frac {1}{2}},$ which equals ${\frac {3}{7}}.$ This implies: ${\frac {1}{3}}<{\frac {2}{5}}<{\frac {3}{7}}<{\frac {1}{2}}.$ Therefore, the next interval is $({\frac {2}{5}},{\frac {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)\!,$ and for even n, the interval's endpoints are reversed: $\left({\frac {p_{n}}{q_{n}}},{\frac {p_{n}+p_{n-1}}{q_{n}+q_{n-1}}}\right)\!.$ 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 in the sequence between these endpoints. Hence, ${\frac {p_{k}+p_{k-1}}{q_{k}+q_{k-1}}}<{\frac {p_{k+1}}{q_{k+1}}}<{\frac {p_{k}}{q_{k}}}.$ In this inequality, ${\frac {p_{k}}{q_{k}}}$ has the smallest denominator, so the second fraction is the mediant of ${\frac {p_{k+1}}{q_{k+1}}}$ and ${\frac {p_{k}}{q_{k}}},$ which equals ${\frac {p_{k+1}+p_{k}}{p_{k+1}+q_{k}}}.$ This implies: ${\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}}}.$ Therefore, 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)\!.$ This is the desired interval; ${\frac {p_{k+1}}{q_{k+1}}}$ is the left endpoint because k + 1 is even. Thus, the inductive hypothesis is true for the (k + 1)-st interval. For even k, the proof is similar. This completes the inductive proof. Since the right endpoints of the intervals are decreasing and every other endpoint is ${\frac {p_{2n-1}}{q_{2n-1}}},$ their limit equals $\lim _{n\to \infty }{\frac {p_{n}}{q_{n}}}.$ The left endpoints have the same limit because they are increasing and every other endpoint is ${\frac {p_{2n}}{q_{2n}}}.$ As mentioned above, this limit is the continued fraction $[0;2,2,\dots ],$ which equals ${\sqrt {2}}-1.$

The development of Cantor's ideas

The development leading to Cantor's article appears in the correspondence between Cantor and 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 individual 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 responded 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 number not in the sequence, thus contradicting his 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 allowed 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, but 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. The proof by contradiction used to prove the uncountability theorem (see Proof of Cantor's uncountability theorem).
2. The proof by contradiction used to prove the existence of transcendental numbers from the countability of the real algebraic numbers and the uncountability of real numbers. Cantor's December 2nd letter mentions but does not contain this existence proof. To prove it: Assume that there are no transcendental numbers in [a, b]. Then 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 Cantor's uncountability theorem. Thus, the assumption that there are no transcendental numbers in [a, b] is false. Therefore, there is a transcendental number in [a, b].

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

The non-constructive proof from Cantor's correspondence is simpler than the one above because it works with all the real numbers rather than the interval [a, b]. For example, this eliminates the subsequence step in the second proof by contradiction.

"Disagreement" on constructivity

The article currently says:

Books as recent as 2014 and 2015 indicate that this disagreement has not been resolved.

There is a cite, which quotes Sheppard:

Cantor's proof of the existence of transcendental numbers is not just an existence proof. It can, at least in principle, be used to construct an explicit transcendental number.

and Stewart:

Meanwhile Georg Cantor, in 1874, had produced a revolutionary proof of the existence of transcendental numbers, without actually constructing any.

But these two statements are not actually in conflict, and we have no evidence that Sheppard and Stewart actually "disagree" in the slightest. Sheppard correctly notes that Cantor's method can be applied to find a particular transcendental; Stewart correctly notes that Cantor did not in fact do that.

I'm not sure how to fix this, but I don't think it can stand as is. There is no modern "disagreement" on the question, not phrased this way. (I'm not sure whether intuitionists consider the proof constructive, because it might use excluded middle (?) but that's a bit of a different issue.) --Trovatore (talk) 07:05, 13 September 2018 (UTC)

"Disagreement" on constructivity

The article currently says:

Books as recent as 2014 and 2015 indicate that this disagreement has not been resolved.

There is a cite, which quotes Sheppard:

Cantor's proof of the existence of transcendental numbers is not just an existence proof. It can, at least in principle, be used to construct an explicit transcendental number.

and Stewart:

Meanwhile Georg Cantor, in 1874, had produced a revolutionary proof of the existence of transcendental numbers, without actually constructing any.

But these two statements are not actually in conflict, and we have no evidence that Sheppard and Stewart actually "disagree" in the slightest. Sheppard correctly notes that Cantor's method can be applied to find a particular transcendental; Stewart correctly notes that Cantor did not in fact do that.

I'm not sure how to fix this, but I don't think it can stand as is. There is no modern "disagreement" on the question, not phrased this way. (I'm not sure whether intuitionists consider the proof constructive, because it might use excluded middle (?) but that's a bit of a different issue.) --Trovatore (talk) 07:05, 13 September 2018 (UTC)

Thank you for your feedback. I agree with you that "Sheppard correctly notes that Cantor's method can be applied to find a particular transcendental." However, I disagree that "Stewart correctly notes that Cantor did not in fact do that."

To understand what Cantor did, I'll quote from the article Georg Cantor and Transcendental Numbers . From the bottom of page 819 to page 820, it states:

Cantor begins his article by defining the algebraic reals and introducing the notation: (ω) for the collection of all algebraic reals, and (ν) for the collection of all natural numbers. Next he states the property mentioned in the article's title; namely, that the collection (ω) can be placed into a one-to-one correspondence with the collection (ν), or equivalently:

... the collection (ω) can be thought of in the form of an infinite sequence: (2.) ω₁, ω₂, ..., ω_η, ... which is ordered by a law and in which all individuals of (ω) appear, each of them being located at a fixed place in (2.) that is given by the accompanying index.

Cantor states that this property of the algebraic reals will be proved in Section 1 of his article, and then he outlines the rest of the article:

To give an application of this property of the collection of all real algebraic numbers, I supplement Section I with Section 2, in which I show that when given an arbitrary sequence of real numbers of the form (2.), one can determine [Note: By this Cantor means that he can "construct"] in any given interval (α ··· β), numbers that are not contained in (2.). Combining the contents of both sections thus gives a new proof of the theorem first demonstrated by Liouville: In every given interval (α ··· β), there are infinitely many transcendentals, that is, numbers that are not algebraic reals. Furthermore, the theorem in Section 2 presents itself as the reason why collections of real numbers forming a so-called continuum (such as, all the real numbers which are ≥ 0 and ≤ 1), cannot correspond one-to-one with the collection (v); thus I have found the clear difference between a so-called continuum and a collection like the totality of all real algebraic numbers.

To appreciate the structure of Cantor's article, we number his theorems and corollaries:

Theorem 1. The collection of all algebraic reals can be written as an infinite sequence.

Theorem 2. Given any sequence of real numbers and any interval [α, β], one can determine a number η in [α, β] that does not belong to the sequence. Hence, one can determine infinitely many such numbers η in [α, β]. (We have used the modern notation [α, β] rather than Cantor's notation (α ··· β).)

Corollary 1. In any given interval [α, β], there are infinitely many transcendental reals.

Corollary 2. The real numbers cannot be written as an infinite sequence. That is, they cannot be put into a one-to-one correspondence with the natural numbers.

Observe the flow of reasoning: Cantor's second theorem holds for any sequence of reals. By applying his theorem to the sequence of algebraic reals, Cantor obtains transcendentals. By applying it to any sequence that allegedly enumerates the reals, he obtains a contradiction—so no such enumerating sequence can exist. Kac and Ulam reason differently [20, p. 12-13]. They prove Theorem 1 and then Corollary 2. By combining these results, they obtain a non-constructive proof of the existence of transcendentals.

So Cantor does provide a method of constructing transcendental numbers. By the way, Kac and Ulam present the same non-constructive proof that Stewart uses.

Also, in a footnote on page 821 of the article I just quoted from, it tells you where to find a proof of Cantor's theorem 2 that meets the demands of constructive mathematicians, which I believe is also acceptable to intuitionists. With this proof, they find Cantor's approach constructive. I believe that they object to Cantor's assumption that a bounded increasing or decreasing sequence of reals has a limit.

Response to DYK

Thank you for your feedback. I wish to respond to your statement: "Indeed, I'm a little confused about how it passed the GA review, because though it's well written and I have no reasons to doubt its accuracy, the second half of "The development of Cantor's ideas" is completely unreferenced."

In the GA Review, the issue of references for derivations and examples did come up with respect to the section "The Proofs". The issue is the same as the one you are raising for the second half of "The development of Cantor's ideas" (in this half of the section, I am comparing the derivations in two different proofs). Here is how I handled the issue during the GA Review:

Concerning "The proofs": My approach was to stay within the guidelines of WP:Scientific citation guidelines#Examples, derivations and restatements whose first paragraph states:

"Wikipedia is neither a textbook nor a journal. Nonetheless, in mathematics and the mathematical sciences, it is frequently helpful to quote theorems, include simple derivations, and provide illustrative examples. For reasons of notation, clarity, consistency, or simplicity it is often necessary to state things in a slightly different way than they are stated in the references, to provide a different derivation, or to provide an example. This is standard practice in journals, and does not make any claim of novelty.[1] In Wikipedia articles this does not constitute original research and is perfectly permissible – in fact, encouraged – provided that a reader who reads and understands the references can easily see how the material in the Wikipedia article can be inferred. Furthermore, copying extensively from a source with only minor modifications is not normally permitted by copyright law, unless the source has a free license."

After receiving my response, the reviewer dropped this issue from his list of issues. --RJGray (talk) 15:30, 13 September 2018 (UTC)

NBG work

Von Neumann's 1929 axiom system

John von Neumann

In 1929, von Neumann published an article containing the axioms that would lead to NBG. This article was motivated by his concern about the consistency of the axiom of limitation of size. He stated that this axiom "does a lot, actually too much." Besides implying the axioms of separation and replacement, and the well-ordering theorem, it also implies that any class whose cardinality is less than that of V is a set. Von Neumann thought that this last implication went beyond Cantorian set theory and concluded: "We must therefore discuss whether its [the axiom's] consistency is not even more problematic than an axiomatization of set theory that does not go beyond the necessary Cantorian framework."

Von Neumann started his consistency investigation by introducing his 1929 axiom system, which contains all the axioms of his 1925 axiom system except the axiom of limitation of size. He replaced this axiom with two of its consequences, the axiom of replacement and a choice axiom. Von Neumann's choice axiom states: "Every relation R has a subclass that is a function with the same domain as R."

Let S be von Neumann's 1929 axiom system. Von Neumann introduced the axiom system S + Regularity (which consists of S and the axiom of regularity) to demonstrate that his 1925 system is consistent relative to S. He proved:

1. If S is consistent, then S + Regularity is consistent.
2. S + Regularity implies the axiom of limitation of size. Since this is the only axiom of his 1925 axiom system that S + Regularity does not have, S + Regularity implies all the axioms of his 1925 system.

These results imply: If S is consistent, then von Neumann's 1925 axiom system is consistent. Proof: If S is consistent, then S + Regularity is consistent (result 1). Using proof by contradiction, assume that the 1925 axiom system is inconsistent, or equivalently: the 1925 axiom system implies a contradiction. Since S + Regularity implies the axioms of the 1925 system (result 2), S + Regularity also implies a contradiction. However, this contradicts the consistency of S + Regularity. Therefore, if S is consistent, then von Neumann's 1925 axiom system is consistent.

Since S is his 1929 axiom system, von Neumann's 1925 axiom system is consistent relative to his 1929 axiom system, which is closer to Cantorian set theory. The major differences between Cantorian set theory and the 1929 axiom system are classes and von Neumann's choice axiom. The axiom system S + Regularity was modified by Bernays and Gödel to produce the equivalent NBG axiom system.

Bernays' axiom system

Paul Bernays

In 1929, Paul Bernays started modifying von Neumann's new axiom system by taking classes and sets as primitives. He published his work in a series of articles appearing from 1937 to 1954. Bernays stated that:

The purpose of modifying the von Neumann system is to remain nearer to the structure of the original Zermelo system and to utilize at the same time some of the set-theoretic concepts of the Schröder logic and of Principia Mathematica which have become familiar to logicians. As will be seen, a considerable simplification results from this arrangement.

Bernays handled sets and classes in a two-sorted logic and introduced two membership primitives: one for membership in sets and one for membership in classes. With these primitives, he rewrote and simplified von Neumann's 1929 axioms. Bernays also included the axiom of regularity in his axiom system.

Gödel's axiom system (NBG)

Kurt Gödel

In 1931, Bernays sent a letter containing his set theory to Kurt Gödel. Gödel simplified Bernays' theory by making every set a class, which allowed him to use just one sort and one membership primitive. He also weakened some of Bernays' axioms and replaced von Neumann's choice axiom with the equivalent axiom of global choice. Gödel used his axioms in his 1940 monograph on the relative consistency of global choice and the generalized continuum hypothesis.

Several reasons have been given for Gödel choosing NBG for his monograph:

• Gödel gave a mathematical reason—NBG's global choice produces a stronger consistency theorem: "This stronger form of the axiom [of choice], if consistent with the other axioms, implies, of course, that a weaker form is also consistent."
• Robert Solovay conjectured: "My guess is that he [Gödel] wished to avoid a discussion of the technicalities involved in developing the rudiments of model theory within axiomatic set theory."
• Kenneth Kunen gave a reason for Gödel avoiding this discussion: "There is also a much more combinatorial approach to L [the constructible universe], developed by ... [Gödel in his 1940 monograph] in an attempt to explain his work to non-logicians. ... This approach has the merit of removing all vestiges of logic from the treatment of L."
• Charles Parsons provided a philosophical reason for Gödel's choice: "This view [that 'property of set' is a primitive of set theory] may be reflected in Gödel's choice of a theory with class variables as the framework for ... [his monograph]."

Gödel's achievement together with the details of his presentation led to the prominence that NBG would enjoy for the next two decades. In 1963, Paul Cohen proved his independence proofs for ZF with the help of some tools that Gödel had developed for his relative consistency proofs for NBG. Later, ZFC became more popular than NBG. This was caused by several factors, including the extra work required to handle forcing in NBG, Cohen's 1966 presentation of forcing, which used ZF, and the proof that NBG is a conservative extension of ZFC.

Bernays' axiom system

Paul Bernays, 1949

Paul Bernays

Paul Bernays, 1949

In 1929, Paul Bernays started modifying von Neumann's new axiom system by taking classes and sets as primitives. He published his work in a series of articles appearing from 1937 to 1954. By using sets, Bernays was following the tradition established by Cantor, Richard Dedekind, and Zermelo. His classes followed the tradition of Boolean algebra since they permit the operation of complement as well as union and intersection. Bernays handled sets and classes in a two-sorted logic and introduced two membership primitives: one for membership in sets and one for membership in classes. With these primitives, Bernays rewrote and simplified von Neumann's 1929 axioms.