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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Aug 30 '18 at 3:14
  • 1
    $\begingroup$ You're already invoking Cantor's theorem, can't you just say $\aleph_0 \leq |A| < |\mathcal{P}(A)|$? $\endgroup$ – guidoar Aug 30 '18 at 3:20
  • $\begingroup$ @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? $\endgroup$ – guidoar Aug 30 '18 at 3:22
  • $\begingroup$ @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. $\endgroup$ – LE Anh Dung Aug 30 '18 at 3:29
  • 1
    $\begingroup$ @LeAnhDung I think it looks fine :) $\endgroup$ – 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)|$$

by Cantor's theorem.

  • $\begingroup$ I think we need countable choice for the injection $\mathbb{N} \to A$ though. $\endgroup$ – user370967 Aug 31 '18 at 12:29
  • $\begingroup$ Of course, we do ^^ $\endgroup$ – LE Anh Dung Aug 31 '18 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.