Power sets, inclusion-exclusion, and comparing set sizes
The cardinality of a set measures its size -- the number of elements it contains. For finite sets this is simply counting, but the concept extends far beyond: power sets grow exponentially, inclusion-exclusion handles overlaps, and bijections let us compare sizes without counting at all.
These counting principles are the bridge between set theory and combinatorics, and they lay the groundwork for understanding infinite cardinalities.
Build the power set P(S) -- the set of all subsets of S. Watch how the number of subsets doubles with each new element.
Explore all subsets of a set, organized by size
Key insight: The power set of an n-element set has exactly 2ⁿ elements. Each element is either in a subset or not, giving 2 choices per element. This exponential growth is why |P(S)| > |S| always -- even for infinite sets.
Count the elements in a union of overlapping sets by adding, subtracting, and correcting for overcounting.
Watch how alternating addition and subtraction gives the correct count
|A union B| = |A| + |B| - |A intersection B|
Key insight: |A ∪ B| = |A| + |B| − |A ∩ B|. Without subtracting the intersection, elements in both sets get counted twice. For three or more sets, the pattern alternates: add singles, subtract pairs, add triples, and so on.
Compare the sizes of sets by constructing bijections. Two sets have the same cardinality if and only if a bijection exists between them.
Build a bijection between sets to compare their cardinalities
{1, 2, 3} and {a, b, c} -- different elements, same cardinality
Key insight: A bijection between two sets proves they have the same size, even when you cannot count the elements. This idea becomes essential for infinite sets, where "counting" breaks down entirely.