Power Sets

Math for CS · Axiom Academy

The set of all subsets — and its surprising connection to binary Example: Let A = \ 1, 2\ . The subsets of A are: (the empty set is always a subset) \ 1, 2\ (the set itself is always a subset) So (A) = \ , \ 1\ , \ 2\ , \ 1,2\ \ . Why? For each element in A , you have exactly two choices: include it or exclude it . With n independent binary choices, there are 2 2 2 = 2^n possible subsets. Let A = \ a, b, c\ . We can list all 2^3 = 8 subsets: Notice the pattern in the table above: the Yes/No columns form all possible binary strings of length n . READ = 0b100 , WRITE = 0b010 , EXEC = 0b001 permissions = READ | EXEC → 0b101 → the subset \ R, X\ A common exam question: what is ( ) ? Be careful: ( ) . The power set of the empty set is not empty — it has one element. You can take the power set of a power set. The cardinalities grow dramatically: |A| = 2 → | (A)| = 4 → | ( (A))| = 16 |A| = 3 → | (A)| = 8 → | ( (A))| = 256 |A| = 4 → | (A)| = 16 → | ( (A))| = 65 , 536 (A) is the set of all subsets of A | (A)| = 2^ |A| — each element is either in or out Subsets correspond to binary strings (bitmasks) Exponential growth makes brute-force subset enumeration intractable for large sets

This is the written version of the interactive lesson above. See the full Math for CS course.