Cantor's first set theory article

${\displaystyle F_{n}}$

${\displaystyle \leq n.}$

${\displaystyle {\frac {a}{b}}}$

${\displaystyle {\frac {c}{d}}}$

${\displaystyle {\frac {a+c}{b+d}}.}$

${\displaystyle {\frac {a}{b}}}$

${\displaystyle {\frac {c}{d}}}$

${\displaystyle F_{b+d}.}$

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

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

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

The ${\displaystyle p_{n}}$ and ${\displaystyle q_{n}}$ sequences satisfy the equations:^[16]

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

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

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

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

and for even n, the interval's endpoints are reversed: ${\displaystyle \left({\frac {p_{n}}{q_{n}}},{\frac {p_{n}+p_{n-1}}{q_{n}+q_{n-1}}}\right)\!.}$

This is true for the first interval since:

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

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

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

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

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

In this inequality, ${\displaystyle {\frac {p_{k}}{q_{k}}}}$ has the smallest denominator, so the second fraction is the mediant of ${\displaystyle {\frac {p_{k+1}}{q_{k+1}}}}$ and ${\displaystyle {\frac {p_{k}}{q_{k}}},}$ which equals ${\displaystyle {\frac {p_{k+1}+p_{k}}{p_{k+1}+q_{k}}}.}$

This implies: ${\displaystyle {\frac {p_{k}+p_{k-1}}{q_{k}+q_{k-1}}}<{\frac {p_{k+1}}{q_{k+1}}}<{\frac {p_{k+1}+p_{k}}{p_{k+1}+q_{k}}}<{\frac {p_{k}}{q_{k}}}.}$

Therefore, the (k + 1)-st interval is ${\displaystyle \left({\frac {p_{k+1}}{q_{k+1}}},{\frac {p_{k+1}+p_{k}}{p_{k+1}+q_{k}}}\right)\!.}$

This is the desired interval; ${\displaystyle {\frac {p_{k+1}}{q_{k+1}}}}$ is the left endpoint because k + 1 is even. Thus, the inductive hypothesis is true for the (k + 1)-st interval. For even k, the proof is similar. This completes the inductive proof.

Since the right endpoints of the intervals are decreasing and every other endpoint is ${\displaystyle {\frac {p_{2n-1}}{q_{2n-1}}},}$ their limit equals ${\displaystyle \lim _{n\to \infty }{\frac {p_{n}}{q_{n}}}.}$ The left endpoints have the same limit because they are increasing and every other endpoint is ${\displaystyle {\frac {p_{2n}}{q_{2n}}}.}$ As mentioned above, this limit is the continued fraction ${\displaystyle [0;2,2,\dots ],}$ which equals ${\displaystyle {\sqrt {2}}-1.}$^[17]

The recursive step starts with the interval (a_n–1, b_n–1), the inequalities k₁ < k₂ < . . . < k_2n–2 < k_2n–1 and a < a₁ < . . . < a_n–1 < b_n–1 . . . < b₁ < b, and the fact that the interval (a_n–1, b_n–1) excludes the first 2n –2 members of the sequence P — that is, x_m ∉ (a_n–1, b_n–1) for m ≤ k_2n–2. Since P is dense in [a, b], there are infinitely many numbers of P in (a_n–1, b_n–1). Let x_k2n –1 be the number with the least index and x_k2n be the number with the next larger index, and let a_n be the smaller and b_n be the larger of these two numbers. Then, k_2n –1 < k_2n, a_n–1 < a_n < b_n < b_n–1, and (a_n, b_n) is a proper subinterval of (a_n–1, b_n–1). Combining these inequalities with the ones for step n –1 of the recursion produces k₁ < k₂ < . . . < k_2n–1 < k_2n and a < a₁ < . . . < a_n < b_n . . . < b₁ < b. Also, x_m ∉ (a_n, b_n) for m = k_2n–1 and m = k_2n since these x_m are the endpoints of (a_n, b_n). This together with (a_n–1, b_n–1) excluding the first 2n –2 members of sequence P implies that the interval (a_n, b_n) excludes the first 2n members of P — that is, x_m ∉ (a_n, b_n) for m ≤ k_2n. Therefore, for all n, x_n ∉ (a_n, b_n) since n ≤ k_2n.^{[proof 1]}

The sequence a_n is increasing and bounded above by b, so the limit A = lim_n → ∞ a_n exists. Similarly, the limit B = lim_n → ∞ b_n exists since the sequence b_n is decreasing and bounded below by a. Also, a_n < b_n implies A ≤ B. If A < B, then for every n: x_n ∉ (A, B) because x_n is not in the larger interval (a_n, b_n). This contradicts P being dense in [a, b]. Hence, A = B. For all n, A ∈ (a_n, b_n) but x_n ∉ (a_n, b_n). Therefore, A is a number in [a, b] that is not contained in P.^{[proof 1]}

The proof is by contradiction and starts by assuming that the real numbers in ${\displaystyle [0,1]}$ can be written as a sequence:

${\displaystyle (\mathrm {I} )\;\;\omega _{1},\,\omega _{2},\,\omega _{3},\,\ldots ,\,\omega _{n},\,\ldots }$

An increasing sequence is extracted from this sequence by letting   ${\displaystyle \omega _{1}^{1}=}$ the first term${\displaystyle ,\ \omega _{1}^{2}=}$ the next largest term following ${\displaystyle \omega _{1}^{1},\ \omega _{1}^{3}=}$ the next largest term following ${\displaystyle \omega _{1}^{2},}$  and so forth. The same procedure is applied to the remaining members of the original sequence to extract another increasing sequence. By continuing this process of extracting sequences, one sees that the sequence ${\displaystyle (\mathrm {I} )}$ can be decomposed into the infinitely many sequences:^[22]

${\displaystyle (1)\;\;\omega _{1}^{1},\,\omega _{1}^{2},\,\omega _{1}^{3},\,\ldots ,\,\omega _{1}^{n},\,\ldots }$

${\displaystyle (2)\;\;\omega _{2}^{1},\,\omega _{2}^{2},\,\omega _{2}^{3},\,\ldots ,\,\omega _{2}^{n},\,\ldots }$

${\displaystyle (3)\;\;\omega _{3}^{1},\,\omega _{3}^{2},\,\omega _{3}^{3},\,\ldots ,\,\omega _{3}^{n},\,\ldots }$

${\displaystyle \ \ \vdots }$

Let ${\displaystyle [p,q]}$ be an interval such that no term of sequence (1) lies in it. For example, let ${\displaystyle p}$ and ${\displaystyle q}$ satisfy ${\displaystyle \omega _{1}^{1}<p<q<\omega _{1}^{2}.}$ Then ${\displaystyle \omega _{1}^{1}<p<q<\omega _{1}^{n}}$ for ${\displaystyle n\geq 2,}$ so no term of sequence (1) lies in ${\displaystyle [p,q].}$^[22]

Now consider whether the terms of the other sequences lie outside ${\displaystyle [p,q].}$ All terms of some of these sequences may lie outside of ${\displaystyle [p,q];}$ however, there must be some sequence such that not all its terms lie outside ${\displaystyle [p,q].}$ Otherwise, the numbers in ${\displaystyle [p,q]}$ would not be contained in sequence ${\displaystyle (\mathrm {I} ),}$ contrary to the initial hypothesis. Let sequence ${\displaystyle (k)}$ be the first sequence that contains a term in ${\displaystyle [p,q]}$ and let ${\displaystyle \omega _{k}^{n}}$ be the first term. Since ${\displaystyle p<\omega _{k}^{n}<q,}$ let ${\displaystyle p_{1}}$ and ${\displaystyle q_{1}}$ satisfy ${\displaystyle p<p_{1}<q_{1}<\omega _{k}^{n}<q.}$ Then ${\displaystyle [p,q]}$ is a proper superset of ${\displaystyle [p_{1},q_{1}]}$ (in symbols, ${\displaystyle [p,q]\supsetneq [p_{1},q_{1}]}$). Also, the terms of sequences ${\displaystyle (1),(2),\ldots ,(k-1)}$ lie outside of ${\displaystyle [p_{1},q_{1}].}$^[22]

Repeat the above argument starting with ${\displaystyle [p_{1},q_{1}]\!:\,}$ Let sequence ${\displaystyle (k_{1})}$ be the first sequence containing a term in ${\displaystyle [p_{1},q_{1}]}$ and let ${\displaystyle \omega _{k_{1}}^{n}}$ be the first term. Since ${\displaystyle \ p_{1}<\omega _{k_{1}}^{n}<q_{1},}$ let ${\displaystyle p_{2}}$ and ${\displaystyle q_{2}}$ satisfy ${\displaystyle p_{1}<p_{2}<q_{2}<\omega _{k_{1}}^{n}<q_{1}.}$ Then ${\displaystyle [p_{1},q_{1}]\supsetneq [p_{2},q_{2}]}$ and the terms of sequences ${\displaystyle (k_{1}),\ldots ,(k_{2}-1)}$ lie outside of ${\displaystyle [p_{2},q_{2}].}$^[22]

One sees that it is possible to form an infinite sequence of nested intervals ${\displaystyle [p,q]\supsetneq [p_{1},q_{1}]\supsetneq [p_{2},q_{2}]\supsetneq \ldots }$ such that:
      the members of the ${\displaystyle 1^{\text{st}},2^{\text{nd}},\ldots ,(k-1)^{\text{st}}}$ sequence lie outside ${\displaystyle [p,q];}$
      the members of the ${\displaystyle k^{\text{th}},\ldots ,(k_{1}-1)^{\text{st}}}$ sequence lie outside ${\displaystyle [p_{1},q_{1}];}$
      the members of the ${\displaystyle (k_{1})^{\text{th}},\ldots ,(k_{2}-1)^{\text{st}}}$ sequence lie outside ${\displaystyle [p_{2},q_{2}];}$
      ${\displaystyle \ldots ;}$^[22]

Since ${\displaystyle p_{n}}$ and ${\displaystyle q_{n}}$ are bounded monotonic sequences, the limits ${\displaystyle \lim _{n\to \infty }p_{n}}$ and ${\displaystyle \lim _{n\to \infty }q_{n}}$ exist. Also, ${\displaystyle p_{n}<q_{n}}$ for all ${\displaystyle n}$ implies ${\displaystyle \lim _{n\to \infty }p_{n}\leq \lim _{n\to \infty }q_{n}.}$ Hence, there is at least one number ${\displaystyle \eta }$ in ${\displaystyle (0,1)}$ that lies in all the intervals ${\displaystyle [p,q]}$ and ${\displaystyle [p_{n},q_{n}].}$ Namely, ${\displaystyle \eta }$ can be any number in ${\displaystyle [\lim _{n\to \infty }p_{n},\lim _{n\to \infty }q_{n}].}$ This implies that ${\displaystyle \eta }$ lies outside all the sequences ${\displaystyle (1),(2),(3),\ldots ,}$ contradicting the initial hypothesis that sequence ${\displaystyle (\mathrm {I} )}$ contains all the real numbers in ${\displaystyle [0,1].}$ Therefore, the set of all real numbers is uncountable.^[22]