# Does $\mathbb{N\times(N^N)}$ have the same cardinality as $\mathbb N$ or $\mathbb R$?

My attempts: Two sets have the same cardinality if there exists a bijection from set 1 to set 2.

• First, I found that $\mathbb{N^N}$ is a function from $\mathbb N$ to $\mathbb N$, so let $f$ be a function such that $f(x)=x$. It is injective, since if $f(x_1) = f(x_2)$, then $x_1 = x_2$. I can see that it is surjective, but I have no idea how to prove it.

• Now I want to prove that $\mathbb{N\times(N^N)}$ has the same cardinality as $\mathbb N$. I know that $\mathbb{N^N}$ has the same cardinality as $\mathbb N$, so if $|\mathbb{N^N}| = |\mathbb N|$, then $|\mathbb{N\times N^N}| =|\mathbb{N \times N}|$. Let $g$ be a function such that $g(m,n)=\frac{(m+n)(m+n+1)}{2}+m$. $g$ is injective, because if $g(m_1, n_1) = g(m_2, n_2)$, then $m_1 = m_2$ and $n_1 = n_2$. Again, I just don't know how to prove that the function is surjective. Also, I'm not sure if my justification for $g$ and $f$ being injective functions is correct and sufficient.

Now that I have defined two bijective functions, $f$ and $g$, I can prove that $\mathbb{Nx(N^N)}$ has the same cardinality as $\mathbb N$. Composition of two bijections is also a bijection, so $(f \circ g)$ is a bijective function from $\mathbb{Nx(N^N)}$ to $\mathbb N$.

Is my proof sufficient? Can you explain to me how to prove that a function is surjective and tell me if my reasoning is correct?

• An element of $\mathbb N^{\mathbb N}$ is an infinite sequence. Even, the set of infinite sequences only containing $1$ and $2$ is uncountable, as you can show with Cantor's diagonal method. – Peter Aug 26 '17 at 13:34
• It has the cardinality of $\Bbb R$. Just think of the decimal expansions of all positive real numbers in $(0,1)$. Try to think of a bijection between these numbers and $\Bbb{N}^{\Bbb N}$. – Clayton Aug 26 '17 at 13:35
• $\mathbb{N}^{\mathbb{N}}$ is not a function, but set of all functions from $\mathbb{N}$ to itself. Try to prove, that $|\mathbb{N}^{\mathbb{N}}|=|2^{\mathbb{N}}|$. – Przemek Aug 26 '17 at 13:36

$\mathbb{N}^\mathbb{N}$ is a function from $\mathbb{N}$ to $\mathbb{N}$
No - $\mathbb{N}^\mathbb{N}$ is the set of all functions from $\mathbb{N}$ to $\mathbb{N}$. And there are uncountably many of these.
HINT re: uncountability: Suppose I have a list $(f_i)_{i\in\mathbb{N}}$ of functions from $\mathbb{N}$ to $\mathbb{N}$. Then:
• What sort of thing is the function $g(x)=f_x(x)+1$?
• Can $g=f_i$, for any $i$?
• What does that tell you about the cardinality of $\mathbb{N}^\mathbb{N}$