Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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$.
