View source for Georg Cantor's first set theory article

[[File:Georg Cantor3.jpg|thumb|Georg Cantor, c. 1870.]]

[[Biography:Georg Cantor|Georg Cantor]] published his first set theory article in 1874, and it contains the first theorems of transfinite [[Set theory|set theory]], which studies [[Infinite set|infinite set]]s and their properties.<ref>{{harvnb|Ferreirós|2007|p=171}}.</ref> One of these theorems is "Cantor's revolutionary discovery" that the [[Set (mathematics)|set]] of all [[Real number|real number]]s is [[Uncountable set|uncountably]], rather than [[Countable set|countably]], infinite.<ref>{{harvnb|Dauben|1993|p=4}}.</ref> This theorem is proved using '''Cantor's first uncountability proof''', which differs from the more familiar proof using his [[Cantor's diagonal argument|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 number|transcendental number]]s. As early as 1930, mathematicians have disagreed on whether this proof is [[Constructive proof|constructive or non-constructive]].<ref>"[Cantor's method is] a method that incidentally, contrary to a widespread interpretation, is fundamentally constructive and not merely existential." ({{harvnb|Fraenkel|1930|p=237}}; English translation: {{harvnb|Gray|1994|p=823}}.)</ref> Books as recent as 2014 and 2015 indicate that this disagreement has not been resolved.<ref>"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." ({{harvnb|Sheppard|2014|p=131}}.) "Meanwhile Georg Cantor, in 1874, had produced a revolutionary proof of the existence of transcendental numbers, without actually constructing any." ({{harvnb|Stewart|2015|p=285}}.)</ref> 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.<ref>{{harvnb|Gray|1994|pp=819&ndash;821}}.</ref> Cantor's correspondence with [[Biography:Richard Dedekind|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 [[Galley proof|proofreading]]. They have traced this and other facts about the article to the influence of [[Biography:Karl Weierstrass|Karl Weierstrass]] and [[Biography:Leopold Kronecker|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.<ref>In letter to Dedekind dated December 25, 1873, Cantor states that he has written and submitted "a short paper" titled ''On a Property of the Collection of All Real Algebraic Numbers''. {{harvnb|Noether|Cavaillès|1937|p=17}}; English translation: {{harvnb|Ewald|1996|p=847}}.</ref> 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.<ref name=Cantor1874>{{harvnb|Cantor|1874}}. English translation: {{harvnb|Ewald|1996|pp=840&ndash;843}}.</ref> 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|sequence]] in which each number appears only once.<ref>{{harvnb|Gray|1994|p=828}}.</ref>

Cantor's second theorem works with a closed interval [''a'',&nbsp;''b''], which is the set of real numbers ≥&nbsp;''a'' and ≤&nbsp;''b''. The theorem states: Given any sequence of real numbers ''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>, … and any interval [''a'',&nbsp;''b''], there is a number in [''a'',&nbsp;''b''] that is not contained in the given sequence. Hence, there are infinitely many such numbers.<ref name=Ewald840_841>{{harvnb|Cantor|1874|p=259}}. English translation: {{harvnb|Ewald|1996|pp=840&ndash;841}}.</ref>

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

Cantor observes that combining his two theorems yields a new proof of [[Liouville number|Liouville's theorem]] that every interval [''a'',&nbsp;''b''] contains infinitely many [[Transcendental number|transcendental number]]s.<ref name=Ewald840_841 />

Cantor then remarks that his second theorem is:
{{quote|the reason why collections of real numbers forming a so-called continuum (such as, all real numbers which are ≥&nbsp;0 and ≤&nbsp;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.''<ref>{{harvnb|Cantor|1874|p=259}}. English translation: {{harvnb|Gray|1994|p=820}}.</ref>}}

This remark contains Cantor's uncountability theorem, which only states that an interval [''a'',&nbsp;''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|cardinality]] than the set of positive integers. Cardinality is defined in Cantor's next article, which was published in 1878.<ref>{{harvnb|Cantor|1878|p=242}}.</ref>

{{Anchor|Proof of Cantor's uncountability theorem}}
{| class="wikitable collapsible collapsed"
! style="background: f5f5f5;" |'''Proof of Cantor's uncountability theorem'''
|- style="text-align: left; vertical-align: top; background: white" 
| style="padding-left: 1em; padding-right: 1em" | Cantor does not explicitly prove his uncountability theorem, which follows easily from his second theorem. To prove it, we use [[Proof by contradiction|proof by contradiction]]. Assume that the interval [''a'',&nbsp;''b''] can be put into one-to-one correspondence with the set of positive integers, or equivalently: The real numbers in [''a'',&nbsp;''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'',&nbsp;''b''] produces a real number in [''a'',&nbsp;''b''] that does not belong to the sequence. This contradicts the original assumption, and proves the uncountability theorem.<ref>Our proof is nearly the same as the proof of Corollary 2 in {{harvnb|Gray|1994|p=820}}. The only difference is that we specify the contradiction.</ref>
|}

Cantor only states his uncountability theorem. He does not use it in any proofs.<ref name=Cantor1874 />

==The proofs==

===First theorem===
[[File:Algebraicszoom.png|thumb|Algebraic numbers on the [[Complex plane|complex plane]] colored by polynomial degree. (red&nbsp;=&nbsp;1, green&nbsp;=&nbsp;2, blue&nbsp;=&nbsp;3, yellow&nbsp;=&nbsp;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|polynomial]] of [[Degree of a polynomial|degree]] ''n'' with integer [[Coefficient|coefficient]]s as: ''n''&nbsp;−&nbsp;1&nbsp;+&nbsp;|''a''<sub>0</sub>|&nbsp;+&nbsp;|''a''<sub>1</sub>|&nbsp;+&nbsp;…&nbsp;+&nbsp;|''a''<sub>''n''</sub>|, where ''a''<sub>0</sub>, ''a''<sub>1</sub>, …, ''a''<sub>''n''</sub> 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 polynomial|irreducible]] over the integers.<ref>{{harvnb|Cantor|1874|pp=259&ndash;260}}. English translation: {{harvnb|Ewald|1996|p=841}}.</ref> The table below contains the beginning of Cantor's enumeration.

{| class="wikitable collapsible collapsed" style="border:1px solid black; margin:auto;"
! colspan="3"| '''Cantor's enumeration of the real algebraic numbers'''
|- style="text-align: center;"
| Real algebraic<br />number || <br />Polynomial || Height of<br />polynomial
|-
| style="padding-left: 4em;" | ''x''<sub>1</sub> = 0 || align="right" | ''x''{{spaces|6}} || align="center" | 1
|-
| style="padding-left: 4em;" | ''x''<sub>2</sub> = −1 || align="right" | ''x'' + 1{{spaces|6}} || align="center" | 2
|-
| style="padding-left: 4em;" | ''x''<sub>3</sub> = 1 || align="right" | ''x'' − 1{{spaces|6}} || align="center" | 2
|-
| style="padding-left: 4em;" | ''x''<sub>4</sub> = −2 || align="right" | ''x'' + 2{{spaces|6}} || align="center" | 3
|-
| style="padding-left: 4em;" | ''x''<sub>5</sub> = −{{sfrac|1|2}} || align="right" | 2''x'' + 1{{spaces|6}} || align="center" | 3
|-
| style="padding-left: 4em;" | ''x''<sub>6</sub> = {{sfrac|1|2}} || align="right" | 2''x'' − 1{{spaces|6}} || align="center" | 3
|-
| style="padding-left: 4em;" | ''x''<sub>7</sub> = 2 || align="right" | ''x'' − 2{{spaces|6}} || align="center" | 3
|-
| style="padding-left: 4em;" | ''x''<sub>8</sub> = −3 || align="right" | ''x'' + 3{{spaces|6}} || align="center" | 4
|-
| style="padding-left: 4em;" | ''x''<sub>9</sub> = {{sfrac|−1 − {{radic|5}}|2}} || align="right" | ''x''<sup>2</sup> + ''x'' − 1{{spaces|6}} || align="center" | 4
|-
| style="padding-left: 3.54em;" | ''x''<sub>10</sub> = −{{radic|2}} || align="right" | ''x''<sup>2</sup> − 2{{spaces|6}} || align="center" | 4
|-
| style="padding-left: 3.54em;" | ''x''<sub>11</sub> = −{{sfrac|1|{{radic|2}}}} || align="right" | 2''x''<sup>2</sup> − 1{{spaces|6}} || align="center" | 4
|-
| style="padding-left: 3.54em;" | ''x''<sub>12</sub> = {{sfrac|1 − {{radic|5}}|2}} || align="right" | ''x''<sup>2</sup> − ''x'' − 1{{spaces|6}} || align="center" | 4
|-
| style="padding-left: 3.54em;" | ''x''<sub>13</sub> = −{{sfrac|1|3}} || align="right" | 3''x'' + 1{{spaces|6}} || align="center" | 4
|-
| style="padding-left: 3.54em;" | ''x''<sub>14</sub> = {{sfrac|1|3}} || align="right" | 3''x'' − 1{{spaces|6}} || align="center" | 4
|-
| style="padding-left: 3.54em; white-space: nowrap;"| ''x''<sub>15</sub> = {{sfrac|−1 + {{radic|5}}|2}}{{spaces|3}} || align="right" style="padding-left: 1.25em; white-space: nowrap;"| ''x''<sup>2</sup> + ''x'' − 1{{spaces|6}} || align="center" | 4
|-
| style="padding-left: 3.54em;" | ''x''<sub>16</sub> = {{sfrac|1|{{radic|2}}}} || align="right" | 2''x''<sup>2</sup> − 1{{spaces|6}} || align="center" | 4
|-
| style="padding-left: 3.54em;" | ''x''<sub>17</sub> = {{radic|2}} || align="right" | ''x''<sup>2</sup> − 2{{spaces|6}} || align="center" | 4
|-
| style="padding-left: 3.54em;" | ''x''<sub>18</sub> = {{sfrac|1 + {{radic|5}}|2}} || align="right" | ''x''<sup>2</sup> − ''x'' − 1{{spaces|6}} || align="center" | 4
|-
| style="padding-left: 3.58em;" | ''x''<sub>19</sub> = 3 || align="right" | ''x'' − 3{{spaces|6}} || align="center" | 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''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>,&nbsp;… and any interval [''a'',&nbsp;''b''], there is a number in [''a'',&nbsp;''b''] that is not contained in the given sequence. We simplify Cantor's proof by using open intervals. The open interval (''a'',&nbsp;''b'') is the set of real numbers >&nbsp;''a'' and <&nbsp;''b''.

To find a number in [''a'',&nbsp;''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'',&nbsp;''b''). Denote the smaller of these two numbers by ''a''<sub>1</sub> and the larger by ''b''<sub>1</sub>.  Similarly, find the first two numbers of the given sequence that are in (''a''<sub>1</sub>,&nbsp;''b''<sub>1</sub>). Denote the smaller by ''a''<sub>2</sub> and the larger by ''b''<sub>2</sub>. Continuing this procedure generates a sequence of intervals (''a''<sub>1</sub>,&nbsp;''b''<sub>1</sub>), (''a''<sub>2</sub>,&nbsp;''b''<sub>2</sub>), (''a''<sub>3</sub>,&nbsp;''b''<sub>3</sub>),&nbsp;… such that each interval in the sequence contains all succeeding intervals—that is, it generates a sequence of [[Nested intervals|nested intervals]]. This implies that the sequence ''a''<sub>1</sub>, ''a''<sub>2</sub>, ''a''<sub>3</sub>,&nbsp;… is increasing and the sequence ''b''<sub>1</sub>, ''b''<sub>2</sub>, ''b''<sub>3</sub>,&nbsp;… is decreasing.<ref>{{harvnb|Cantor|1874|pp=260&ndash;261}}. English translation: {{harvnb|Ewald|1996|pp=841&ndash;842}}.</ref>

Either the number of intervals generated is finite or infinite. If finite, let (''a''<sub>''N''</sub>,&nbsp;''b''<sub>''N''</sub>) be the last interval. If infinite, take the [[Limit of a sequence|limit]]s ''a''<sub>∞</sub>&nbsp;=&nbsp;lim<sub>''n''&nbsp;→&nbsp;∞</sub>&nbsp;''a''<sub>''n''</sub> and ''b''<sub>∞</sub>&nbsp;=&nbsp;lim<sub>''n''&nbsp;→&nbsp;∞</sub>&nbsp;''b''<sub>''n''</sub>. Since ''a''<sub>''n''</sub>&nbsp;<&nbsp;''b''<sub>''n''</sub> for all ''n'', either ''a''<sub>∞</sub>&nbsp;=&nbsp;''b''<sub>∞</sub> or ''a''<sub>∞</sub>&nbsp;<&nbsp;''b''<sub>∞</sub>. Thus, there are three cases to consider:

[[File:Cantor's first uncountability proof Case 1 svg.svg|thumb|350px|Case 1: Last interval (''a''<sub>''N''</sub>, ''b''<sub>''N''</sub>)]]
[[File:Cantor's first uncountability proof Case 2 svg.svg|thumb|350px|Case 2: ''a''<sub>∞</sub> = ''b''<sub>∞</sub>]]
[[File:Cantor's first uncountability proof Case 3 svg.svg|thumb|350px|Case 3: ''a''<sub>∞</sub> < ''b''<sub>∞</sub>]]

{{plainlist|indent=1}}
* Case 1: There is a last interval (''a''<sub>''N''</sub>,&nbsp;''b''<sub>''N''</sub>). Since at most one ''x''<sub>''n''</sub> can be in this interval, every ''y'' in this interval except ''x''<sub>''n''</sub> (if it exists) is not contained in the given sequence. 
* Case 2: ''a''<sub>∞</sub>&nbsp;=&nbsp;''b''<sub>∞</sub>. Then ''a''<sub>∞</sub> is not contained in the given sequence since for all ''n''{{space|hair}}: ''a''<sub>∞</sub> belongs to the interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>), but as Cantor observes, ''x''<sub>''n''</sub> does not. This observation is implied by the following proof.
{| class="wikitable collapsible collapsed"
! style="background: f5f5f5;" |'''Proof that for all&nbsp;''n''{{space|hair}}:{{space|hair}} (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) excludes ''x''<sub>1</sub>,&nbsp;…&nbsp;,&nbsp;''x''<sub>2''n''</sub>'''
|- style="text-align: left; vertical-align: top; background: white" 
| style="padding-left: 1em; padding-right: 1em" | Proof by [[Mathematical induction|induction]]. Basis step: If ''a''<sub>1</sub>&nbsp;=&nbsp;''x''<sub>''j''</sub>, ''b''<sub>1</sub>&nbsp;=&nbsp;''x''<sub>''k''</sub>, and ''E''<sub>1</sub>&nbsp;=&nbsp;max(''j'',&nbsp;''k''), then (''a''<sub>1</sub>,&nbsp;''b''<sub>1</sub>) excludes ''x''<sub>1</sub>,&nbsp;…&nbsp;,&nbsp;''x''<sub>''E''<sub>1</sub></sub>. Also, ''E''<sub>1</sub>&nbsp;≥&nbsp;2 since the interval (''a''<sub>1</sub>,&nbsp;''b''<sub>1</sub>) excludes its two endpoints. Inductive step: Assume that (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) excludes ''x''<sub>1</sub>,&nbsp;…&nbsp;,&nbsp;''x''<sub>''E''<sub>''n''</sub></sub> and ''E''<sub>''n''</sub>&nbsp;≥&nbsp;2''n''. If ''a''<sub>''n''+1</sub>&nbsp;=&nbsp;''x''<sub>''j''</sub>, ''b''<sub>''n''+1</sub>&nbsp;=&nbsp;''x''<sub>''k''</sub>, and ''E''<sub>''n''+1</sub>&nbsp;=&nbsp;max(''j'',&nbsp;''k''), then (''a''<sub>''n''+1</sub>,&nbsp;''b''<sub>''n''+1</sub>) excludes ''x''<sub>1</sub>,&nbsp;…&nbsp;,&nbsp;''x''<sub>''E''<sub>''n''+1</sub></sub>. Also, ''E''<sub>''n''+1</sub>&nbsp;≥&nbsp;''E''<sub>''n''</sub>&nbsp;+&nbsp;2&nbsp;≥ 2''n''&nbsp;+&nbsp;2&nbsp;= 2(''n''&nbsp;+&nbsp;1) since the interval (''a''<sub>''n''+1</sub>,&nbsp;''b''<sub>''n''+1</sub>) excludes the numbers that (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) excludes plus the two endpoints ''a''<sub>''n''+1</sub> and ''b''<sub>''n''+1</sub>. Therefore, for all ''n''{{space|hair}}: (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) excludes ''x''<sub>1</sub>,&nbsp;…&nbsp;,&nbsp;''x''<sub>2''n''</sub>''.
|}
* Case 3: ''a''<sub>∞</sub>&nbsp;<&nbsp;''b''<sub>∞</sub>. Then every ''y'' in [''a''<sub>∞</sub>,&nbsp;''b''<sub>∞</sub>] is not contained in the given sequence since for all ''n''{{space|hair}}: ''y'' belongs to (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) but ''x''<sub>''n''</sub> does not.<ref name=Ewald842>{{harvnb|Cantor|1874|p=261}}. English translation: {{harvnb|Ewald|1996|p=842}}.</ref>

The proof is complete since, in all cases, at least one real number in [''a'',&nbsp;''b''] has been found that is not contained in the given sequence.{{efn-ua|The difference between our proof and Cantor's is that he generates the sequence of closed intervals [''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>]. To find ''a''<sub>''n''&nbsp;+&nbsp;1</sub> and ''b''<sub>''n''&nbsp;+&nbsp;1</sub>, he must also use the open intervals (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). By generating a sequence of open intervals, we avoid working with the closed intervals.}}

Cantor's proofs are constructive and have been used to write a [[Computer program|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.<ref>{{harvnb|Gray|1994|p=822}}.</ref>

===Dense sequences===
Cantor observes that ''a''<sub>∞</sub>&nbsp;=&nbsp;''b''<sub>∞</sub> when his construction is applied to the sequence of real algebraic numbers.<ref name=Ewald842 /> This sequence is [[Dense set|dense]] in [''a'',&nbsp;''b''], which means that every open subinterval (''y'',&nbsp;''z'') of [''a'',&nbsp;''b''] contains a term of the sequence. Cantor's observation follows from the [[Lemma (mathematics)|lemma]]: If the sequence is dense in [''a'',&nbsp;''b''], then ''a''<sub>∞</sub>&nbsp;=&nbsp;''b''<sub>∞</sub>.

We prove the contrapositive: If ''a''<sub>∞</sub>&nbsp;≠&nbsp;''b''<sub>∞</sub>, then the sequence is not dense in [''a'',&nbsp;''b'']. If ''a''<sub>∞</sub> ≠&nbsp;''b''<sub>∞</sub>, then case 2 does not occur. Hence, there are two cases to consider:

{{plainlist|indent=1}}
* Case 1: There is a last interval (''a''<sub>''N''</sub>,&nbsp;''b''<sub>''N''</sub>), so at most one ''x''<sub>''n''</sub> can be in this interval. If there is such an ''x''<sub>''n''</sub>, then the interval (''a''<sub>''N''</sub>,&nbsp;''x''<sub>''n''</sub>) contains no terms of the sequence. Otherwise, the interval (''a''<sub>''N''</sub>,&nbsp;''b''<sub>''N''</sub>) contains no terms of the sequence. 
* Case 3: ''a''<sub>∞</sub>&nbsp;<&nbsp;''b''<sub>∞</sub>. The interval (''a''<sub>∞</sub>,&nbsp;''b''<sub>∞</sub>) contains no terms of the sequence. 

In both cases, an open subinterval of [''a'',&nbsp;''b''] has been found that contains no terms of the sequence, which implies that the sequence is not dense in [''a'',&nbsp;''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: {{sfrac|1|2}}, {{sfrac|1|3}}, {{sfrac|2|3}}, {{sfrac|1|4}}, {{sfrac|3|4}}, {{sfrac|1|5}}, {{sfrac|2|5}}, {{sfrac|3|5}}, {{sfrac|4|5}}, … This sequence is obtained by ordering the [[Rational number|rational number]]s in (0,&nbsp;1) by increasing denominators, ordering those with the same denominator by increasing numerators, and omitting reducible fractions.{{efn-ua|This example is nearly the same as an exercise in {{harvnb|Gray|1994|p=823}}. The only difference is that this sequence contains only [[Irreducible fraction|irreducible fraction]]s, while Gray's sequence includes the reducible fractions of the initial interval.}} 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''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). The second column lists the terms visited during the search for the first two terms in (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). These two terms are in red.

{| class="wikitable" style="border:1px solid black; margin:auto;"
|+'''Generating a number using Cantor's construction'''
! '''Interval !! Finding the next interval !! Interval (decimal)'''
|-
|<math>\left(\;\frac{1}{3}, \;\;\!\frac{1}{2}\;\right)</math> 
|| <math>\;\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}} </math>
|| <math>\left(0.3333\dots,\; 0.5000\dots\right)</math> 
|-
|<math>\left(\;\frac{2}{5}, \;\;\!\frac{3}{7}\;\right)</math>  
|| <math>\;\frac{4}{7}, \;\dots,\; \frac{1}{12}, {\color{red}\frac{5}{12},}\;\! \frac{7}{12}, \;\dots,\; \frac{6}{17}, {\color{red}\frac{7}{17}}</math>
|| <math>\left(0.4000\dots,\; 0.4285\dots\right)</math>
|-
|<math>\left(\frac{7}{17}, \frac{5}{12}\right)</math>  
|| <math>\frac{8}{17}, \;\!\dots,\;\! \frac{11}{29}, {\color{red}\frac{12}{29},}\;\! \frac{13}{29}, \;\dots,\; \frac{16}{41}, {\color{red}\frac{17}{41}}</math>
|| <math>\left(0.4117\dots,\; 0.4166\dots\right)</math>
|-
|<math>\left(\frac{12}{29}, \frac{17}{41}\right)</math> 
|| <math>\frac{18}{41}, \;\!\dots,\;\! \frac{27}{70}, {\color{red}\frac{29}{70},}\;\! \frac{31}{70}, \;\dots,\; \frac{40}{99}, {\color{red}\frac{41}{99}}</math>
|| <math>\left(0.4137\dots,\; 0.4146\dots\right)</math> 
|-
|<math>\left(\frac{41}{99}, \frac{29}{70}\right)</math>  
|| <math>\frac{43}{99}, \dots, \frac{69}{169}, {\color{red}\frac{70}{169},}\;\! \frac{71}{169}, \,\dots, \frac{98}{239}, {\color{red}\frac{99}{239}}</math>
|| <math>\left(0.4141\dots,\; 0.4142\dots\right)</math>
|}

Since the sequence contains all the rational numbers in (0,&nbsp;1), the construction generates an [[Irrational number|irrational number]], which turns out to be {{sqrt|2}}&nbsp;&minus;&nbsp;1.

{| class="wikitable collapsible collapsed"
! style="background: f5f5f5;" |'''Proof that the number generated is {{sqrt|2}} &minus; 1'''
|- style="text-align: left; vertical-align: top; background: white" 
| style="padding-left: 1em; padding-right: 1em" |The proof uses [[Farey sequence]]s and continued fractions. The Farey sequence <math>F_n</math> is the increasing sequence of completely reduced fractions whose denominators are <math>\leq n.</math> If <math>\frac{a}{b}</math> and <math>\frac{c}{d}</math> are adjacent in a Farey sequence, the lowest denominator fraction between them is their [[Mediant (mathematics)|mediant]] <math>\frac{a+c}{b+d}.</math> This mediant is adjacent to both <math>\frac{a}{b}</math> and <math>\frac{c}{d}</math> in the Farey sequence <math>F_{b+d}.</math><ref>{{harvnb|LeVeque|1956|pp=154&ndash;155}}.</ref>

Cantor's construction produces mediants because the rational numbers were sequenced by increasing denominator. The first interval in the table is <math>(\frac{1}{3}, \frac{1}{2}).</math> Since <math>\frac{1}{3}</math> and <math>\frac{1}{2}</math> are adjacent in <math>F_3,</math> their mediant <math>\frac{2}{5}</math> is the first fraction in the sequence between <math>\frac{1}{3}</math> and <math>\frac{1}{2}.</math> Hence, <math>\frac{1}{3} < \frac{2}{5} < \frac{1}{2}.</math> In this inequality, <math>\frac{1}{2}</math> has the smallest denominator, so the second fraction is the mediant of <math>\frac{2}{5}</math> and <math>\frac{1}{2},</math> which equals <math>\frac{3}{7}.</math> This implies: <math>\frac{1}{3} < \frac{2}{5} < \frac{3}{7} < \frac{1}{2}.</math> Therefore, the next interval is <math>(\frac{2}{5}, \frac{3}{7}).</math>

We will prove that the endpoints of the intervals converge to the continued fraction <math>[0; 2, 2, \dots].</math> This continued fraction is the limit of its convergents:
:<math>\frac{p_n}{q_n} = [0; 2, \dots, 2]\;\;(n\;2\text{'s}).</math>

The <math>p_n</math> and <math>q_n</math> sequences satisfy the equations:<ref>{{harvnb|LeVeque|1956|p=174}}.</ref>
:<math>p_0 = 0\;\;\;\;\;\;\;p_1 = 1\;\;\;\;\;\;\;p_{n+1} = 2p_n + p_{n-1} \text{ for } n \geq 1</math>
:<math>q_0 = 1\;\;\;\;\;\;\;q_1 = 2\;\;\;\;\;\;\;q_{n+1} = 2q_n + q_{n-1} \text{ for } n \geq 1</math>

First, we prove by induction that for odd ''n'', the ''n''-th interval in the table is: 
:<math>\left(\frac{p_n + p_{n-1}}{q_n + q_{n-1}}, \frac{p_n}{q_n}\right)\!,</math> 
and for even ''n'', the interval's endpoints are reversed: <math>\left(\frac{p_n}{q_n}, \frac{p_n + p_{n-1}}{q_n + q_{n-1}}\right)\!.</math>

This is true for the first interval since:
:<math>\left(\frac{p_1 + p_0}{q_1 + q_0}, \frac{p_1}{q_1}\right) = \left(\frac{1}{3}, \frac{1}{2}\right)\!.</math>

Assume that the inductive hypothesis is true for the ''k''-th interval. If ''k'' is odd, this interval is:
:<math>\left(\frac{p_k + p_{k-1}}{q_k + q_{k-1}}, \frac{p_k}{q_k}\right)\!.</math>

The mediant of its endpoints <math>\frac{2p_k + p_{k-1}}{2q_k + q_{k-1}} = \frac{p_{k+1}}{q_{k+1}}</math> is the first fraction in the sequence between these endpoints.<br /><br />

Hence, <math>\frac{p_k + p_{k-1}}{q_k + q_{k-1}} < \frac{p_{k+1}}{q_{k+1}} < \frac{p_k}{q_k}.</math><br /><br />

In this inequality, <math>\frac{p_k}{q_k}</math> has the smallest denominator, so the second fraction is the mediant of <math>\frac{p_{k+1}}{q_{k+1}}</math> and <math>\frac{p_k}{q_k},</math> which equals <math>\frac{p_{k+1} + p_k}{p_{k+1} + q_k}.</math><br /><br />

This implies: <math>\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}.</math><br /><br />

Therefore, the (''k''&nbsp;+&nbsp;1)-st interval is <math>\left(\frac{p_{k+1}}{q_{k+1}}, \frac{p_{k+1} + p_k}{p_{k+1} + q_k}\right)\!.</math><br /><br />

This is the desired interval; <math>\frac{p_{k+1}}{q_{k+1}}</math> is the left endpoint because ''k''&nbsp;+&nbsp;1 is even. Thus, the inductive hypothesis is true for the (''k''&nbsp;+&nbsp;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 <math>\frac{p_{2n-1}}{q_{2n-1}},</math> their limit equals
<math>\lim_{n \to \infty} \frac{p_n}{q_n}.</math> The left endpoints have the same limit because they are increasing and every other endpoint is <math>\frac{p_{2n}}{q_{2n}}.</math> As mentioned above, this limit is the continued fraction <math>[0; 2, 2, \dots],</math> which equals <math>\sqrt{2}-1.</math><ref>{{harvnb|Weisstein|2003|p=541}}.</ref>
|}

==The development of Cantor's ideas==
The development leading to Cantor's article appears in the correspondence between Cantor and [[Biography:Richard Dedekind|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''<sub>''n''<sub>1</sub>,&nbsp;''n''<sub>2</sub>,&nbsp;.&nbsp;.&nbsp;.&nbsp;,&nbsp;''n''<sub>''ν''</sub></sub>) where ''n''<sub>1</sub>, ''n''<sub>2</sub>, .&nbsp;.&nbsp;. , ''n''<sub>''ν''</sub>, and ''ν'' are positive integers.<ref>{{harvnb|Noether|Cavaillès|1937|pp=12&ndash;13}}. English translation: {{harvnb|Gray|1994|p=827}}; {{harvnb|Ewald|1996|p=844}}.</ref>

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.<ref name=Noether18>{{harvnb|Noether|Cavaillès|1937|p=18}}. English translation: {{harvnb|Ewald|1996|p=848}}.</ref>

{{Anchor|Cantor's December 2nd letter}}
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 number|Liouville's theorem]] that there are transcendental numbers."<ref>{{harvnb|Noether|Cavaillès|1937|p=13}}. English translation: {{harvnb|Gray|1994|p=827}}.</ref>

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.<ref>{{harvnb|Noether|Cavaillès|1937|pp=14&ndash;15}}. English translation: {{harvnb|Ewald|1996|pp=845&ndash;846}}.</ref> 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:

{{quote|I show directly that if I start with a sequence<br />(I)&nbsp;&nbsp;&nbsp;&nbsp; ω<sub>1</sub>, ω<sub>2</sub>, … , ω<sub>''n''</sub>, …<br />I can determine, in ''every'' given interval [α,&nbsp;β], a number η that is not included in (I).<ref>{{harvnb|Noether|Cavaillès|1937|p=16}}. English translation: {{harvnb|Gray|1994|p=827}}.</ref>}}

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'',&nbsp;''b''] to produce a transcendental number in this interval.<ref name=Ewald840_841 />

The non-constructive proof uses two proofs by contradiction:
# The proof by contradiction used to prove the uncountability theorem (see Proof of Cantor's uncountability theorem).
# 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 this existence proof but does not contain it. Here is a proof: Assume that there are no transcendental numbers in [''a'',&nbsp;''b'']. Then all the numbers in [''a'',&nbsp;''b''] are algebraic. This implies that they form a [[Subsequence|subsequence]] of the sequence of all real algebraic numbers, which contradicts Cantor's uncountability theorem. Thus, the assumption that there are no transcendental numbers in [''a'',&nbsp;''b''] is false. Therefore, there is a transcendental number in [''a'',&nbsp;''b''].{{efn-ua|The beginning of our proof is derived from the proof below by restricting the numbers in this proof to the interval [''a'',&nbsp;''b'']. However, we derive the contradiction by using a subsequence because Cantor was using sequences in his 1873 work on countability.<br> '''Satz 68. Es gibt transzendente Zahlen.'''<br>Gäbe es nämlich keine transzendenten Zahlen, so wären alle Zahlen algebraisch, das Kontinuum also identisch mit der Menge aller algebraischen Zahlen. Das ist aber unmöglich, weil die Menge aller algebraischen Zahlen abzählbar ist, das Kontinuum aber nicht.<ref>{{harvnb|Perron|1921|p=162}}.</ref><br>'''''Translation:'' Theorem 68. There are transcendental numbers.'''<br> If there were no transcendental numbers, then all numbers would be algebraic. Hence, the [[Continuum (set theory)|continuum]] would be identical to the set of all algebraic numbers. However, this is impossible because the set of all algebraic numbers is countable, but the continuum is not.}}

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'',&nbsp;''b'']. This eliminates the subsequence step and all occurrences of [''a'',&nbsp;''b''] in the second proof by contradiction.

==The disagreement about Cantor's existence proof==
[[File:Oskar Perron.jpg|thumb|upright=0.93|Oskar Perron]]
The correspondence containing Cantor's non-constructive reasoning was published in 1937. By then, other mathematicians had rediscovered its non-constructive proof. As early as 1921, this proof was attributed to Cantor and criticized for not producing any transcendental numbers.<ref>{{harvnb|Gray|1994|pp=827&ndash;828}}.</ref>  In that year, [[Biography:Oskar Perron|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."<ref>{{harvnb|Perron|1921|p=162}}. English translation: {{harvnb|Gray|1994|p=828}}.</ref>

[[File:Adolf Abraham Halevi Fraenkel.jpg|thumb|upright=0.93|Abraham Fraenkel]]
Some mathematicians have attempted to correct this misunderstanding of Cantor's work. In 1930, the [[Set theory|set theorist]] [[Biography:Abraham Fraenkel|Abraham Fraenkel]] stated that Cantor's method is "… a method that incidentally, contrary to a widespread interpretation, is fundamentally constructive and not merely existential."<ref>{{harvnb|Fraenkel|1930|p=237}}. English translation: {{harvnb|Gray|1994|p=823}}.</ref> In 1972, [[Biography:Irving Kaplansky|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 [[Cantor's diagonal argument|diagonal procedure]] …, we get a perfectly definite transcendental number (it could be computed to any number of decimal places)."<ref>{{harvnb|Kaplansky|1972|p=25}}.</ref>

Cantor's diagonal argument has often replaced his 1874 construction in expositions of his proof. The diagonal argument is constructive and produces a more efficient computer program than his 1874 construction. Using it, a computer program has been written that computes the digits of a transcendental number in polynomial time. The program that uses Cantor's 1874 construction requires at least sub-exponential time.{{efn-ua|The program using the diagonal method produces <math>n</math> digits in [[Big O notation#Use in computer science|<math>{\color{Blue}O}(n^2 \log^2 n \log \log n)</math>]] steps, while the program using the 1874 method requires at least <math>O(2^{\sqrt[3]{n}})</math> steps to produce <math>n</math> digits. ({{harvnb|Gray|1994|pp=822&ndash;823}}.)}}

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 later rediscovered.  The opinion that Cantor's proof is non-constructive appears in some books that were quite successful as measured by the length of time new editions or reprints appeared—for example: [[Biography:Eric Temple Bell|Eric Temple Bell's]] ''Men of Mathematics'' (1937; still being reprinted), Godfrey Hardy and [[Biography:E. M. Wright|E. M. Wright's]] ''An Introduction to the Theory of Numbers'' (1938; 2008 6th edition), [[Biography:Garrett Birkhoff|Garrett Birkhoff]] and [[Biography:Saunders Mac Lane|Saunders Mac Lane's]] ''A Survey of Modern Algebra'' (1941; 1997 5th edition), and [[Biography:Michael Spivak|Michael Spivak's]] ''[[Calculus]]'' (1967; 2008 4th edition).<ref>{{harvnb|Bell|1937|pp=568&ndash;569}}; {{harvnb|Hardy|Wright|1938|p=159}} (6th ed., pp. 205&ndash;206); {{harvnb|Birkhoff|Mac Lane|1941|p=392}}, (5th ed., pp. 436&ndash;437); {{harvnb|Spivak|1967|pp=369&ndash;370}} (4th ed., pp. 448&ndash;449).</ref> Since these books view Cantor's proof as non-constructive, they do not mention his constructive proof. On the other hand, the quotations above from Fraenkel and Kaplansky show that they knew Cantor's work can be used non-constructively. The disagreement about Cantor's proof shows no sign of being resolved: since 2014, at least two books have appeared stating that Cantor's proof is constructive, and at least four have appeared stating that his proof does not construct any (or a single) transcendental.<ref>Proof is constructive: {{harvnb|Dasgupta|2014|p=107}}; {{harvnb|Sheppard|2014|pp=131&ndash;132}}. Proof is non-constructive: {{harvnb|Jarvis|2014|p=18}}; {{harvnb|Chowdhary|2015|p=19}}; {{harvnb|Stewart|2015|p=285}}; {{harvnb|Stewart|Tall|2015|p=333}}.</ref>

Asserting that Cantor gave a non-constructive proof can lead to erroneous statements about the [[History of mathematics|history of mathematics]]. In ''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 specific transcendental number." Birkhoff and Mac Lane are talking about the non-constructive proof.<ref>{{harvnb|Birkhoff|Mac Lane|1941|p=392}}, (5th ed., pp. 436&ndash;437).</ref> Cantor's proof produces transcendental numbers, and there appears to be no evidence that his argument was rejected.<ref>{{harvnb|Gray|1994|p=828}}.</ref> Even [[Biography:Leopold Kronecker|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.<ref>{{harvnb|Edwards|1989}}; {{harvnb|Gray|1994|p=828}}.</ref> In fact, applying Cantor's construction to the sequence of real algebraic numbers produces a limiting process that Kronecker accepted—namely, it determines a number to any required degree of accuracy.<ref>{{harvnb|Edwards|1989|pp=74&ndash;75}}.</ref>{{efn-ua|Kronecker's opinion was: "Definitions must contain the means of reaching a decision in a finite number of steps, and existence proofs must be conducted so that the quantity in question can be calculated with any required degree of accuracy."<ref>{{harvnb|Burton|1995|p=595}}.</ref> So Kronecker would accept Cantor's argument as a valid existence proof, but he would not accept its conclusion that transcendental numbers exist. For Kronecker, they do not exist because their definition contains no means for deciding in a finite number of steps whether or not a given number is transcendental.<ref>{{harvnb|Dauben|1979|p=69}}.</ref> To prove that Cantor's construction calculates numbers to any required degree of accuracy, we need to prove: Given a ''k'', an ''n'' can be computed such that 
{{nowrap|''b''<sub>''n''</sub> – ''a<sub>n</sub>'' ≤ {{sfrac|1|''k''}}}} where (''a<sub>n</sub>'',&nbsp;''b<sub>n</sub>'') is the {{nowrap|''n''-th}} interval of Cantor's construction. An example of how to prove this is given in {{harvnb|Gray|1994|p=822}}. Cantor's diagonal argument provides an accuracy of 10<sup>−''n''</sup> after ''n'' real algebraic numbers have been calculated because each of these numbers generates one digit of the transcendental number.<ref>{{harvnb|Gray|1994|p=824}}.</ref>}}

== The influence of Weierstrass and Kronecker on Cantor's article ==
[[File:Karl Weierstrass.jpg|thumb|upright=0.93|Karl Weierstrass]]
[[File:Leopold Kronecker 1865.jpg|thumb|upright=0.93|Leopold Kronecker, 1865]]
Historians of mathematics have discovered the following facts about Cantor's article "On a Property of the Collection of All Real Algebraic Numbers":

* Cantor's uncountability theorem was left out of the article he submitted. He added it during [[Galley proof|proofreading]].<ref name=Ferreiros184>{{harvnb|Ferreirós|2007|p=184}}.</ref>
* The article's title refers to the set of real algebraic numbers. The main topic in Cantor's correspondence was the set of real numbers.<ref>{{harvnb|Noether|Cavaillès|1937|pp=12&ndash;16}}. English translation: {{harvnb|Ewald|1996|pp=843&ndash;846}}.</ref>
* The proof of Cantor's second theorem came from Dedekind. However, it omits Dedekind's explanation of why the limits ''a''<sub>∞</sub> and ''b''<sub>∞</sub> exist.<ref>{{harvnb|Dauben|1979|p=67}}.</ref>
* 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.<ref name=Noether18 />

To explain these facts, historians have pointed to the influence of Cantor's former professors, [[Biography:Karl Weierstrass|Karl Weierstrass]] and Leopold Kronecker. Cantor discussed his results with Weierstrass on December 23, 1873.<ref name=Noether16_17>{{harvnb|Noether|Cavaillès|1937|pp=16&ndash;17}}. English translation: {{harvnb|Ewald|1996|p=847}}.</ref> Weierstrass was first amazed by the concept of countability, but then found the countability of the set of real algebraic numbers useful.<ref>{{harvnb|Grattan-Guinness|1971|p=124}}.</ref> Cantor did not want to publish yet, but Weierstrass felt that he must publish at least his results concerning the algebraic numbers.<ref name=Noether16_17 />

From his correspondence, it appears that Cantor only discussed his article with Weierstrass. However, Cantor told Dedekind: "The restriction which I have imposed on the published version of my investigations is caused in part by local circumstances …"<ref name=Noether16_17 /> Cantor biographer [[Biography:Joseph Dauben|Joseph Dauben]] believes that "local circumstances" refers to Kronecker who, as a member of the editorial board of ''[[Crelle's Journal]]'', had delayed publication of an 1870 article by [[Biography:Eduard Heine|Eduard Heine]], one of Cantor's colleagues. Cantor would submit his article to ''Crelle's Journal''.<ref>{{harvnb|Dauben|1979|pp=67, 308&ndash;309}}.</ref>

Weierstrass advised Cantor to leave his uncountability theorem out of the article he submitted, but Weierstrass also told Cantor that he could add it as a marginal note during proofreading, which he did.<ref name=Ferreiros184 /> It appears in a remark at the end of the article's introduction.<ref>See "The article" section. Also: {{harvnb|Cantor|1874|p=259}}; English translation: {{harvnb|Ewald|1996|p=841}}.</ref> The opinions of Kronecker and Weierstrass both played a role here. Kronecker did not accept infinite sets, and it seems that Weierstrass did not accept that two infinite sets could be so different, with one being countable and the other not.<ref>{{harvnb|Ferreirós|2007|pp=184&ndash;185, 245}}.</ref> Weierstrass changed his opinion later.<ref>"It is unclear when his attitude changed, but there is evidence that by the mid-1880s he was accepting the conclusion that infinite sets are of different powers [cardinalities]." {{harv|Ferreirós|2007|p=185.}}</ref> Without the uncountability theorem, the article needed a title that did not refer to this theorem. Cantor chose ''Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen''<!-- Spelled "Ueber", not "Über", in the title, despite the standard use of umlauts in the text of the article. --> ("On a Property of the Collection of All Real Algebraic Numbers"), which refers to the countability of the set of real algebraic numbers, the result that Weierstrass found useful.<ref>{{harvnb|Ferreirós|2007|p=177}}.</ref>

Kronecker's influence appears in the proof of Cantor's second theorem. Cantor used Dedekind's version of the proof except he left out why the limits ''a''<sub>∞</sub>&nbsp;=&nbsp;lim<sub>''n''&nbsp;→&nbsp;∞</sub>&nbsp;''a<sub>n</sub>'' and 
''b''<sub>∞</sub>&nbsp;=&nbsp;lim<sub>''n''&nbsp;→&nbsp;∞</sub>&nbsp;''b<sub>n</sub>'' exist. Dedekind had used his "principle of continuity" to prove they exist. This principle (which is equivalent to the least upper bound property of the real numbers) comes from Dedekind's construction of the real numbers, a construction Kronecker did not accept.<ref>{{harvnb|Dauben|1979|pp=67&ndash;68}}.</ref>

Cantor restricted his first theorem to the set of real algebraic numbers even though Dedekind had sent him a proof that handled all algebraic numbers.<ref name=Noether18 /> Cantor did this for expository reasons and because of "local circumstances."<ref>{{harvnb|Ferreirós|2007|p=183}}.</ref> This restriction simplifies the article because the second theorem works with real sequences. Hence, the construction in the second theorem can be applied directly to the enumeration of the real algebraic numbers to produce "an effective procedure for the calculation of transcendental numbers." This procedure would be acceptable to Weierstrass.<ref>{{harvnb|Ferreirós|2007|p=185}}.</ref>

==Dedekind's contributions to Cantor's article==
[[File:Dedekind.jpeg|thumb|upright=0.93|Richard Dedekind, c. 1870.]]

Since 1856, Dedekind had developed theories involving infinitely many infinite sets—for example: [[Ideal (ring theory)|ideal]]s, which he used in [[Algebraic number theory|algebraic number theory]], and [[Dedekind cut]]s, which he used to construct the real numbers. This work enabled him to understand and contribute to Cantor's work.<ref>{{harvnb|Ferreirós|2007|pp=109&ndash;111, 172&ndash;174.}}</ref>

Dedekind's first contribution concerns the theorem that the set of real algebraic numbers is countable. Cantor is usually given credit for this theorem, but the mathematical historian José Ferreirós calls it "Dedekind's theorem."<ref>{{harvnb|Ferreirós|1993|p=350}}.</ref> Their correspondence reveals what each mathematician contributed to the theorem.

In his letter introducing the concept of countability, Cantor stated without proof that the set of positive rational numbers is countable, as are sets of the form (''a''<sub>''n''<sub>1</sub>,&nbsp;''n''<sub>2</sub>,&nbsp;…,&nbsp;''n''<sub>''ν''</sub></sub>) where ''n''<sub>1</sub>,&nbsp;''n''<sub>2</sub>,&nbsp;…,&nbsp;''n<sub>ν''</sub>, and ''ν'' are positive integers.<ref>{{harvnb|Noether|Cavaillès|1937|pp=12&ndash;13}}. English translation: {{harvnb|Ewald|1996|p=844}}.</ref> Cantor's second result uses indexed numbers: a set of the form (''a''<sub>''n''<sub>1</sub>,&nbsp;''n''<sub>2</sub>,&nbsp;…,&nbsp;''n''<sub>''ν''</sub></sub>) is the range of a function from the ''ν'' indices to the set of real numbers. His second result implies his first: let ''ν''&nbsp;=&nbsp;2 and ''a''<sub>''n''<sub>1</sub>,&nbsp;''n''<sub>2</sub></sub>&nbsp;=&nbsp;{{sfrac|''n''<sub>1</sub>|''n''<sub>2</sub>}}. The function can be quite general—for example, ''a''<sub>''n''<sub>1</sub>,&nbsp;''n''<sub>2</sub>,&nbsp;''n''<sub>3</sub>,&nbsp;''n''<sub>4</sub>,&nbsp;''n''<sub>5</sub></sub>&nbsp;= {{nowrap|({{sfrac|''n''<sub>1</sub>|''n''<sub>2</sub>}})}}<sup>{{nowrap|{{sfrac|1|''n''<sub>3</sub>}}</sup>}}&nbsp;+&nbsp;{{nowrap|tan({{sfrac|''n''<sub>4</sub>|''n''<sub>5</sub>}}).}}

Dedekind replied with a proof of the theorem that the set of all algebraic numbers is countable.<ref name=Noether18 /> To obtain this result from Cantor's theorem about indexed numbers, Dedekind had to remove the restriction to positive integer indices and realize that the ordering produced can order the polynomials that have integer coefficients.

In his reply, Cantor did not claim to have proved Dedekind's result. He did indicate how he proved his theorem about indexed numbers: "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''<sub>1</sub><sup>2</sup>&nbsp;+&nbsp;''n''<sub>2</sub><sup>2</sup>&nbsp;+&nbsp;···&nbsp;+&nbsp;''n''<sub>''ν''</sub><sup>2</sup>&nbsp;=&nbsp;<math>\mathfrak{N}</math> and order the elements accordingly."<ref>{{harvnb|Noether|Cavaillès|1937|p=13}}. English translation: {{harvnb|Ewald|1996|p=845}}.</ref> Cantor's ordering cannot handle indices that are 0.<ref>{{harvnb|Ferreirós|2007|p=179}}.</ref>

Dedekind's second contribution is his proof of Cantor's second theorem. Dedekind sent Cantor this proof in reply to Cantor's letter that announced the uncountability theorem and proved it using infinitely many sequences. Before Dedekind's proof arrived, Cantor wrote that he had found a simpler proof that did not use infinitely many sequences.<ref>{{harvnb|Noether|Cavaillès|1937|pp=14&ndash;16, 19}}. English translation: {{harvnb|Ewald|1996|pp=845&ndash;847, 849}}.</ref> So Cantor had a choice of proofs and chose to publish Dedekind's.

Cantor thanked 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."<ref name=Noether16_17 /> However, he did not mention Dedekind's help in his article. In previous articles, he had acknowledged help received from Kronecker, Weierstrass, Heine, and Hermann Schwarz. Cantor's failure to mention Dedekind's contributions damaged his relationship with Dedekind. Dedekind stopped replying to his letters and did not resume the correspondence until October 1876.<ref>{{harvnb|Ferreirós|1993|pp=349&ndash;350}}; {{harvnb|Ferreirós|2007|pp=185&ndash;186}}.</ref>

==The legacy of Cantor's article==
Cantor's article introduced the uncountability theorem and the concept of countability. Both would lead to significant developments in mathematics.

The uncountability theorem demonstrated that one-to-one correspondences can be used to analyze infinite sets. In 1878, Cantor used them to define and compare cardinalities. He also constructed one-to-one correspondences to prove that the ''n''-dimensional spaces '''R'''<sup>''n''</sup> (where '''R''' is the set of real numbers) and the set of irrational numbers have the same cardinality as '''R'''.<ref>{{harvnb|Cantor|1878|pp=245&ndash;254}}.</ref>{{efn-ua|Cantor's method of constructing a one-to-one correspondence between the set of irrational numbers and '''R''' can be used to construct one between the set of transcendental numbers and '''R'''.<ref>{{harvnb|Cantor|1879|p=4}}.</ref> The construction begins with the set of transcendental numbers ''T'' and removes a countable [[Subset|subset]] {''t<sub>n</sub>''} (for example, {{nowrap|''t<sub>n</sub>'' {{=}} {{sfrac|''[[E (mathematical constant)|e]]''|''n''}}}}). Let this set be ''T''<sub>0</sub>. Then ''T''&nbsp;<nowiki>=</nowiki> &nbsp;''T''<sub>0</sub>&nbsp;∪&nbsp;{''t<sub>n</sub>''}&nbsp;<nowiki>=</nowiki> ''T''<sub>0</sub>&nbsp;∪&nbsp;{''t''<sub>{{nowrap|2''n'' – 1}}</sub>}&nbsp;∪&nbsp;{''t''<sub>2''n''</sub>}, and '''R'''&nbsp;<nowiki>=</nowiki>&nbsp;''T''&nbsp;∪&nbsp;{''a''<sub>''n''</sub>}&nbsp;<nowiki>=</nowiki> ''T''<sub>0</sub>&nbsp;∪&nbsp;{''t''<sub>''n''</sub>}&nbsp;∪&nbsp;{''a''<sub>''n''</sub>} where ''a''<sub>''n''</sub> is the sequence of real algebraic numbers. So both ''T'' and '''R''' are the union of three pairwise disjoint sets: ''T''<sub>0</sub> and two countable sets. A one-to-one correspondence between ''T'' and '''R''' is given by the function: {{nowrap|''g''(''t'') {{=}} ''t''}} if ''t''&nbsp;∈&nbsp;''T''<sub>0</sub>, {{nowrap|''g''(''t''<sub>2''n'' – 1</sub>) {{=}} ''t<sub>n</sub>''}}, and {{nowrap|''g''(''t''<sub>2''n''</sub>)&nbsp; {{=}} ''a<sub>n</sub>''.}}}}

In 1883, Cantor extended the natural numbers with his infinite [[Ordinal number|ordinals]]. This extension was necessary for his work on the Cantor–Bendixson theorem. Cantor discovered other uses for the ordinals—for example, he used sets of ordinals to produce an infinity of sets having different infinite cardinalities.<ref>{{harvnb|Ferreirós|2007|pp=267&ndash;273}}.</ref> His work on infinite sets together with Dedekind's set-theoretical work created set theory.<ref>{{harvnb|Ferreirós|2007|pp=xvi, 320&ndash;321, 324}}.</ref>

The concept of countability led to countable operations and objects that are used in various areas of mathematics. For example, in 1878, Cantor introduced countable [[Union (set theory)|union]]s of sets.<ref>{{harvnb|Cantor|1878|p=243}}.</ref> In the 1890s, [[Biography:Émile Borel|Émile Borel]] used countable unions in his [[Borel measure|theory of measure]], and [[Biography:René-Louis Baire|René Baire]] used countable ordinals to define his [[Baire function|classes of functions]].<ref>{{harvnb|Hawkins|1970|pp=103&ndash;106, 127}}.</ref> Building on the work of Borel and Baire, [[Biography:Henri Lebesgue|Henri Lebesgue]] created his theories of [[Lebesgue measure|measure]] and [[Lebesgue integration|integration]], which were published from 1899 to 1901.<ref>{{harvnb|Hawkins|1970|pp=118, 120&ndash;124, 127}}.</ref>

Countable [[Model theory|models]] are used in set theory. In 1922, [[Biography:Thoralf Skolem|Thoralf Skolem]] proved that if conventional [[Set theory#Axiomatic set theory|axioms of set theory]] are consistent, then they have a countable model. Since this model is countable, its set of real numbers is countable. This consequence is called [[Skolem's paradox]], and Skolem explained why it does not contradict Cantor's uncountability theorem: although there is a one-to-one correspondence between this set and the set of positive integers, no such one-to-one correspondence is a member of the model. Thus the model considers its set of real numbers to be uncountable, or more precisely, the [[First-order logic|first-order sentence]] that says the set of real numbers is uncountable is true within the model.<ref>{{harvnb|Ferreirós|2007|pp=362&ndash;363}}.</ref> In 1963, [[Biography:Paul Cohen|Paul Cohen]] used countable models to prove his [[Independence (mathematical logic)|independence]] theorems.<ref>{{harvnb|Cohen|1963|pp=1143&ndash;1144}}.</ref>

==See also==
*[[Cantor's theorem]]

==Notes==
{{notelist-ua}}

==References==
{{reflist|2}}

==Bibliography==
* {{Citation | ref=harv
  | first = Eric Temple
  | last = Bell
  | title = Men of Mathematics
  | publisher = Simon & Schuster
  | year = 1937
  | isbn = 0-671-62818-6}}.
* {{Citation | ref=harv
  | first1 = Garrett 
  | last1 = Birkhoff
  | first2 = Saunders
  | last2 = Mac Lane
  | title = A Survey of Modern Algebra
  | publisher = Macmillan
  | year = 1941
  | isbn = 978-1-56881-068-3}}.
* {{Citation | ref=harv
  | last = Burton
  | first = David M.
  | title = Burton's History of Mathematics
  | publisher = William C. Brown
  | year = 1995
  | edition = 3rd 
  | isbn = 0-697-16089-0}}.
* {{Citation | ref=harv
  | first = Georg
  | last = Cantor
  | title = Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen
  | url = http://www.digizeitschriften.de/main/dms/img/?PPN=GDZPPN002155583
  | volume = 77
  | pages = 258&ndash;262
  | journal = Journal für die Reine und Angewandte Mathematik
  | year = 1874
  | doi=10.1515/crll.1874.77.258}}.
* {{Citation | ref=harv
  | first = Georg
  | last = Cantor
  | title = Ein Beitrag zur Mannigfaltigkeitslehre
  | url = http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002156806
  | volume = 84
  | pages = 242&ndash;258
  | journal = Journal für die Reine und Angewandte Mathematik
  | year = 1878}}.
* {{Citation | ref=harv
  | first = Georg
  | last = Cantor
  | title = Ueber unendliche, lineare Punktmannichfaltigkeiten. 1.
  | url = http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN235181684_0015&DMDID=DMDLOG_0004
  | volume = 15
  | pages = 1&ndash;7
  | journal = [[Mathematische Annalen]] 
  | year = 1879
  | doi=10.1007/bf01444101}}.
* {{Citation | ref=harv
  | last = Chowdhary
  | first = K. R.
  | title = Fundamentals of Discrete Mathematical Structures
  | publisher = PHI Learning
  | year = 2015
  | edition = 3rd 
  | isbn = 978-81-203-5074-8}}.
* {{Citation | ref=harv
  | first = Paul J.
  | last = Cohen 
  | year = 1963
  | title = The Independence of the Continuum Hypothesis
  | journal = Proceedings of the National Academy of Sciences of the United States of America
  | volume = 50
  | pages = 1143–1148
  | doi = 10.1073/pnas.50.6.1143
  | pmid=16578557
  | pmc=221287}}.
* {{Citation | ref=harv
  | last = Dasgupta
  | first = Abhijit
  | title = Set Theory: With an Introduction to Real Point Sets
  | publisher = Springer
  | year = 2014 
  | isbn = 978-1-4614-8853-8}}.
* {{Citation | ref=harv
  | last = Dauben
  | first = Joseph
  | title = Georg Cantor: His Mathematics and Philosophy of the Infinite
  | publisher = Harvard University Press
  | year = 1979
  | isbn = 0-674-34871-0}}.
* {{Citation | ref=harv
  | last = Dauben
  | first = Joseph
  | title = Georg Cantor and the Battle for Transfinite Set Theory
  | url = http://acmsonline.org/home2/wp-content/uploads/2016/05/Dauben-Cantor.pdf
  | journal = 9th ACMS Conference Proceedings
  | year = 1993}}.
* {{Citation | ref=harv
  | last = Edwards
  | first = Harold M.
  | chapter = Kronecker's Views on the Foundations of Mathematics
  | editor-last1 = Rowe 
  | editor-first1= David E.
  | editor-last2 = McCleary
  | editor-first2 = John (eds.)
  | title = The History of Modern Mathematics, Volume 1
  | pages = 67&ndash;77
  | publisher = Academic Press
  | year = 1989
  | isbn = 0-12-599662-4}}. 
* {{Citation | ref=harv
  | last = Ewald
  | first = William B. (ed.)
  | title = From [[Biography:Immanuel Kant|Immanuel Kant]] to [[Biography:David Hilbert|David Hilbert]]: A Source Book in the Foundations of Mathematics, Volume 2
  | publisher = Oxford University Press
  | year = 1996
  | isbn = 0-19-850536-1}}.
* {{Citation | ref=harv
  | last = Ferreirós
  | first = José 
  | title = On the relations between Georg Cantor and Richard Dedekind
  | url = http://www.sciencedirect.com/science/article/pii/S031508608371030X
  | journal = Historia Mathematica
  | volume = 20
  | pages = 343&ndash;363
  | year = 1993
  | doi = 10.1006/hmat.1993.1030}}.
* {{Citation | ref=harv
  | last = Ferreirós
  | first = José 
  | title = Labyrinth of Thought: A History of Set Theory and Its Role in Mathematical Thought
  | publisher = Birkhäuser
  | year = 2007
  | edition = 2nd revised
  | isbn = 3-7643-8349-6}}.
* {{Citation | ref=harv
  | first = Abraham 
  | last = Fraenkel
  | title = Georg Cantor
  | url = http://www.digizeitschriften.de/main/dms/img/?PPN=PPN37721857X_0039&DMDID=dmdlog27
  | journal = Jahresbericht der Deutschen Mathematiker-Vereinigung
  | volume = 39
  | pages = 189&ndash;266
  | year = 1930}}.
* {{Citation | ref=harv
  | first = Ivor
  | last = Grattan-Guinness
  | title = The Correspondence between Georg Cantor and Philip Jourdain
  | url = http://www.digizeitschriften.de/main/dms/img/?PPN=GDZPPN002136651
  | journal = Jahresbericht der Deutschen Mathematiker-Vereinigung
  | volume = 73
  | pages = 111&ndash;130
  | year = 1971}}.
* {{Citation | ref=harv
  | first = Robert 
  | last = Gray
  | title = Georg Cantor and Transcendental Numbers
  | url = http://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Gray819-832.pdf
  | journal = [[American Mathematical Monthly]]
  | volume = 101
  | pages = 819&ndash;832
  | year = 1994
  | doi=10.2307/2975129
  | mr=1300488
  | zbl=0827.01004}}.
* {{Citation | ref=harv
  | last1 = Hardy 
  | first1 = Godfrey 
  | last2 = Wright 
  | first2 = E. M. 
  | title = An Introduction to the Theory of Numbers
  | publisher = Clarendon Press
  | year = 1938
  | isbn = 978-0-19-921985-8}}.
* {{Citation | ref=harv
  | last = Hawkins
  | first = Thomas
  | title = Lebesgue's Theory of Integration
  | publisher = University of Wisconsin Press
  | year = 1970
  | isbn = 0-299-05550-7}}.
* {{Citation | ref=harv
  | last = Jarvis
  | first = Frazer 
  | title = Algebraic Number Theory
  | publisher = Springer
  | year = 2014
  | isbn = 978-3-319-07544-0}}.
* {{Citation | ref=harv
  | last = Kaplansky
  | first = Irving
  | title = Set Theory and Metric Spaces
  | publisher = Allyn and Bacon
  | year = 1972
  | isbn = 0-8284-0298-1}}.
* {{Citation | ref=harv
  | last = LeVeque 
  | first = William J.
  | title = Topics in Number Theory, Volume I
  | publisher = Addison-Welsey
  | year = 1956
  | isbn = 978-0-486-42539-9}}. (Reprinted by Dover Publications, 2002.)
* {{Citation | ref=harv
  | last = Noether
  | first = Emmy 
  | last2 = Cavaillès
  | first2 = Jean (eds.)
  | title = Briefwechsel Cantor-Dedekind
  | publisher = Hermann
  | year = 1937}}.
* {{Citation | ref=harv
  | last = Perron
  | first = Oskar
  | title = Irrationalzahlen
  | url = https://archive.org/stream/irrationalzahlen00perruoft#page/n5/mode/2up
  | publisher = de Gruyter
  | year = 1921}}.
* {{Citation | ref=harv
  | last = Sheppard 
  | first = Barnaby 
  | title = The Logic of Infinity
  | publisher = Cambridge University Press
  | year = 2014
  | isbn = 978-1-107-67866-8}}.
* {{Citation | ref=harv
  | last = Spivak
  | first = Michael 
  | title = Calculus
  | url = https://archive.org/details/Calculus_643
  | publisher = W. A. Benjamin 
  | year = 1967
  | isbn = 978-0914098911}}.
* {{Citation | ref=harv
  | last = Stewart 
  | first = Ian 
  | title = Galois Theory
  | publisher = CRC Press
  | year = 2015
  | edition = 4th
  | isbn = 978-1-4822-4582-0}}.
* {{Citation | ref=harv
  | last1 = Stewart
  | first1 = Ian 
  | last2 = Tall 
  | first2 = David 
  | title = The Foundations of Mathematics
  | publisher = Oxford University Press
  | year = 2015
  | edition = 2nd
  | isbn = 978-0-19-870644-1}}.
* {{Citation | ref=harv
  | contribution = Continued Fraction
  | title = CRC Concise Encyclopedia of Mathematics
  | editor-last = Weisstein
  | editor-first = Eric W.
  | publisher = Chapman & Hall/CRC
  | year = 2003
  | isbn = 1-58488-347-2}}.

[[Category:History of mathematics]]
[[Category:Set theory]]
[[Category:Real analysis]]

{{Sourceattribution|Georg Cantor's first set theory article|1}}