2
$\begingroup$

I'm not sure if this statement is correct, but my friend said so.

The problem arose from this T/F question: Let $F=\{f: f$ be a primitive recursive function from $\mathbb{N}$ to $\mathbb{N}\}$, then $2^F$ (Power set of $F$) is uncountable.

And its answer is True. The set of primitive recursive functions is countable, and I would like to know the proof to the statement above...I believe I've seen it somewhere in the book but can't find it now.

Thank you for your time.

$\endgroup$
5
$\begingroup$

This is Cantor's diagonalization lemma:

Let $S$ be a countable set and suppose that there is a bijective function $\phi: S \to 2^S$. Let $U = \{x \in S \mid x \notin \phi(x)\}$. (Notice that our only assumption is the existence of the bijective function.)

Since $U \in 2^S$, and $\phi$ is bijective, there must be a $u \in S$ s.t. $\phi(u) = U$.

Now I ask you: Is $u \in U$?

If you answer that question, you have the answer: $\phi$ cannot exist! Hence $2^S$ cannot be countable. You should also show that there is an injective function $\psi: S \to 2^S$, but this is trivial: $\psi(x) = \{x\}$, so $|S| \leq |2^S|$.

To complete the argument you must also show that there cannot be a bijective function from $\mathbb{N}$ to $2^S$ but this is immediate since there is one from $\mathbb{N}$ to $S$.

$\endgroup$
  • $\begingroup$ $x \notin \phi(x)$ $\endgroup$ – Hendrik Jan Jan 17 '13 at 12:31
  • $\begingroup$ @HendrikJan Thank you, updated. That's how it goes when you "leave it to the reader" ... :) $\endgroup$ – Pål GD Jan 17 '13 at 12:32

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.