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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.