Power Sets & Partitions

All 2^n subsets, and splitting a set into disjoint blocks.

The idea

The power set of a set $A$, written $P(A)$, is the set whose elements are all the subsets of $A$, from the empty set $\varnothing$ up to $A$ itself.

To count the subsets, build one: for each element of $A$, decide whether it is in or out. Every run of decisions produces a subset, distinct runs produce distinct subsets, and every subset arises from some run, so subsets correspond exactly to runs of decisions. With $n$ elements there are $n$ independent two-way decisions, so $|P(A)| = 2^{n}.$

A partition of $A$ divides it into blocks: non-empty subsets that are pairwise disjoint and whose union is all of $A$. These three conditions say precisely that every element of $A$ lies in exactly one block, so a partition records a way of sorting the elements of $A$ into piles.

Ways to work on it

• Walkthrough. Counting subsets (2^n) and recognizing valid partitions.
• Practice. Compute the size of a power set.
• Hardest. Count every partition of a small set.

Not sure where to start? Take the ten-question placement test.