Lemma 6

Let D be a countable totally ordered set, not reduced to one element, possessing a smallest and a greatest element. Suppose that D has no gap (E, III, p. 73, exerc. 19), that is to say that every open interval $]x, y[$, where $x$ and $y$ are elements of D such that $x < y$, is nonempty. There then exists an isomorphism of ordered sets from $\mathbf{I}\cap \mathbf{Q}$ onto D.

Let $a$ be the smallest element and $b$ the greatest element of D. By assumption, we have $b=\not a$ and $]a, x[=\not\emptyset$ for every $x\in D-\{a\}$. The set D$-\{a\}$ is totally ordered, is not empty and has no smallest element; it is therefore infinite (E, III, p. 34, cor. 1 of prop. 3). The sets $\mathbf{I}\cap \mathbf{Q}$ and D, infinite and countable, are equipotent to $\mathbf{N}$.

Choose bijections $n\mapsto a_n$ and $n\mapsto b_n$ of $\mathbf{N}$ onto $\mathbf{I}\cap \mathbf{Q}$ and D respectively, such that $a_0= 0,a_1= 1,b_0=a,b_1=b$. There exists a unique strictly increasing mapping $f:\mathbf{I}\cap \mathbf{Q}\rightarrow D$ possessing the following properties: we have $f(0) =a$ and $f(1) =b$; for $n\geqslant 2$, we have $f(a_n) =b_m$, where $m$ is the smallest natural number for which the mapping of $\{a_0, . . . , a_n\}$ into D which coincides with $f$ in $\{a_0, . . . , a_{n-1}\}$ and maps $a_n$ onto $b_m$ is strictly increasing. These properties indeed define $f(a_n)$ by induction on $n$, the existence of the integer $m$ being ensured by the fact that D is without gaps.

Since the mapping $f$ is strictly increasing and $\mathbf{I}\cap \mathbf{Q}$ is totally ordered, $f$ defines an isomorphism of ordered sets from $\mathbf{I}\cap \mathbf{Q}$ onto its image (E, III, p. 14, prop. 11). It remains for us to prove that $f$ is surjective. For this, let us prove by induction that $b_m$ belongs to the image of $f$ for every $m\in \mathbf{N}$.

One has $b_0=f(0)$ and $b_1=f(1)$. Suppose that we have $m\geqslant 2$ and that, for $0\leqslant k\leqslant m-1$, there exists $c_k\in \mathbf{I}\cap \mathbf{Q}$ such that $f(c_k) =b_k$. We have $c_0= 0$ and $c_1= 1$, since $f$ is injective. Consider the smallest integer $n\in \mathbf{N}$ for which $a_n$ does not belong to $\{c_0, . . . , c_{m-1}\}$ and the mapping $g$ of $\{c_0, . . . , c_{m-1}, a_n\}$ into D which coincides with $f$ in $\{c_0, . . . , c_{m-1}\}$ and maps $a_n$ onto $b_m$ is strictly increasing; such an integer exists since $\mathbf{I}\cap \mathbf{Q}$ has no gap. Let $f'$ be the mapping of $\{a_0, . . . , a_n\}$ into D which coincides with $f$ in $\{a_0, . . . , a_{n-1}\}$ and which maps $a_n$ onto $b_m$. Let us prove that it is strictly increasing. Let $j\in \{0, . . . , n-1\}$; by definition of the integer $n$, there exists $k\in \{0, . . . , m-1\}$ such that $a_j=c_k$, or $a_j< c_k$ and $b_m\geqslant f(c_k)$, or $a_j> c_k$ and $b_m\leqslant f(c_k)$. Suppose $b_k< b_m$; we then have $g(c_k) =f(c_k) =b_k< b_m=g(a_n)$, whence $c_k< a_n$ since $g$ is strictly increasing, then $a_j\leqslant c_k< a_n$; moreover, $f'(a_j) =$ $f(a_j)\leqslant f(c_k) =b_k< b_m=f'(a_n)$. Analogously, if $b_k> b_m$, we obtain $a_n< c_k\leqslant a_j$ and $f'(a_j) =f(a_j)\geqslant f(c_k) =b_k> b_m=f'(a_n)$. Since $f$ itself is strictly increasing, it follows that the mapping $f'$ is strictly increasing.

If $m'$ is the integer such that $f(a_n) =b_{m'}$, we have $m'\leqslant m$, by definition of $f$. If we had $m'< m$, we would have $f(a_n) =b_{m'}=f(c_{m'})$, whence $a_n=c_{m'}$, since $f$ is injective, which contradicts the definition of $a_n$. Thus, $m'=m$ and $f(a_n) =b_m$, which proves that $b_m$ belongs to the image of $f$ and completes by induction the proof of the surjectivity of $f$.