View source for User:RJGray/Cantor draft

=== End of Cantor's 1879 proof ===
The sequence ''a''<sub>''n''</sub> is increasing and [[Upper and lower bounds|bounded above]] by ''b'', so the limit ''a''<sub>∞</sub>&nbsp;=&nbsp;lim<sub>''n''&nbsp;→&nbsp;∞</sub>&nbsp;''a''<sub>''n''</sub> exists. Similarly, the limit ''b''<sub>∞</sub>&nbsp;=&nbsp;lim<sub>''n''&nbsp;→&nbsp;∞</sub>&nbsp;''b''<sub>''n''</sub> exists because the sequence ''b''<sub>''n''</sub> is decreasing and [[Upper and lower bounds|bounded below]] by ''a''. Also, ''a''<sub>''n''</sub>&nbsp;<&nbsp;''b''<sub>''n''</sub> for all ''n'' implies ''a''<sub>∞</sub>&nbsp;≤&nbsp;''b''<sub>∞</sub>. However, if ''a''<sub>∞</sub>&nbsp;<&nbsp;''b''<sub>∞</sub>, then ''x''<sub>''n''</sub>&nbsp;∉&nbsp;(''a''<sub>∞</sub>,&nbsp;''b''<sub>∞</sub>) for all ''n'' since ''x''<sub>''n''</sub> is not in the larger interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). This contradicts ''P'' being dense in [''a'',&nbsp;''b'']. Hence, ''a''<sub>∞</sub>&nbsp;=&nbsp;''b''<sub>∞</sub>. So for all ''n'', {{nowrap|''a''<sub>∞</sub> ∈ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}} but {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}. Therefore, ''a''<sub>∞</sub> is a number in [''a'',&nbsp;''b''] that is not contained in ''P''.<ref group=proof name=p/>

== Cantor's 1879 uncountability proof ==
=== Everywhere dense ===
In 1879, Cantor published a new uncountability proof that modifies his 1874 proof. He first defines the [[topological]] notion of a point set ''P'' being "everywhere [[dense set|dense]] in an interval":{{efn-ua|Cantor was not the first to define "everywhere dense" but his terminology was adopted with or without the "everywhere" (everywhere dense: {{harvnb|Arkhangel'skii|Fedorchuk|1990|p=15}}; dense: {{harvnb|Kelley|1991|p=49}}). In 1870, [[Hermann Hankel]] had defined this concept using different terminology: "a multitude of points … ''fill the segment'' if no interval, however small, can be given within the segment in which one does not find at least one point of that multitude" ({{harvnb|Ferreirós|2007|p=155}}). Hankel was building on [[Peter Gustav Lejeune Dirichlet]]'s 1829 article that contains the [[Dirichlet function]], a non-([[Riemann integral|Riemann]]) [[integrable function]] whose value is 0 for [[rational number]]s and 1 for [[irrational number]]s. ({{harvnb|Ferreirós|2007|p=149}}.)}}

:If ''P'' lies partially or completely in the interval [α,&nbsp;β], then the remarkable case can happen that ''every'' interval [γ,&nbsp;δ] contained in [α,&nbsp;β], ''no matter how small,'' contains points of ''P''.  In such a case, we will say that ''P'' is ''everywhere dense in the interval'' [α,&nbsp;β].{{efn-ua|The original German text from {{harvnb|Cantor|1879|p=2}} (Cantor's closed set notation (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) is translated to [α,&nbsp;β]): {{langx|de|Liegt ''P'' theilweise oder ganz im Intervalle (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β), so kann der bemerkenswerthe Fall eintreten, dass ''jedes noch so kleine'' in (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) enthaltene Intervall (γ&nbsp;.&nbsp;.&nbsp;.&nbsp;δ) Punkte von ''P'' enthält. In einem solchen Falle wollen wir sagen, dass ''P'' ''im Intervalle'' (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) ''überall-dicht'' sei.|label=none|italic=unset}}}}

In this discussion of Cantor's proof: ''a'',&nbsp;''b'',&nbsp;''c'',&nbsp;''d'' are used instead of α,&nbsp;β,&nbsp;γ,&nbsp;δ. Also, Cantor only uses the interval notation [''a'',&nbsp;''b''] when ''a''&nbsp;<&nbsp;''b''.

Since the discussion of Cantor's 1874 proof was simplified by using open intervals rather than closed intervals, the same simplification is used here. This requires an equivalent definition of everywhere dense: A set ''P'' is everywhere dense in the interval [''a'',&nbsp;''b''] if and only if every open [[subinterval]] (''c'',&nbsp;''d'') of [''a'',&nbsp;''b''] contains at least one point of ''P''.<ref>{{harvnb|Arkhangel'skii|Fedorchuk|1990|p=16}}.</ref>

Cantor did not specify how many points of ''P'' an open subinterval (''c'',&nbsp;''d'') must contain. He did not need to specify this because the assumption that every open subinterval contains at least one point of ''P'' implies that every open subinterval contains infinitely many points of ''P''. This is proved by generating a sequence of points belonging to both ''P'' and (''c'',&nbsp;''d''). Since ''P'' is dense in [''a'',&nbsp;''b''], the subinterval (''c'',&nbsp;''d'') contains at least one point ''x''<sub>1</sub> of ''P''. By assumption, the subinterval (''x''<sub>1</sub>,&nbsp;''d'') contains at least one point ''x''<sub>2</sub> of ''P'' and ''x''<sub>2</sub>&nbsp;>&nbsp;''x''<sub>1</sub> since ''x''<sub>2</sub> belongs to this subinterval. In general, after generating ''x''<sub>''n''</sub>, the subinterval (x<sub>''n''</sub>,&nbsp;''d'') is used to generate a point ''x''<sub>''n''&nbsp;+&nbsp;1</sub> satisfying ''x''<sub>''n''&nbsp;+&nbsp;1</sub>&nbsp;>&nbsp;''x''<sub>''n''</sub>. The infinitely many points ''x''<sub>''n''</sub> belong to both ''P'' and (''c'',&nbsp;''d'').

=== Cantor's 1879 proof ===
Cantor modified his 1874 proof with a new proof of its [[#Second theorem|second theorem]]: Given any sequence ''P'' 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 ''P''. Cantor's new proof has two cases (his 1874 proof has three). First, it handles the case of ''P'' not being dense in the interval, then it deals with the more difficult case of ''P'' being dense. This division into cases not only indicates which sequences are more difficult to handle, but it also reveals the important role denseness plays in the proof.  ** TEXT OF CANTOR'S PROOF! **

In the first case, ''P'' is not dense in [''a'',&nbsp;''b'']. By definition:<br>
{{space|8}}''P'' is dense in [''a'',&nbsp;''b''] {{space|4}}if and only if {{space|1}}for all subintervals (''c'',&nbsp;''d'') of [''a'',&nbsp;''b''], there is an ''x''&nbsp;∈&nbsp;''P'' such that {{nowrap|''x'' ∈ (''c'', ''d'')}}.<br>
Taking the negation of each side of the "if and only if" produces:<br> 
{{space|5}}''P'' is not dense in [''a'',&nbsp;''b''] {{space}}if and only if {{space}}there is a subinterval (''c'',&nbsp;''d'') of [''a'',&nbsp;''b''] such that for all ''x''&nbsp;∈&nbsp;''P'', {{space|hair|3}}{{nowrap|''x'' ∉ (''c'', ''d'')}}.<br>
Therefore, every number in (''c'',&nbsp;''d'') is not contained in the sequence ''P''.<ref group=proof name=p/> This case handles [[#Case1|case 1]] and [[#Case3|case 3]] of Cantor's 1874 proof.

In the second case, which handles [[#Case2|case 2]] of Cantor's 1874 proof, ''P'' is dense in [''a'',&nbsp;''b'']. The denseness of sequence ''P'' is used to [[recursively define]] a nested sequence of intervals that excludes all of the numbers in ''P''. The [[base case (recursion)|base case]] starts with the interval (''a'',&nbsp;''b''). Since ''P'' is dense in [''a'',&nbsp;''b''], there are infinitely many numbers of ''P'' in (''a'',&nbsp;''b''). Let ''x''<sub>''k''<sub>1</sub></sub> be the number with the least index and ''x''<sub>''k''<sub>2</sub></sub> be the number with the next larger index, and let ''a''<sub>1</sub> be the smaller and ''b''<sub>1</sub> be the larger of these two numbers. Then, ''k''<sub>1</sub>&nbsp;<&nbsp;''k''<sub>2</sub>, {{nowrap|''a'' < ''a''<sub>1</sub> < ''b''<sub>1</sub> < ''b''}}, and (''a''<sub>1</sub>,&nbsp;''b''<sub>1</sub>) is a [[proper subinterval]] of (''a'',&nbsp;''b''). Also, {{nowrap|''x''<sub>''m''</sub> ∉ (''a''<sub>1</sub>,&nbsp;''b''<sub>1</sub>)}} for ''m''&nbsp;≤&nbsp;''k''<sub>2</sub> since these ''x''<sub>''m''</sub> are the endpoints of (''a''<sub>1</sub>,&nbsp;''b''<sub>1</sub>). The base case repeats the above proof with the interval (''a''<sub>1</sub>,&nbsp;''b''<sub>1</sub>) to obtain ''x''<sub>''k''<sub>3</sub></sub>, ''x''<sub>''k''<sub>4</sub></sub>, ''a''<sub>2</sub>, ''b''<sub>2</sub> such that     
{{nowrap|''k''<sub>1</sub> < ''k''<sub>2</sub> < ''k''<sub>3</sub> < ''k''<sub>4</sub>}} and {{nowrap|''a'' < ''a''<sub>1</sub> < ''a''<sub>2</sub> < ''b''<sub>2</sub> < ''b''<sub>1</sub> < ''b''}} and {{nowrap|''x''<sub>''m''</sub> ∉ (''a''<sub>2</sub>, ''b''<sub>2</sub>)}} for ''m''&nbsp;≤&nbsp;''k''<sub>4</sub>.<ref group=proof name=p/>

The [[recursive step]] starts with the interval (''a''<sub>''n''–1</sub>,&nbsp;''b''<sub>''n''–1</sub>), the inequalities {{nowrap|''k''<sub>1</sub> < ''k''<sub>2</sub> <  . . . < ''k''<sub>2''n''–2</sub></sub> < ''k''<sub>2''n''–1</sub></sub>}} and {{nowrap|''a'' < ''a''<sub>1</sub> < . . . < ''a''<sub>''n''–1</sub> < ''b''<sub>''n''–1</sub> . . . < ''b''<sub>1</sub> < ''b''}}, and the statement that the interval (''a''<sub>''n''–1</sub>,&nbsp;''b''<sub>''n''–1</sub>) excludes the first 2''n''{{space|hair|2}}–2 members of the sequence ''P''{{space|hair|2}}—{{space|hair|2}}that is, {{nowrap|''x''<sub>''m''</sub> ∉ (''a''<sub>''n''–1</sub>, ''b''<sub>''n''–1</sub>)}} for ''m''&nbsp;≤&nbsp;''k''<sub>2''n''–2</sub>. Since ''P'' is dense in [''a'',&nbsp;''b''], there are infinitely many numbers of ''P'' in (''a''<sub>''n''–1</sub>,&nbsp;''b''<sub>''n''–1</sub>). Let ''x''<sub>''k''<sub>2''n''{{space|hair|2}}–1</sub></sub> be the number with the least index and ''x''<sub>''k''<sub>2''n''</sub></sub> be the number with the next larger index, and let ''a''<sub>''n''</sub> be the smaller and ''b''<sub>''n''</sub> be the larger of these two numbers. Then, ''k''<sub>2''n''{{space|hair|2}}–1</sub>&nbsp;<&nbsp;''k''<sub>2''n''</sub>, {{nowrap|''a''<sub>''n''–1</sub> < ''a''<sub>''n''</sub> < ''b''<sub>''n''</sub> < ''b''<sub>''n''–1</sub>}}, and (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) is a [[proper subinterval]] of (''a''<sub>''n''–1</sub>,&nbsp;''b''<sub>''n''–1</sub>). Combining these inequalities with the ones for step ''n''{{space|hair|2}}–1 of the recursion produces {{nowrap|''k''<sub>1</sub> < ''k''<sub>2</sub> <  . . . < ''k''<sub>2''n''–1</sub></sub> < ''k''<sub>2''n''</sub></sub>}} and {{nowrap|''a'' < ''a''<sub>1</sub> < . . . < ''a''<sub>''n''</sub> < ''b''<sub>''n''</sub> . . . < ''b''<sub>1</sub> < ''b''}}. Also, {{nowrap|''x''<sub>''m''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}} for ''m''&nbsp;=&nbsp;''k''<sub>2''n''–1</sub></sub> and ''m''&nbsp;=&nbsp;''k''<sub>2''n''</sub></sub> since these ''x''<sub>''m''</sub> are the endpoints of (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). This together with the statement that (''a''<sub>''n''–1</sub>,&nbsp;''b''<sub>''n''–1</sub>) excludes the first 2''n''{{space|hair|2}}–2 members of the sequence ''P'' implies that the interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) excludes the first 2''n'' members of the sequence ''P''{{space|hair|2}}—{{space|hair|2}}that is, {{nowrap|''x''<sub>''m''</sub> ∉ (''a''<sub>''n''</sub>, ''b''<sub>''n''</sub>)}} for ''m''&nbsp;≤&nbsp;''k''<sub>2''n''</sub>. Therefore, for all ''n'', {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>, ''b''<sub>''n''</sub>)}} since ''n''&nbsp;≤&nbsp;''k''<sub>2''n''</sub>.<ref group=proof name=p/>

The sequence ''a''<sub>''n''</sub> is increasing and bounded by ''b'', so the limit ''a''<sub>∞</sub>&nbsp;=&nbsp;lim<sub>''n''&nbsp;→&nbsp;∞</sub>&nbsp;''a''<sub>''n''</sub> exists. Similarly, the limit ''b''<sub>∞</sub>&nbsp;=&nbsp;lim<sub>''n''&nbsp;→&nbsp;∞</sub>&nbsp;''b''<sub>''n''</sub> exists since the sequence ''b''<sub>''n''</sub> is decreasing and bounded by ''a''. Also, ''a''<sub>''n''</sub>&nbsp;<&nbsp;''b''<sub>''n''</sub> implies ''a''<sub>∞</sub>&nbsp;≤&nbsp;''b''<sub>∞</sub>. If ''a''<sub>∞</sub>&nbsp;<&nbsp;''b''<sub>∞</sub>, then for every ''n'': ''x''<sub>''n''</sub>&nbsp;∉&nbsp;(''a''<sub>∞</sub>,&nbsp;''b''<sub>∞</sub>) because ''x''<sub>''n''</sub> is not in the larger interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). This contradicts ''P'' being dense in [''a'',&nbsp;''b'']. Hence, ''a''<sub>∞</sub>&nbsp;=&nbsp;''b''<sub>∞</sub>. So for all ''n'', {{nowrap|''a''<sub>∞</sub> ∈ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}} but {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}. Therefore, ''a''<sub>∞</sub> is a number in [''a'',&nbsp;''b''] that is not contained in ''P''.<ref group=proof name=p/>

== Cantor's 1874 & 1879 proof ==

{{Anchor|Cantor's 1874 interval sequence}}
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 the [[open interval]] (''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{{space|hair|4}}—{{space|hair|4}}that is, it generates a sequence of [[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>

=== Cantor's 1879 proof ===
The sequence ''a''<sub>''n''</sub> is increasing and [[Upper and lower bounds|bounded above]] by ''b'', so the limit ''a''<sub>∞</sub>&nbsp;=&nbsp;lim<sub>''n''&nbsp;→&nbsp;∞</sub>&nbsp;''a''<sub>''n''</sub> exists. Similarly, the limit ''b''<sub>∞</sub>&nbsp;=&nbsp;lim<sub>''n''&nbsp;→&nbsp;∞</sub>&nbsp;''b''<sub>''n''</sub> exists because the sequence ''b''<sub>''n''</sub> is decreasing and [[Upper and lower bounds|bounded below]] by ''a''. Also, ''a''<sub>''n''</sub>&nbsp;<&nbsp;''b''<sub>''n''</sub> for all ''n'' implies ''a''<sub>∞</sub>&nbsp;≤&nbsp;''b''<sub>∞</sub>. However, if ''a''<sub>∞</sub>&nbsp;<&nbsp;''b''<sub>∞</sub>, then ''x''<sub>''n''</sub>&nbsp;∉&nbsp;(''a''<sub>∞</sub>,&nbsp;''b''<sub>∞</sub>) for all ''n'' since ''x''<sub>''n''</sub> is not in the larger interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). This contradicts ''P'' being dense in [''a'',&nbsp;''b''], so ''a''<sub>∞</sub>&nbsp;=&nbsp;''b''<sub>∞</sub>. Now, for every ''n'', {{nowrap|''a''<sub>∞</sub> ∈ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}} but {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}. Therefore, ''a''<sub>∞</sub> is a number in [''a'',&nbsp;''b''] that is not contained in ''P''.<ref group=proof name=p/>

==ADD to end of Cantor's 1879 proof==
In the [[#Example of Cantor's construction|Example of Cantor's construction]], each successive nested interval excludes rational numbers for two different reasons. It will exclude the finitely many rationals visited in the search for the first two rationals within the interval (these two rationals will have the least indices). These rationals are then used to form an interval that excludes the rationals visited in the search along with infinitely many more rationals. However, it still contains infinitely many rationals since our sequence of rationals is dense in [0,&nbsp;1]. Forming this interval from the two rationals with the least indices guarantees that this interval excludes an initial segment of our sequence that contains at least two more members than the preceding initial segment. Since the denseness of our sequence guarantees that this process never ends, all rationals will be excluded.<ref group=proof name=p /> Because of the ordering of the rationals in our sequence, the [[Intersection (set theory)|intersection]] of the nested intervals is the [[#Number generated|set]] {{{sqrt|2}}&nbsp;&minus;&nbsp;1}.{{efn-ua|Different orderings can produce nested intervals whose intersection is {''x''} for any ''x'': Let ''x''<sub>''n''</sub> be the [[Decimal approximation of a real number|decimal approximation]] of ''x'' to ''n''-digits. Starting with the interval [''x''<sub>0</sub>,&nbsp;''x''<sub>0</sub>&nbsp;+&nbsp;1] and continuing with the intervals [''x''<sub>''n''</sub>,&nbsp;''x''<sub>''n''</sub>&nbsp;+&nbsp;1/10<sup>''n''</sup>{{space|thin}}] for ''n''&nbsp;≥&nbsp;1 produces a sequence of intervals whose intersection is {''x''}.}}

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

== NEW PROOF ==

===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.{{efn-ua|This implies the rest of the theorem{{space|hair|4}}—{{space|hair|4}}namely, there are infinitely many numbers in [''a'',&nbsp;''b''] that are not contained in the given sequence. For example, let <math>[0,1]</math> be the interval and consider its [[subinterval]]s <math>[0, \tfrac{1}{2}],</math> <math>[\tfrac{3}{4},\tfrac{7}{8}],</math> <math>[\tfrac{15}{16}, \tfrac{31}{32}],</math> <math> \ldots.</math> Since these subintervals are [[pairwise disjoint]], applying the first part of the theorem to each subinterval produces infinitely many numbers in <math>[0,1]</math> that are not contained in the given sequence. In general, for the interval <math>[a, b],</math> apply the first part of the theorem to the subintervals <math>[a, a + \tfrac{1}{2}(b-a)],</math> <math>[a + \tfrac{3}{4}(b-a), a + \tfrac{7}{8}(b-a)],</math> <math>[a + \tfrac{15}{16}(b-a), a + \tfrac{31}{32}(b-a)],</math> <math>\ldots .</math>}}

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 the [[open interval]] (''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{{space|hair|4}}—{{space|hair|4}}that is, it generates a sequence of [[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>''L''</sub>,&nbsp;''b''<sub>''L''</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:
{{Anchor|Case1}}[[File:Cantor's first uncountability proof Case 1 svg.svg|thumb|350px|alt=Illustration of case 1. [[Real line]] containing closed interval [''a'',&nbsp;''b''] that contains nested open intervals (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) for ''n''&nbsp;= 1 to ''L''. Two distinct numbers ''y'' and one ''x''<sub>''n''</sub> are in (''a''<sub>''L''</sub>,&nbsp;''b''<sub>''L''</sub>).|Case 1: Last interval (''a''<sub>''L''</sub>, ''b''<sub>''L''</sub>)]]
:Case 1: There is a last interval (''a''<sub>''L''</sub>,&nbsp;''b''<sub>''L''</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.
{{Anchor|Case2}}[[File:Cantor's first uncountability proof Case 2 svg.svg|thumb|350px|alt=Illustration of case 2. Real line containing interval [''a'',&nbsp;''b''] that contains nested intervals (''a''<sub>''n''</sub>, ''b''<sub>''n''</sub>) for ''n''&nbsp;=&nbsp;1 to ∞. These intervals converge to ''a''<sub>∞</sub>.|Case 2: ''a''<sub>∞</sub> = ''b''<sub>∞</sub>]]
: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 ''x''<sub>''n''</sub> does not belong to (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). In symbols, ''a''<sub>∞</sub>&nbsp;[[∈]]&nbsp;(''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) but ''x''<sub>''n''</sub>&nbsp;[[∉]]&nbsp;(''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>).
{{Anchor|x_n not in}}
:{| class="wikitable collapsible collapsed"
! style="background: f5f5f5;" |'''Proof that for all&nbsp;''n''{{space|hair|2}}: {{nowrap|{{space|thin|2}}''x''<sub>''n''</sub>&nbsp;{{space|hair|2}}∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}'''&nbsp;{{space|thin|2}}
|- style="text-align: left; vertical-align: top; background: white" 
| style="padding-left: 1em; padding-right: 1em" | This is implied by the stronger result: For all&nbsp;''n'', (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) excludes ''x''<sub>1</sub>,&nbsp;...&nbsp;,&nbsp;''x''<sub>2''n''</sub>, which is proved 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>. (This proof is similar to a proof that Cantor published in 1879. The main difference is that Cantor's proof is embedded in a larger proof and uses notation from it. Our proof does not depend on this notation.<ref group=proof name=p />)
|}
{{Anchor|Case3}}[[File:Cantor's first uncountability proof Case 3 svg.svg|thumb|350px|alt=Illustration of case 3. Real line containing [''a'',&nbsp;''b''] that contains nested intervals (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) for ''n''&nbsp;=&nbsp;1 to ∞. These intervals converge to the closed interval [a<sub>∞</sub>,&nbsp;b<sub>∞</sub>]. The number y is in this interval.|Case 3: ''a''<sub>∞</sub> < ''b''<sub>∞</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 main difference between Cantor's proof and the above proof 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 uses the [[Interior (topology)|interior]] of the interval [''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>], which is the open interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). Generating open intervals combines Cantor's use of closed intervals and their interiors, which allows the [[#Cases|case diagrams]] to depict all the details of the proof.}}

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.<ref>{{harvnb|Gray|1994|p=822}}.</ref>

Cantor's 1879 proof is the same as his 1874 proof except for a new proof of the first part of his [[#Second theorem|second theorem]]: Given any sequence ''P'' 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 sequence ''P''. The new proof has only two cases. **Big proof ref goes here!**

Cantor's new proof first handles the case of the sequence ''P'' not being dense in the interval. Then it deals with the more difficult case of ''P'' being dense. This division into cases not only indicates which sequences are most difficult to handle, but it also reveals the important role denseness plays in the proof.<ref group=proof name=p />

In the first case, ''P'' is not dense in [''a'',&nbsp;''b'']. By definition, ''P'' is dense if and only if for all [[subset]]s (''c'',&nbsp; ''d'') of [''a'',&nbsp;''b''], there is an ''x''<sub>''n''</sub> in ''P'' such that ''x''<sub>''n''</sub> is in (''c'',&nbsp;''d''). Taking the negation of each side of the "if and only if" produces: ''P'' is not dense in [''a'',&nbsp;''b''] if and only if there exists a subset (''c'',&nbsp;''d'') of [''a'',&nbsp;''b''] such that for all ''x''<sub>''n''</sub> in ''P'', ''x''<sub>''n''</sub> is not in (''c'',&nbsp;''d''). Therefore, every number in (''c'',&nbsp;''d'') is not contained in the sequence ''P''.<ref group=proof name=p /> This case handles [[#Case1|case 1]] and [[#Case3|case 3]] of Cantor's 1874 proof. In the diagram for case 1, every ''x''<sub>''n''</sub> in (''a''<sub>''L''</sub>,&nbsp;''y'') is not in the sequence. In the diagram for case 3, every ''x''<sub>''n''</sub> in (''a''<sub>∞</sub>,&nbsp;''b''<sub>∞</sub>) is not in the sequence. 

In the second case, ''P'' is dense in [''a'',&nbsp;''b'']. The denseness of ''P'' is used to [[recursively define]] a nested sequence of intervals is used to prove that this nested sequence excludes all members of ''P''. The [[base case]] starts with the observation that since ''P'' is dense in [''a'',&nbsp;''b''], there are infinitely many real numbers in ''P'' that belong to (''a'',&nbsp;''b''). Let ''x''<sub>''k''<sub>1</sub></sub> be the real number with the least index ''k''<sub>1</sub> and let ''x''<sub>''k''<sub>2</sub></sub> be the real number with the next larger index ''k''<sub>2</sub>. Let ''a''<sub>1</sub> be the smaller of these two reals and let ''b''<sub>1</sub> be the larger. Then, {{nowrap|''a'' < ''a''<sub>1</sub> < ''b''<sub>1</sub> < ''b''}} and {{nowrap|''k''<sub>1</sub> < ''k''<sub>2</sub>}}. Since ''x''<sub>''k''<sub>1</sub></sub> and ''x''<sub>''k''<sub>2</sub></sub> are the reals in ''P'' with the least indexes, for all {{nowrap|''j''&nbsp;≤&nbsp;''k''<sub>2</sub>}}, **MAY NEED MORE** the numbers ''x''<sub>''j''</sub> are not in (''a''<sub>1</sub>,&nbsp;''b''<sub>1</sub>). **MAY NEED MORE** May want to prove this! If j < k2, then if xj is in (a1, b1), it canoot be xj in interval or xj would have been chosen instead of xk+1 or xk+2!!

The recursive part of the definition starts with the interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) and with the inequalities  {{nowrap|''a'' < ''a''<sub>1</sub> < ... < ''a''<sub>''n''</sub> < ''b''<sub>''n''</sub> < ... < ''b''<sub>1</sub> < ''b''}} and {{nowrap|''k''<sub>1</sub> < ''k''<sub>2</sub> < ... < ''k''<sub>2''n''{{space|thin}}−{{space|hair}}1</sub> < ''k''<sub>2''n''</sub>}} such that for all ''j''&nbsp;≤&nbsp;''k''<sub>2''n''</sub>, the numbers ''x''<sub>''j''</sub> are not in (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). Since ''P'' is dense in [''a'',&nbsp;''b''], there are infinitely many real numbers in ''P'' that belong to (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). Let ''x''<sub>''k''<sub>2''n''{{space|thin}}+{{space|hair}}1</sub></sub> be the real number with the least index ''k''<sub>2''n''{{space|thin}}+{{space|hair}}2</sub> and let ''x''<sub>2''n''{{space|thin}}+{{space|hair}}2</sub> be the real number with the next larger index ''k''<sub>2''n''{{space|thin}}+{{space|hair}}2</sub>. Let ''a''<sub>''n''{{space|thin}}+{{space|hair}}1</sub> be the smaller of these two reals and let ''b''<sub>''n''{{space|thin}}+{{space|hair}}1</sub> be the larger. Then, {{nowrap|''a''<sub>''n''</sub> < ''a''<sub>''n''{{space|thin}}+{{space|hair}}1</sub> < ''b''<sub>''n''{{space|thin}}+{{space|hair}}1</sub> < ''b''<sub>''n''</sub>}} and {{nowrap|''k''<sub>2''n''{{space|thin}}+{{space|hair}}1</sub> < ''k''<sub>2''n''{{space|thin}}+{{space|hair}}2</sub>}}. Since ''x''<sub>''k''<sub>1</sub></sub> and ''x''<sub>''k''<sub>2</sub></sub> are the reals in ''P'' with the least indexes **MAY NEED MORE** for all {{nowrap|''j''&nbsp;≤&nbsp;''k''<sub>2''n''{{space|thin}}+{{space|hair}}2</sub>}}, the numbers ''x''<sub>''j''</sub> are not in (''a''<sub>''n''{{space|thin}}+{{space|hair}}1</sub>,&nbsp;''b''<sub>''n''{{space|thin}}+{{space|hair}}1</sub>). **MAY NEED MORE HERE!**

The sequence ''a''<sub>''n''</sub> is increasing and bounded above by ''b'', so it has a limit ''a''<sub>∞</sub>, which satisfies ''a''<sub>''n''</sub>&nbsp;≤&nbsp;''a''<sub>∞</sub> for all ''n''. The sequence ''b''<sub>''n''</sub> is decreasing and bounded below by ''a'', so it has a limit ''b''<sub>∞</sub>, which satisfies ''b''<sub>∞</sub>&nbsp;≤&nbsp;''b''<sub>''n''</sub> for all ''n''. Also, ''a''<sub>''n''</sub>&nbsp;<&nbsp;''b''<sub>''n''</sub> implies ''a''<sub>∞</sub>&nbsp;≤&nbsp;''b''<sub>∞</sub>. Therefore, {{nowrap|''a''<sub>''n''</sub> ≤ ''a''<sub>∞</sub> ≤ ''b''<sub>∞</sub> ≤ ''b''<sub>''n''</sub>}}. If ''a''<sub>∞</sub>&nbsp;<&nbsp;''b''<sub>∞</sub>, then for every ''n'': ''x''<sub>''n''</sub>&nbsp;∉&nbsp;(''a''<sub>∞</sub>,&nbsp;''b''<sub>∞</sub>) because ''x''<sub>''n''</sub> is not in the larger interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). This contradicts ''P'' being dense in [''a'',&nbsp;''b'']. Therefore, ''a''<sub>∞</sub>&nbsp;=&nbsp;''b''<sub>∞</sub>. Since for all ''n'': {{nowrap|''a''<sub>∞</sub> ∈ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}} but {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}, the limit ''a''<sub>∞</sub> is a real number that is not contained in the sequence ''P''.<ref group=proof name=p /> **MAY NEED MORE HERE!** This case handles [[#Case2|case 2]] of Cantor's 1874 proof.

===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.{{efn-ua|This implies the rest of the theorem — namely, there are infinitely many numbers in [''a'',&nbsp;''b''] that are not contained in the given sequence. For example, let <math>[0,1]</math> be the interval and consider its [[subinterval]]s <math>[0, \tfrac{1}{2}],</math> <math>[\tfrac{3}{4},\tfrac{7}{8}],</math> <math>[\tfrac{15}{16}, \tfrac{31}{32}],</math> <math> \ldots.</math> Since these subintervals are [[pairwise disjoint]], applying the first part of the theorem to each subinterval produces infinitely many numbers in <math>[0,1]</math> that are not contained in the given sequence. In general, for the interval <math>[a, b],</math> apply the first part of the theorem to the subintervals <math>[a, a + \tfrac{1}{2}(b-a)],</math> <math>[a + \tfrac{3}{4}(b-a), a + \tfrac{7}{8}(b-a)],</math> <math>[a + \tfrac{15}{16}(b-a), a + \tfrac{31}{32}(b-a)],</math> <math>\ldots .</math>}}

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 the [[open interval]] (''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]]. 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>''L''</sub>,&nbsp;''b''<sub>''L''</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:

{{Anchor|Case1}}[[File:Cantor's first uncountability proof Case 1 svg.svg|thumb|350px|alt=Diagram of case 1. [[Real line]] containing closed interval [''a'',&nbsp;''b''] that contains nested open intervals (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) for ''n''&nbsp;= 1 to ''L''. Two distinct numbers ''y'' and one ''x''<sub>''n''</sub> are in (''a''<sub>''L''</sub>,&nbsp;''b''<sub>''L''</sub>).|Case 1: Last interval (''a''<sub>''L''</sub>, ''b''<sub>''L''</sub>)]]
:Case 1: There is a last interval (''a''<sub>''L''</sub>,&nbsp;''b''<sub>''L''</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.
{{Anchor|Case2}}[[File:Cantor's first uncountability proof Case 2 svg.svg|thumb|350px|alt=Diagram of case 2. Real line containing interval [''a'',&nbsp;''b''] that contains nested intervals (''a''<sub>''n''</sub>, ''b''<sub>''n''</sub>) for ''n''&nbsp;=&nbsp;1 to ∞. These intervals converge to ''a''<sub>∞</sub>.|Case 2: ''a''<sub>∞</sub> = ''b''<sub>∞</sub>]]
: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.
{{Anchor|x_n not in}}
:{| class="wikitable collapsible collapsed"
! style="background: f5f5f5;" |'''Proof that for all&nbsp;''n''{{space|hair}}:&nbsp;''x''<sub>''n''</sub>&nbsp;{{space|hair}}[[∉]]&nbsp;(''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}'''
|- style="text-align: left; vertical-align: top; background: white" 
| style="padding-left: 1em; padding-right: 1em" | This is implied by the stronger result: For all&nbsp;''n'', (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) excludes ''x''<sub>1</sub>,&nbsp;...&nbsp;,&nbsp;''x''<sub>2''n''</sub>, which is proved 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>. (This proof is similar to a proof that Cantor published in 1879. The main difference is that Cantor's proof is embedded in a larger proof and uses notation from it. Our proof does not depend on this notation.<ref group=proof name=p />)
|}
{{Anchor|Case3}}[[File:Cantor's first uncountability proof Case 3 svg.svg|thumb|350px|alt=Diagram of case 3. Real line containing [''a'',&nbsp;''b''] that contains nested intervals (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) for ''n''&nbsp;=&nbsp;1 to ∞. These intervals converge to the closed interval [a<sub>∞</sub>,&nbsp;b<sub>∞</sub>]. The number y is in this interval.|Case 3: ''a''<sub>∞</sub> < ''b''<sub>∞</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>

In the first case, ''P'' is not dense in [''a'',&nbsp;''b'']. By definition, ''P'' is dense if and only if for all {{nowrap|(''c'', ''d'') ⊆ [''a'',&nbsp;''b'']}}, there is an ''x''&nbsp;∈&nbsp;''P'' such that {{nowrap|''x'' ∈ (''c'', ''d'')}}. Taking the negation of each side of the "if and only if" produces: ''P'' is not dense in [''a'',&nbsp;''b''] if and only if there exists a {{nowrap|(''c'', ''d'') ⊆ [''a'',&nbsp;''b'']}} such that for all ''x''&nbsp;∈&nbsp;''P'', we have {{nowrap|''x'' ∉ (''c'', ''d'')}}. Thus, every number in (''c'',&nbsp;''d'') is not contained in the sequence ''P''.<ref group=proof name=p /> This case handles [[#Case1|case 1]] and [[#Case3|case 3]] of Cantor's 1874 proof.

In the second case, ''P'' is dense in [''a'',&nbsp;''b'']. The denseness of ''P'' is used to [[recursively define]] a nested sequence of intervals that excludes all elements of ''P''. The definition begins with
''a''<sub>1</sub>&nbsp;=&nbsp;''a'' and ''b''<sub>1</sub>&nbsp;=&nbsp;''b''. The definition's inductive case starts with the interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>), which because of the denseness of ''P'' contains infinitely many elements of ''P''. From these elements of ''P'', the two with smallest indices are used to define ''a''<sub>''n''&nbsp;+&nbsp;1</sub> and ''b''<sub>''n''&nbsp;+&nbsp;1</sub>; namely, ''a''<sub>''n''&nbsp;+&nbsp;1</sub> is the least of these two numbers and  ''b''<sub>''n''&nbsp;+&nbsp;1</sub> is the greatest. [[#x_n not in|Cantor's 1874 proof]] demonstrates that for all&nbsp;''n''{{space|hair}}:{{space|hair}} {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}. The sequence ''a''<sub>''n''</sub> is increasing and bounded above by ''b'', so it has a limit ''c'', which satisfies ''a''<sub>''n''</sub>&nbsp;<&nbsp;''c''. The sequence ''b''<sub>''n''</sub> is decreasing and bounded below by ''a'', so it has a limit ''d'', which satisfies ''d''&nbsp;<&nbsp;''b''<sub>''n''</sub>. Also, ''a''<sub>''n''</sub>&nbsp;<&nbsp;''b''<sub>''n''</sub> implies ''c''&nbsp;≤&nbsp;''d''. Therefore, {{nowrap|''a''<sub>''n''</sub> < ''c'' ≤ ''d'' < ''b''<sub>''n''</sub>}}. If ''c''&nbsp;<&nbsp;''d'', then for every ''n'': ''x''<sub>''n''</sub>&nbsp;∉&nbsp;(''c'',&nbsp;''d'') because ''x''<sub>''n''</sub> is not in the larger interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). This contradicts ''P'' being dense in [''a'',&nbsp;''b'']. Therefore, ''c''&nbsp;=&nbsp;''d''. Since for all ''n'': {{nowrap|''c'' ∈ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}} but {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}, the limit ''c'' is a real number that is not contained in the sequence ''P''.<ref group=proof name=p /> This case handles [[#Case2|case 2]] of Cantor's 1874 proof.

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

== Accessibility ==
Accessibility. For screen readers: used [[Template:lang-de]] to enclose German sentences in notes.

===Deutsch===
{{langx|de|Seite 5: Dem widerspricht aber ein sehr allgemeiner Satz, welchen wir in Borchardt's Journal, Bd. 77, pag. 260, mit aller Strenge bewiesen haben, nämlich der folgende Satz:|label=none|italic=invert}}

===Francais===
{{langx|fr|mit}}

Seite 5: Dem widerspricht aber ein sehr allgemeiner Satz, welchen wir in Borchardt's Journal, Bd. 77, pag. 260, mit aller Strenge bewiesen haben, nämlich der folgende Satz:

{{langx|de|''Liegt'' P ''theilweise oder ganz im Intervalle'' (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β), ''so kann der bemerkenswerthe Fall eintreten, dass'' jedes noch so kleine ''in (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) enthaltene Intervall (γ&nbsp;.&nbsp;.&nbsp;.&nbsp;δ) Punkte von'' P ''enthält. In einem solchen Falle wollen wir sagen, dass'' P im Intervalle ''(α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) ''überall-dicht'' sei.|label=none|italic=invert}}}}

{{space|5}}''"Hat man eine einfach unendliche Reihe''<br>
{{space|12}}ω<sub>1</sub>,&nbsp;ω<sub>2</sub>,&nbsp;.&nbsp;.&nbsp;.&nbsp;,&nbsp;ω<sub>ν</sub>,&nbsp;.&nbsp;.&nbsp;.<br>
''von reellen, ungleichen Zahlen, die nach irgend einem Gesetz fortschreiten, so lässt sich in jedem vorgegebenen, Intervalle (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) eine Zahl η (und folglich lassen sich deren unendlich viele) angeben, welche nicht in jener Reihe (als Glied derselben) vorkommt."''
:If ''P'' lies partially or completely in the interval [α,&nbsp;β], then the remarkable case can happen that ''every'' intervals [γ,&nbsp;δ] contained in [α,&nbsp;β], ''no matter how small'', contains points of ''P''.  In such a case, we will say that ''P'' is ''everywhere dense in the interval'' [α,&nbsp;β].{{efn-ua|The original German text from {{harvnb|Cantor|1879|p=2}} (Cantor's closed set notation (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) is translated to [α,&nbsp;β]): {{langx|de|''Liegt'' P ''theilweise oder ganz im Intervalle'' (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β), ''so kann der bemerkenswerthe Fall eintreten, dass'' jedes noch so kleine ''in (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) enthaltene Intervall (γ&nbsp;.&nbsp;.&nbsp;.&nbsp;δ) Punkte von'' P ''enthält. In einem solchen Falle wollen wir sagen, dass'' P im Intervalle ''(α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) ''überall-dicht'' sei.|label=none|italic=invert}}}}

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

==To change to US-PD==

===Example ===
:File: "[[Cantor's first set theory article]]"
:Click on Cantor photo
:Click on More details
:Click on Edit (at top of page)
:Change or add to Permission = Template:PD-old or Template:PD-old|PD-other

==Photo info==
===Cantor===
:{{Information
:|Description    = en|1=Georg Cantor}}
:|Source         =https://opc.mfo.de/detail?photo_id=10525
:|Author         =unknown|Author}}
:|Date           =circa 1870
:|Permission     =PD-old}}
:}}

===Perron===
:{{Information
:|Description=en|1=German mathematician Oskar Perron (1880-1975) at Munich in 1948. }}
:|Source=https://opc.mfo.de/detail?photo_id=3261
:|Author=Jacobs, Konrad
:|Date=1948
:|permission=OTRS 2008042410024381}} Template:cc-by-sa-2.0-de}}
:|other_versions=
:}}

:DEFAULTSORT:Perron, Oskar}}
:Category:1948 in Munich]]
:Category:Pictures from Oberwolfach Photo Collection]]
:Category:Oskar Perron (mathematician)]]

===Fraenkel===
:int:filedesc}} ==
:Information
:|Description=en|1=[[:en:Abraham Fraenkel|Abraham Halevi (Adolf) Fraenkel]], German-born Israeli mathematician, first Dean of Mathematics as the Hebrew University of Jerusalem and Rector of the University; 1956, recipient of the Israel Prize for exact sciences (1956); member of the Israel Academy of Sciences and Humanities; Zionist, member of the Jewish National Council and the Jewish Assembly of Representatives under the British mandate, belonged to the "Mizrachi"}}
:|Source=The David B. Keidan Collection of Digital Images from the Central Zionist Archives
:        (via http://id.lib.harvard.edu/images/olvwork485526/catalog Harvard University Library])
:|Author=unknown|author}}
:|Date=between 1939 and 1949
:|Permission=
:|other_versions=
}}

int:license-header}} ==
PD-Israel}}

:Category:Abraham Fraenkel]]
:Category:Photographs from the Central Zionist Archives]]
:Notation:PHG\1110747
:Original number:110747
:Name of photographer/institution:Unknown
:Copyright:By the archives

===Weierstrass===

:int:filedesc}} ==
:Source: from de:Image:Karl_Weierstrass.jpg, 
:from http://www.sil.si.edu/digitalcollections/hst/scientific-identity/explore.htm

:Category:Karl Weierstraß]]
:Category:Rectors of Humboldt-Universität zu Berlin]]

:int:license-header}} ==
:PD-Art|PD-old-70}}

:Category:Artworks missing infobox template]]

===Kronecker===

:int:filedesc}} ==
:Information
:|Description=Leopold Kronecker
:|Source=http://www.britannica.com/EBchecked/media/28346/Kronecker-1865
:|Author={{unknown|author}}
:|Date=1865
:|Permission=PD-old-70}}
:|other_versions=
:}}

:Category:Leopold Kronecker]]

===Dedekind===

:int:filedesc}} ==
:{{Information
:|Description= Photo de Richard Dedekind vers 1870
:|Source=http://dbeveridge.web.wesleyan.edu/wescourses/2001f/chem160/01/Photo_Gallery_Science/Dedekind/FrameSet.htm
:|Date=<nowiki>{{original upload date|2007-02-10}}</nowiki>
:|Author= not found
:|Permission=La photo date de plus de 150 ans (en effet, nous sommes en 2020), elle est dans le domaine public
:|other_versions=
:}}

== {{int:license-header}} ==
{{PD-old}}

[[:Category:Richard Dedekind]]

== Cantor's 1874 & 1879 proof ==

{{Anchor|Cantor's 1874 interval sequence}}
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 the [[open interval]] (''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{{space|hair|4}}—{{space|hair|4}}that is, it generates a sequence of [[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>

=== Cantor's 1879 proof ===
Cantor's 1879 proof is the same as his 1874 proof except for a new proof of the first part of his [[#Second theorem|second theorem]]: Given any sequence ''P'' 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 sequence ''P''. Cantor's new proof has only two cases: It first handles the case of the sequence ''P'' not being dense in the interval, then it deals with the more difficult case of ''P'' being dense. This division into cases not only indicates which sequences are more difficult to handle, but it also reveals the important role denseness plays in the proof.<ref group=proof name=p>Since Cantor's proof has not been published in English, an English translation is given alongside the original German text, which is from {{harvnb|Cantor|1879|pp=5–7}}. The translation starts one sentence before the proof because this sentence mentions Cantor's 1874 proof. Cantor states it was printed in Borchardt's Journal. Crelle’s Journal was also called Borchardt’s Journal from 1856-1880 when [[Carl Wilhelm Borchardt]] edited the journal ({{harvnb|Audin|2011|p=80}}). Square brackets are used to identify this mention of Cantor's earlier proof, to clarify the translation, and to provide page numbers. Also, "{{lang|de|Mannichfaltigkeit|italic=no}}" (manifold) has been translated to "set" and Cantor's notation for closed sets (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) has been translated to [α,&nbsp;β]. Cantor changed his terminology from {{lang|de|Mannichfaltigkeit|italic=no}} to {{lang|de|Menge|italic=no}} (set) in his 1883 article, which introduced sets of [[ordinal number]]s ({{harvnb|Kanamori|2012|p=5}}). Currently in mathematics, a [[manifold]] is type of [[topological space]].

{| class="wikitable collapsible collapsed"
|-
! style="width: 47%;" | English translation
! style="width: 53%;" | German text
|- 
|[Page 5]<br>
&nbsp;.&nbsp;.&nbsp;.&nbsp;But this contradicts a very general theorem, which we have 
proved with full rigor in Borchardt's Journal, Vol. 77, page 260; namely, the following theorem:<br>
{{space|5}}''"If one has a simply [countably] infinite sequence''<br> 
{{space|12}}ω<sub>1</sub>,&nbsp;ω<sub>2</sub>,&nbsp;.&nbsp;.&nbsp;.&nbsp;,&nbsp;ω<sub>ν</sub>,&nbsp;.&nbsp;.&nbsp;.<br>
''of real, unequal numbers that proceed according to some rule, then in every given interval [α,&nbsp;β] a number η (and thus infinitely many of them) can be specified that does not occur in this sequence (as a member of it)."''

{{space|5}}In view of the great interest in this theorem, not only in the present discussion, but also in many other arithmetical as well as analytical relations, it might not be superfluous if we develop the argument followed there [Cantor's 1874 proof] more clearly here by using simplifying modifications.

{{space|5}}Starting with the sequence:<br>
{{space|12}}ω<sub>1</sub>,&nbsp;ω<sub>2</sub>,&nbsp;.&nbsp;.&nbsp;.&nbsp;,&nbsp;ω<sub>ν</sub>,&nbsp;.&nbsp;.&nbsp;.<br>
(which we give [denote by] the symbol (ω)) and an arbitrary interval [α,&nbsp;β], where α&nbsp;<&nbsp;β, we will now demonstrate that in this interval a real number η can be found that does ''not'' occur in (ω).

{{space|5}}I. We first notice that if our set (ω) is ''not everywhere dense'' in the interval [α,&nbsp;β], then within this interval another interval [γ,&nbsp;δ] must be present, all of whose numbers do not belong to (ω). From the interval [γ,&nbsp;δ], one can then choose any number for η. It lies in the interval [α,&nbsp;β] and definitely does ''not'' occur in our sequence (ω). Thus, this case presents no special considerations and we can move on to the ''more difficult'' case.

{{space|5}}II. Let the set (ω) be ''everywhere dense'' in the interval [α,&nbsp;β]. In this case, every interval [γ,δ] located in [α,β], however small, contains numbers of our sequence (ω). To show that, ''nevertheless,'' numbers η in the interval [α,&nbsp;β] exist that do not occur in (ω), we employ the following observation.

{{space|5}}Since some numbers in our sequence:<br>
{{space|12}}ω<sub>1</sub>,&nbsp;ω<sub>2</sub>,&nbsp;.&nbsp;.&nbsp;.&nbsp;,&nbsp;ω<sub>ν</sub>,&nbsp;.&nbsp;.&nbsp;.

|{{langx|de|[Seite 5]<br>
&nbsp;.&nbsp;.&nbsp;.&nbsp;Dem widerspricht aber ein sehr allgemeiner Satz, welchen wir in Borchardt's Journal, Bd. 77, pag. 260, mit aller Strenge bewiesen haben, nämlich der folgende Satz:

{{space|5}}''"Hat man eine einfach unendliche Reihe''<br>
{{space|12}}ω<sub>1</sub>,&nbsp;ω<sub>2</sub>,&nbsp;.&nbsp;.&nbsp;.&nbsp;,&nbsp;ω<sub>ν</sub>,&nbsp;.&nbsp;.&nbsp;.<br>
''von reellen, ungleichen Zahlen, die nach irgend einem Gesetz fortschreiten, so lässt sich in jedem vorgegebenen, Intervalle (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) eine Zahl η (und folglich lassen sich deren unendlich viele) angeben, welche nicht in jener Reihe (als Glied derselben) vorkommt."''

{{space|5}}In Anbetracht des grossen Interesses, welches sich an diesen Satz, nicht blos bei der gegenwärtigen Erörterung, sondern auch in vielen anderen sowohl arithmetischen, wie analytischen Beziehungen, knüpft, dürfte es nicht überflüssig sein, wenn wir die dort befolgte Beweisführung [Cantors 1874 Beweis], unter Anwendung vereinfachender Modificationen, hier deutlicher entwickeln.

{{space|5}}Unter Zugrundelegung der Reihe:<br>
{{space|12}}ω<sub>1</sub>,&nbsp;ω<sub>2</sub>,&nbsp;.&nbsp;.&nbsp;.&nbsp;,&nbsp;ω<sub>ν</sub>,&nbsp;.&nbsp;.&nbsp;.<br>
(welcher wir das Zeichen (ω) beilegen) und eines beliebigen Intervalles (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β), wo α&nbsp;<&nbsp;β ist, soll also nun gezeigt werden, dass in diesem Intervalle eine reelle Zahl η gefunden werden kann, welche in (ω) ''nicht'' vorkommt.

{{space|5}}I. Wir bemerken zunächst, dass wenn unsre Mannichfaltigkeit (ω) in dem Intervall (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β)  ''nicht überall-dicht'' ist, innerhalb dieses Intervalles ein anderes (γ&nbsp;.&nbsp;.&nbsp;.&nbsp;δ) vorhanden sein muss, dessen Zahlen sämmtlich nicht zu (ω) gehören; man kann alsdann für η irgend eine Zahl des Intervalls (γ&nbsp;.&nbsp;.&nbsp;.&nbsp;δ) wählen, sie liegt im Intervalle (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) und kommt sicher in unsrer Reihe (ω) ''nicht'' vor. Dieser Fall bietet daher keinerlei besondere Umstände; und wir können zu dem ''schwierigeren'' übergehen.

{{space|5}}II. Die Mannichfaltigkeit (ω) sei im Intervalle (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) ''überall-dicht''. In diesem Falle enthält jedes, noch so kleine in (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) gelegene Intervall (γ&nbsp;.&nbsp;.&nbsp;.&nbsp;δ) Zahlen unserer Reihe (ω). Um zu zeigen, dass ''nichtsdestoweniger'' Zahlen η im Intervalle (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) existiren, welche in (ω) nicht vorkommen, stellen wir die folgende Betrachtung an.

{{space|5}}Da in unserer Reihe:<br>
{{space|12}}ω<sub>1</sub>,&nbsp;ω<sub>2</sub>,&nbsp;.&nbsp;.&nbsp;.&nbsp;,&nbsp;ω<sub>ν</sub>,&nbsp;.&nbsp;.&nbsp;.
<br>|label=none|italic=unset}} 
|-
|[Page 6]<br>
definitely occur ''within'' the interval [α,&nbsp;β], one of these numbers must have the ''least index,'' let it be ω<sub>κ<sub>1</sub></sub>, and another: ω<sub>κ<sub>2</sub></sub> with the next larger index.

{{space|5}}Let the smaller of the two numbers ω<sub>κ<sub>1</sub></sub>, ω<sub>κ<sub>2</sub></sub> be denoted by α', the larger by β'. (Their equality is impossible because we assumed that our sequence consists of nothing but unequal numbers.)

{{space|5}}Then according to the definition:<br>
{{space|12}}α&nbsp;<&nbsp;α'&nbsp;<&nbsp;β'&nbsp;<&nbsp;β{{space|hair}},<br>
furthermore:<br>                           
{{space|17}}κ<sub>1</sub>&nbsp;<&nbsp;κ<sub>2</sub>{{space|hair}};<br>
and all numbers ω<sub>μ</sub> of our sequence, 
for which μ ≤ κ<sub>2</sub>, do ''not'' lie in the interior of the interval [α',&nbsp;β'], as is immediately clear from the definition of the numbers κ<sub>1</sub>, κ<sub>2</sub>. Similarly, let ω<sub>κ<sub>3</sub></sub> and ω<sub>κ<sub>4</sub></sub> be the two numbers of our sequence with smallest indices that fall in the ''interior'' of the interval [α',&nbsp;β'] and let the smaller of the numbers ω<sub>κ<sub>3</sub></sub>, ω<sub>κ<sub>4</sub></sub> be denoted by α<nowiki>''</nowiki>, the larger by β<nowiki>''</nowiki>.

{{space|5}}Then one has: <br> 
{{space|12}}α'&nbsp;< α<nowiki>''</nowiki>&nbsp;<&nbsp;β<nowiki>''</nowiki>&nbsp;<&nbsp;β'{{space|hair}},<br>
{{space|14}}κ<sub>2</sub>&nbsp;<&nbsp;κ<sub>3</sub>&nbsp;<&nbsp;κ<sub>4</sub>{{space|hair}};<br>
and one sees that all numbers ω<sub>μ</sub> of our sequence, for which μ&nbsp;≤&nbsp;κ<sub>4</sub>, do ''not'' fall into the ''interior'' of the interval [α<nowiki>''</nowiki>,&nbsp;β<nowiki>''</nowiki>].

{{space|5}} After one has followed this rule to reach an interval {{nowrap|[α<sup>(ν - 1)</sup>, β<sup>(ν - 1)</sup>]}}, the next interval is produced by selecting the first two (i. e. with lowest indices) numbers of our sequence (ω) (let them be {{nowrap|ω<sub>κ<sub>2ν - 1</sub></sub>}} and ω<sub>κ<sub>2ν</sub></sub>) that fall into the ''interior'' of {{nowrap|[α<sup>(ν - 1)</sup>,&nbsp;β<sup>(ν - 1)</sup>]}}. Let the smaller of these two numbers be denoted  by α<sup>(ν)</sup>, the larger by β<sup>(ν)</sup>.

{{space|5}}The interval [α<sup>(ν)</sup>,&nbsp;β<sup>(ν)</sup>] then lies in the ''interior'' of all preceding intervals and has the ''specific'' relation with our sequence (ω) that all numbers ω<sub>μ</sub>, for which μ ≤ κ<sub>2ν</sub>, ''definitely do not lie in its interior''. Since obviously:<br>
{{space|12}}{{nowrap|κ<sub>1</sub> < κ<sub>2</sub> < κ<sub>3</sub> <  . . . , ω<sub>κ<sub>2ν – 2</sub></sub> < ω<sub>κ<sub>2ν – 1</sub></sub> < ω<sub>κ<sub>2ν</sub></sub>{{space|hair}}, . . . }}<br>
and these numbers, as indices, are ''whole'' numbers, so:<br>
{{space|12}}κ<sub>2ν</sub>&nbsp;≥&nbsp;2ν{{space|hair}},<br>
and hence:<br>
{{space|12}}ν&nbsp;<&nbsp;κ<sub>2ν</sub>{{space|hair}};<br>
thus, we can certainly say (and this is sufficient for the following):

{{space|5}}''That if ν is an arbitrary whole number, the [real] quantity ω<sub>ν</sub> lies outside the interval [α<sup>(ν)</sup>&nbsp;.&nbsp;.&nbsp;.&nbsp;β<sup>(ν)</sup>].''

|{{langx|de|[Seite 6]<br>
sicher Zahlen ''innerhalb'' des Intervalls (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) vorkommen, so muss eine von diesen Zahlen den ''kleinsten Index'' haben, sie sei ω<sub>κ<sub>1</sub></sub>, und eine andere: ω<sub>κ<sub>2</sub></sub> mit dem nächst grösseren Index behaftet sein.

{{space|5}}Die kleinere der beiden Zahlen ω<sub>κ<sub>1</sub></sub>, ω<sub>κ<sub>2</sub></sub> werde mit α', die grössere mit β' bezeichnet. (Ihre Gleichheit ist ausgeschlossen, weil wir voraussetzten, dass unsere Reihe aus lauter ungleichen Zahlen besteht.)

{{space|5}}Es ist alsdann der Definition nach:<br>
{{space|12}}α&nbsp;<&nbsp;α'&nbsp;<&nbsp;β'&nbsp;<&nbsp;β{{space|hair}},<br>
ferner:<br>                           
{{space|17}}κ<sub>1</sub>&nbsp;<&nbsp;κ<sub>2</sub>{{space|hair}};<br>
und ausserdem ist zu bemerken, dass alle Zahlen ω<sub>μ</sub> unserer Reihe, 
für welche μ ≤ κ<sub>2</sub>, ''nicht'' im Innern des Intervalls (α'&nbsp;.&nbsp;.&nbsp;.&nbsp;β') liegen, wie aus der Bestimmung der Zahlen κ<sub>1</sub>, κ<sub>2</sub> sofort erhellt. Ganz ebenso mögen ω<sub>κ<sub>3</sub></sub>, ω<sub>κ<sub>4</sub></sub> die beiden mit den kleinsten Indices versehenen Zahlen unserer Reihen [see note 1 below] sein, welche in das ''Innere'' des Intervalls (α'&nbsp;.&nbsp;.&nbsp;.&nbsp;β') fallen und die kleinere der Zahlen ω<sub>κ<sub>3</sub></sub>, ω<sub>κ<sub>4</sub></sub> werde mit α<nowiki>''</nowiki>, die grössere mit β<nowiki>''</nowiki> bezeichnet.

{{space|5}}Man hat alsdann: <br> 
{{space|12}}α'&nbsp;< α<nowiki>''</nowiki>&nbsp;<&nbsp;β<nowiki>''</nowiki>&nbsp;<&nbsp;β'{{space|hair}},<br>
{{space|14}}κ<sub>2</sub>&nbsp;<&nbsp;κ<sub>3</sub>&nbsp;<&nbsp;κ<sub>4</sub>{{space|hair}};<br>
und man erkennt, dass alle Zahlen ω<sub>μ</sub> unserer Reihe, für welche μ&nbsp;≤&nbsp;κ<sub>4</sub> ''nicht'' in das ''Innere'' des Intervalls (α<nowiki>''</nowiki>&nbsp;.&nbsp;.&nbsp;.&nbsp;β<nowiki>''</nowiki>) fallen.

{{space|5}}Nachdem man unter Befolgung des gleichen Gesetzes zu einem Intervall {{nowrap|(α<sup>(ν - 1)</sup>, . . . β<sup>(ν - 1)</sup>)}} gelangt ist, ergiebt sich das folgende Intervall dadurch aus demselben, dass man die beiden ersten (d. h. mit niedrigsten Indices versehenen) Zahlen unserer Reihe (ω) aufstellt (sie seien ω<sub>κ<sub>2ν – 1</sub></sub> und ω<sub>κ<sub>2ν</sub></sub>), welche in das ''Innere'' von {{nowrap|(α<sup>(ν – 1)</sup> . . . β<sup>(ν – 1)</sup>)}} fallen; die kleinere dieser beiden Zahlen werde mit α<sup>(ν)</sup>, die grössere mit β<sup>(ν)</sup> bezeichnet.

{{space|5}}Das Intervall (α<sup>(ν)</sup>&nbsp;.&nbsp;.&nbsp;.&nbsp;β<sup>(ν)</sup>) liegt alsdann im ''Innern'' aller vorangegangenen Intervalle und hat zu unserer Reihe (ω) die ''eigenthümliche'' 
Beziehung, dass alle Zahlen ω<sub>μ</sub>, für welche μ ≤ κ<sub>2ν</sub> ''sicher nicht in seinem Innern'' liegen.  Da offenbar:<br>
{{space|12}}{{nowrap|κ<sub>1</sub> < κ<sub>2</sub> < κ<sub>3</sub> <  . . . , ω<sub>κ<sub>2ν – 2</sub></sub> < ω<sub>κ<sub>2ν – 1</sub></sub> < ω<sub>κ<sub>2ν</sub></sub>{{space|hair}}, . . . }}

und diese Zahlen, als Indices, ''ganze'' Zahlen sind, so ist:<br>
{{space|12}}κ<sub>2ν</sub>&nbsp;≥&nbsp;2ν{{space|hair}},<br>
und daher:<br>
{{space|12}}ν&nbsp;<&nbsp;κ<sub>2ν</sub>{{space|hair}};<br>
wir können daher, und dies ist für das Folgende ausreichend, gewiss sagen:

{{space|5}}''Dass, wenn ν eine beliebige ganze Zahl ist, die Grösse ω<sub>ν</sub> ausserhalb des Intervalls (α<sup>(ν)</sup>&nbsp;.&nbsp;.&nbsp;.&nbsp;β<sup>(ν)</sup>) liegt.''|label=none|italic=unset}}
|-
|[Page 7]<br>
{{space|5}}Since the numbers α',  α<nowiki>''</nowiki>,  α<nowiki>'''</nowiki>,&nbsp;.&nbsp;.&nbsp;., α<sup>(ν)</sup>,&nbsp;.&nbsp;.&nbsp;. are continually increasing by value while simultaneously being enclosed in the interval [α,&nbsp;β], they have, by a well-known fundamental theorem of the theory of magnitudes [see note 2 below], a limit that we denote by A, so that:<br>
{{space|12}}{{nowrap|A {{eq}} Lim α<sup>(ν)</sup>  for  ν {{eq}} ∞.}}

{{space|5}}The same applies to the numbers β', β<nowiki>''</nowiki>, β<nowiki>'''</nowiki>,&nbsp;.&nbsp;.&nbsp;., β<sup>(ν)</sup>,&nbsp;.&nbsp;.&nbsp;., which are continually decreasing and likewise lying in the interval [α,&nbsp;β]. We call their limit B, so that:<br> 
{{space|12}}{{nowrap|B {{eq}} Lim β<sup>(ν)</sup>  for  ν {{eq}} ∞.}}

{{space|5}}Obviously, one has:<br>
{{space|12}}{{nowrap|α<sup>(ν)</sup> < A ≤ B < β<sup>(ν)</sup>.}}

{{space|5}}But it is easy to see that the case A&nbsp;<&nbsp;B can ''not'' occur here since otherwise every number ω<sub>ν</sub> of our sequence would lie ''outside'' of the interval [A,&nbsp;B] by lying outside the interval [α<sup>(ν)</sup>,&nbsp;β<sup>(ν)</sup>]. So our sequence (ω) would ''not'' be ''everywhere dense'' in the interval [α,&nbsp;β], contrary 
to the assumption.

{{space|5}}Thus, there only remains the case A&nbsp;{{eq}}&nbsp;B and now it is demonstrated that the number:<br> 
{{space|12}}η&nbsp;{{eq}}&nbsp;A&nbsp;{{eq}}&nbsp;B<br> 
does ''not'' occur in our sequence (ω).

{{space|5}}If it were a member of our sequence, such as the ν<sup>th</sup>, then one would have: η {{eq}} ω<sub>ν</sub>.

{{space|5}}But the latter equation is not possible for any value of ν because η is in the ''interior'' of the interval [α<sup>(ν)</sup>,&nbsp;β<sup>(ν)</sup>], but ω<sub>ν</sub> lies ''outside'' of it.

|{{langx|de|[Seite 7]<br>
{{space|5}}Da die Zahlen α', α<nowiki>''</nowiki>, α<nowiki>'''</nowiki>,,&nbsp;.&nbsp;.&nbsp;., α<sup>(ν)</sup>,,&nbsp;.&nbsp;.&nbsp;. ihrer Grösse nach fortwährend wachsen, dabei jedoch im Intervalle (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) eingeschlossen sind, so haben sie, nach einem bekannten Fundamentalsatze der Grössenlehre, eine Grenze, die wir mit A bezeichnen, so dass:<br>
{{space|12}}{{nowrap|A {{eq}} Lim α<sup>(ν)</sup>  für  ν {{eq}} ∞.}}

{{space|5}}Ein Gleiches gilt für die Zahlen β', β<nowiki>''</nowiki>, β<nowiki>'''</nowiki>,&nbsp;.&nbsp;.&nbsp;., β<sup>(ν)</sup>,&nbsp;.&nbsp;.&nbsp;.  welche fortwährend abnehmen und dabei ebenfalls im Intervalle (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) liegen; wir nennen ihre Grenze B, so dass:<br>
{{space|12}}{{nowrap|B {{eq}} Lim β<sup>(ν)</sup> für ν {{eq}} ∞.}}

{{space|5}}Man hat offenbar:<br>
{{space|12}}{{nowrap|α<sup>(ν)</sup> < A ≤ B < β<sup>(ν)</sup>.}}

{{space|5}}Es ist aber leicht zu sehen, dass der Fall A&nbsp;<&nbsp;B hier ''nicht'' vorkommen kann; da sonst jede Zahl ω<sub>ν</sub>, unserer Reihe ''ausserhalb'' des Intervalles (A&nbsp;.&nbsp;.&nbsp;.&nbsp;B) liegen würde, indem ω<sub>ν</sub>, ausserhalb des Intervalls (α<sup>(ν)</sup> . . . β<sup>(ν)</sup>) gelegen ist; unsere Reihe (ω) wäre im Intervall (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) ''nicht überalldicht,'' gegen die Voraussetzung.

{{space|5}}Es bleibt daher nur der Fall A&nbsp;{{eq}}&nbsp;B übrig und es zeigt sich nun, dass die Zahl:<br>
{{space|12}}{{nowrap|η {{eq}} A {{eq}} B}}<br>
in unserer Reihe (ω) ''nicht'' vorkommt.

{{space|5}}Denn, würde sie ein Glied unserer Reihe sein, etwa das ν<sup>te</sup>, so hätte man: η {{eq}} ω<sub>ν</sub>.

{{space|5}}Die letztere Gleichung ist aber für keinen Werth von v möglich, weil η im ''Innern'' des Intervalls [α<sup>(ν)</sup>,&nbsp;β<sup>(ν)</sup>], ω<sub>ν</sub> aber ''ausserhalb'' desselben liegt.|label=none|italic=unset}}
|-
| colspan="2" | Note 1:  This is the only occurrence of "{{lang|de|unserer Reihen|italic=no}}" ("our sequences") in the proof. There is only one sequence involved in Cantor's proof and everywhere else "{{lang|de|Reihe|italic=no}}" ("sequence") is used, so it is most likely a typographical error and should be "{{lang|de|unserer Reihe|italic=no}}" ("our sequence"), which is how it has been translated.<br>
Note 2: {{lang|de|Grössenlehre|italic=no}}, which has been translated as "the theory of magnitudes", is a term used by 19th century German mathematicians that refers to the theory of [[Discrete mathematics|discrete]] and [[Linear continuum|continuous]] magnitudes. ({{harvnb|Ferreirós|2007|pp=41–42, 202}}.)
|}</ref>

In the first case, ''P'' is not dense in [''a'',&nbsp;''b'']. By definition, ''P'' is dense if and only if for all subintervals (''c'',&nbsp;''d'') of [''a'',&nbsp;''b''], there is an ''x''&nbsp;∈&nbsp;''P'' such that {{nowrap|''x'' ∈ (''c'', ''d'')}}. Taking the negation of each side of the "if and only if" produces: ''P'' is not dense in [''a'',&nbsp;''b''] if and only if there exists a subinterval (''c'',&nbsp;''d'') of [''a'',&nbsp;''b''] such that for all ''x''&nbsp;∈&nbsp;''P''{{space|hair|4}}:  {{space|hair|5}}{{nowrap|''x'' ∉ (''c'', ''d'')}}. Therefore, every number in (''c'',&nbsp;''d'') is not contained in the sequence ''P''.<ref group=proof name=p /> This case handles [[#Case1|case 1]] and [[#Case3|case 3]] of Cantor's 1874.
 
In the second case, ''P'' is dense in [''a'',&nbsp;''b'']. The denseness of ''P'' is used to [[recursively define]] a nested sequence of intervals that excludes all elements of ''P''. (Cantor's definition of this sequence is same as [[#Cantor's 1874 interval definition|his 1874 definition]] and he uses essentially his same α, β notation for the nested sequence of intervals.{{efn-ua|Cantor's notation only differs by the position of the dots. 1874 notation: {{nowrap|(α · · · β)}}, {{nowrap|(α' · · · β')}}, {{nowrap|(<nowiki>α'' · · · β''</nowiki>)}}, {{nowrap|· · ·}} ({{harvnb|Cantor|1874|p=261}}). 1879 notation: {{nowrap|(α . . . β)}}, {{nowrap|(α' . . . β')}}, {{nowrap|(<nowiki>α'' . . . β''</nowiki>)}}, {{nowrap|. . .}} ({{harvnb|Cantor|1879|p=4}}).}}) The [[Base case (recursion)|base case]] of the recursion is (''a''<sub>1</sub>, ''b''<sub>1</sub>) = (''a'', ''b''). The [[recursive step]] starts with the interval (''a''<sub>''n''</sub>, ''b''<sub>''n''</sub>) which contains infinitely many elements of ''P'' since ''P'' is dense in [''a'',&nbsp;''b''].
WORKING HERE! Then the construction of the next interval follows: The two members of ''P'' with the smallest indices are used to define ''a''<sub>''n''&nbsp;+&nbsp;1</sub> and ''b''<sub>''n''&nbsp;+&nbsp;1</sub>{{space|hair|4}}—{{space|hair|4}}namely, ''a''<sub>''n''&nbsp;+&nbsp;1</sub> is the least of these two members and  ''b''<sub>''n''&nbsp;+&nbsp;1</sub> is the greatest. [[#x_n not in|Cantor's 1874 proof]] demonstrates that for all&nbsp;''n''{{space|hair}}:{{space|hair}} {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}. The sequence ''a''<sub>''n''</sub> is increasing and bounded above by ''b'', so it has a limit ''a''<sub>∞</sub>, which satisfies ''a''<sub>''n''</sub>&nbsp;<&nbsp;''a''<sub>∞</sub>. The sequence ''b''<sub>''n''</sub> is decreasing and bounded below by ''a'', so it has a limit ''b''<sub>∞</sub>, which satisfies ''b''<sub>∞</sub>&nbsp;<&nbsp;''b''<sub>''n''</sub>. Also, ''a''<sub>''n''</sub>&nbsp;<&nbsp;''b''<sub>''n''</sub> implies ''a''<sub>∞</sub>&nbsp;≤&nbsp;''b''<sub>∞</sub>. Therefore, {{nowrap|''a''<sub>''n''</sub> < ''a''<sub>∞</sub> ≤ ''b''<sub>∞</sub> < ''b''<sub>''n''</sub>}}. If ''a''<sub>∞</sub>&nbsp;<&nbsp;''b''<sub>∞</sub>, then for every ''n'': ''x''<sub>''n''</sub>&nbsp;∉&nbsp;(''a''<sub>∞</sub>,&nbsp;''b''<sub>∞</sub>) because ''x''<sub>''n''</sub> is not in the larger interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). This contradicts ''P'' being dense in [''a'',&nbsp;''b'']. Therefore, ''a''<sub>∞</sub>&nbsp;=&nbsp;''b''<sub>∞</sub>. Since for all ''n'': {{nowrap|''a''<sub>∞</sub> ∈ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}} but {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}, the limit ''a''<sub>∞</sub> is a real number that is not contained in the sequence ''P''.<ref group=proof name=p /> This case handles [[#Case2|case 2]] of Cantor's 1874 proof.

In the [[#Example of Cantor's construction|Example of Cantor's construction]], the sequence ''P'' successive nested interval excludes rational numbers for two different reasons. It will exclude the finitely many rationals visited in the search for the first two rationals within the interval (these two rationals will have the least indices). These rationals are then used to form an interval that excludes the rationals visited in the search along with infinitely many more rationals. However, it still contains infinitely many rationals since our sequence of rationals is dense in [0, 1]. Forming this interval from the two rationals with the least indices guarantees that this interval excludes an initial segment of our sequence that contains at least two more members than the preceding initial segment. Since the denseness of our sequence guarantees that this process never ends, all rationals will be excluded.<ref group=proof name=p /> Because of the ordering of the rationals in our sequence, the [[Intersection (set theory)|intersection]] of the nested intervals is the [[#Number generated|set]] {{{sqrt|2}}&nbsp;&minus;&nbsp;1}.

==ADD to end of Cantor's 1879 proof==
In the [[#Example of Cantor's construction|Example of Cantor's construction]], each successive nested interval excludes rational numbers for two different reasons. It will exclude the finitely many rationals visited in the search for the first two rationals within the interval (these two rationals will have the least indices). These rationals are then used to form an interval that excludes the rationals visited in the search along with infinitely many more rationals. However, it still contains infinitely many rationals since our sequence of rationals is dense in [0,&nbsp;1]. Forming this interval from the two rationals with the least indices guarantees that this interval excludes an initial segment of our sequence that contains at least two more members than the preceding initial segment. Since the denseness of our sequence guarantees that this process never ends, all rationals will be excluded.<ref group=proof name=p /> Because of the ordering of the rationals in our sequence, the [[Intersection (set theory)|intersection]] of the nested intervals is the [[#Number generated|set]] {{{sqrt|2}}&nbsp;&minus;&nbsp;1}.{{efn-ua|Different orderings can produce nested intervals whose intersection is {''x''} for any ''x'': Let ''x''<sub>''n''</sub> be the [[Decimal approximation of a real number|decimal approximation]] of ''x'' to ''n''-digits. Starting with the interval [''x''<sub>0</sub>,&nbsp;''x''<sub>0</sub>&nbsp;+&nbsp;1] and continuing with the intervals [''x''<sub>''n''</sub>,&nbsp;''x''<sub>''n''</sub>&nbsp;+&nbsp;1/10<sup>''n''</sup>{{space|thin}}] for ''n''&nbsp;≥&nbsp;1 produces a sequence of intervals whose intersection is {''x''}.}}

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

== NEW PROOF ==

===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.{{efn-ua|This implies the rest of the theorem{{space|hair|4}}—{{space|hair|4}}namely, there are infinitely many numbers in [''a'',&nbsp;''b''] that are not contained in the given sequence. For example, let <math>[0,1]</math> be the interval and consider its [[subinterval]]s <math>[0, \tfrac{1}{2}],</math> <math>[\tfrac{3}{4},\tfrac{7}{8}],</math> <math>[\tfrac{15}{16}, \tfrac{31}{32}],</math> <math> \ldots.</math> Since these subintervals are [[pairwise disjoint]], applying the first part of the theorem to each subinterval produces infinitely many numbers in <math>[0,1]</math> that are not contained in the given sequence. In general, for the interval <math>[a, b],</math> apply the first part of the theorem to the subintervals <math>[a, a + \tfrac{1}{2}(b-a)],</math> <math>[a + \tfrac{3}{4}(b-a), a + \tfrac{7}{8}(b-a)],</math> <math>[a + \tfrac{15}{16}(b-a), a + \tfrac{31}{32}(b-a)],</math> <math>\ldots .</math>}}

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 the [[open interval]] (''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{{space|hair|4}}—{{space|hair|4}}that is, it generates a sequence of [[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>''L''</sub>,&nbsp;''b''<sub>''L''</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:
{{Anchor|Case1}}[[File:Cantor's first uncountability proof Case 1 svg.svg|thumb|350px|alt=Illustration of case 1. [[Real line]] containing closed interval [''a'',&nbsp;''b''] that contains nested open intervals (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) for ''n''&nbsp;= 1 to ''L''. Two distinct numbers ''y'' and one ''x''<sub>''n''</sub> are in (''a''<sub>''L''</sub>,&nbsp;''b''<sub>''L''</sub>).|Case 1: Last interval (''a''<sub>''L''</sub>, ''b''<sub>''L''</sub>)]]
:Case 1: There is a last interval (''a''<sub>''L''</sub>,&nbsp;''b''<sub>''L''</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.
{{Anchor|Case2}}[[File:Cantor's first uncountability proof Case 2 svg.svg|thumb|350px|alt=Illustration of case 2. Real line containing interval [''a'',&nbsp;''b''] that contains nested intervals (''a''<sub>''n''</sub>, ''b''<sub>''n''</sub>) for ''n''&nbsp;=&nbsp;1 to ∞. These intervals converge to ''a''<sub>∞</sub>.|Case 2: ''a''<sub>∞</sub> = ''b''<sub>∞</sub>]]
: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 ''x''<sub>''n''</sub> does not belong to (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). In symbols, ''a''<sub>∞</sub>&nbsp;[[∈]]&nbsp;(''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) but ''x''<sub>''n''</sub>&nbsp;[[∉]]&nbsp;(''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>).
{{Anchor|x_n not in}}
:{| class="wikitable collapsible collapsed"
! style="background: f5f5f5;" |'''Proof that for all&nbsp;''n''{{space|hair|2}}: {{nowrap|{{space|thin|2}}''x''<sub>''n''</sub>&nbsp;{{space|hair|2}}∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}'''&nbsp;{{space|thin|2}}
|- style="text-align: left; vertical-align: top; background: white" 
| style="padding-left: 1em; padding-right: 1em" | This is implied by the stronger result: For all&nbsp;''n'', (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) excludes ''x''<sub>1</sub>,&nbsp;...&nbsp;,&nbsp;''x''<sub>2''n''</sub>, which is proved 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>. (This proof is similar to a proof that Cantor published in 1879. The main difference is that Cantor's proof is embedded in a larger proof and uses notation from it. Our proof does not depend on this notation.<ref group=proof name=p />)
|}
{{Anchor|Case3}}[[File:Cantor's first uncountability proof Case 3 svg.svg|thumb|350px|alt=Illustration of case 3. Real line containing [''a'',&nbsp;''b''] that contains nested intervals (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) for ''n''&nbsp;=&nbsp;1 to ∞. These intervals converge to the closed interval [a<sub>∞</sub>,&nbsp;b<sub>∞</sub>]. The number y is in this interval.|Case 3: ''a''<sub>∞</sub> < ''b''<sub>∞</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 main difference between Cantor's proof and the above proof 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 uses the [[Interior (topology)|interior]] of the interval [''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>], which is the open interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). Generating open intervals combines Cantor's use of closed intervals and their interiors, which allows the [[#Cases|case diagrams]] to depict all the details of the proof.}}

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.<ref>{{harvnb|Gray|1994|p=822}}.</ref>

Cantor's 1879 proof is the same as his 1874 proof except for a new proof of the first part of his [[#Second theorem|second theorem]]: Given any sequence ''P'' 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 sequence ''P''. The new proof has only two cases. **Big proof ref goes here!**

Cantor's new proof first handles the case of the sequence ''P'' not being dense in the interval. Then it deals with the more difficult case of ''P'' being dense. This division into cases not only indicates which sequences are most difficult to handle, but it also reveals the important role denseness plays in the proof.<ref group=proof name=p />

In the first case, ''P'' is not dense in [''a'',&nbsp;''b'']. By definition, ''P'' is dense if and only if for all [[subset]]s (''c'',&nbsp; ''d'') of [''a'',&nbsp;''b''], there is an ''x''<sub>''n''</sub> in ''P'' such that ''x''<sub>''n''</sub> is in (''c'',&nbsp;''d''). Taking the negation of each side of the "if and only if" produces: ''P'' is not dense in [''a'',&nbsp;''b''] if and only if there exists a subset (''c'',&nbsp;''d'') of [''a'',&nbsp;''b''] such that for all ''x''<sub>''n''</sub> in ''P'', ''x''<sub>''n''</sub> is not in (''c'',&nbsp;''d''). Therefore, every number in (''c'',&nbsp;''d'') is not contained in the sequence ''P''.<ref group=proof name=p /> This case handles [[#Case1|case 1]] and [[#Case3|case 3]] of Cantor's 1874 proof. In the diagram for case 1, every ''x''<sub>''n''</sub> in (''a''<sub>''L''</sub>,&nbsp;''y'') is not in the sequence. In the diagram for case 3, every ''x''<sub>''n''</sub> in (''a''<sub>∞</sub>,&nbsp;''b''<sub>∞</sub>) is not in the sequence. 

In the second case, ''P'' is dense in [''a'',&nbsp;''b'']. The denseness of ''P'' is used to [[recursively define]] a nested sequence of intervals is used to prove that this nested sequence excludes all members of ''P''. The [[base case]] starts with the observation that since ''P'' is dense in [''a'',&nbsp;''b''], there are infinitely many real numbers in ''P'' that belong to (''a'',&nbsp;''b''). Let ''x''<sub>''k''<sub>1</sub></sub> be the real number with the least index ''k''<sub>1</sub> and let ''x''<sub>''k''<sub>2</sub></sub> be the real number with the next larger index ''k''<sub>2</sub>. Let ''a''<sub>1</sub> be the smaller of these two reals and let ''b''<sub>1</sub> be the larger. Then, {{nowrap|''a'' < ''a''<sub>1</sub> < ''b''<sub>1</sub> < ''b''}} and {{nowrap|''k''<sub>1</sub> < ''k''<sub>2</sub>}}. Since ''x''<sub>''k''<sub>1</sub></sub> and ''x''<sub>''k''<sub>2</sub></sub> are the reals in ''P'' with the least indexes, for all {{nowrap|''j''&nbsp;≤&nbsp;''k''<sub>2</sub>}}, **MAY NEED MORE** the numbers ''x''<sub>''j''</sub> are not in (''a''<sub>1</sub>,&nbsp;''b''<sub>1</sub>). **MAY NEED MORE** May want to prove this! If j < k2, then if xj is in (a1, b1), it canoot be xj in interval or xj would have been chosen instead of xk+1 or xk+2!!

The recursive part of the definition starts with the interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) and with the inequalities  {{nowrap|''a'' < ''a''<sub>1</sub> < ... < ''a''<sub>''n''</sub> < ''b''<sub>''n''</sub> < ... < ''b''<sub>1</sub> < ''b''}} and {{nowrap|''k''<sub>1</sub> < ''k''<sub>2</sub> < ... < ''k''<sub>2''n''{{space|thin}}−{{space|hair}}1</sub> < ''k''<sub>2''n''</sub>}} such that for all ''j''&nbsp;≤&nbsp;''k''<sub>2''n''</sub>, the numbers ''x''<sub>''j''</sub> are not in (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). Since ''P'' is dense in [''a'',&nbsp;''b''], there are infinitely many real numbers in ''P'' that belong to (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). Let ''x''<sub>''k''<sub>2''n''{{space|thin}}+{{space|hair}}1</sub></sub> be the real number with the least index ''k''<sub>2''n''{{space|thin}}+{{space|hair}}2</sub> and let ''x''<sub>2''n''{{space|thin}}+{{space|hair}}2</sub> be the real number with the next larger index ''k''<sub>2''n''{{space|thin}}+{{space|hair}}2</sub>. Let ''a''<sub>''n''{{space|thin}}+{{space|hair}}1</sub> be the smaller of these two reals and let ''b''<sub>''n''{{space|thin}}+{{space|hair}}1</sub> be the larger. Then, {{nowrap|''a''<sub>''n''</sub> < ''a''<sub>''n''{{space|thin}}+{{space|hair}}1</sub> < ''b''<sub>''n''{{space|thin}}+{{space|hair}}1</sub> < ''b''<sub>''n''</sub>}} and {{nowrap|''k''<sub>2''n''{{space|thin}}+{{space|hair}}1</sub> < ''k''<sub>2''n''{{space|thin}}+{{space|hair}}2</sub>}}. Since ''x''<sub>''k''<sub>1</sub></sub> and ''x''<sub>''k''<sub>2</sub></sub> are the reals in ''P'' with the least indexes **MAY NEED MORE** for all {{nowrap|''j''&nbsp;≤&nbsp;''k''<sub>2''n''{{space|thin}}+{{space|hair}}2</sub>}}, the numbers ''x''<sub>''j''</sub> are not in (''a''<sub>''n''{{space|thin}}+{{space|hair}}1</sub>,&nbsp;''b''<sub>''n''{{space|thin}}+{{space|hair}}1</sub>). **MAY NEED MORE HERE!**

The sequence ''a''<sub>''n''</sub> is increasing and bounded above by ''b'', so it has a limit ''a''<sub>∞</sub>, which satisfies ''a''<sub>''n''</sub>&nbsp;≤&nbsp;''a''<sub>∞</sub> for all ''n''. The sequence ''b''<sub>''n''</sub> is decreasing and bounded below by ''a'', so it has a limit ''b''<sub>∞</sub>, which satisfies ''b''<sub>∞</sub>&nbsp;≤&nbsp;''b''<sub>''n''</sub> for all ''n''. Also, ''a''<sub>''n''</sub>&nbsp;<&nbsp;''b''<sub>''n''</sub> implies ''a''<sub>∞</sub>&nbsp;≤&nbsp;''b''<sub>∞</sub>. Therefore, {{nowrap|''a''<sub>''n''</sub> ≤ ''a''<sub>∞</sub> ≤ ''b''<sub>∞</sub> ≤ ''b''<sub>''n''</sub>}}. If ''a''<sub>∞</sub>&nbsp;<&nbsp;''b''<sub>∞</sub>, then for every ''n'': ''x''<sub>''n''</sub>&nbsp;∉&nbsp;(''a''<sub>∞</sub>,&nbsp;''b''<sub>∞</sub>) because ''x''<sub>''n''</sub> is not in the larger interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). This contradicts ''P'' being dense in [''a'',&nbsp;''b'']. Therefore, ''a''<sub>∞</sub>&nbsp;=&nbsp;''b''<sub>∞</sub>. Since for all ''n'': {{nowrap|''a''<sub>∞</sub> ∈ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}} but {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}, the limit ''a''<sub>∞</sub> is a real number that is not contained in the sequence ''P''.<ref group=proof name=p /> **MAY NEED MORE HERE!** This case handles [[#Case2|case 2]] of Cantor's 1874 proof.

===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.{{efn-ua|This implies the rest of the theorem — namely, there are infinitely many numbers in [''a'',&nbsp;''b''] that are not contained in the given sequence. For example, let <math>[0,1]</math> be the interval and consider its [[subinterval]]s <math>[0, \tfrac{1}{2}],</math> <math>[\tfrac{3}{4},\tfrac{7}{8}],</math> <math>[\tfrac{15}{16}, \tfrac{31}{32}],</math> <math> \ldots.</math> Since these subintervals are [[pairwise disjoint]], applying the first part of the theorem to each subinterval produces infinitely many numbers in <math>[0,1]</math> that are not contained in the given sequence. In general, for the interval <math>[a, b],</math> apply the first part of the theorem to the subintervals <math>[a, a + \tfrac{1}{2}(b-a)],</math> <math>[a + \tfrac{3}{4}(b-a), a + \tfrac{7}{8}(b-a)],</math> <math>[a + \tfrac{15}{16}(b-a), a + \tfrac{31}{32}(b-a)],</math> <math>\ldots .</math>}}

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 the [[open interval]] (''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]]. 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>''L''</sub>,&nbsp;''b''<sub>''L''</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:

{{Anchor|Case1}}[[File:Cantor's first uncountability proof Case 1 svg.svg|thumb|350px|alt=Diagram of case 1. [[Real line]] containing closed interval [''a'',&nbsp;''b''] that contains nested open intervals (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) for ''n''&nbsp;= 1 to ''L''. Two distinct numbers ''y'' and one ''x''<sub>''n''</sub> are in (''a''<sub>''L''</sub>,&nbsp;''b''<sub>''L''</sub>).|Case 1: Last interval (''a''<sub>''L''</sub>, ''b''<sub>''L''</sub>)]]
:Case 1: There is a last interval (''a''<sub>''L''</sub>,&nbsp;''b''<sub>''L''</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.
{{Anchor|Case2}}[[File:Cantor's first uncountability proof Case 2 svg.svg|thumb|350px|alt=Diagram of case 2. Real line containing interval [''a'',&nbsp;''b''] that contains nested intervals (''a''<sub>''n''</sub>, ''b''<sub>''n''</sub>) for ''n''&nbsp;=&nbsp;1 to ∞. These intervals converge to ''a''<sub>∞</sub>.|Case 2: ''a''<sub>∞</sub> = ''b''<sub>∞</sub>]]
: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.
{{Anchor|x_n not in}}
:{| class="wikitable collapsible collapsed"
! style="background: f5f5f5;" |'''Proof that for all&nbsp;''n''{{space|hair}}:&nbsp; {{nowrap|''x''<sub>''n''</sub>&nbsp;{{space|hair}}[[∉]]&nbsp;(''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}'''&nbsp;
|- style="text-align: left; vertical-align: top; background: white" 
| style="padding-left: 1em; padding-right: 1em" | This is implied by the stronger result: For all&nbsp;''n'', (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) excludes ''x''<sub>1</sub>,&nbsp;...&nbsp;,&nbsp;''x''<sub>2''n''</sub>, which is proved 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>. (This proof is similar to a proof that Cantor published in 1879. The main difference is that Cantor's proof is embedded in a larger proof and uses notation from it. Our proof does not depend on this notation.<ref group=proof name=p />)
|}
{{Anchor|Case3}}[[File:Cantor's first uncountability proof Case 3 svg.svg|thumb|350px|alt=Diagram of case 3. Real line containing [''a'',&nbsp;''b''] that contains nested intervals (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>) for ''n''&nbsp;=&nbsp;1 to ∞. These intervals converge to the closed interval [a<sub>∞</sub>,&nbsp;b<sub>∞</sub>]. The number y is in this interval.|Case 3: ''a''<sub>∞</sub> < ''b''<sub>∞</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>

In the first case, ''P'' is not dense in [''a'',&nbsp;''b'']. By definition, ''P'' is dense if and only if for all {{nowrap|(''c'', ''d'') ⊆ [''a'',&nbsp;''b'']}}, there is an ''x''&nbsp;∈&nbsp;''P'' such that {{nowrap|''x'' ∈ (''c'', ''d'')}}. Taking the negation of each side of the "if and only if" produces: ''P'' is not dense in [''a'',&nbsp;''b''] if and only if there exists a {{nowrap|(''c'', ''d'') ⊆ [''a'',&nbsp;''b'']}} such that for all ''x''&nbsp;∈&nbsp;''P'', we have {{nowrap|''x'' ∉ (''c'', ''d'')}}. Thus, every number in (''c'',&nbsp;''d'') is not contained in the sequence ''P''.<ref group=proof name=p /> This case handles [[#Case1|case 1]] and [[#Case3|case 3]] of Cantor's 1874 proof.

In the second case, ''P'' is dense in [''a'',&nbsp;''b'']. The denseness of ''P'' is used to [[recursively define]] a nested sequence of intervals that excludes all elements of ''P''. The definition begins with
''a''<sub>1</sub>&nbsp;=&nbsp;''a'' and ''b''<sub>1</sub>&nbsp;=&nbsp;''b''. The definition's inductive case starts with the interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>), which because of the denseness of ''P'' contains infinitely many elements of ''P''. From these elements of ''P'', the two with smallest indices are used to define ''a''<sub>''n''&nbsp;+&nbsp;1</sub> and ''b''<sub>''n''&nbsp;+&nbsp;1</sub>; namely, ''a''<sub>''n''&nbsp;+&nbsp;1</sub> is the least of these two numbers and  ''b''<sub>''n''&nbsp;+&nbsp;1</sub> is the greatest. [[#x_n not in|Cantor's 1874 proof]] demonstrates that for all&nbsp;''n''{{space|hair}}:{{space|hair}} {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}. The sequence ''a''<sub>''n''</sub> is increasing and bounded above by ''b'', so it has a limit ''c'', which satisfies ''a''<sub>''n''</sub>&nbsp;<&nbsp;''c''. The sequence ''b''<sub>''n''</sub> is decreasing and bounded below by ''a'', so it has a limit ''d'', which satisfies ''d''&nbsp;<&nbsp;''b''<sub>''n''</sub>. Also, ''a''<sub>''n''</sub>&nbsp;<&nbsp;''b''<sub>''n''</sub> implies ''c''&nbsp;≤&nbsp;''d''. Therefore, {{nowrap|''a''<sub>''n''</sub> < ''c'' ≤ ''d'' < ''b''<sub>''n''</sub>}}. If ''c''&nbsp;<&nbsp;''d'', then for every ''n'': ''x''<sub>''n''</sub>&nbsp;∉&nbsp;(''c'',&nbsp;''d'') because ''x''<sub>''n''</sub> is not in the larger interval (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>). This contradicts ''P'' being dense in [''a'',&nbsp;''b'']. Therefore, ''c''&nbsp;=&nbsp;''d''. Since for all ''n'': {{nowrap|''c'' ∈ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}} but {{nowrap|''x''<sub>''n''</sub> ∉ (''a''<sub>''n''</sub>,&nbsp;''b''<sub>''n''</sub>)}}, the limit ''c'' is a real number that is not contained in the sequence ''P''.<ref group=proof name=p /> This case handles [[#Case2|case 2]] of Cantor's 1874 proof.

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

== Accessibility ==
Accessibility. For screen readers: used [[Template:lang-de]] to enclose German sentences in notes.

===Deutsch===
{{langx|de|Seite 5: Dem widerspricht aber ein sehr allgemeiner Satz, welchen wir in Borchardt's Journal, Bd. 77, pag. 260, mit aller Strenge bewiesen haben, nämlich der folgende Satz:|label=none|italic=invert}}

===Francais===
{{langx|fr|mit}}

Seite 5: Dem widerspricht aber ein sehr allgemeiner Satz, welchen wir in Borchardt's Journal, Bd. 77, pag. 260, mit aller Strenge bewiesen haben, nämlich der folgende Satz:

{{langx|de|''Liegt'' P ''theilweise oder ganz im Intervalle'' (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β), ''so kann der bemerkenswerthe Fall eintreten, dass'' jedes noch so kleine ''in (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) enthaltene Intervall (γ&nbsp;.&nbsp;.&nbsp;.&nbsp;δ) Punkte von'' P ''enthält. In einem solchen Falle wollen wir sagen, dass'' P im Intervalle ''(α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) ''überall-dicht'' sei.|label=none|italic=invert}}}}

{{space|5}}''"Hat man eine einfach unendliche Reihe''<br>
{{space|12}}ω<sub>1</sub>,&nbsp;ω<sub>2</sub>,&nbsp;.&nbsp;.&nbsp;.&nbsp;,&nbsp;ω<sub>ν</sub>,&nbsp;.&nbsp;.&nbsp;.<br>
''von reellen, ungleichen Zahlen, die nach irgend einem Gesetz fortschreiten, so lässt sich in jedem vorgegebenen, Intervalle (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) eine Zahl η (und folglich lassen sich deren unendlich viele) angeben, welche nicht in jener Reihe (als Glied derselben) vorkommt."''
:If ''P'' lies partially or completely in the interval [α,&nbsp;β], then the remarkable case can happen that ''every'' intervals [γ,&nbsp;δ] contained in [α,&nbsp;β], ''no matter how small'', contains points of ''P''.  In such a case, we will say that ''P'' is ''everywhere dense in the interval'' [α,&nbsp;β].{{efn-ua|The original German text from {{harvnb|Cantor|1879|p=2}} (Cantor's closed set notation (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) is translated to [α,&nbsp;β]): {{langx|de|''Liegt'' P ''theilweise oder ganz im Intervalle'' (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β), ''so kann der bemerkenswerthe Fall eintreten, dass'' jedes noch so kleine ''in (α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) enthaltene Intervall (γ&nbsp;.&nbsp;.&nbsp;.&nbsp;δ) Punkte von'' P ''enthält. In einem solchen Falle wollen wir sagen, dass'' P im Intervalle ''(α&nbsp;.&nbsp;.&nbsp;.&nbsp;β) ''überall-dicht'' sei.|label=none|italic=invert}}}}

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

==To change to US-PD==

===Example ===
:File: "[[Cantor's first set theory article]]"
:Click on Cantor photo
:Click on More details
:Click on Edit (at top of page)
:Change or add to Permission = Template:PD-old or Template:PD-old|PD-other

==Photo info==
===Cantor===
:{{Information
:|Description    = en|1=Georg Cantor}}
:|Source         =https://opc.mfo.de/detail?photo_id=10525
:|Author         =unknown|Author}}
:|Date           =circa 1870
:|Permission     =PD-old}}
:}}

===Perron===
:{{Information
:|Description=en|1=German mathematician Oskar Perron (1880-1975) at Munich in 1948. }}
:|Source=https://opc.mfo.de/detail?photo_id=3261
:|Author=Jacobs, Konrad
:|Date=1948
:|permission=OTRS 2008042410024381}} Template:cc-by-sa-2.0-de}}
:|other_versions=
:}}

:DEFAULTSORT:Perron, Oskar}}
:Category:1948 in Munich]]
:Category:Pictures from Oberwolfach Photo Collection]]
:Category:Oskar Perron (mathematician)]]

===Fraenkel===
:int:filedesc}} ==
:Information
:|Description=en|1=[[:en:Abraham Fraenkel|Abraham Halevi (Adolf) Fraenkel]], German-born Israeli mathematician, first Dean of Mathematics as the Hebrew University of Jerusalem and Rector of the University; 1956, recipient of the Israel Prize for exact sciences (1956); member of the Israel Academy of Sciences and Humanities; Zionist, member of the Jewish National Council and the Jewish Assembly of Representatives under the British mandate, belonged to the "Mizrachi"}}
:|Source=The David B. Keidan Collection of Digital Images from the Central Zionist Archives
:        (via http://id.lib.harvard.edu/images/olvwork485526/catalog Harvard University Library])
:|Author=unknown|author}}
:|Date=between 1939 and 1949
:|Permission=
:|other_versions=
}}

int:license-header}} ==
PD-Israel}}

:Category:Abraham Fraenkel]]
:Category:Photographs from the Central Zionist Archives]]
:Notation:PHG\1110747
:Original number:110747
:Name of photographer/institution:Unknown
:Copyright:By the archives

===Weierstrass===

:int:filedesc}} ==
:Source: from de:Image:Karl_Weierstrass.jpg, 
:from http://www.sil.si.edu/digitalcollections/hst/scientific-identity/explore.htm

:Category:Karl Weierstraß]]
:Category:Rectors of Humboldt-Universität zu Berlin]]

:int:license-header}} ==
:PD-Art|PD-old-70}}

:Category:Artworks missing infobox template]]

===Kronecker===

:int:filedesc}} ==
:Information
:|Description=Leopold Kronecker
:|Source=http://www.britannica.com/EBchecked/media/28346/Kronecker-1865
:|Author={{unknown|author}}
:|Date=1865
:|Permission=PD-old-70}}
:|other_versions=
:}}

:Category:Leopold Kronecker]]

===Dedekind===

:int:filedesc}} ==
:{{Information
:|Description= Photo de Richard Dedekind vers 1870
:|Source=http://dbeveridge.web.wesleyan.edu/wescourses/2001f/chem160/01/Photo_Gallery_Science/Dedekind/FrameSet.htm
:|Date=<nowiki>{{original upload date|2007-02-10}}</nowiki>
:|Author= not found
:|Permission=La photo date de plus de 150 ans (en effet, nous sommes en 2020), elle est dans le domaine public
:|other_versions=
:}}

== {{int:license-header}} ==
{{PD-old}}

[[:Category:Richard Dedekind]]