Continued fractions and strange homeomorphisms.

Usually one thinks of real numbers represented by a sequence (possibly infinite) of numbers between 0 and 9. For example

[tex]34,140414\dots[/tex]

One can use various bases like binary, hexadesimal, but the most common is decimal, although with the growing trend of computer science the other bases also gain popularity. It is clear what a finite such string means. Say 1,2 is one and one fifth. The infite sequence is a little bit harder, but is conveniently defined as the sum of an infinite series. For example 1,212121… is

[tex]1\cdot 1+2\cdot 10^{-1}+1\cdot 10^{-2}+2\cdot 10^{-3}+\dots[/tex]

This sum always converges because it is dominated by a geometric series (exercise), but there is one tiny problem. Namely now

[tex]1 = 0,999\dots,[/tex]

This problem is unavoidable by going from one base to another. In binary representation we have

[tex]1 = 0,111\dots.[/tex]

The representation is not unique. It suggests a question:

Is there a way to represent real numbers in a unique way?
and
Why should we limit ourselves to some finite list of numbers (like 0…9)?

The answer is continued fractions. There are several articles on them in Wikipedia, but I didn’t find any (satisfactory) proof of Theorem 1 below.

A continued fraction is a sequence (finite or not) of positive natural numbers which represents uniquely a positive real number. Moreover this sequence is finite if and only if it represents a rational number. I will now expose the basic theory of continued fractions and in the end I’ll show how to use them to construct a homeomorphism between [tex](\mathbb{R}\setminus \mathbb{Q}) [/tex] and [tex](\mathbb{R}\setminus \mathbb{Q})^n[/tex] for any [tex]n[/tex].

From now on in this post I call positive natural numbers (1,2,3,…) just numbers and real numbers just reals.

So, what is a continued fraction? Given a sequence of numbers of length four

[tex]a=(a_0,a_1,a_2,a_3)[/tex]

let

[tex]r(a)=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3}}}.[/tex]

Then [tex]r(a)[/tex] is a real whose continued fraction is [tex]a[/tex]. This real is often denoted by

[tex][a_0;a_1,a_2,a_3].[/tex]

More generally, let us define a continued fraction of length [tex]k[/tex] by induction. Let [tex]a[/tex] be a finite sequence of numbers of length [tex]k[/tex]. The first element of the sequence can be zero, but not others. If [tex]k=1[/tex], then [tex]a=(a_0)[/tex] and we put [tex]r(a)=a_0[/tex]. Suppose [tex]r(a)[/tex] is defined for sequences of length [tex]k[/tex] and let [tex]a[/tex] be a sequence of length [tex]k+1[/tex]. Let

[tex]b=(a_1,\dots,a_{k})[/tex],

so [tex]b[/tex] is [tex]a[/tex] without the first number, [tex]a_0[/tex]. Now define

[tex]r(a)=a_0+\frac{1}{r(b)}[/tex].

Note that [tex]r(b)[/tex] is defined by the induction hypothesis.

Suppose now that we have an infinite sequence [tex]a=(a_0,a_1,\dots)[/tex]. What is [tex]r(a)[/tex]? We simply define it as the limit

[tex]r(a)=\lim_{n\to \infty}r(a\restriction n),[/tex]

where [tex]a\restriction n=(a_0,\dots,a_{n-1})[/tex] is the initial subsequence of [tex]a[/tex] of length [tex]n[/tex].

(A) Every continued fraction represents a real.

Theorem 1 For any sequence [tex]a[/tex] of positive natural numbers the limit
[tex]r(a)=\lim_{n\to \infty}r(a\restriction n)[/tex] exists.

This theorem is not trivial, because if one substitutes “number” by “complex number”, it is not any more true. The following proof is a product of a discussion with Daisuke Ikegami. I found also some proof on the web, but I didn’t understand it.

Proof. Suppose an infinite sequence [tex]a=(a_0,a_1,a_2,\dots)[/tex] is given. Denote by [tex]s_n[/tex] the “[tex]n[/tex]:th partial continued fraction,”
[tex]s_n=r(a\restriction n)[/tex]
Next we have to be tricky with the “when the denominator gets bigger the ratio gets smaller”. Using this we get

(1) [tex]s_1\leqslant s_3\leqslant s_5\leqslant\cdots[/tex]
(2) [tex]s_2\ge s_4\ge s_6\ge\cdots[/tex]
(3) for any [tex]n,\,s_{2n}\ge s_{2n+1}[/tex]

To show this, define for each number [tex]n[/tex] a function [tex]f_n\colon \mathbb{R_+}\to\mathbb{R}[/tex] such that for every [tex]x[/tex]

[tex]f_n(x)=r(a_0,\dots,a_{n-1},x),[/tex]

i.e. replace the last item of the continued fraction by [tex]x[/tex]. For convention [tex]f_0(x)=x[/tex]. Note that [tex]f_n(x)=r(a_0,\dots,a_{n-1}+\frac{1}{x})=f_{n-1}(a_{n-1}+\frac{1}{x})[/tex]. It is now easy to see that [tex]f_0[/tex] is increasing and if [tex]f_n[/tex] is increasing, then [tex]f_{n+1}[/tex] is decreasing and vice versa. Now moving from [tex]s_3[/tex] to [tex]s_5[/tex] corresponds to replacing [tex]a_3[/tex] by the larger number

[tex]a_3+\frac{1}{a_4+\frac{1}{a_5}}[/tex]

and because [tex]f_4[/tex] is increasing, we get [tex]s_3\leqslant s_5[/tex]. Similarly for any odd [tex]n[/tex], [tex]s_n\leqslant s_{n+2}[/tex]. The same argument works for (2) and (3). Now the Calculus Student notices that we have two bounded monotone sequences [tex](s_{2n+1})[/tex] and [tex](s_{2n})[/tex], so both converge. We have to show that they converge to the same value. For that it is enough to show that [tex]s_{2n}-s_{2n+1}[/tex] approaches zero. Let us prove a stronger statement by induction on [tex]n[/tex]: whenever [tex](b_0,\dots,b_{n-1})[/tex] is any sequence of numbers and [tex]k[/tex] is any number, then

[tex]|r(b_0,\dots,b_{n-1})-r(b_0,\dots,b_{n-1},k)|<\frac{1}{n}[/tex].

I call this property continuity and will come back to it later. Continuity clearly implies [tex]s_{2n}-s_{2n+1}\leqslant\frac{1}{n}[/tex]. For n=1 our claim is

[tex]|b_0-(b_0+\frac{1}{k})|=|\frac{1}{k}|\leqslant 1. [/tex]

Suppose the claim holds for sequences of length n and consider

[tex] |r(b_0,\dots,b_{n-1},b_{n})-r(b_0,\dots,b_{n-1},b_{n},k)|[/tex]

[tex]=|b_0+\frac{1}{r(b_1,\dots,b_{n-1},b_{n})}-(b_0+\frac{1}{r(b_1,\dots,b_{n-1},b_{n},k)}|[/tex]

Denote [tex]t=r(b_1,\dots,b_{n-1},b_{n})[/tex] and [tex]s=r(b_1,\dots,b_{n-1},b_{n},k)[/tex]. By the induction hypothesis [tex]|s-t|\leqslant\frac{1}{n}[/tex] and because numbers are positive natural numbers, we have [tex]s,t\ge 1[/tex]. Denote [tex]v=\min\{s,t\}[/tex]. Continuing the above:

[tex]= |\frac{1}{s}-\frac{1}{t}|<|\frac{1}{v}-\frac{1}{v+\frac{1}{n}}| = |\frac{1}{nv(v+\frac{1}{n})}|\leqslant |\frac{1}{n+1}|.[/tex]

In the first inequality above we use the fact that [tex]x\mapsto x^{-1}[/tex] is decreasing and if [tex]s<t[/tex], then [tex](s+\frac{1}{n})[/tex] is further to the right from [tex]s[/tex] than [tex]t[/tex] and if [tex]t<s[/tex] the same for [tex]t+\frac{1}{n}[/tex]. In the last inequality we use that [tex]v\ge 1[/tex]. This completes the proof. [tex]\square[/tex]

(B) Every real is represented by a continued fraction

Let [tex]x[/tex] be a positive real. Define [tex]x_0=x [/tex] and [tex]a_0[/tex] to be the integer part of it, i.e. the largest integer smaller than [tex]x_0[/tex]. Then define [tex]x_{n+1}=\frac{1}{x_n-a_n}[/tex] and let [tex]a_{n+1}[/tex] be the integer part of [tex]x_{n+1}[/tex]. For rational number [tex]x[/tex] this process terminates after finitely many steps: it is easy to see that the reduced denominator of [tex]x_{n+1}[/tex] is strictly smaller than that of [tex]x_n[/tex], and so [tex]x_n[/tex] is an integer for some [tex]n[/tex]. On the other hand if [tex]a[/tex] is a finite sequence, then clearly r(a) is rational.

To see that this continued fraction represents [tex]x[/tex] and not some other real number, show by induction that

[tex]x=r(a_0,\dots,a_n,x_{n+1})[/tex]

whence by the continuity argument in the proof of Theorem 1 we have

[tex]x-r(a_0,\dots,a_n) = |r(a_0,\dots,a_n,x_{n+1})-r(a_0,\dots,a_n)| \leqslant \frac{1}{n}.[/tex]

(C) Uniqueness

Let us now verify that every real is represented by a unique continued fraction. This is simple. Suppose we have two continued fractions such that [tex]r(a_0,\dots,a_n) = r(b_0,\dots,b_n)[/tex]. They are of the form [tex]a_0+\varepsilon[/tex] and [tex]b_0+\varepsilon'[/tex]. Since both epsilons are between zero and one, we conclude [tex]a_0=b_0[/tex]. Continuing this we get [tex]a_n=b_n[/tex] by induction.

Homeomorphisms

Let us denote by [tex]\mathcal{N}[/tex] the space of all infinite sequences of natural numbers and by [tex]\mathcal{N}^*[/tex] the space of all countable (finite and infinite) sequences of natural numbers. By the above (A), (B) and (C), the function [tex]r[/tex] which assignes a real to a sequence in [tex]\mathcal{N}^*[/tex] is a bijection. Let us define a topology on [tex]\mathcal{N}^*[/tex] as follows. For any finite sequence [tex]s\in\mathcal{N}^*[/tex] let [tex]U_s[/tex] consist of all sequences [tex]t[/tex] which begin with [tex]s[/tex], i.e.[tex]t\restriction n=s[/tex], where [tex]n[/tex] is the length of [tex]s[/tex] and [tex]t\restriction n[/tex] means the initial subsequence of [tex]t[/tex] of length [tex]n[/tex]. The sets [tex]U_s[/tex] form a basis for a topology. Thus the basic neighbourhoods of a point [tex]x\in \mathcal{N}^*[/tex] are the sets [tex]U_{x\restriction n}[/tex]. Now from the property that I called continuity in the proof of Theorem 1 it follows that both [tex]r[/tex] and [tex]r^{-1}[/tex] are continuous with respect to that topology: for the former one for any [tex]\varepsilon[/tex] take [tex]n[/tex] such that [tex]\frac{1}{n}[/tex] is less than [tex]\varepsilon[/tex] and the corresponding neighbourhood; for latter, for a neightbourhood of the form [tex]U_{x\restriction n}[/tex] take [tex]\delta[/tex] to be something less than [tex]\frac{1}{n}[/tex].

Hence the space [tex]\mathcal{N}^*[/tex] is homeomorphic to the real numbers. Since the infinite sequences are presicely those who get mapped to the irrational numbers, the space [tex]\mathcal{N}[/tex] is homeomorphic to the space of irrational numbers [tex]\mathbb{R}\setminus\mathcal{Q}[/tex].

Now let us define a map [tex]f\colon\mathcal{N}\to \mathcal{N}\times \mathcal{N}[/tex] such that a sequence [tex](a_n)_{n=0}^\infty[/tex] gets mapped to the pair of sequences given by [tex]\langle (a_{2n})_{n=0}^\infty,(a_{2n+1})_{n=0}^\infty\rangle[/tex]. This is a homeomorphism (exercise) and so provides a homeomorphism between [tex](\mathbb{R}\setminus \mathbb{Q}) [/tex] and [tex](\mathbb{R}\setminus \mathbb{Q})^2[/tex].

There is also a homeomorphism between the space of irrational numbers and the space of sequences of irrational numbers:

The space [tex]\mathcal{N}[/tex] is in fact precisely the space of all functions from [tex]\mathbb{N}[/tex] to [tex]\mathbb{N}[/tex] equipped with the standard product topology.
Denote by [tex]A^B[/tex] the space of all functions from [tex]A[/tex] to [tex]B[/tex]. So we have [tex]\mathcal{N}=\mathbb{N}^{\mathbb{N}}[/tex]. But we all know that there is a bijection [tex]p\colon \mathbb{N}\times \mathbb{N}\to \mathbb{N}[/tex]. Using this bijection we obtain a homeomorphism between the space [tex]\mathbb{N}^{\mathbb{N}\times\mathbb{N}}[/tex] and [tex]\mathcal{N}[/tex]. (The homeomorphism being [tex]f\mapsto p\circ f[/tex]) On the other hand each function [tex]f\colon \mathbb{N}\times \mathbb{N}\to \mathbb{N}[/tex] can be thought as a sequence of functions: for each [tex]n,\,f(n,\cdot)\colon \mathbb{N}\to \mathbb{N}[/tex]. This gives

[tex]\mathbb{N}^{\mathbb{N}\times \mathbb{N}}=(\mathbb{N}^{\mathbb{N}})^{\mathbb{N}}.[/tex]

So we get that the space of irrational numbers is homeomorphic to the space of all sequences of irrational numbers.

These techniques are central in descriptive set theory, and is used in particular to show the proper growth of the Borel hierarchy and that there are Analytic non-Borel sets.

Exercise (a) Using continued fractions define a surjective continuous map from the unit interval to the unit square. (b) Is it possible that such a map is differentiable at every point?