# Proof that the set of all functions from $\mathbb N$ to $\mathbb N$ is not enumerable

I'm trying to show that the set of all functions from $\mathbb N$ to $\mathbb N$ is not enumerable. Can someone verify my proof below?

Proof: Let $\mathcal{F}(\mathbb{N}; \mathbb{N})$ be the set of all functions such that $f: \mathbb{N} \rightarrow \mathbb{N}$
Define $\Phi: \mathbb{N} \rightarrow \mathcal{F}(\mathbb{N}; \mathbb{N})$ and suppose by hypothesis $\Phi$ is surjective.
Let $A \in \mathcal{F}(\mathbb{N}; \mathbb{N})$ be a set of functions such that $g_{n}: \mathbb{N} \rightarrow \{n\} \neq \Phi_{n}$.
Then, $A \neq \Phi$, $\Phi$ is not surjective by the Cantor's diagonal argument. Contradiction!

EDIT: $A \subset \mathcal{F}(\mathbb{N}; \mathbb{N})$

• $A\in\mathcal F(\mathbb N;\mathbb N)$ means that $A$ is a function. However, you call it a set of functions... Is $g_n$ the function sending each element of $\mathbb N$ to $n$? What is the relation between $g_n$ and $A$? Commented Aug 24, 2014 at 19:12
• Can you elaborate on "a set of functions such that $g_n\colon \mathbb{N}\to \{n\}$..."? I don't understand your notation. Commented Aug 24, 2014 at 19:15
• EDIT: A \subset \mathcal{F}(\mathbb{N}; \mathbb{N}) Commented Aug 24, 2014 at 19:16
• How would be a proof for the proposition? Commented Aug 24, 2014 at 19:18
• Did you change the question from "Verify my proof" to "Give a proof"? Because the current version of the proof you suggest is difficult to save...
– Did
Commented Aug 24, 2014 at 19:24

I think your argument is salvageable, but there are definitely some issues.

On the second line, you want to say something along the lines of "Suppose that there exists a surjective function $\Phi: \mathbb N \mapsto \mathcal{F}(\mathbb N; \mathbb N)$." Using the word "define" is a little misleading in this context.

The third line of your proof does not make sense as written. It looks like you are trying to adapt the canonical proof of Cantor's Theorem, but you've adapted the method in a way that doesn't quite work. In this case, you want to define a function that cannot be in the range of $\Phi$. Trying to cook up some special subset of $\mathcal F(\mathbb N; \mathbb N)$ isn't helpful.

The idea of applying a "diagonalization argument" is a good one (forget about $A$). Define $g: \mathbb N \to \mathbb N$ by $$g(n)=\Phi(n)(n)+1.$$ Note that this makes sense, since $\Phi(n): \mathbb N \rightarrow \mathbb N$ is a function for each $n$, so we can apply it to the natural number $n$. Also note that $g \neq \Phi(n)$ for any $n$: the values of $g$ and $\Phi(n)$ at $n$ differ. This contradicts surjectivity of $\Phi(n)$.

• Sorry. I still don't get it. Could you explain more the function $g$ and $\Phi$ Commented Aug 24, 2014 at 20:58
• @GuilhermeDuarte no problem. The function $\Phi$ is a surjection from $\mathbb N$ to $\mathcal F(\mathbb N; \mathbb N)$, assumed to exist for a contradiction. This means that $\Phi(n): \mathbb N \to \mathbb N$ is a function for each $n$. We can consider $\Phi(n)(k) \in \mathbb N$ for each $k$; this is the value of the function $\Phi(n)$ at $k$. Now, we want to define $g: \mathbb N \to \mathbb N$ so that $g \notin \Phi(\mathbb N)$. We do this by a "diagonalization" trick: defined $g$ by $g(n) = \Phi(n)(n)+1$, and for each $n$. Then $g$ and $\Phi(n)$ differ at a value (namely $n$). Commented Aug 24, 2014 at 21:06
• Since $g$ differs from any $\Phi(n)$ at a value, $g$ is not equal to any element in the image of $\mathbb N$ under $\Phi$, which contradicts the surjectivity assumption. Commented Aug 24, 2014 at 21:07
• Finally, I've got it. Thanks!!!!!!! Commented Aug 24, 2014 at 21:19

This proof based on the fact that $\mathcal{P}(\Bbb N)$ is not enumerable :
Let $\varphi:\mathcal P(\Bbb N)\to \mathcal F(\Bbb N,\Bbb N)$ defined by $\varphi(A)=\chi_A$ , $\varphi$ is injective and $\mathcal P(\Bbb N)$ is not enumerable, hence $\mathcal F(\Bbb N,\Bbb N)$ is not enumerable.

• OP wrote: "Can someone verify my proof below?" He's not asking for the answer. Commented Aug 24, 2014 at 19:26

Note that if $f$ is a function from $\mathbb N$ to $\mathbb N$, then we can identify $f$ with the sequence of natural numbers $\langle a_1, a_2, \dots \rangle$, where $f(n) = a_n$.

If you define $\mathcal F$ as the set of all such sequences, then using diagonalization will be much more natural and clear.

• @Guilherme D Look at this
– leo
Commented Aug 25, 2014 at 3:42