# 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

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

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$.

• Why isn't it in $F$? – Jason Oct 13 '16 at 16:35
• @Jason I added a proof. This is similar to Cantor's diagonalisation proof. – miracle173 Oct 14 '16 at 4:55
• @miracle173 Thank you very much for this answer. How do you then prove that $card(F)=card(R)$, where R is real numbers. – Daniele1234 Feb 9 '18 at 23:53

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 '15 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 '15 at 18:25

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

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

• I'd like to understand what's wrong behind this reasoning. – Alex B. Nov 1 '18 at 9:16