Inclusion-Exclusion Principle

Definition

A combinatorial method to find the cardinality of the union of multiple sets by adding the sizes of individual sets, subtracting the sizes of their pairwise intersections, adding back the sizes of triple intersections, and so on: $|A \cup B| = |A| + |B| - |A \cap B|$ How to read: “The cardinality of A union B equals the cardinality of A plus the cardinality of B minus the cardinality of A intersect B.” Meaning / when to use: Used to count the elements in the union of overlapping sets. We add the sets’ sizes and then subtract the size of their intersection to correct for double counting.

Why It Matters

When sets are not mutually exclusive, the Addition Principle fails because it double-counts overlapping elements. Inclusion-Exclusion corrects for this bias, enabling accurate probability and size calculations in complex, overlapping systems.

Core Concepts

• Overlapping Sets: Used when sets $A$ and $B$ have common elements ($A \cap B \neq \emptyset$).
• Generalization: For three sets, the formula extends to: $|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$ How to read: “The cardinality of the union of sets A, B, and C equals the sum of their individual cardinalities minus the sum of their pairwise intersections plus the cardinality of their triple intersection.” Meaning: Generalization of inclusion-exclusion to three sets.
• Venn Diagrams: Visually represent how elements are shared among sets, demonstrating why the overlap subtraction is necessary.

Connected Concepts

• Addition Principle
• Multiplication Principle
• Probability Models: Equally Likely Outcomes
• First Principles Thinking