# How to prove "The power set of a countable set must be uncountable"?

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

• $x \notin \phi(x)$ Jan 17, 2013 at 12:31
• @HendrikJan Thank you, updated. That's how it goes when you "leave it to the reader" ... :) Jan 17, 2013 at 12:32