Explicit Bijection from $\mathbb{N}$ to $\mathbb{Q}^+$.

Question

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

Answer 1

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

Answer 2

I came up with the same question I was studying for my Discrete Computational Structures class, where finding a bijective function $f : \mathbb{N} \to \mathbb{Q}^+$ was given as an exercise. I gave it a shot and came up with a function that incorporates the formula for triangular numbers.

I encountered this question while I was looking for other solutions in the Internet. It has been almost a year since this question was asked, but here, I hope this helps anybody:

Figure to use while explaining:

\begin{array}{ c | c | c | c c } \tfrac{p}{q} & 1 & 2 & 3 & \cdots\\ \hline 1 & \tfrac{1}{1} & \tfrac{1}{2} & \tfrac{1}{3} & \cdots\\ 2 & \tfrac{2}{1} & \tfrac{2}{2} & \tfrac{2}{3} & \cdots\\ 3 & \tfrac{3}{1} & \tfrac{3}{2} & \tfrac{3}{3} & \cdots\\ \vdots & \vdots & \vdots & \vdots & \ddots\\ \end{array}

While counting rational numbers diagonally, going in the direction $\swarrow$, one may recognize the pattern that on each diagonal the sum of the nominator $p$ and the denominator $q$ is constant, with $p$ increasing starting from $1$ and $q$ decreasing until $1$.

The $k$-th diagonal comes only after $k$-th triangular number many elements have been counted. Since the domain of our function is $\mathbb{N}$, our indexing starts from $0$, hence the first element of the $k$-th diagonal is the element with the index:

$$ \frac{k (k + 1)}{2} $$

It is actually somewhat similar to what is done with modular arithmetic. The difference is that this time, the modules are not of constant size, rather growing in size. After each module, we have some offset, which decrements the nominator and increments the denominator. So we have something like the following:

$$ \frac{k (k + 1)}{2} + r $$

Where $r \in \mathbb{N}$ and $0 \leq r < k$, is the offset. And this is it, we now have all the indexes in our hand, whenever we are given the index of the diagonal $k$, and the offset $r$!

One may find out that the rational number in the $k$-th diagonal with the offset $r$ is equal to the following:

$$ \frac{1 + r}{k + 1 - r} $$

Easy way to think about it is that the nominator increases by one as the offset increases, and starts off from $1$. Then the sum of the nominator and denominator is $k + 1$ where $k$ is the index of the given diagonal.

As one last thing, to prevent the denominator from decreasing below $1$, we shall introduce a restriction: $k + 1 - r \geq 1 \Longleftrightarrow k \geq r$.

Using all this, we can define our bijection as the following:

$$ f(n) = \frac{1 + r}{k + 1 - r} \qquad \text{ where } n = \frac{k (k + 1)}{2} + r \text{ and } r \leq k \text{ and } k, r \in \mathbb{N} $$