Problem Detail: 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.
Asked By : goldfrapp04
Answered By : Pål GD
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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/8986 3.2K people like this
