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]