elementary set theory - Saving a failed bijection between $mathbb{N}$ and $mathbb{Q^+}$

I just tried to have some fun on a late evening and create a bijection between $\mathbb{N}$ and $\mathbb{Q^+}$ (after finding a challenge in a text I read).

The very first thing I did, and which is the elementary mistake I guess, was looking for a way to generate the sequence $(1, \frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, \frac{2}{4}, \frac{3}{4}, \dots)$.

I then proceeded to find two functions, $d,n : \mathbb{Z} \cap [1, \infty) \to \mathbb{Z} \cap [1, \infty)$, such that $d$ generates the sequence $(2, 3, 3, 4, 4, 4, 5, 5, 5, 5 \dots )$ and $n$ generates the sequence $(1, 1, 2, 1, 2, 3, 1,2, 3, 4 \dots)$, which in the end gives the function

$$h(x) =
\begin{cases}
x & \text{if}\> x = 0 \>\text{or}\>x=1 \\
\frac{n(x)}{d(x)} & \text{else}
\end{cases}$$

The functions $n$ and $d$ are given by:

$$
d(x) = \left\lceil\frac{1}{2}(\sqrt{8(x-1)+1}-1) +1\right\rceil\\
n(x) = (x-1) - \frac{(d(x) - 1)(d(x)-2)}{2}
$$

Some quick programming verified that these are indeed the functions I am looking for. However, to my horror I realised a tad too late that this is in fact not a bijection between $\mathbb{N}$ and $\mathbb{Q^+}$, as the sequence I used as starting point is not the (positive) rational numbers, but instead a subset of all ordered pairs $(x,y)$. For instance $\frac{1}{2}$, and $\frac{2}{4}$ are the same rational number. Consequently, if $h : \mathbb{N} \to \mathbb{Q^+}$, then it is not a bijection as it is not injective.

First of all: Does my functions seem reasonable? Is this in fact a bijection between $\mathbb{N}$ and the ordered pairs? Very open question I guess, but I often fear I've done some silly mistake here or there.

Secondly: Is there any fairly easy way to "save" my function $h$ such that it indeed becomes a bijection between $\mathbb{N}$ and $\mathbb{Q^+}$.

Lastly: I assume there exists some bijection from the set of all ordered pairs to $\mathbb{Q^+}$? How would such a bijection look? And how would a bijection from my subset of ordered pairs to $\mathbb{Q^+}$?

Answer

First your function doesn't seem to even be a bijection between $\mathbb Z^+$ and $\mathbb Z^+\times\mathbb Z^+$. What's missing is that the first component never is allowed to be larger than the second. What you need is to ensure this. This is normally done by walking diagonals in $\mathbb Z^+\times\mathbb Z^+$, ie the sequence first diagonal: $(1,1)$, then second: $(2,1)$, $(1,2)$, then third: $(3,1)$, $(2,2)$, $(1,3)$ etc.

This map means that you can construct a surjection from $\mathbb Z^+$ to $\mathbb Q^+$.

Related is the Schröder-Bernstein theorem which says that if theres an injection both ways there's an bijection (and the proof shows how to actually construct one). This is related since given a surjection you can create a reverse injection by just (arbitrarily) selecting one of the elements that maps to. For example the surjection above is $q(1)=1/1$, $q(2)=2/1$, $q(3)=1/2$, $q(4)=3/1$, $q(5)=2/2$, $q(6)=1/3)$ giving the reverse that we can choose $r(1) = 1$ (since $q(1)=1/1$, we could have chosen $r(1)=5$ as $q(5)=2/2=1$), we have $r$ being a injection from $\mathbb Q^+$ to $\mathbb N^+$ and of course that the identity map is an injection the other way - and consequently there exists a bijection between.

To be concrete we can save the day for a bijective map between $\mathbb N^+\times \mathbb N^+$ and $\mathbb Q^+$, but it's probably easier to work with the original intention - mapping between $\mathbb N^+$ and $\mathbb Q^+$ directly. What you do is that you have an enumeration $q_j$ ($1/1$, $2/1$, $1/2$, $3/1$, $2/2$, $1/3$, ...) such covering all positive rational number. What you do is traverse this and only keep the rational numbers that have not appeared earlier in the sequence (for example you would skip $2/2$ which have appeared earlier leaving $1/1$, $2/1$, $1/2$, $3/1$, $1/3$ etc).

Another approach would be to use prime number factorizations of natural numbers and noting that they're are possible and unique to for rational numbers (given that we're allowed to have negative exponents). That is for each natural $n$ number we have a unique sequence $n_j$ (of non-negative integers) such that $n = \prod \pi_j^{n_j}$ (where $\pi_j$ is the $j$th prime). And for each rational number $q$ we have a unique sequence $q_j$ of integers such that $q = \prod \pi_j^{q_j}$. Now let

$$q_j(n_j) = \begin{cases} n_j/2 & \mbox{if }n_j\mbox{ is even} \\
-(n_j+1)/2 & \mbox{if }n_j\mbox{ is odd} \end{cases}$$

this would define a bijection between $\mathbb Z^+$ and $\mathbb Q^+$