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?

  • $\begingroup$ 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. $\endgroup$ – Peter Aug 26 '17 at 13:34
  • $\begingroup$ 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}$. $\endgroup$ – Clayton Aug 26 '17 at 13:35
  • 1
    $\begingroup$ $\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}}|$. $\endgroup$ – 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}$


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.