# Constructing a Bijection to Demonstrate Countably Infinite Set

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.

## 3 Answers

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

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.

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