Constructing a Bijection to Demonstrate Countably Infinite Set

Question

I'm looking to prove that $\mathbb{Z} \times \mathbb{Q}$ is countably infinite by constructing a bijection $f: \mathbb{Z} \times \mathbb{Q} \rightarrow \mathbb{N}$. I understand that I can demonstrate $\mathbb{Z} \times \mathbb{Q}$ is countably infinite by showing that $\mathbb{Z}$ and $\mathbb{Q}$ individually are countably infinite, and thus it follows that their Cartesian product is countably infinite. However, I was more curious how one would construct a bijection to prove this, since by definition one must exist.

Answer 1

The existence of a bijection $b: \mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,B\rightarrow\mathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:A\times B\rightarrow\mathbb{N}$, given by $$m:A\times B\rightarrow\mathbb{N}:(x,y)\mapsto b(i(x),j(y)).$$ If $i$ and $j$ are each bijective, then $m$ is a bijection.

Exercise: check the various claims I've made in the previous paragraph!

So the point is that once you've picked your pairing function $b$, and your bijections $\mathbb{Z}\rightarrow\mathbb{N}$ and $\mathbb{Q}\rightarrow\mathbb{N}$, you've already got all the ingredients needed to give a bijection $\mathbb{Z}\times\mathbb{Q}\rightarrow\mathbb{N}$. It is worth noting that there's no reason to expect the resulting bijection to be nice - indeed, is there even a nice bijection between $\mathbb{Q}$ and $\mathbb{N}$? (OK fine, that's totally subjective, but my point is that we shouldn't hope for an easy-to-write-down example of the type of bijection we know must exist.)