The lecture encyclopedia
Set constructions support both description and counting. A Cartesian product forms ordered combinations, a power set collects subsets, and inclusion-exclusion counts unions without counting shared elements too many times.
Difference and compound expressions #
A - B contains elements in A that are not in B. It equals A ∩ B′ when the complement is taken in a suitable shared universe. Set difference is directional: A - B need not equal B - A.
To evaluate a compound expression, perform inner operations first and keep intermediate sets explicit. A complement of an entire expression applies to that whole result, not just its last term. De Morgan's laws express this precisely: the complement of a union is the intersection of the complements, and the complement of an intersection is their union.
Ordered pairs #
A × B contains pairs (a, b) with a ∈ A and b ∈ B. If A = {1, 2} and B = {x, y}, the product contains (1,x), (1,y), (2,x), and (2,y). Reversing the product reverses the roles of the positions; (1,x) and (x,1) are different ordered pairs.
For finite sets, |A × B| = |A| |B| because every first-coordinate choice can be paired with every second-coordinate choice. If either set is empty, the product is empty.
Power-set counting #
A subset of an n-element set makes one include-or-exclude choice per element, giving 2ⁿ subsets. The power set includes the empty subset and the entire original set. Its elements are sets, so distinguish a subset from an element of a subset when interpreting nested braces.
Correcting overlap #
For two finite sets, |A ∪ B| = |A| + |B| - |A ∩ B|. Adding the separate totals counts the overlap twice, so one copy is subtracted. If 18 items have property A, 12 have B, and 5 have both, then 25 have at least one.[1]
For three sets, add the three individual totals, subtract all three pairwise intersections, and add the triple intersection once. The final addition repairs the over-subtraction of the central region. Pairwise intersection totals normally include members of all three sets, so they must not be mistaken for exactly-two-only counts.