# The set of natural number functions is uncountable

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.

-
What is the question? –  Did Feb 22 at 6:36
I'm wondering where I went wrong in my thoughts on this problem, since I would say the set of functions is countable, but I know that it's actually uncountable. –  user125093 Feb 22 at 6:40
Ergo the "argument" that the product of countably many countable sets is countable is at best fishy, no? Actually this argument is wrong and you are probably mixing it up with the fact that the union of countably many countable sets is countable –  Did Feb 22 at 6:42
One. Two. Three. Four. Five. Six. And there are definitely more. –  Asaf Karagila Feb 22 at 6:57

The countably infinite product of $\mathbb{N}$ is not countable, I believe, by Cantor's diagonal argument.

-
I thought it's the case that a countable product of countable sets is countable. –  user125093 Feb 22 at 6:38
Countable union of countable sets is countable. Perhaps that is what you had in mind. –  André Nicolas Feb 22 at 6:40
Andre, yeah that must be the source of the confusion. Thank you! –  user125093 Feb 22 at 6:41

The cardinality of the natural number functions is $\mathbb{N}^{\mathbb{N}} \geq 2^{\mathbb{N}}$ and $2^{\mathbb{N}}$ is uncountable

-
$\geq$ actually (and indeed $=$, I believe). –  Eric Stucky Feb 22 at 6:42
@Eric Stucky: thanks –  WLOG Feb 22 at 6:47

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.

-

Every real number in $(0,1)$ has either one or two decimal representations. (Some have two, like $0.1000\ldots$ which is equal to $0.0999\ldots$.) But any way, each real number in $(0,1)$ gives at least one decimal representation. And that decimal representation can be viewed as a function from $\mathbb{N}$ to $\mathbb{N}$ by taking the $n$th digit after the decimal. (Actually, it's more restrictive: from $\mathbb{N}$ to $\{0,1,2,3,4,5,6,7,8,9\}$.)

For example, $0.72465\ldots$ can be used to define a function \begin{align}1&\mapsto7\\ 2&\mapsto2\\ 3&\mapsto4\\ 4&\mapsto6\\ 5&\mapsto5\\ \vdots&\phantom{\mapsto{}}\vdots\end{align}

So the set of functions from $\mathbb{N}$ to $\mathbb{N}$ contains a subset that is as large as the real interval $(0,1)$. (And seemingly even stronger, so does the set of functions from $\mathbb{N}$ to $\{0,1,2,3,4,5,6,7,8,9\}$. And seemingly even stronger still, if we used binary instead of decimal, so does the set of functions from $\mathbb{N}$ to $\{0,1\}$.)

-