# Rudin proof: $\mathbb{Q}$ is countable

I'm reading Rudin and he states that the set of fractions is countable because the set $(a,b)$ with $a \in \mathbb{Z}, b \in \mathbb{Z_0}$ is countable and we can write any fraction as $a/b$

Of course, there are missing a lot of details (I think). So can someone verify my reasoning?

Define $$f: \mathbb{Z} \times \mathbb{Z}_0 \to \mathbb{Q}: (a,b) \mapsto \frac{a}{b}$$

Clearly, $f$ is surjective. Let's prove a little lemma first:

Lemma: $f: A \to B$ surjective $\Rightarrow \exists T \subset A: f: T \to B$ is bijective

Proof: For every $b \in B$, $f^{-1}(b) := \{a \in A|f(a) = b\} \neq \emptyset$, since $f$ is surjective. Therefore, the set $f^{-1}(b)$ contains at least one element. For every $b \in B$, remove elements (if necessary) $a \in A$ such that $f^{-1}(b)$ becomes a singleton. Call the set of removed elements $R$. Then clearly $R \subset A$ and it follows that $f: A - R := T \subset A \to B$ is a bijection, since for any $b \in B$, there is only one element in the domain that gets mapped to $b \quad \triangle$

Applying the lemma to $f$ above, we find that there is a set $T \subset \mathbb{Z} \times \mathbb{Z_0}$ such that $|T| = |\mathbb{Q}|$

Since $\mathbb{Q}$ is infinite, $T$ is infinite. Also, $\mathbb{Z} \times \mathbb{Z_0}$ is countable, because it is the product of two countable sets and Rudin already proved that every infinite subset of a countable set is countable, so it must follow that $T$, and therefore $\mathbb{Q}$, is countable.

Does this seem correct?

• You're using the axiom of choice. Jul 13, 2017 at 19:28
• Am I? Why would that be bad? (I have heard about this controversial axiom but I don't know what it exactly states, I'm just a first year university math student). My guess is that I use it when I remove elements.
– user370967
Jul 13, 2017 at 19:29
• You use it when you choose one element per $f^{-1}(b)$. Of course here for this specific theorem you don't need it, precisely because everything is countable. Jul 13, 2017 at 19:44
• @HennoBrandsma : how does "countable implies well orderable" require countable choice ? You can always establish a bijection with $\mathbb{N}$ and transfer the canonical well-ordering of $\mathbb{N}$. Since you fix it once and for all at the beginning of the proof, there's no choice needed Jul 15, 2017 at 7:00
• You assert that the product of two countable sets is countable. Although this is true and does not require the Axiom of Choice, I would ask whether this was already covered in the text or whether you already knew it ( or possibly both). ... BTW, the Axiom of Choice is not controversial, but the Q of which results need it, and which do not, is of considerable interest in the study of logical foundations. Aug 1, 2017 at 2:38

You can simplify this argument by noting that the set

$A:= \left\{(a,b) \in \mathbb{Z} \times \mathbb{Z_{\neq 0}} : \gcd(a,b) = 1\right\} \subset \mathbb{Z} \times \mathbb{Z_{\neq 0}}$ is isomorphic to $\mathbb{Q}$.

$\textbf{Proof.}$ Consider the map $f: A \to \mathbb{Q}$ given by $(a,b) \mapsto \frac ab$. That $f$ is surjective is equivalent to the fact that any rational number $r$ can be written as $p/q$ with $p,q \in \mathbb{Z}, q \neq 0, \gcd(p,q) = 1$. Also, $(a,b) = (c,d)$ in $A$ $\iff a=c \ \& \ b=d$ in $\mathbb{Z}$ $\iff \frac ab = \frac cd$ in $\mathbb{Q}$ with $\gcd(a,b) = \gcd(b,c) = 1$, so $f$ is a well-defined bijection.

Since $A \subset \mathbb{Z} \times \mathbb{Z_{\neq 0}}$, it is countable. It follows that $\mathbb{Q}$ is as well.

EDIT

Also, here's a different proof of your lemma, providing that |A|=|B|, and $f$ is a function.

$f:A \to B$ is a surjective function, so it has an injective left inverse $g:B \to A$. As $|A| =|B|$, $g$ must be a bijection.