Prove that the set of $\mathbb{N} \times \mathbb{N} \times \mathbb{N}$ is countable.

I have seen proofs of $\mathbb{N}\times\mathbb{N}$. The proof by list where you list each element in a pair of elements and then counting them diagonally is the most convincing. I have two thoughts in mind:

1. Write it as a composition of functions. Show that both functions are bijections, so the composition is also a bijection.
2. Show that $\mathbb{N} \times \mathbb{N} \times \mathbb{N}$ has the same cardinality as $\mathbb{N}\times\mathbb{N}$, and $\mathbb{N}\times\mathbb{N}$ has the same cardinality as $\mathbb{N}$.

Generally, I'm having difficulty going from $\mathbb{N}\times\mathbb{N}\times\mathbb{N}$ to $\mathbb{N}\times\mathbb{N}$, since it easy to prove the bijection from $\mathbb{N}\times\mathbb{N}$ to $\mathbb{N}$.

• Youre idea in 1. seems like a good approach. – JJC94 Oct 31 '17 at 0:48
• It's not a proof-explanation if you don't point at a specific proof and ask us to explain it. – Asaf Karagila Oct 31 '17 at 0:51
• Consider the Cantor pairing. – Wuestenfux Oct 31 '17 at 9:42

If you already know that $\Bbb{N\times N}$ is countable, fix a bijection $f\colon\Bbb{N\times N\to N}$. Now consider $g\colon\Bbb{N\times N\times N\to N\times N}$ defined as: $$g(n,m,k)=(n,f(m,k)),$$ or better yet $h\colon\Bbb{N\times N\times N\to N}$ defined as $$h(n,m,k)=f(n,f(m,k))$$ and cut out the middle-man.

As my freshman discrete mathematics professor used to tell us, go home and convince yourself this is correct.

• I can convince myself this is correct, but how can I prove it to a stubborn skeptic? – tigerustin Nov 1 '17 at 2:11
• Slowly and carefully by verifying the definitions of a bijection. – Asaf Karagila Nov 1 '17 at 6:53
• I proved injectivity. How would I prove surjectivity? – tigerustin Nov 1 '17 at 20:21
• Exactly the same. Slowly, carefully and by using the fact that $f$ is already surjective itself. – Asaf Karagila Nov 1 '17 at 20:23
• I really don't understand. Can you explain further please? I don't want to have to start another thread on this question. – tigerustin Nov 2 '17 at 2:10

Why not think in stages? Let $\varphi : \mathbb{N}\times\mathbb{N} \to \mathbb{N}$ denote your favorite bijection. But then

$$\mathbb{N} \times \mathbb{N} \times \mathbb{N} = (\mathbb{N} \times \mathbb{N}) \times \mathbb{N} \approx \varphi(\mathbb{N}\times \mathbb{N}) \times \mathbb{N} = \mathbb{N} \times \mathbb{N} \approx \varphi(\mathbb{N}\times \mathbb{N}) = \mathbb{N}$$ (where, in this context, $=$ means equality, and $\approx$ denotes "of the same cardinality"). You can do this for any number of copies of $\mathbb{N}$ via an induction argument.

Consider $f:\mathbb N \times \mathbb N \times \mathbb N \to \mathbb N$ given by $f(a,b,c)=2^a3^b5^c$

and use the Fundamental theorem of arithmetic for a cute solution.

• Gives an injective mapping. – Wuestenfux Oct 31 '17 at 9:41
• And it is clearly infinite, so... – Andres Mejia Oct 31 '17 at 14:06
• It would be difficult to prove bijectivity of this function? – tigerustin Nov 1 '17 at 2:12
• It’s not bijective. It is an infinite subset of the natural numbers – Andres Mejia Nov 1 '17 at 2:15

I like to think of 'countable' as 'listable' ... That is, as long as you can create a list of objects and ensure that all elements of some set $S$ are somewhere on that list, then $S$ is countable. To me, the advantage of that kind of thinking is that elements from $S$ may be repeated on the list, and that the list may even contain objects that are not in $S$; as long as every element of $S$ is at least once in the list, it's clear that $S$ is countable. As such, this method avoids having to construct explicit and possibly complicated bijections.

So, how can we create a list of all elements of $\mathbb{N} \times \mathbb{N} \times \mathbb{N}$?

Here is one way:

First, get all triples with elements that sum to $0$: which is just $<0,0,0>$

Now get all those that sum to $1$: $<1,0,0>,<0,1,0>,<0,0,1>$

Then those that sum to $2$, then $3$, etc.

Thus, the list is:

$<0,0,0>,<1,0,0>,<0,1,0>,<0,0,1>,<2,0,0>,<1,1,0>,...$

Since for any $n$ there can only be finitely many triples whose elements sum to $n$, you will eventually get to every triple.

Note that this is of course just the same thing as diagonally going through an array of elements, just now in $3$ dimensions.

• Reminiscent of the method I know for showing the algebraics are countable. Nice. – Kaj Hansen Oct 31 '17 at 2:34

Cantor-Bernstein's Theorems states that if $A$ and $B$ are two sets and there exists two injections $f:A \to B$ and $g:B \to A$ then there is a biyection from $A$ to $B$ (i.e. $A$ and $B$ have the same cardinality).

Let $f:\mathbb{N} \times \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ be defined as $f(m,n,k)=2^n \cdot 3^m \cdot 5^k$, then if $f(m_1,n_1,k_1) = f(m_2,n_2,k_2) \Leftrightarrow 2^{m_1}3^{n_1}5^{k_1}=2^{m_2}3^{n_2}5^{k_2}$, the Fundamental Theroem of Arithmetic shows that $m_1=m_2$, $n_1=n_2$ and $k_1=k_2$. Then $f$ is a injective function.

Next, consider the function $g:\mathbb{N} \to \mathbb{N} \times \mathbb{N} \times \mathbb{N}$ defined by $g(n)=(0,0,n)$, then $$g(n)=g(m) \Leftrightarrow (0,0,n) =(0,0,m) \Leftrightarrow n=m$$ and hence $g$ is injective.

Applying Canotr-Bernstein's Theorem gives that $\mathbb{N} \times \mathbb{N} \times \mathbb{N}$ is countable.

Using induction, you can easily prove this result for the product of any finite number of copies of $\mathbb{N}$. The hardest part of the proof is the base case, which is that $\mathbb{N} \times \mathbb{N}$ is countable. It seems you already have this result.

For the induction hypothesis, assume that $\displaystyle \prod^n \mathbb{N}$ is countable. Now we just need to show that $\displaystyle \prod^{n+1} \mathbb{N}$ is countable. First, note that can write the $(n\!+\!1)$-fold product in the form $\mathbb{N} \times \left( \displaystyle \prod^n \mathbb{N} \right)$. A bijection $\displaystyle f:\prod^n \mathbb{N} \rightarrow \mathbb{N}$ is guaranteed by the induction hypothesis, which we can use to construct a bijection between the $(n\!+\!1)$-fold product and $\mathbb{N} \times \mathbb{N}$:

$$(x_1, x_2, \cdots, x_{n+1}) \mapsto (x_1, f(x_2, x_3, \cdots, x_{n+1}))$$

And $\mathbb{N} \times \mathbb{N}$ is countable per the base case.