Computing Power Sets
What you'll learn: How to systematically find all subsets of a finite set and understand why a set with n elements always has exactly 2^n subsets.
The Core Idea
The power set of a set A is the set of all possible subsets of A, including the empty set and A itself. Computing a power set means listing every single subset.
Here's the key insight: for each element in your original set, you face a binary choice—either include it in a subset or don't. If you have n elements, you make this choice n times, giving you 2 × 2 × 2 × ... (n times) = 2^n total subsets.
Working Through Examples
Example 1: Let A = {1, 2}
For element 1: include it or not (2 choices)
For element 2: include it or not (2 choices)
Total: 2² = 4 subsets
The power set is: P(A) = { ∅, {1}, {2}, {1,2} }
Example 2: Let B = {a, b, c}
You have 3 elements, so expect 2³ = 8 subsets:
P(B) = { ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }
Notice how we systematically vary which elements to include: none, singles, pairs, then all three.
The Formula in Action
- 0 elements → 2⁰ = 1 subset (just ∅)
- 1 element → 2¹ = 2 subsets
- 2 elements → 2² = 4 subsets
- 3 elements → 2³ = 8 subsets
- 4 elements → 2⁴ = 16 subsets
Power sets grow exponentially fast!
Key Takeaway: For any finite set with n elements, its power set contains exactly 2^n subsets, found by systematically including or excluding each element.