[Math] Does $\mathbb{N\times(N^N)}$ have the same cardinality as $\mathbb N$ or $\mathbb R$

elementary-set-theory

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?

Best Answer

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

Related Question