Exact bijection to prove rationals are countable

Question

It is a well-known fact that the set of rationals $\mathbb{Q}$ is countable. The proof for $\mathbb{Q^+}$, the strictly positive rationals, is the classic "snaking" pattern detailed in a bunch of textbooks and internet sources, e.g here. ProofWiki has 4 (!) different proofs outlined here, but the proofs of (2), (3) and (4) all assume proofs that the cartesian product of countable sets is also countable, or that the union of $k$ countable sets is also countable. My Discrete Math class will not have been exposed to those facts at the time that I discuss the countability of $\mathbb{Q^+}$, whereas proof (1) is an informal, non-rigorous proof of the "snaking" pattern which is not particularly satisfying to me (or to my best students).

What I'm interested in is a mathematically accurate characterization of the "snaking" pattern; i.e I'm looking to find the formula $f(n)$ for a bijection $f$ from $\mathbb{N}^*$ (strictly positive integers) to $\mathbb{Q^+}$.

Answer 1

If we assume the Natural numbers include $0$;

Fact 1: $f:\mathbb N \times \mathbb N \rightarrow \mathbb N; f(a,b) = a+\sum_{i=0}^{a+b} i$ is a bijection.

Pf: Suppose $f(a,b) = f(c,d)$. If $a+b = c+d$ then $a+\sum_{i=0}^{a+b} i + c+\sum_{i=0}^{a+b} i$ so $a = c$ and $b = d$. If $a+b < c+d$ then $f(c,d) = c+ \sum_{i=0}^{a+b} i + \sum_{k=a+b+1}^{c+d}k > c+\sum_{i_0}^{a+b} i + a > f(a,b)$ which is a contradiction. If $a+b > c+d$ we get a similar contradiction by the same argument. So $f$ is injective.

If $n \in \mathbb N$ then there exist $m$ so that $sum_{i=0}^m i \le n < \sum_{i=0}^{m+1} i$ so let $k = n - sum_{i=0}^m i$ and we have $k \le m$ so $f(k,m-k) = \sum_{i=0}^m i + k = n$ so $f$ is surjective.

Fact 2: if the natural numbers don't contain $0$ $\mathbb N$ is still bijective with $\mathbb N \times N$.

Let $f$ be as in Fact 1. Let $g:\mathbb N \times N \rightarrow \mathbb N$ via $g(a,b) = f^{-1}(a-1,b-1) + 1$ which is clearly a bijection.

Fact 3: if $q = a/b; a,b \in \mathbb Z^+; \gcd(a,b) = 1$ then $h(q) = (a,b)$ $h:\mathbb Q^+ \rightarrow \mathbb N\times \mathbb N: h(q=a/b) = (a,b)$ is injective although not surjective.

Pf: if $r = a/b$ and $q \ne a/b$ then $h(q) \ne (a,b)= h(r)$.

Fact 4: $k:\mathbb N \rightarrow \mathbb Q^+: k(n) = n$ is an injection.

So we have $g\circ h:\mathbb Q^+ \rightarrow \mathbb N$ is an injection. and we have $k: \mathbb N \rightarrow Q^+$ is an injection.

So $\mathbb Q^+$ and $\mathbb N$ have same cardinality.

So my question... Do you still want to find the precise bijection.

Answer 2

Define $$g(n)=(-1)^n \Big\lceil\frac{n}{2}\Big\rceil,$$

and then set $$f(p_1^{e_1}\dots p_k^{e_k})=p_1^{g(e_1)}\dots p_k^{g(e_k)},$$ where $p_1,\dots,p_k$ are distinct primes. (Since an empty product equals $1,$ we have $f(1)=1.)$

The function $f$ is a bijection from $\mathbb{N^+}$ to $\mathbb{Q^+}.$

This isn't the same as the snaking pattern that one often sees, but it is an easily-defined formula for a bijection between the two sets.

Answer 3

For a rational $r$, let

$$\begin{cases}p(r):=r\arg\min_n(rn\in\mathbb N),\\q(r):=p(r)/r\end{cases}$$ which turns it to an irreducible fraction, and let $$\phi(p,q)=\begin{cases}\gcd(p,q)=1\to1\\\gcd(p,q)>1\to0\end{cases}$$ which tests for irreducibility of a fraction.

Then

$$n(r):=\sum_{s=2}^{p(r)+q(r)-1}\sum_{i=1}^{s-1}\phi(i,s-i)+\sum_{i=1}^{p(r)}\phi(i,p(r)+q(r)-i)$$ formally defines the bijection from $\mathbb Q^+$ to $\mathbb N^*$.

For example, $n(1.25)=25$.