Prove that rational numbers (not just positive) are countable without using axiom of choice.

Question

Prove that rational numbers (not just positive) are countable without using axiom of choice(since it is controversial).

I have seen proofs that use the fact that union of countable sets is countable, which is proved using axiom of choice (if it is not, can you provide a proof showing that). I have also seen many proofs that showing that positive rational numbers are countable, but not both positive and negative rational numbers. I dislike the listing all the rational numbers and assigning a one-one correspondence proof as well (e.g. Cantor's proof) because it feels like cheating to me.

However, I can't find a good proof myself. Hence, I really hope that someone can provide me with a nice proof on this, nice being explicit bijection. Thanks.

Answer 1

You don't need the axiom of choice for the following statement:

If $X$ is countable, and $f$ is a function whose domain is $X$, then the range of $f$ is countable.

You also don't need the axiom of choice for the following statement:

$\Bbb{N\times Z}$ is countable.

Finally, define $f(n,m)=\frac nm$ or $0$ if $m=0$, and show that this is a surjection onto the rational numbers.

Answer 2

Explicit bijections are rather tedious to come up with. However, the Schroeder-Bernstein theorem implies that a subset of a countable set is countable (or finite, if your definition of countable excludes finite sets) and its proof does not require AC (see https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem). This provides an alternative to the nice observations in Asaf Karaglia's answer: it is easy to identify $\mathbb{Q}$ with an (infinite) subset of $\mathbb{N} \times \mathbb{Z}$ and then use the countability of the latter. (You can reconstruct a more or less explicit bijection from the usual proofs of the S-B theoem, if you really want one.)

Answer 3

Every positive rational number can be written as a finite continued fraction$^*$, and every finite continued fraction can be associated with a string over the alphabet $\Sigma=\{0,1\}$. For instance: $$ \frac{89}{13}=[6;1,5,2] \longrightarrow 11111101111100, $$ $$ \frac{101}{47}=[2;6,1,2,2]\longrightarrow 1100000010011, $$ so, by reading that string as the binary representation of an integer number, we have the existence of an injective map from $\mathbb{Q}^+$ to $\mathbb{N}^+$. So $\mathbb{Q}^+$ is countable. Moreover, it is not difficult to modify a bit the above contruction in order to get a bijective map from $\mathbb{Q}$ to $\mathbb{N}$. The key idea is just to identify any (positive) rational number as a path in the Stern-Brocot tree.

^{$^*$: the representation is unique if we require that the last element of the continued fraction is not one.
So the canonical representation of $\frac{89}{13}$ is $[6;1,5,2]$, not $[6;1,5,1,1]$.}

Answer 4

This is a proof I came up recently: First, note that to prove: $$(1)\text{ If } f: A \to B \text{ is injective and } B \text{ is countable, then } A \text{ is countable.} $$ it is sufficient to prove that for every $A \subseteq \mathbb{N}$, $A$ is countable - and you can prove it without AC. Then, from $(1)$, we can conclude that $\mathbb{N} \times \mathbb{N}$ if countable by defining the function $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$, with $f(n, m) = 2^n 3^m $, and proving that it is injective. Hence the cartesian product of countable sets is countable.

Now, define $g: \mathbb{N} \times \mathbb{Z} \to \mathbb{Q}$ by $g(n, m) = \frac{n}{m}$. Obviously, $g$ is surjective. From the hypothesis, $\mathbb{N} \times \mathbb{Z} = A$ is countable, then there is a enumeration $\phi: \mathbb{N} \to A$.

Now, set $h = g \circ \phi$ (which is surjective) and define the following relation in $\mathbb{N}$: $$n \sim m \text{ iff } h(n) = h(m)$$ $\sim$ is an equivalence relation.

For each $X \in \mathbb{N}/\sim$, let $n_X$ be its least element and define $H: \mathbb{N}/\sim \to \mathbb{Q}$ by setting $H(X) = h(n_X)$. Then H is a bijection.

Beacause $\sim$ is an equivalence relation, the function that takes $X \in \mathbb{N}/\sim$ to $n_X$ is an injection, hence $\mathbb{N}/\sim$ is countable.

It follows that $\mathbb{Q}$ is countable. $\square$

I guess I may be too late.

Answer 5

Let $S = \{q \in \mathbb Q \, | \, 0 \le q \lt 1\}$.

Let $\mathbb N = \text{ the positive integers}$.

Claim a function

$\tag 1 f: \mathbb N \to S$

can be defined using recursion that is a bijective correspondence.

There is a demonstration of the validity of this claim in the next section. But for now just assume we have such an explicit bijection $f$.

Now it is easy to see that $S \times \mathbb Z$ can be naturally put into a bijective correspondence with the set of all rational numbers $\mathbb Q$ (the coordinate $(p, m)$ corresponding to $p + m$). But since $S \times \mathbb Z$ is now countable (we have $f$ and see also Asaf Karagila's answer), the set $\mathbb Q$ is countable.

The reader is invited to edit the next section to get an explicit bijection between $\mathbb N$ and $\mathbb Q$.

---

The implementation of this function $f$ is described by the following computer program using Python:

#--------*---------*---------*---------*---------*---------*---------*---------*
# Desc: Implement a bijective corresponce between the integers {n | n > 0} and
#       the set of rational numbers {q | 0 <= q < 1} 
#--------*---------*---------*---------*---------*---------*---------*---------*

from fractions import Fraction
import sys

def daFunctionGraph(curCoordinate):
    nextInteger = curCoordinate[0] + 1
    p = curCoordinate[1]
    tickPrecision = curCoordinate[1].denominator
    if p + Fraction(1, tickPrecision) == 1:
        return [nextInteger, Fraction(1, tickPrecision + 1)]
    else:
        while True:
            q = p + Fraction(1, tickPrecision)
            if q.denominator == tickPrecision:
                return [nextInteger, q]
            else:
                p = p + Fraction(1, tickPrecision)


#--------*---------*---------*---------*---------*---------*---------*---------#
while True:#                       M A I N L I N E                             #
#--------*---------*---------*---------*---------*---------*---------*---------#
    current = [1, Fraction(0, 1)]
    while True:
        print(current[1], end=', ')
        if current[0] == 100:
            break
        current = daFunctionGraph(current)

    sys.exit() # END PROGRAM

The first 100 outputs from $f$ are enumerated by this program; you can use the 'slider' to see all the outputs:

0, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 1/8, 3/8, 5/8, 7/8, 1/9, 2/9, 4/9, 5/9, 7/9, 8/9, 1/10, 3/10, 7/10, 9/10, 1/11, 2/11, 3/11, 4/11, 5/11, 6/11, 7/11, 8/11, 9/11, 10/11, 1/12, 5/12, 7/12, 11/12, 1/13, 2/13, 3/13, 4/13, 5/13, 6/13, 7/13, 8/13, 9/13, 10/13, 11/13, 12/13, 1/14, 3/14, 5/14, 9/14, 11/14, 13/14, 1/15, 2/15, 4/15, 7/15, 8/15, 11/15, 13/15, 14/15, 1/16, 3/16, 5/16, 7/16, 9/16, 11/16, 13/16, 15/16, 1/17, 2/17, 3/17, 4/17, 5/17, 6/17, 7/17, 8/17, 9/17, 10/17, 11/17, 12/17, 13/17, 14/17, 15/17, 16/17, 1/18, 5/18, 7/18, 11/18,