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.)

Answer 2

It is not hard to construct explicitly an injective function $f\colon \mathbf{Z}\times \mathbf{Q}\to\mathbf{N}$. For this we will use base 13 representation of elements in the codomain. We need symbols (digits) to represent numbers 10, 11 and 12. Let us agree to use $t, e, w$ for that purpose.

Now take an element in the domain, e.g., $x=(-7, 308/17)$ we define $f(x)$ as below: stripping away the parentheses $x$ is the string of symbols: $-7, 308/17$. Now in this replace minus sign by $t$, comma by $e$ and slash by $w$ getting $f(x)=t7e308w17$. This expression is a number in base 13 (hence a non-negative integer). As two different strings of digits represent two different integers we see that $f$ indeed is an injection to non-negative integers.

Answer 3

If you have formulas for bijections $\mathbb N \mapsto \mathbb Z$ and $\mathbb N \mapsto \mathbb Q$, then the proof that $\mathbb Z \times \mathbb Q$ is countable will give you a formula for a bijection $\mathbb N \mapsto \mathbb Z \times \mathbb Q$.