Definition: A set $A$ is countable if it is finite or if there is a bijection $c: \mathbb N \to A$; otherwise it is uncountable.
Theorem: if $A$ is an infinite set, then $\mathcal{P}(A)$ is uncountable.
Cantor’s theorem: suppose that $f$ is a mapping from a set $A$ to its power set $\mathcal{P}(A)$. Then $f$ is not surjective.
Lemma 1: assuming the Axiom of Dependent Choice, if $A$ is an
infinite set, then $A$ contains a countably infinite subset.
Lemma 2: $A$ is countable if and only if $A=\emptyset$ or there exists a surjection from $\mathbb N$ onto $A$.
The proof is quite short, but I'm not sure if I apply Lemmas correctly. Please help me check it out!
Proof: $A$ is an infinite set, then by Lemma 1 there exists a countably infinite subset $B$ of $A$. Thus there exists a bijection $g: \mathbb N \to B$. Assume the contrary that $\mathcal{P}(A)$ is countable, then $\mathcal{P}(B) \subseteq \mathcal{P}(A)$ is countable too. By Lemma 2, there exists a surjection $h: \mathbb N \to \mathcal{P}(B)$. As a result, $h \circ g^{-1}: B \to \mathcal{P}(B)$ is surjective. This contradicts Cantor's theorem. Hence $\mathcal{P}(A)$ is uncountable.
Best Answer
Let $A$ be an infinite set.
It is well known that we can find an injection $\mathbb{N} \to A$. Hence, $|\mathbb{N}| \leq |A|$ and it follows that $$|\mathbb{N}| <|\mathcal{P}(\mathbb{N)}| \leq |\mathcal{P}(A)|$$
by Cantor's theorem.