0
$\begingroup$

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

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

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.

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

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.

$\endgroup$
3
$\begingroup$

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.

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

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.

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

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.

$\endgroup$
0
$\begingroup$

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.

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