Cfrgtkky

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.

The existence of a bijection $b: mathbb{N}timesmathbb{N}rightarrowmathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,Brightarrowmathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:Atimes Brightarrowmathbb{N}$, given by $$m:Atimes Brightarrowmathbb{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}rightarrowmathbb{N}$ and $mathbb{Q}rightarrowmathbb{N}$, you've already got all the ingredients needed to give a bijection $mathbb{Z}timesmathbb{Q}rightarrowmathbb{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 $fcolon
mathbf{Z}times mathbf{Q}tomathbf{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$.