What's the bijection between reals and infinite sequences of integers?

Question

In Descriptive Set Theory we often see the notion of encoding a real as a sequence of integers or natural numbers -- i.e. there obviously is a bijection according to ZF axioms. But how does it look like concretely? Anybody has seen a simple construction?

My own approach is by chain-fractions:

Let $q\in\mathbb{R}$ be the given real and now define the sequence $(z_i,q_i)$ by $$z_{i+1}=\begin{cases}[q_i]&\text{if } \{q_i\}\leq\frac{1}{2}\\ [q_{i}]+1&\text{else} \end{cases}$$ $$q_{i+1}=(q_i-z_{i+1})^{-1}$$ where $[q]$ is the next lower integer and $\{q\}=q-[q]$. (Hence $(q_i-z_{i+1})\in(-\frac12,\frac12]$ thereby absolute value of $q_{i+1}$, its reciprocal, is bigger than 2.) Now my bijection is mapping $q$ to the sequence: $$m_i=\begin{cases}z_i-2&z_i>0, i>1\\ z_i&i=1\\ z_i+2&z_i<0, i>1\end{cases}$$ with $i$ starting at 1 and above $q_0$ becomes the initial $q$. And the inverse of my bijection just calculates the chain-fraction:$q_{i-1}\in(z_i-\frac12,z_i+\frac12]$ with $q_{i-1}=z_i+q_i^{-1}$ step-wise narrowing down the real by a sequence of intervals each containing the next.

is there a paper or book covering my example? any other simple constructions?

Answer 1

[Note: this answer uses the convention where $\mathbb{N} := \{ 0, 1, 2, \dots \}$ contains zero.]

There's an elegant explicit order-preserving bijection between the Baire space $\mathbb{N}^{\mathbb{N}}$ (under lexicographical order) and $\mathbb{R}_{\geq 0}$ (under the usual order) described here.

In particular, we define the image of:

$$ (a_0, a_1, a_2, a_3, \dots) $$

to be the generalised continued fraction:

$$ a_0 + \cfrac{1}{1 + \cfrac{1}{a_1 + \cfrac{1}{1 + \cfrac{1}{a_2 + \ddots}}}} $$

This order-preserving bijection shows that $\mathbb{R}_{\geq 0}$ and $\mathbb{N}^{\mathbb{N}}$ are not only isomorphic as sets (i.e. equinumerous), but also isomorphic as totally-ordered sets.

Topologically, this bijection from $\mathbb{N}^{\mathbb{N}}$ to $\mathbb{R}_{\geq 0}$ is continuous, meaning that every open subset of the nonnegative reals corresponds to an open subset of Baire space. The converse is not quite true (if it were, the two spaces would be homeomorphic, which they're not); continuity of the inverse map fails exactly at the positive rationals.

Answer 2

When it comes to relative cardinalities and bijections, the Cantor-Schröder–Bernstein theorem expresses what in my view is the fundamental fact that cardinal comparisons obey the principle of anti-symmetry. Namely, if $|A|\leq|B|$ and $|B|\leq|A|$ then $A$ and $B$ are bijective. That is, if $A$ and $B$ each inject into each other, then the Cantor-Schröder–Bernstein theorem provides a bijection of $A$ with $B$, defined explicitly from those injections. To my way of thinking, it is ultimately this fact that entitles us to think of equinumerosity as a measure of size. (In particular, it is part of my belief that almost every philosophical discussion of Hume's principle should be augmented with a discussion of the Cantor-Schröder–Bernstein theorem.)

In your case, there is an easy injection from the reals to infinite sequence of natural numbers, since we can map every real number to the canonical enumeration of the rational numbers below it. And there is an easy injection from the infinite sequences of natural numbers to the reals, by mapping $(n_0,n_1,n_2,\dots)$ to the real number $0.1000\cdots010\cdots010\cdots$, where the number of zeros in each block is $n_0$, $n_1$, and so on.

So the Cantor-Schröder–Bernstein theorem shows that the two sets are equinumerous by the explicit map provided in that proof.

Ultimately, what I am claiming is that it is more important to understand the equinumerosity relation on sets than to try to find a "natural" bijection, which I view as a meaningless concept adding no insight.

Answer 3

There are bijections $$ \text{Map}(\mathbb{N},\mathbb{N}) \xrightarrow{\alpha} \text{Map}(\mathbb{N},\mathbb{N})\setminus\{0\} \xrightarrow{\beta} \text{SInc}(\mathbb{N},\mathbb{N}) \setminus\{\text{id}\} \xrightarrow{\gamma} \mathcal{P}_\infty(\mathbb{N})\setminus\{\mathbb{N}\} \xrightarrow{\delta} (0,1) \xrightarrow{\epsilon} \mathbb{R} $$ as follows.

1. $\alpha(u)=u$ unless $u$ is constant, in which case $\alpha(u)=u+1$.
2. $\text{SInc}(\mathbb{N},\mathbb{N})$ is the set of strictly increasing maps from $\mathbb{N}$ to itself, and $\beta(u)(n)=n+\sum_{i\leq n}u(i)$.
3. $\mathcal{P}_\infty(\mathbb{N})$ is the set of infinite subsets of $\mathbb{N}$, and $\gamma(v)=v(\mathbb{N})$.
4. $\delta(S)=\sum_{i\in S}2^{-i-1}$.
5. $\epsilon(x)=(x-\frac{1}{2})/\sqrt{x(1-x)}$.

We can also give a bijection from $\text{Map}(\mathbb{N},\mathbb{N})$ to the full set $\mathcal{P}(\mathbb{N})$ of all subsets of $\mathbb{N}$, as follows. We first note that the rules discussed above also give bijections $$ \text{Map}(\mathbb{N},\mathbb{N}) \xrightarrow{\beta} \text{SInc}(\mathbb{N},\mathbb{N}) \xrightarrow{\gamma} \mathcal{P}_\infty(\mathbb{N}). $$ We also have a bijection $\zeta$ from the set $\mathcal{P}_0(\mathbb{N})$ of finite subsets of $\mathbb{N}$ to $\mathbb{N}$ itself given by $\zeta(S)=\sum_{i\in S}2^i$. Now for $u\in\text{Map}(\mathbb{N},\mathbb{N})$ we define $\eta(u)\in \mathcal{P}(\mathbb{N})=\mathcal{P}_0(\mathbb{N})\amalg\mathcal{P}_\infty(\mathbb{N})$ by $$ \eta(u) = \begin{cases} \zeta^{-1}(n) & \text{ if } u \text{ is constant with value } 2n \\ \gamma\beta(n) & \text{ if } u \text{ is constant with value } 2n+1 \\ \gamma\beta(u) & \text{ if } u \text{ is not constant. } \end{cases} $$ This gives a bijection $\eta\colon\text{Map}(\mathbb{N},\mathbb{N})\to \mathcal{P}(\mathbb{N})$.