Baire space homeomorphic to irrationals

Undoubtedly, there are many good introductions to continued fractions, where you can learn about them much more than what I mention below. See, for example, the resources and links given in the Wikipedia article. This article about infinite continued fractions also contains at least those facts, that are needed for this proof.

I tried to start from scratch (i.e., I assumed no knowledge of continued fractions), and tried to derive only the results needed in the proof that the map from the OP is a homeomorphism. It's for the reader to judge to which extent I succeeded. (But very probably I have achieved that - at least for someone who is not already familiar with properties of continued fractions - the short proof mentioned in Brian M. Scott's comment will seem much more attractive. That proof is indeed much shorter and slicker. A comparison of the two proofs is explained at the end of this post.) $\newcommand{\dcc}[1]{\lfloor{#1}\rfloor}\newcommand{\Z}{\mathbb Z}\newcommand{\N}{\mathbb N}\newcommand{\R}{\mathbb R}\newcommand{\Q}{\mathbb Q}$

---

Let $\N=\{1,2,\dots\}$. (I.e., for the purposes of this question, let us not count zero as a natural number.)

First let us make our notions clear.

We will use the notation $$[a_0;a_1,a_2,\dots,a_n]=a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{ \ddots + \cfrac1{a_n}}}}.$$ It is clear what a finite continued fraction is - we can simply calculate the value of the above number.

What is an infinite continued fraction $$[a_0;a_1,a_2,\dots]=a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{ \ddots }}}$$ determined by a sequence $(a_0,a_1,a_2,a_3,\dots)$ with $a_0\in\Z$ and $a_1,a_2,\dots\in\N$? The natural thing is to define it as the limit $$\lim\limits_{n\to\infty}[a_0;a_1,a_2,\dots,a_n]$$ provided that this limit exists.

We will try to show that the above limit exists for every such sequence. Moreover, the limit is always an irrational number and every irrational number can be expressed in this way.

We will call the finite continued fractions $[a_0;a_1,a_2,\dots,a_n]$ convergents of the infinite continued fraction $[a_0;a_1,a_2,\dots,a_n,\dots]$

If we want to work only with numbers in the interval $(0,1)$, we have $a_0=0$. But let us allow $a_0$ to be any integer and let us have a look at some properties of continued fractions in general.

Although we have introduced continued factions with all $a_i$'s having integer values, it is sometimes useful to allow also real values. This allows us, for example, to combine the continued fractions in the following way: $$[a_0;a_1,a_2]=[a_0;a_1+\frac1{a_2}].$$ Similar trick will be used in the proof of the following observation, which will be very useful and which we will use repeatedly.

Claim 1 (monotonicity). The function $t\mapsto [a_0;a_1,a_2,\dots,a_n,t]$ defined for $t\in(0,\infty)$ is monotonous, it is decreasing for even $n$ and increasing for odd $n$. (In particular, this function is injective.)

Proof. This can be shown by induction on $n$.

$1^\circ$ The function $t\mapsto a_0+\frac1t$ is decreasing in $t$.

$2^\circ$ It suffices to notice that $$[a_0; a_1,\dots,a_{n-1},a_n,t]=[a_0; a_1,\dots,a_{n-1},a_n+\frac1t]$$ and use the inductive hypothesis. (We know the function $g(x)=[a_0; a_1,\dots,a_{n-1},x]$ is monotonous and construct a new function $f(t)=g(a_n+\frac1t)$. If $g$ was increasing, the new function $f$ is decreasing and vice versa.)

Claim 2. For any sequence $(a_0,a_1,a_2,\dots)$ (with $a_0\in\Z$ and $a_i\in\N$ for $i>0$) we have $$[a_0;a_1,\dots,a_{2n}]\le[a_0;a_1,\dots,a_{2n},a_{2n+1},a_{2n+2}],$$ i.e., the sequence of even convergents is increasing; $$[a_0;a_1,\dots,a_{2n-1}]\ge[a_0;a_1,\dots,a_{2n-1},a_{2n},a_{2n+1}],$$ i.e., the sequence of odd convergence is decreasing; $$[a_0;a_1,\dots,a_{2n}]\le[a_0;a_1,\dots,a_{2n},a_{2n+1}],$$ i.e., odd convergents are bigger than even convergents.

This is illustrated nicely in the following picture, which was taken from here.

Proof. Use Claim 1 and observe that $$[a_0;a_1,\dots,a_{2n},a_{2n+1},a_{2n+2}]=[a_0;a_1,\dots,a_{2n}+\frac1{a_{2n+1}+\frac1{a_{2n+2}}}] \text{ and }a_{2n}\le a_{2n}+\frac1{a_{2n+1}+\frac1{a_{2n+2}}}$$ $$[a_0;a_1,\dots,a_{2n-1},a_{2n},a_{2n+1}]=[a_0;a_1,\dots,a_{2n-1}+\frac1{a_{2n}+\frac1{a_{2n+1}}}] \text{ and }a_{2n-1}\le a_{2n-1}+\frac1{a_{2n}+\frac1{a_{2n+1}}}$$ $$[a_0;a_1,\dots,a_{2n},a_{2n+1}]=[a_0;a_1,\dots,a_{2n}+\frac1{a_{2n+1}}] \text{ and }a_{2n}\le a_{2n}+\frac1{a_{2n+1}}$$

Claim 3 The distance between $[a_0;a_1,\dots,a_n]$ and $[a_0;a_1,\dots,a_n+1]$ is at most $\frac1{n+1}$.

Proof. This can be shown by induction:

$1^\circ$ $\left(a_0+\frac1{a_1}\right)-\left(a_0+\frac1{a_1+1}\right)=\frac1{a_1}-\frac1{a_1+1}=\frac1{a_1(a_1+1)}\le\frac1{1\cdot(1+1)}=\frac12.$

$2^\circ$ Suppose the claim is true for finite continued fractions of length $(n-1)$. That means that the distance between $[0;a_2,\dots,a_{n-1},a_n]$ and $[0;a_2,\dots,a_{n-1},a_n+1]$ is at most $\frac1n$. Let $c$ be the bigger of these two numbers, and $d$ be the smaller one. The distance between $[a_0;a_1,a_2,\dots,a_{n-1},a_n]$ and $[a_0;a_1,a_2,\dots,a_{n-1},a_n+1]$ is precisely $$\frac1{a_1+d}-\frac1{a_1+c} \overset{(1)}\le \frac1{a_1+d}-\frac1{a_1+d+\frac1n} \overset{(2)}\le \frac11-\frac1{1+\frac1n} = 1- \frac{n}{n+1}=\frac1{n+1}.$$ (The inequality (1) follows from $c\le d+\frac1n$. The inequality (2) follows from the fact that the function $f(t)=\frac1t-\frac1{t+\frac1n}=\frac{\frac1n}{t(t+\frac1n)}$ is decreasing and $a_1+d\ge1$.)

Claim 4. For any given sequence $(a_0,a_1,a_2,\dots)$ with $a_0\in\Z$ and $a_1,a_2,\dots\in\N$ the convergents $[a_0;a_1,\dots,a_n]$ converge to some number $x$. This number will be denoted as $x:=[a_0;a_1,a_2,\dots]$.

Proof. We have shown that even convergents form an increasing sequence, and odd convergents form a decreasing sequence. Since both sequences are bounded, each of them has a limit. Since the difference between $n$-th terms is at most $\frac1{2n}$, they both converge to the same limit $x$.

Claim 5. For any sequence of integers $a_1,a_2,\dots\in\N$ the infinite continued fraction $x=[0;a_1,a_2,\dots]$ belongs to the interval $(0,1)$.

Proof. From Claim 2 we see that each convergent is smaller than $[0;a_1,a_2,a_3]=\frac1{a_1+\frac1{a_2+\frac1{a_3}}}$. Then also the limit of the convergents fulfill the inequality $$x\le \frac1{a_1+\frac1{a_2+\frac1{a_3}}} < \frac1{a_1}\le 1.$$ Similarly, each convergent is bigger than $[0;a_1,a_2]$, hence the limit $$x\ge \frac1{a_1+\frac1{a_2}}>0.$$

Claim 6. The infinite continued fraction $x=[a_0;a_1,a_2,\dots,a_n,\dots]$ is between $[a_0;a_1,\dots,a_n]$ and $[a_0;a_1,\dots,a_n+1]$ for each $n$.

This follows from monotonicity of the function $t\mapsto [0; a_1,\dots,a_n+t]$ after plugging in the values $t=0$, $t=1$ and $t=[0;a_{n+1},a_{n+2},\dots]$. (From Claim 5 we know that $0<[0;a_{n+1},a_{n+2},\dots]<1$.)

Claims 7. Every irrational number can be expressed as an infinite continued fraction.

Proof. An irrational number $x\notin\Q$ can be expressed as $x=\dcc{x}+(x-\dcc{x})$, where $a_0=\dcc{x}$ is an integer and the decimal part $(x-\dcc{x})$ is an irrational number in the interval $(0,1)$. Hence it suffices to show the claim for the number from this interval.

Suppose we are given an irrational number $x\in(0,1)$.

We will construct by induction for each $n\in\mathbb N$ numbers $a_n\in\mathbb N$ and $x_n\in(0,1)\setminus\mathbb Q$ such that $$x=[0;a_1,a_2,\dots,a_n+x_n]=\cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{ \ddots + \cfrac1{a_n+x_n}}}}.$$

$1^\circ$ We want to write $x=\cfrac1{a_1+x_1}$, where $a_1\in\mathbb N$ and $x_1\in(0,1)$. Clearly, we have to choose $a_1$ in a such way that $\cfrac1{a_1}>x>\cfrac1{a_1+1}$, which is equivalent to $a_1<\frac1x<a_1+1$. So the only possible choice for $a_1$ is $\dcc{\frac1x}$.

If we put $x_1=\frac1x-\dcc{\frac1x}$, then we have $x_1+a_1=\frac1x$, i.e., $\frac1x=\frac1{a_1+x_1}$. It is clear that $x_1\in(0,1)$. The number $x_1$ must be irrational. (If $x_1$ were rational, then $x=1/(a_1+x_1)$ would be a rational number, too.)

$2^\circ$ Suppose we already have the first $(n-1)$ numbers with the required properties, i.e. $$x=[0;a_1,a_2,\dots,a_{n-1}+x_{n-1}].$$ Repeating the first step with $x_{n-1}$ instead of $x$, we choose $a_n=\dcc{\frac1{x_{n-1}}}$ and $x_n=\frac1{x_{n-1}}-a_n$ to get $x_{n-1}=\frac1{a_n+x_n}$. In this way we get $$x=[0;a_1,a_2,\dots,a_{n-1},a_n+x_n].$$

Now we get (using Claim 1 - monotonicity) that $x$ is between $[0;a_1,a_2,\dots,a_{n-1},a_n]$ and $[0;a_1,a_2,\dots,a_{n-1},a_n+1]$. This implies that the distance between $x$ and $[0;a_1,a_2,\dots,a_{n-1},a_n]$ is at most $\frac1{n+1}$.

This shows that $$[0;a_1,a_2,\dots,a_{n-1},a_n,\dots,]=\lim\limits_{n\to\infty} [0;a_1,a_2,\dots,a_{n-1},a_n]=x.$$

Claim 8. Every rational number $\frac pq\in(0,1)$ can be expressed as a finite continued fraction (of length at most $p$).

Consequently, every rational number can be expressed as a finite continued fraction.

Proof. Induction on $p$.

$1^\circ$ If $p=1$ we have $\frac1q=[0;q]$.

If $p=2$ then either $\frac pq = \frac2{2k}=\frac1k$, which reduces this to $p=1$, or $\frac pq=\frac2{2k+1}=\frac1{\frac{2k+1}2}=\frac1{k+\frac12}=[0;k,2]$.

$2^\circ$ For $\frac pq$ we can express $q=ap+r$ with $0\le r<p$. If $r=0$ then $\frac pq = \frac 1a = [0;a]$. If $r\ne 0$ then $$\frac pq = \frac p{ap+r}=\frac1{a+\frac rp}=[0;a,a_1,\dots,a_n]$$ where $\frac rp=[0;a_1,\dots,a_n]$ is the finite continued fraction for $\frac rp$. (Which exists by the inductive hypothesis.)

Claim 9. Two different infinite continued fractions cannot be equal to the same number.

Proof. Let $x\ne y$ and
$x=[a_0;a_1,a_2,\dots]$,
$y=[b_0;b_1,b_2,\dots]$.

If the sequences determining these two numbers are not the same, then there is the smallest $n$ such that $a_n\ne b_n$. W.l.o.g. we can assume that $a_n<b_n$.

The case $n=0$ can be easily solved using Claim 5. So we will assume $n>0$. Then we have
$x=[a_0;a_1,a_2,\dots,a_{n-1},a_n,a_{n+1},\dots]$
$y=[a_0;a_1,a_2,\dots,a_{n-1},b_n,b_{n+1},\dots]$

To see that $x\ne y$ we will use the fact that the function $f(t)=[a_0;a_1,a_2,\dots,a_{n-1},t]$ is injective. We have $x=f(s_1)$ and $y=f(s_2)$ for
$s_1=[a_n;a_{n+1},\dots]$
$s_2=[b_n;b_{n+1},\dots]$.

Now $$s_1=a_n+\frac1{a_{n+1}+\frac1{a_{n+2}+\frac1\ddots}} \le a_{n}+1 \le b_n < b_n+ \frac1{b_{n+1}+\frac1{b_{n+2}+\frac1\ddots}} = s_2.$$

Claim 10. If $x$ is a (value of a) finite continued fraction and $y$ is an infinite continued fraction, then $x\ne y$.

Proof. So we have
$x=[a_0;a_1,\dots,a_n]$
$y=[b_0;b_1,\dots,b_n,b_{n+1},\dots]$

First, we cannot have $a_0=b_0,a_1=b_1,\dots,a_n=b_n$, since this would mean that $x$ is one of the convergents of $y$. From Claim 2 we know that $x$ is then one of terms of a (strictly) monotone sequence which converges to $y$. (Depending on the parity of $n$, it is either the increasing sequence of even-length convergents or the decreasing sequence of odd-length convergents.) Then, clearly, $x\ne y$.

So there is smallest $m$ such that $a_m\ne b_m$.

We have
$x=[a_0;a_1,\dots,a_{m-1},a_m,\dots,a_n]$
$y=[a_0;a_1,\dots,a_{m-1},b_m,b_{n+1},\dots]$

This means that for $f(t)=[a_0;a_1,\dots,a_{m-1},t]$ and $s_1=[a_m;a_{m+1},\dots,a_n]$, $s_2=[b_m;b_{m+1},\dots,b_n]$ we have $x=f(s_1)$ and $y=f(s_2)$. Since $f$ is injective, it suffices to show that $s_1\ne s_2$.

Case I. $a_m<b_m$

$$s_1= a_m+\frac1{a_{m+1}+\frac1{\ddots+\frac1{a_n}}} \le a_m+1 \le b_m < b_m+\frac1{b_{m+1}+\frac1\ddots} =s_2.$$

Case II. $b_m<a_m$

$$s_2= b_m+\frac1{b_{m+1}+\frac1\ddots} \overset{(1)}<b_m+1 \le a_m \overset{(2)}\le a_m+\frac1{a_{m+1}+\frac1{\ddots+\frac1{a_n}}} =s_2$$ (The inequality (1) is strict according to Claim 5. Note that the same argument would not be valid if $y$ were a finite continued fraction. If $m=n$, the inequality (2) is in fact equality, so we cannot use strict inequality on that place.)

---

Summary.

Using the above observations we want to show that $$f\colon (a_0,a_1,a_2,\dots)\mapsto [a_0;a_1,a_2,\dots]$$ is a homeomorphism from $\Z\times\N^{\N}$ to $\R\setminus\Q$. (Basically the same arguments would work for continued fractions starting with $a_0=0$ and irrational numbers in the interval $(0,1)$.) Here both $\Z$ and $\N$ are considered with the discrete topology.

The map $f$ is bijective.

We know that each irrational number can be obtained as a continued fraction, and this can be done in only one way. Moreover, if we take any sequence from $\Z\times\N^{\N}$, the corresponding number cannot be rational (this follows from Claim 8 and Claim 10). So we see that $f$ is indeed a map from $\Z\times\N^{\N}$ to $\R\setminus\Q$ and it is surjective.

Claim 9 says that the map $f$ is injective.

The map $f$ is a homeomorphism.

The standard base for the product topology on $\Z\times\N^{\N}$ is the base consisting of sets $$\mathscr N_{a_0,a_1,\dots,a_n}=\{x\in\Z\times\N^{\N}; x_0=a_0, x_1=a_1,\dots,x_n=a_n\}.$$ I.e. the basic sets consist of sequences where the first $(n+1)$ coordinates are prescribed (and the remaining coordinates are arbitrary.)

Now let us consider an irrational number $x$, which corresponds to an infinite continued fraction $[a_0;a_1,\dots,a_n,a_{n+1},\dots]$. According to Claim 6 this number lies (strictly) between $[a_0;a_1,\dots,a_n]$ and $[a_0;a_1,\dots,a_n+1]$. Moreover, these numbers converge to $x$. Which means that in this way we obtain decreasing open intervals containing $x$, such that only $x$ belongs to all of these intervals. So these intervals intersected with $\R\setminus\Q$ form a local base at $x$.

Therefore we have a base for the topological space $\R\setminus\Q$ consisting of open intervals with the endpoints $[a_0;a_1,\dots,a_n]$ and $[a_0;a_1,\dots,a_n+1]$. Using monotonicity argument once again we can see that the irrationals in these intervals are precisely numbers with infinite continued fractions starting with $a_0,a_1,\dots,a_n$.

This shows that the bijection $f$ maps each basic set of $\Z\times\N^\N$ to a basic set of $\R\setminus\Q$. And the same is true for the inverse map $f^{-1}$.

Therefore, the two topologies have the same (up to a bijection) bases, hence they are the same (homeomorphic).

---

EDIT: Only after finishing the proof using continued fractions I took time and read in detail the proof given in these notes by Arnold W. Miller. (A link to this text was given in the comment above.) The proof is rather short and elegant, I recommend anyone interested in this question to have a look. (So I can feel somewhat silly for wasting time with much more complicated proof. But I have decided not to consider this a waste of time, but as an exercise in deriving some basic properties of continued fractions.)

Let me just very briefly compare the two approaches. In Miller's proof some system of open intervals with rational endpoints is constructed. These intervals are indexed by finite sequences of integers. In the proof using continued fractions we also constructed such intervals, namely the interval $I_{(a_0,a_1,\dots,a_n)}$ is the interval with the rational endpoints $[a_0;a_1,\dots,a_n]$ and $[a_0;a_1,\dots,a_{n+1}]$. If you have a look at the properties of the intervals constructed in the other proof, these intervals have rather similar properties. Perhaps one minor difference is that we cannot claim that closure of $I_{(a_0,\dots,a_n,a_{n+1})}$ is a subset of $I_{(a_0,\dots,a_n)}$. (For example, in our construction $I_{0,1}$ is the interval between the continued fractions $[0;1]$ and $[0;2]$, i.e. the interval $(\frac12,1)$. In the next step one of the intervals is the interval $I_{0,1,1}$ between $[0;1,1]$ and $[0;1,2]$, i.e., the interval $(\frac12,\frac23)$.) But even in the construction using continued fractions we could show that the closure of $I_{(a_0,\dots,a_n,a_{n+1},a_{n+2})}$ is a subset of $I_{(a_0,\dots,a_n)}$. Which means that we could use basically the same argument as in the other proof.

So I would dare to say that modulo some technical details (such as choice of indexing sets, difference I have just explained), the proof using continued fractions can be considered a special case of Miller's proof.

I have decided to post Arnold W. Miller's proof as a separate CW answer. The proof comes from his book Descriptive Set Theory and Forcing: How to Prove Theorems about Borel Sets the Hard Way. It is freely available here. (The same text was also published by Springer as a part Lecture Notes in Logic, here is projecteuclid link.)

I have two reasons for doing this. One is that I like the proof and in this way the proof will have more visibility than if it is just linked from comments and other answer. And also in this way some notation, which may not be familiar to all users reading this question, might be explained here.

---

What follows here is the exact copy of the text from Miller's notes. I have used the TeX-source which he published on his website. The only changes I have made were that I have replaced macros and I have modified it to use MarkDown.

Theorem. (Baire) $\omega^\omega$ is homeomorphic to the irrationals $\mathbb P$.

Proof. First replace $\omega$ by the integers $\mathbb Z$. We will construct a mapping from $\mathbb Z^\omega$ to $\mathbb P$. Enumerate the rationals $\mathbb Q=\{q_n: n\in\omega\}$. Inductively construct a sequence of open intervals $\langle I_s : s\in \mathbb Z^{<\omega}\rangle$ satisfying the following:

• $I_{\langle\rangle}=\mathbb R$, and for $s\not= \langle\rangle$ each $I_s$ is a nontrivial open interval in $\mathbb R$ with rational endpoints,
• for every $s\in \mathbb Z^{<\omega}$ and $n\in \mathbb Z\;\;\; I_{s\widehat{\ } n}\subseteq I_s$,
• the right end point of $I_{s\widehat{\ } n}$ is the left end point of $I_{s\widehat{\ } n+1}$,
• $\{I_{s\widehat{\ } n}: n\in \mathbb Z\}$ covers all of $I_s$ except for their endpoints,
• the length of $I_s$ is less than $1\over |s|$ for $s\not= \langle\rangle$, and
• the $n^{th}$ rational $q_n$ is an endpoint of $I_t$ for some $|t|\leq n+1$.

Define the function $f:\mathbb Z^{\omega}\rightarrow\mathbb P$ as follows. Given $x\in\mathbb Z^{\omega}$ the set $$\bigcap_{n\in\omega}I_{x\upharpoonright n}$$ must consist of a singleton irrational. It is nonempty because $$\operatorname{closure}(I_{x\upharpoonright n+1})\subseteq I_{x\upharpoonright n}.$$ It is a singleton because their diameters shrink to zero.

So we can define $f$ by $$\{f(x)\}=\bigcap_{n\in\omega}I_{x\upharpoonright n}.$$ The function $f$ is one-to-one because if $s$ and $t$ are incomparable then $I_s$ and $I_t$ are disjoint. It is onto since for every $u\in\mathbb P$ and $n\in\omega$ there is a unique $s$ of length $n$ with $u\in I_s$. It is a homeomorphism because $$f([s])=I_s\cap\mathbb P$$ and the sets of the form $I_s\cap\mathbb P$ form a basis for $\mathbb P$. $\hspace{5cm}\square$

Note that the map given is also an order isomorphism from $\mathbb Z^\omega$ with the lexicographical order to $\mathbb P$ with it's usual order.

---

Notation

Just in case someone is unfamiliar with some of the notation above.

$\omega=\{0,1,2,\dots\}$ denotes the set of all non-negative integers

The notation $A^{<\omega}$ is used for the set of all finite sequences of elements from $A$. In this proof we work with finite sequences of integers, i.e. with the set $\mathbb Z^{<\omega}$.

The symbol $s\widehat{\ }a$ stands for concatenation. I.e., if $s=\langle s_0,s_1,\dots,s_k\rangle$ is some finite sequence and $a\in\mathbb Z$, then $s\widehat{\ }a=\langle s_0,s_1,\dots,s_k,a \rangle$ is the finite sequences where $a$ is added on the end.

The symbol $|s|$ denotes length of the finite sequence $s$.

If $x=\langle x_0,x_1,\dots,x_n,\dots\in\rangle\mathbb Z^\omega$ is a sequence, then $x\upharpoonright n=\langle x_0,x_1,\dots,x_{n-1}\rangle$ is the finite sequence consisting of the first $n$ elements.

If $s\in\mathbb Z^{\omega}$, then $[s]$ denotes the set of all infinite sequences which start with $s$. I.e., if $s=\langle s_0, \dots, s_n\rangle$ then $$[s]=\{x\in\mathbb Z^\omega; x_0=s_0, x_1=s_1,\dots,x_n=s_n\}.$$ For example for the empty sequence $\langle\rangle$ we get the whole $\mathbb Z^\omega$ in this way.

The system $\{[s]; s\in\mathbb Z^\omega\}$ is a base of the product topology on $\mathbb Z^\omega$ (i.e., of the Baire space).

Comments

I understand the phrase "$\{I_{s\widehat{\ } n}: n\in \mathbb Z\}$ covers all of $I_s$ except for their endpoints" in the way that it is supposed to say that $\bigcup\limits_{n\in\mathbb Z} I_{s\widehat{\ } n}$ contains all irrational numbers from $I_s$. (Clearly, it cannot contain the endpoints of the intervals $I_{s\widehat{\ } n}$, which belong to the interval $I_s$.) This property is precisely the reason why each irrational number must belong to one of the intervals at each step. (So this implies that the map defined above is surjective.)

The condition that $q_n$ is an endpoint of some interval in some stage is made to ensure that no rational number will belong to the intersection $\bigcap_{n\in\omega}I_{x\upharpoonright n}$. (Hence the values $f(x)$ of the function $f$ indeed belong to $\mathbb P$.)

People who are already familiar with descriptive set theory have certainly noticed that the system constructed in this proof is a Souslin scheme.