Maths WorkshopMaths problems with full solutions
Exercise 628Logic, sets and proofs › Sets and mapsL1Added 4 Nov 2026

Cardinality of the power set

#power set#cardinality#induction

Statement

Let Ep={a1,…,ap}E_p=\{a_1,\ldots,a_p\} be a set with pp elements.

  1. Show that ∣P(Ep+1)∣=2∣P(Ep)∣|\mathcal{P}(E_{p+1})|=2|\mathcal{P}(E_p)|.
  2. Deduce that ∣P(En)∣=2n|\mathcal{P}(E_n)|=2^n.
Hint

A subset of Ep+1E_{p+1} either contains ap+1a_{p+1} or not. Multiply equalities for p=0,…,n−1p=0,\ldots,n-1.

Show solutionHide solution

Solution

1. The subsets of Ep+1E_{p+1} split into: (a) those contained in EpE_p, of which there are ∣P(Ep)∣|\mathcal{P}(E_p)|; (b) those of the form S∪{ap+1}S\cup\{a_{p+1}\} with S⊆EpS\subseteq E_p, also ∣P(Ep)∣|\mathcal{P}(E_p)| in number. Hence ∣P(Ep+1)∣=2∣P(Ep)∣|\mathcal{P}(E_{p+1})|=2|\mathcal{P}(E_p)|.

2. Multiplying ∣P(Ep+1)∣=2∣P(Ep)∣|\mathcal{P}(E_{p+1})|=2|\mathcal{P}(E_p)| for p=0,…,n−1p=0,\ldots,n-1:
∣P(En)∣=2n∣P(E0)∣.|\mathcal{P}(E_n)|=2^n|\mathcal{P}(E_0)|.
Since E0=∅E_0=\emptyset, P(E0)={∅}\mathcal{P}(E_0)=\{\emptyset\}, so ∣P(E0)∣=1|\mathcal{P}(E_0)|=1, and ∣P(En)∣=2n|\mathcal{P}(E_n)|=2^n.

Conclusion. ∣P(En)∣=2n|\mathcal{P}(E_n)|=2^n.