Is There an Injection Between the Natural and Rational Numbers?

There is an injective function from the natural numbers to the rational numbers, and there is also an injective function in the reverse direction. The first map is immediate: regard each natural number as a rational number. The reverse map takes a little more work because the rationals include fractions and negative numbers, but each rational can be encoded by a pair of integers in a way that preserves distinctness.

The convention for whether $0$ is a natural number varies. The construction below works either way; the only adjustment is whether you add one to the final code.

From natural numbers to rational numbers

Define

$$f(n)=\frac{n}{1}.$$

This is an injection: if $f(m)=f(n)$, then $m/1=n/1$, so $m=n$. If your natural numbers include $0$, this sends $0$ to the rational number $0$; if they start at $1$, it maps the positive integers into the rationals as usual.

In fact, this function is just the inclusion of the natural numbers among the rationals. It is not onto, since, for example, $1/2$ is rational but is not the image of a natural number.

From rational numbers to natural numbers

To build an injection in the other direction, use the unique reduced representation of each rational number:

$$x=\frac{p}{q}, \qquad p\in\mathbb{Z},\quad q\geq 1,\quad \gcd(|p|,q)=1.$$

Requiring $q$ to be positive and the fraction to be reduced ensures that each rational has exactly one such representation. For example, $2/3$ is in this form, while $4/6$ is not. The number $0$ is represented as $0/1$.

First encode the signed numerator as a nonnegative integer. Define

$$z(p)=\begin{cases} 2p, & p\geq 0,\\ -2p-1, & p<0. \end{cases}$$

This assigns different codes to different integers: $0,1,-1,2,-2,\ldots$ receive codes $0,2,1,4,3,\ldots$. The denominator can be encoded by $q-1$, which is also nonnegative.

Now pair the two codes using the Cantor pairing function

$$\pi(a,b)=\frac{(a+b)(a+b+1)}{2}+b,$$

which is an injection from pairs of nonnegative integers to nonnegative integers. Thus, if natural numbers include zero, define

$$g\left(\frac{p}{q}\right)=\pi\bigl(z(p),q-1\bigr).$$

If natural numbers start at $1$, use $g(p/q)=\pi(z(p),q-1)+1$ instead.

Why the reverse map is injective

Suppose two rationals receive the same code. Because the pairing function is injective, their pairs $(z(p),q-1)$ must be equal. The encoding $z$ is injective, so the numerators are equal; equality of $q-1$ gives equality of the denominators. Therefore the rationals have the same reduced numerator and denominator, and are equal. This proves that $g$ is injective.

For a concrete calculation, take $-3/5$. Its numerator code is $z(-3)=-2(-3)-1=5$, and its denominator code is $5-1=4$. Therefore

$$g\left(-\frac{3}{5}\right)=\pi(5,4)=\frac{9\cdot 10}{2}+4=49.$$

Under the convention that natural numbers begin at $1$, the code is $50$. The exact numerical code is not important; what matters is that distinct reduced fractions get distinct codes.

What the two injections tell you

The existence of injections both ways shows that the rationals and natural numbers have the same cardinality. More formally, the Cantor–Schröder–Bernstein theorem says that if there is an injection from $A$ to $B$ and an injection from $B$ to $A$, then there is a bijection between $A$ and $B$. Hence the rationals are countably infinite, despite being dense in the real line: between any two distinct real numbers there is a rational number, but the rationals can still be listed in a sequence.

The two injections above do not themselves need to be inverses. An injection from $\mathbb{N}$ to $\mathbb{Q}$ only guarantees that different natural numbers have different rational images; it need not reach every rational. Likewise, the encoding of rationals into natural numbers assigns codes to rationals, but not every natural-number code needs to correspond to a reduced fraction.

Common mistakes

• Assuming density means uncountability. A set can be dense in a larger set and still be countable. Density describes how points are distributed, not how many there are in the sense of cardinality.
• Using unreduced fractions without handling duplicates. The same rational, such as $1/2$, has many fraction representations, including $2/4$. Reduce fractions first, or use a different encoding that explicitly handles duplicates.
• Forgetting negative numerators. A code for nonnegative integers alone cannot represent all rational numbers. The zigzag encoding $z$ gives every integer a distinct nonnegative code.
• Mixing conventions for natural numbers. If $\mathbb{N}$ starts at $1$, shift a code in the nonnegative integers by one; if it includes $0$, no shift is needed.