# If $A$ is infinite, then $\mathcal{P}(A)$ is uncountable

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.

• What is your definition of uncountable? Is it that it is strictly larger than $\mathbb N$? If it simply means infinite and not countable (which is the standard usage), then it is easier to prove that if $\mathcal P(A)$ is countable then in fact it is finite. This has the advantage of not using any form of the axiom of choice. – Andrés E. Caicedo Aug 30 '18 at 3:14
• You're already invoking Cantor's theorem, can't you just say $\aleph_0 \leq |A| < |\mathcal{P}(A)|$? – guidoar Aug 30 '18 at 3:20
• @AndrésE.Caicedo I'm quite interested in the proof of 'if $\mathcal{P}(A)$ is countable then it is finite', would you mind giving a sketch of it? – guidoar Aug 30 '18 at 3:22
• @AndrésE.Caicedo "A set $A$ is countable if it is finite or if there is a bijection $c: \mathbb N \to A$; otherwise it is uncountable." I have edited my post to add this definition. – LE Anh Dung Aug 30 '18 at 3:29
• @LeAnhDung I think it looks fine :) – guidoar Aug 30 '18 at 3:47

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)|$$
• I think we need countable choice for the injection $\mathbb{N} \to A$ though. – user370967 Aug 31 '18 at 12:29