Prove the set $\Bbb Z^+ \times\Bbb Z^+ \times \Bbb Z^+$ is countable.

Question

Prove the set $\Bbb Z^+ \times \Bbb Z^+ \times \Bbb Z^+$ is countable.

I know you can use diagonal processing to prove that $\Bbb Z^+ \times \Bbb Z^+$ is countable, but how would you go from there?

User matcounterxamples.net's answer here gives the idea how to go from product of two to product of finitely many. — , Sep 09 '16 at 03:53
You may show that $$(a,b,c)\mapsto a+\binom{a+b-1}{2}+\binom{a+b+c-2}{3}$$ is a bijective map from $\mathbb{Z}^+\times\mathbb{Z}^+\times \mathbb{Z}^+$ to $\mathbb{Z}^+$ , for instance. — Jack D'Aurizio, Sep 09 '16 at 04:04
Map the triple $(a,b,c)$ to the number $2^a 3^b 5^c$. This is an injection (1-1 function) by the fundamental theorem of arithmetic, ie unique factorization into prime powers. So the triple product of the naturals fits nicely inside one copy of the naturals. Same trick for any finite product. — user4894, Sep 09 '16 at 04:15

score 0 · Answer 1 · answered Sep 09 '16 at 04:21

I have given this answer already two or three years ago. Let me repeat. Instead of constructing a bijection, I'll indicate how to give 1-1 function, call it $\phi$, from the 3-fold product to positive integers.

Instead of a formula for such a function, I'll write out the function for a specific element. You can figure out how to do it in general.

Here we go. What is $\phi(7,4,14)$?

Consider numbers written in base 11, where we use the digits $0,1,2,\ldots, 9$ as usual, and for number TEN we use the COMMA symbol. So $(7,4,14)$ after stripping off the parentheses represents a 6-digit number in base 11. It is the number $$ 4 + (1\times 11) + (10\times 11^2) + (4\times 11^3) + (10\times 11^4) + (7\times 11^5)$$ This number is defined as $\phi(7,4,14)$.

As base expansion is unique this is a 1-1 function.

score 0 · Accepted Answer · answered Sep 09 '16 at 04:26

As there exists a bijection $f\colon \Bbb Z^+\times \Bbb Z^+\to\Bbb Z^+$, there also is a bijection $\Bbb Z^+\times \Bbb Z^+ \times \Bbb Z^+ = (\Bbb Z^+\times \Bbb Z^+)\times \Bbb Z^+\to \Bbb Z^+\times \Bbb Z^+$, and so also a bijection $$ \Bbb Z^+\times \Bbb Z^+ \times \Bbb Z^+\to\Bbb Z^+\times \Bbb Z^+ \to \Bbb Z^+$$ namely $(x,y,z)\mapsto f(f(x,y),z)$.

score 0 · Answer 3 · answered Sep 09 '16 at 04:29

Since $\mathbb{Z}^+\times\mathbb{Z}^+$ is countable, there is an injective map from $\mathbb{Z}^+\times\mathbb{Z}^+$ to $\mathbb{Z}^+$.
It follows that there is an injective map from $\left(\mathbb{Z}^+\times\mathbb{Z}^+\right)\times \mathbb{Z}^+$ to $\mathbb{Z}^+\times \mathbb{Z}^+$.
By composition of injective maps, there is an injective map from $\mathbb{Z}^+\times\mathbb{Z}^+\times \mathbb{Z}^+$ to $\mathbb{Z}^+$,
hence $\mathbb{Z}^+\times\mathbb{Z}^+\times \mathbb{Z}^+$ is countable.

If you replace injective with bijective and find a bijective map from $\mathbb{Z}^+\times\mathbb{Z}^+$ to $\mathbb{Z}^+$, you also get a bijective map from $\mathbb{Z}^+\times\mathbb{Z}^+\times \mathbb{Z}^+$ to $\mathbb{Z}^+$. The one listed in the comments is a chance.

Prove the set $\Bbb Z^+ \times\Bbb Z^+ \times \Bbb Z^+$ is countable.

3 Answers3