Prove that $ℕ^n$ is countable for every n∈ℕ
I'm stuck please help this quesion
$\begingroup$ $\endgroup$
3 
- 3$\begingroup$ Inducation.${}$ $\endgroup$Git Gud– Git Gud2014-03-17 01:25:51 +00:00Commented Mar 17, 2014 at 1:25
- $\begingroup$ Related: Show that the set of all finite subsets of $\Bbb N$ is countable. $\endgroup$MJD– MJD2014-03-17 19:37:30 +00:00Commented Mar 17, 2014 at 19:37
- $\begingroup$ possible duplicate of show that the set of all 2-element subsets of $\mathbb{N}$ is countable $\endgroup$MJD– MJD2014-03-17 19:38:08 +00:00Commented Mar 17, 2014 at 19:38
Add a comment |
3 Answers
$\begingroup$ $\endgroup$
Hint: Let $n\in\mathbf{N}$ and $p_1,\dots,p_n$ be distinct primes. Consider $f:\mathbf{N}^n\to\mathbf{N}$ given by $f(m_1,\dots,m_n)=p_1^{m_1}\cdots p_n^{m_n}$. What can you deduce from such a function?
$\begingroup$ $\endgroup$
2 A typical element of the product set is something like (3,58,15), the case $(n=3)$. Consider base 11 number system where this represents a unique (positive) integer by treating comma as symbol (digit) for ten: So the example above represents $$ 5 + ( 1\times 11) + (10\times 11^2)+ (8\times 11^3) + (5\times 11^4) +(10\times 11^5) +(3\times11^6)$$ This gives an injective function to positive integers, so the product set is countable.
- $\begingroup$ Never seen that before! That's pretty clever :) $\endgroup$Stella Biderman– Stella Biderman2014-03-17 03:55:41 +00:00Commented Mar 17, 2014 at 3:55
- $\begingroup$ @ Stella Biderman. I don't deserve the credit. Not my original. Read it in American Math Monthly (don't know the author) 25 years ago. That proof was for rational numbers where $1/2$ is read as a base 11 integer treating the slash as digit 10. I reused for this case. $\endgroup$P Vanchinathan– P Vanchinathan2014-03-17 06:54:34 +00:00Commented Mar 17, 2014 at 6:54
$\begingroup$ $\endgroup$
Hint: note that $\mathbb{N}^n =\mathbb{N}^{n-1} \times \mathbb{N}$. If you've proven that $\mathbb{N}^{n-1}$ is countable, then this must be the same as $\mathbb{N}\times \mathbb{N}$.
