Exercise 628Logic, sets and proofs › Sets and mapsL1Added 4 Nov 2026
Cardinality of the power set
#power set#cardinality#induction
Statement
Let be a set with elements.
- Show that .
- Deduce that .
Hint
A subset of either contains or not. Multiply equalities for .
Show solutionHide solution
Solution
1. The subsets of split into: (a) those contained in , of which there are ; (b) those of the form with , also in number. Hence .
2. Multiplying for :
Since , , so , and .
Conclusion. .