How do I prove that there doesn't exist a set whose power set is countable? I don't even know where to begin on this one.
Let $A$ be a countable set. In other words, $|A| = |\mathbb{N}|$. I'm trying to prove that there doesn't exist an $x$ such that $\mathcal{P}x = A$. 
Maybe a proof by contradiction? Suppose there was a set $x$ whose power set was countable ...
 A: HINT: 


*

*Can the power set of a finite set be infinite?  

*Is the power set of a countably infinite set countable? In particular, is $\wp(\Bbb N)$ countable?

A: Here is a stronger fact (provable without the axiom of choice): If $\mathbb N$ injects into $\mathcal P(A)$, then in fact $\mathcal P(\mathbb N)$ injects into $\mathcal P(A)$. This is an elegant result of Kuratowski, and appears as Théorème B in 

Alfred Tarski. Sur les ensembles finis, Fund. Math. 6 (1924), 45–95.

(Clearly, if $\mathcal P(A)$ is infinite, then so is $A$. The stronger fact is fairly easy if one assumes that $\mathbb N$ injects into $A$. But it is consistent with the axioms of set theory without choice that there are infinite sets into which $\mathbb N$ does not inject. Even more, it is consistent that there are infinite sets $A$ such that $\mathbb N$ does not inject into $\mathcal P(A)$, so the assumption cannot be weakened.)
The outline of the proof is simple: If $\mathbb N$ injects into $\mathcal P(A)$, then there is a surjection $g$ from $A$ onto $\mathbb N$. But then we have an injection $f$ from $\mathcal P(\mathbb N)$ into $\mathcal P(A)$, given by $f(X)=\{a\in A\mid g(a)\in X\}$. The difficult step is to produce the surjection $g$. 
I wrote the details of this argument in my blog.
