Power sets, inclusion-exclusion, and comparing set sizes
How big is a set? For small sets you count, but a few clever ideas let you measure size without counting at all.
Add or remove elements and watch the number of subsets double or halve. Turn on the Hasse diagram to see how the subsets nest.
Explore all subsets of a set, organized by size
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.
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.
Choose two or three sets, set the sizes with the sliders, then step through the count. Watch each subtraction undo a double count.
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.
Pick a pair of sets, click an element on the left and then one on the right to pair them, then press Check Bijection. Can every element find exactly one partner?
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.
Spot a mistake or have an idea?