Flaw in my proof that $\mathbb Q$ is countable?

158 Views Asked by At

I got an idea about an easy proof that $\mathbb Q$ is countable, one that does not involve the typical "snake around a grid" argument. However, I fear that I am making the same mistake in using an inequality with infinite cardinalities that I seemed to make in an early attempt at a short proof of the Cantor–Schröder–Bernstein theorem. Have I made a mistake, or is this a legitimate proof? If this proof is not correct, can it be remedied with a simple fix (in your own judgment of what a "simple" fix would be)?

Take it as known, for countable $A$ and $B$, $A\times B$ also is countable. Also, take it as known that $\mathbb Z$ and $\mathbb Z_{>0}$ are countable.

Let $f:\mathbb Z\times\mathbb Z_{>0}\rightarrow \mathbb Q$ be defined by $f(a,b)=\frac{a}{b}$. Then, given $q\in \mathbb Q$, there is $(a,b)\in Z\times\mathbb Z_{>0}$ such that $f(a,b)=q$, so $f$ is surjective.

Therefore, $cardinality(Z\times\mathbb Z_{>0})\ge cardinality(\mathbb Q)$.

Since $Z\times\mathbb Z_{>0}$ is countable, then $\mathbb Q$ must be countable, too. $\square$

(A simple fix might be that it requires proof to say that inequalities with infinite cardinalities work the way we might hope, but that such proof is given in the proof of the CSB theorem, to which an answer to the linked question alludes.)