# 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 '14 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 '14 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 '14 at 6:42
One. Two. Three. Four. Five. Six. And there are definitely more. –  Asaf Karagila Feb 22 '14 at 6:57

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.

-

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 '14 at 6:42
@Eric Stucky: thanks –  WLOG Feb 22 '14 at 6:47

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

-

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 '14 at 6:38
Countable union of countable sets is countable. Perhaps that is what you had in mind. –  André Nicolas Feb 22 '14 at 6:40
Andre, yeah that must be the source of the confusion. Thank you! –  user125093 Feb 22 '14 at 6:41
I have a question. Is the union of the set of natural number functions countable? –  Valentino Feb 19 at 18:15
@valentino That is actually the same thing as the countably infinite product of $\mathbb{N}$. Both can be abbreviated $\mathbb{N}^\mathbb{N}$. This is the same as how $\mathbb{R}^3$ can be seen as the space of functions from $\{1,2,3\} \to \mathbb{R}$ –  Eric Auld Feb 19 at 18:25