This question already has an answer here:

Cantor diagonal argument is a powerful proof technique. It has been used for a lot of proofs. For instance, it has been used to prove that $|\mathbb{N}| < |\mathbb{R}|$.

What can we say about the cardinality of $\mathbb{N}^m$, being $m$ a positive integer?

Can I relate the cardinality of $\mathbb{N}^m$ and $\mathbb{N}^p$, being $p$ another positive integer?

At a first glance, I can say that $|\mathbb{N}^m| < |\mathbb{R}^m|$. I don't know if this is right... It somehow makes sense and I just hope that this is an inherited property.

On the other hand, I don't feel good saying that $$|\mathbb{R}^m| < |\mathbb{N}^{m+1}|.$$

Now, I would like to know if there exists some kind of ordering for these sets cardinality (I guess so).

If it exists, can it be proved again using the Cantor diagonal argument? I mean, is there a multidimensional variant of this proof-strategy?


marked as duplicate by Hayden, Shailesh, Ramiro, Leucippus, Edward Jiang May 5 '16 at 0:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ You can actually show that $|\mathbb{N}^m|=|\mathbb{N}|$. See proofwiki.org/wiki/… $\endgroup$ – Vincent May 4 '16 at 21:04
  • $\begingroup$ @Red the question you have linked does not talk about Cantor Diagonal Argument (or variation)...should this really be a case of a question marked as duplicate? $\endgroup$ – the_candyman May 4 '16 at 21:38

As mentioned in the comments, $|\mathbb{N}^m|=|\mathbb{N}|$ for all $m\geq 1$. To get an idea of why this is the case, one can use Cantor-Schroeder-Bernstein, which says if $f:A\rightarrow B$ and $g: B\rightarrow A$ are injections, then there exists a bijection between $A$ and $B$. Informally, it says that if $B$ is no larger than $A$, and $A$ is no larger than $B$, then they have to be, in fact, the same size.

I'll show an injection $f: \mathbb{N}^2\rightarrow \mathbb{N}$; you can fill in the details to expand this to an injection $f: \mathbb{N}^m\rightarrow \mathbb{N}$ for larger $m$.

We define $f$ by $$f(n,m)=2^n3^m$$ This is an injection by the Fundamental Theorem of Arithmetic, so that if $2^n3^m=2^a3^b$, because these are prime factorizations, we know that $a=n$ and $m=b$. In other words, $f(n,m)=f(a,b)$ implies $(a,b)=(n,m)$.

To get an injection the other way, we can define $g:\mathbb{N}\rightarrow \mathbb{N}^2$ by $g(n)=(n,0)$.

In fact, $\mathbb{R}^m$ has the same size as $\mathbb{R}$ for every $m\geq 0$ as well!

  • $\begingroup$ thanks a lot for your answer $\endgroup$ – the_candyman May 4 '16 at 21:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.