What if the sets are disjoint?

Their intersections are empty, so their sizes simply add.

Can probabilities replace counts?

Yes, using joint-event probabilities for intersections.

Can pairwise overlaps alone solve every three-set problem?

No; the triple overlap may also be needed.

AI Glossary / Graphs and symbolic AI / Advanced

Inclusion-exclusion principle

Definition

The inclusion-exclusion principle calculates the size of a union of overlapping sets, or the probability that at least one of several events occurs. It adds individual sizes or probabilities, subtracts pairwise overlaps, adds triple overlaps, and continues with alternating signs. The corrections ensure that each included outcome contributes exactly once.

What it means

Adding category totals can count the same item several times. If a document belongs to both a finance collection and a training collection, adding the two collection sizes counts that document twice. Subtracting their intersection removes the extra copy.
With three or more collections, simply subtracting every pairwise overlap goes too far for items shared by several collections. Triple intersections must be added back, with further corrections for larger combinations.
The principle is an exact mathematical identity when the required quantities are known consistently. It does not discover overlaps from category totals alone or compensate for unreliable identifiers and mismatched populations.

How it works

For two finite sets, the union size is the size of A plus the size of B minus the size of their intersection. A union means membership in at least one set; an intersection means membership in all the sets named.
For three sets, add the sizes of A, B, and C; subtract the sizes of A intersect B, A intersect C, and B intersect C; then add the size of the three-way intersection.
An element in all three sets is initially counted three times, subtracted three times, and added once. Its final contribution is one. An element in exactly two sets contributes two minus one, also one.
The probability version uses probabilities instead of counts. It does not require independence. Independence can sometimes simplify an intersection calculation, but it must be justified separately. For many sets, evaluating all nonempty intersections can become expensive because their number grows as 2 raised to the number of sets, minus 1.

Three practical examples

An AI training-data team estimates the number of distinct documents across several source collections. Overlap counts prevent duplicated documents from inflating the reported dataset size.
An evaluation team counts examples flagged by at least one of several tests. The combined count differs from the total number of flags because one example may trigger multiple tests.
A service team calculates the probability that at least one of several failure events occurs. Joint-event probabilities matter; adding individual probabilities can overstate the result when failures overlap.

Think of it this way

Imagine combining three invitation lists. First count every name on every list. Then remove duplicate pairwise appearances. People on all three lists have now been removed too many times, so add one copy of each of those names back.

Worked example

Consider an invented evaluation containing 100 distinct test cases. Test A flags 40 cases, Test B flags 35, and Test C flags 30. The pairwise intersections contain 15 cases for A and B, 10 for A and C, and 12 for B and C. Five cases appear in all three sets.
The pairwise intersection counts include the five triple-flagged cases. They do not mean cases flagged by exactly two tests.
The number flagged by at least one test is 40 + 35 + 30 minus 15 minus 10 minus 12 plus 5, which equals 73. Therefore, 27 cases receive no flag. Simply adding the three test totals would report 105 flags, not 105 distinct cases.
Reconstruct the disjoint regions to verify the calculation. Exactly A and B contains 15 minus 5, or 10 cases. Exactly A and C contains 5 cases. Exactly B and C contains 7 cases. The triple intersection contains 5.
A alone contains 40 minus 15 minus 10 plus 5, or 20 cases. B alone contains 35 minus 15 minus 12 plus 5, or 13. C alone contains 30 minus 10 minus 12 plus 5, also 13.
Adding these seven disjoint regions gives 20 + 13 + 13 + 10 + 5 + 7 + 5 = 73. Exactly one test flags 46 cases; exactly two flag 22; and all three flag 5. At least two tests flag 27 cases.
If one case is selected uniformly from these 100, the probability that it has at least one flag is 73/100, or 0.73. This is a probability for the stated selection procedure. It does not establish a 73% rate in future production traffic or prove that every flag identifies a real defect.
Finally, omitting the triple-intersection correction would produce 68. The missing five are exactly the cases whose three initial appearances were canceled by three pairwise subtractions.

Illustrative case study

Fictional Cedar Evaluation reports model problems by adding the numbers of cases flagged for unsupported claims, missing details, and inconsistent answers. Reviewers notice that a single answer may appear in several categories.
The team rebuilds its report around stable case identifiers and the same evaluation window. It displays both the total number of category flags and the number of distinct cases with any flag.
For three categories, it verifies the distinct-case total using inclusion-exclusion and independently groups records by their exact combination of flags. Reviewers can reconcile category totals without interpreting duplicate flags as additional cases. The report still distinguishes detected flags from confirmed defects.

Common misconceptions and mistakes

“Pairwise intersections mean exactly two sets.” They also include elements in larger intersections.
“Subtracting overlaps once is always enough.” Higher-order overlap needs further correction.
“The formula requires independent events.” It does not.
“Category totals determine the union.” Overlap information is also needed.
“An exact formula guarantees accurate input data.” Identity matching and measurement scope remain separate issues.

Business use

Use the principle when reporting combined coverage, affected cases, or overlapping populations. Define the counting unit, time window, and inclusion rules consistently across all inputs.
Check that the union is at least as large as every individual set and no larger than the stated universe. Reconstructed disjoint regions should not have negative sizes.

Check your understanding

Why is the triple overlap added back?

Answer: Pairwise subtraction removes those cases too many times.

How many cases have exactly two flags?

Answer: Twenty-two.

Does 0.73 prove a future defect rate?

Answer: No; it describes uniform selection from this particular evaluation.

Related terms

Cardinality (data modeling)
Joint probability
Union
intersection
cardinality
complement
disjoint sets
union bound
duplicate counting

Learn next

Draw the seven occupied regions for three sets and recover every supplied total. Then compare exact inclusion-exclusion with the simpler upper bound obtained by adding individual probabilities.

Sources

AIMA glossary, inclusion-exclusion principle: https://github.com/aimacode/aima-glossary/blob/master/glossary.md Scott Sheffield, MIT probability and inclusion-exclusion lecture: https://math.mit.edu/~sheffield/600/Lecture4.pdf Ohio State Ximera, Inclusion-Exclusion Principle: https://ximera.osu.edu/math/combinatorics/combinatoricsBook/combinatoricsBook/combinatorics/inclusionExclusion/inclusionExclusion

Previous: Incident response Next: Incompatibility of fairness metrics