Reading Bartle and Sherbert's intro to Real Analysis and going over denumerable sets. I know because of a diagonal procedure that this bijection exists, but I've been trying to find an explicit function $f:\mathbb{N}\rightarrow \mathbb{Q}^+$ and having difficulty. My thoughts were to incorporate triangular numbers somehow since each successive diagonal has one more term in it. Hints would be great here as I'm coming up empty…
[Math] Explicit Bijection from $\mathbb{N}$ to $\mathbb{Q}^+$.
elementary-set-theoryreal-analysis
Related Solutions
The nicest trick in the book is to find a bijection between $\mathbb R$ and $\mathbb{N^N}$, in this case we are practically done. Why?
$$\mathbb{(N^N)^N\sim N^{N\times N}\sim N^N}$$
And the bijections above are easy to calculate (I will leave those to you, the first bijection is a simple Currying, and for the second you can use Cantor's pairing function).
So if we can find a nice bijection between the real numbers the infinite sequences of natural numbers we are about done. Now, we know that $\mathbb{N^N}$ can be identified with the real numbers, in fact continued fractions form a bijection between the irrationals and $\mathbb{N^N}$.
We first need to handle the rational numbers, but that much is not very difficult. Take an enumeration of the rationals (e.g. Calkin-Wilf tree) in $(0,1)$, suppose $q_i$ is the $i$-th rational in the enumeration; now we take a sequence of irrationals, e.g. $r_n = \frac1{\sqrt{n^2+1}}$, and we define the following function:
$$h(x)=\begin{cases} r_{2n} & \exists n: x=r_n\\ r_{2n+1} & \exists n: x=q_n \\ x &\text{otherwise}\end{cases}$$
Now we can finally describe a list of bijections which, when composed, give us a bijection between $\mathbb R$ and $\mathbb{R^N}$.
- $\mathbb{R^N\to (0,1)^N}$ by any bijection of this sort.
- $\mathbb{(0,1)^N\to \left((0,1)\setminus Q\right)^N}$ by the encoding given by $h$.
- $\mathbb{\left((0,1)\setminus Q\right)^N\to \left(N^N\right)^N}$ by continued fractions.
- $\mathbb{\left(N^N\right)^N\to N^{N\times N}}$ by Currying.
- $\mathbb{N^{N\times N}\to N^N}$ by a pairing function.
- $\mathbb{N^N\to (0,1)\setminus Q}$ by decoding the continued fractions.
- $\mathbb{(0,1)\setminus Q\to (0,1)}$ by the decoding of $h$, i.e. $h^{-1}$.
- $\mathbb{(0,1)\to R}$ by any bijection of this sort, e.g. the inverse of the bijection used for the first step.
First note that the set $\mathcal P_{\text{fin}}(\Bbb N)$ of finite subsets of $\Bbb N_0$ is in bijection with $\Bbb N_0$: $$ \begin{align}\alpha\colon \mathcal P_{\text{fin}}(\Bbb N)&\to \Bbb N\\A&\mapsto \sum_{k\in A}2^k\end{align}$$
Every real number $a\in[0,1)$ as a binary expansion $a=\sum_{k=0}^\infty a_k2^{-k-1} $ with $a_k\in\{0,1\}$. For those cases with two expansions we pick the one ending in zeroes. Now we map $$ \begin{align}\beta\colon [0,1)&\to \mathcal P(\Bbb N)\\a&\mapsto \{\,k\in\Bbb N\mid a_k=0\,\}\end{align}$$ This one fails to be bijective: We leave out precisely the finite subsets of $\Bbb N$. In other words, we have a bijection $$ \beta\colon [0,1)\to\mathcal P(\Bbb N)\setminus \mathcal P_{\text{fin}}(\Bbb N)$$ The rest is glueing and playing Hilbert's Hotel: We have a bijection $$ \begin{align}\gamma\colon \Bbb R&\to (0,\infty)\\x&\mapsto e^x\end{align}$$ and a bijection $$ \begin{align}\delta\colon (0,\infty)&\to [0,\infty)\\x&\mapsto \begin{cases}x-1,&x\in\Bbb N\\x,&\text{otherwise}\end{cases}\end{align}$$ and a bijection $$ \begin{align}\epsilon \colon [0,\infty)&\to [0,1)\\x&\mapsto\begin{cases} \frac1{1+x},&x>0\\0,&x=0\end{cases}\end{align}$$ All in all this gives us a bijection $$ \zeta\colon \Bbb R\stackrel{\beta\circ\epsilon\circ\delta\circ\gamma}\longrightarrow \mathcal P(\Bbb N)\setminus\mathcal P_{\text{fin}}(\Bbb N)$$ To complete the construction we have to hide countably many finite sets by defining for example $$ \begin{align}\eta \colon \Bbb R&\to \mathcal P(\Bbb N)\\x&\mapsto\begin{cases}\alpha^{-1}(x),&x\in\Bbb N\\ \zeta(x-\sqrt 2),&x=n+m\sqrt 2\text{ with }n\in\Bbb N, m\in\Bbb N_{>0}\\ \zeta(x),&\text{otherwise}\end{cases}\end{align}$$
Best Answer
One of the tries is a bijection $f:\mathbb N\to(0,1]\cap\mathbb Q$ where $f(0)=1$ and then if $f(n)=\frac{p_k}q$ for $\gcd(p_k,q)=1$ with $p_k<q-1$ then $f(n+1)=\frac{p_{k+1}}q$ for $\gcd(p_{k+1},q)=0$ and $p_{k+1}>p_k$ over the set of proper coprimes of $q$: $\{p_k\in\mathbb N: 0<p_k<q, \gcd(p_k,q)=1\}$, and if $f(n)=\frac{q-1}{q}$ then $f(n+1)=\frac{1}{q+1}$.
I don't quite remember but this injection of $\mathbb N\to(0,1]\cap\mathbb Q$ had a few direct formulas. And it was also surjective.
This injection can be extended for $g:\mathbb N\to\mathbb Q^+$ by $g(2k)=f(k)$ and $g(2k+1)=1/f(k)$.