0
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ $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$? $\endgroup$ – drhab Aug 24 '14 at 19:12
  • $\begingroup$ Can you elaborate on "a set of functions such that $g_n\colon \mathbb{N}\to \{n\}$..."? I don't understand your notation. $\endgroup$ – Tomek Kania Aug 24 '14 at 19:15
  • $\begingroup$ EDIT: A \subset \mathcal{F}(\mathbb{N}; \mathbb{N}) $\endgroup$ – Guilherme Duarte Aug 24 '14 at 19:16
  • $\begingroup$ How would be a proof for the proposition? $\endgroup$ – Guilherme Duarte Aug 24 '14 at 19:18
  • 1
    $\begingroup$ 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... $\endgroup$ – Did Aug 24 '14 at 19:24
7
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Sorry. I still don't get it. Could you explain more the function $g$ and $\Phi$ $\endgroup$ – Guilherme Duarte Aug 24 '14 at 20:58
  • 1
    $\begingroup$ @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$). $\endgroup$ – vociferous_rutabaga Aug 24 '14 at 21:06
  • 1
    $\begingroup$ 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. $\endgroup$ – vociferous_rutabaga Aug 24 '14 at 21:07
  • 1
    $\begingroup$ Finally, I've got it. Thanks!!!!!!! $\endgroup$ – Guilherme Duarte Aug 24 '14 at 21:19
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ OP wrote: "Can someone verify my proof below?" He's not asking for the answer. $\endgroup$ – Thomas Andrews Aug 24 '14 at 19:26
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @Guilherme D Look at this $\endgroup$ – leo Aug 25 '14 at 3:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.