[Solved]: How to prove "The power set of a countable set must be uncountable"?

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

 Download Related Notes/Documents