Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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