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

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

• Just FYI, the construction you're talking about, where you write positive rational numbers in an infinite square pattern and follow a snakelike path through successive diagonals of the square, is not what's called the "diagonal argument." The actual "diagonal argument" in this context is an argument showing that there is no bijection of the natural numbers with the real numbers (or equivalently with infinite binary strings). Commented Dec 11, 2013 at 0:46
• No, I know of that diagonal argument. The argument is not a proof so to speak... He actually calls it a diagonal procedure so perhaps I should edit my question. Commented Dec 11, 2013 at 0:49
• See here. Commented Dec 11, 2013 at 0:55
• That looks helpful. Let me digest it! Thanks for the link. Commented Dec 11, 2013 at 1:05
• Related question: math.stackexchange.com/questions/7643/… Commented Dec 11, 2013 at 13:06

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

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

• I don't think it's a bijection. $1/2$ and $69/138$ are the same rational number but are mapped to different natural numbers here.
– Kuba
Commented Mar 12, 2016 at 19:01