# Cantor’s Lemma¶

A (closed) interval, \([a,b]\) is a set of numbers: \(\{x: a\leq x\leq b\}\). Intervals can contain other intervals: \([a,b]\subset [c,d]\) if and only if \(a\leq c\) and \(d\leq b\).

The next lemma allows defining limits without knowing what they are, or showing that a sequence of intervals has a point in common.

Assume \(a_n\leq b_n\) are two sequences, \(a_n\) monotonically increasing and \(b_n\) monotonically decreasing. Also assume that the sequence \(b_n-a_n\) converges to \(0\).

These sequences can be thought of a sequence of intervals. The monotonicity requirements mean that each interval contains all following ones. The convergence requirement says that the limit of the lengths of the intervals is \(0\).

Since \(b_n\) is decreasing, \(b_n\leq b_1\), and so \(a_n\leq b_1\). Therefore, \(a_n\) is bounded, and so has a limit, \(a\). For similar reasons, \(b_n\) is bounded and so has a limit, \(b\).

By the results on the limits of addition and negation, \(b-a=0\), so \(b=a\). Call the limit \(c\). Limits for monotnic sequences are the bounds, so \(a_n\leq c\leq b_n\) for every \(n\).

If \(d<c\) the because \(c\) is the least upper bound on \(a_n\), for some \(n\), \(d < a_n\), and therefore \(d\notin [a_n,b_n]\). Similarly, if \(d>c\), some \(b_n\) is smaller than \(d\), and therefore \(d\notin [a_n,b_n]\).

The only number that is common to all intervals is \(c\).

This result is known as “Cantor’s Lemma”.

Here is an application of this lemma: if \(f:N\to [0,1]\) is a function there is a number \(x\), \(f(n)\neq x\) for every \(n\).

Define a sequence by induction.

\(a_0=0\) and \(b_0=1\).

look at \(f(n)\). For \(n+1\), define \(c_n=b_n-a_n\). \([a_n,b_n]\) is the union of three intervals:

- \([a_n,a_n+c_n/3]\)
- \([a_n+c_n/3,a_n+2c_n/3]\)
- \([a_n+2c_n/3,b_n]\)

Not all of them can contain \(f(n)\), because the intersection of all three is empty. For \([a_{n+1},b_{n+1}]\), choose the smallest that does not contain \(f(n)\)

Note that by induction, \(0<=b_n-a_n = 3^{-n}<1/n\) and so the conditions for Cantor’s Lemma are fullfilled.

Let \(c\) be the common limit. By the \(n+1`st stage, :math:`c!=f(n)\). This proves the result.

This result is often summarized as “there are more real numbers between \(0\) and \(1\) than