Question: I thought the set of natural number functions would be of the same cardinality as the countably infinite product of $\mathbb{N}$, which is countable.

Each natural number function can be identified with an infinite-tuple of $\mathbb{N}$ by letting the $i$th entry be the image of the number $i$ under the function.

Answer: 
Cantors diagonalisation method: If it is countable then it is $F=\{f\_1,f\_2,\ldots\}$. But the function $g(i):=f\_i(i)+1$ is not in $F$. A contradiction to the initial assumption. 

Proof:

For every $i $ we have
$$g(i)=f\_i (i)+1 \implies g (i)\ne f\_i (i) \implies g \ne f\_i $$
and so $g \notin F$.
Let's consider the following set: $F = \{ f:D \in 2^\mathbb{N} \rightarrow \mathbb{N} \ | \ f(x) = x \}$;

Notice how there is a function $f$ for each possible set of natural numbers residing inside $2^\mathbb{N}$, which will allow us to draw the following conclusion: $|F| = |2^\mathbb{N}|$.

Now, observe how $F$ is a much smaller set than [$\mathbb{N}^\mathbb{N}$](http://www.u.arizona.edu/~mwalker/econ519/Econ519LectureNotes/SetOfAllFunctions.pdf)(because it contains only functions of the form $f(x)=x$), but even so, it's uncountable. Therefore $\mathbb{N}^\mathbb{N}$ is evidently uncountable since it's a superset of $F$.

$F \subseteq \mathbb{N}^\mathbb{N}, |F| = |2^\mathbb{N}| \implies |\mathbb{N}^\mathbb{N}|=|2^\mathbb{N}| \ \ \ \square $