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