0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.