12
$\begingroup$

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?

$\endgroup$
3
  • 3
    $\begingroup$ mathoverflow.net/questions/56633/… $\endgroup$ May 20, 2021 at 16:21
  • 6
    $\begingroup$ Note that in descriptive set theory more often than not "the reals" are $\Bbb N^{\Bbb N}$! $\endgroup$ May 20, 2021 at 16:23
  • $\begingroup$ or elements of the power set of $\mathbb{N}$, or elements of ${0,1}^\mathbb{N}$, or indeed any Cantor space, whichever is more convenient at the time. $\endgroup$
    – David Roberts
    May 21, 2021 at 0:05

3 Answers 3

44
$\begingroup$

[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.

$\endgroup$
6
  • $\begingroup$ Doesn't this give you the irrationals rather than the full real line? $\endgroup$ May 20, 2021 at 22:06
  • 12
    $\begingroup$ It gives you all of $\mathbb{R}_{\geq 0}$. Rationals correspond to sequences that are eventually zero. $\endgroup$ May 21, 2021 at 1:38
  • 3
    $\begingroup$ Also, the repeating sequences correspond to the roots of quadratics. $\endgroup$ May 21, 2021 at 23:35
  • 1
    $\begingroup$ in fact, the two links in the text go to the same page. maybe you meant to put a different url in the second one? $\endgroup$
    – Jonas Frey
    May 22, 2021 at 1:21
  • 3
    $\begingroup$ Whoops! The second link was meant to go to Oscar Cunningham's blog post: oscarcunningham.com/494/… $\endgroup$ May 22, 2021 at 9:45
22
$\begingroup$

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.

$\endgroup$
8
  • 9
    $\begingroup$ @user11566470 Cantor–Schröder–Bernstein needs no Choice, only EM cf cs.bham.ac.uk/~mhe/agda-new/CantorSchroederBernstein.html $\endgroup$
    – David Roberts
    May 20, 2021 at 23:58
  • 7
    $\begingroup$ I'm sorry to disappoint. It's true, I freely use the law of excluded middle in all mathematical arguments; it is a core part of my conception of mathematical truth. $\endgroup$ May 21, 2021 at 6:48
  • 1
    $\begingroup$ 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. You've spent too much time at the philosophy department... :-) $\endgroup$
    – Asaf Karagila
    May 21, 2021 at 11:18
  • 4
    $\begingroup$ Looking for more concrete maps/bijections between sets (especially definable without AC/LEM) has very tangible payoffs: often those maps turn out to additionally be continuous, or have other good properties. Adam Goucher’s answer shows that very nicely in this case, giving a continuous bijection $\mathbb{N}^\mathbb{N} \to \mathbb{R}$, which has many descriptive set-theoretic consequences. The question of what it means for bijections to be “natural” in this way is certainly imprecise, but looking for them absolutely can give real insights. $\endgroup$ May 21, 2021 at 13:06
  • 2
    $\begingroup$ I completely agree with Peter that when one has a specific notion of naturality, then there can be big payoffs. $\endgroup$ May 21, 2021 at 14:03
19
$\begingroup$

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})$.

$\endgroup$
2
  • $\begingroup$ Do you want $\alpha$? I think $\beta$ maps the zero sequence to the identity function. $\endgroup$ May 21, 2021 at 9:21
  • 1
    $\begingroup$ @MeesdeVries Yes, $\beta(0)=\text{id}$ and $\gamma(\text{id})=\mathbb{N}$ and $\delta(\mathbb{N})=1$, so I have to use $\alpha$ if I want the codomain to be $(0,1)$ rather than $(0,1]$. $\endgroup$ May 21, 2021 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.