Inclusion–exclusion

Why do eleven listed memberships describe only eight cards?

Ten distinct cards are numbered 1 through 10. The red list A contains {1,2,3,4,5,6}; the striped list B contains {4,5,6,7,8}. A card may be on both lists. We want cards appearing on at least one list, counting each physical card once.

Adding the list sizes gives 6 + 5 = 11 memberships. Cards 4,5 and 6 have each been listed twice. Subtract one extra copy of each: 6 + 5 − 3 = 8 cards. The union is {1,2,3,4,5,6,7,8}; cards 9 and 10 are on neither list.

Subtracting the shared cards twice would remove them entirely. The aim is one count for every wanted card, not to discard any card merely because it has two properties.

Prepare with finite counts and local set definitions

Counting, zero and natural numbers supplies the idea of one count per distinct object. Addition and subtraction supplies the numerical operations. Examples, explanations and counterexamples helps distinguish a complete proof from a few successful examples. These published lessons are linked below.

A set contains distinct elements. x ∈ A means x is an element of A; A ⊆ B means every element of A belongs to B. A ∪ B is their union: membership in at least one of A or B. A ∩ B is their intersection: membership in both. |A| denotes the number of elements in finite A. A ∖ B contains members of A that are not in B. These definitions are enough to begin; set operations and earlier counting rules develop them further.

First read through the exact three-set regions and the questions “none” and “exactly one”. Then return to the indexed-set proof. Its notation is defined locally, so no binomial theorem is assumed. The later function example uses integer powers; review Powers, roots and the real number line if necessary, then return to that example.

Two sets: add, then subtract one duplicate count

For finite A and B, |A ∪ B| = |A| + |B| − |A ∩ B|. Partition the union into A ∖ B, A ∩ B and B ∖ A. These three regions are disjoint. A-only and B-only elements appear once in the sum; shared elements appear twice and must lose one count.

The size of a shared region cannot be negative or exceed either set: 0 ≤ |A ∩ B| ≤ min(|A|,|B|). Also max(|A|,|B|) ≤ |A ∪ B| ≤ |A| + |B|. If both sets lie in a finite universe Ω, then |A ∪ B| ≤ |Ω|, giving |A ∩ B| ≥ |A| + |B| − |Ω|.

If A and B are disjoint, their intersection has size zero and addition suffices. If A = B, the union has the common set’s size. If A ⊆ B, then A ∩ B = A and the union is B. Empty sets obey the same rule.

Three sets: the triple overlap needs its count restored

For three finite sets, |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. Each distinct pair is used once; A ∩ B and B ∩ A are the same intersection.

An element in exactly one set contributes 1. An element in exactly two sets contributes 2 − 1 = 1. An element in all three contributes 3 − 3 + 1 = 1. Subtracting pair intersections without the final addition would give a triple member zero counts.

An inclusive pair intersection includes the triple region. “In A and B” permits membership in C too; “in A and B only” excludes C. If there are three elements in A ∩ B and two in all three, the A-and-B-only region has 3 − 2 = 1 element. Confusing these two counts changes the formula.

Eight exact membership regions account for the whole universe

The three-set display has a twelve-card universe. Cards 1,2 are outside all three; 3,4 are A only; 5 is B only; 6 is A and B only; 7 is C only; 8 is A and C only; 9,10 are B and C only; 11,12 are in all three. Each card occupies exactly one of the eight regions.

The inclusive sizes are |A| = |B| = |C| = 6; |A ∩ B| = 3; |A ∩ C| = 3; |B ∩ C| = 4; and |A ∩ B ∩ C| = 2. Thus the union count is 18 − 3 − 3 − 4 + 2 = 10. The two outside cards make the universe total twelve.

A membership word records A, then B, then C, with 1 for membership and 0 for absence. For example 110 means A and B only, and 111 means all three. The boxes are exact membership regions, not areas proportional to counts or probabilities. Their element lists and table give the quantities.

None, at least one and exactly one ask different questions

If all sets lie in a stated finite universe Ω, the number in none is |Ω| − |A ∪ B ∪ C|. In the twelve-card case this is 12 − 10 = 2. At least one is the union, with ten cards, including cards with several memberships.

Write E₁ for the set of elements with exactly one membership. It consists only of the three single-membership regions. Here it has 2 + 1 + 1 = 4 cards. Removing the union from Ω does not count exactly one; it counts none.

For three sets, exactly one can also be computed as |A| + |B| + |C| − 2(|A ∩ B| + |A ∩ C| + |B ∩ C|) + 3|A ∩ B ∩ C|. A double member contributes 2 − 2 = 0; a triple member contributes 3 − 6 + 3 = 0; a single member contributes 1. The coefficients differ because the desired outcomes differ.

Do not silently convert a count into a probability. A finite sample space would also need stated probabilities, and dividing by its size is valid for probabilities only under an equal-likelihood model. No independence assumption is part of inclusion–exclusion itself.

For any finite number of sets, alternate all distinct intersections

Let A₁,…,Aₙ be finite sets with n ≥ 1. Write [n] = {1,…,n}. For a nonempty subset I of [n], let Aᵢ for i ∈ I be the selected sets, and ⋂ᵢ∈I Aᵢ their common intersection. Then |⋃ᵢ₌₁ⁿ Aᵢ| = Σ∅≠I⊆[n] (−1)^(|I|+1) |⋂ᵢ∈I Aᵢ|.

The sum symbol means one term for each nonempty index subset. Add single sets, subtract every distinct pair intersection, add every distinct triple intersection, and continue alternating. An odd number of selected indices gives a plus sign; an even number gives a minus sign. Each index subset is used exactly once.

The indices matter even when two sets happen to be equal. Equal sets do not let us omit their indexed terms. The complete alternating sum still corrects the multiple membership counts. Missing higher intersections is insufficient information for an exact general union count.

When n = 0, the union of no sets is empty and the empty sum is zero. If a finite universe is specified, every universe member is then in none. The n ≥ 1 formula above needs no convention for an intersection of no sets.

Pair opposite contributions for one arbitrary element

Fix an arbitrary element x. If x belongs to no selected set, it appears in no nonempty intersection and contributes zero. Otherwise let M be the nonempty set of indices i for which x ∈ Aᵢ. A term counts x exactly when its nonempty index subset I lies inside M.

Choose one distinguished index d ∈ M. Apart from the singleton {d}, pair every nonempty subset J ⊆ M that omits d with J ∪ {d}. Both intersections contain x. Their selected-index counts differ by one, so their signs are opposite and their contributions cancel.

These pairs cover every counted index subset except {d}. Removing d reverses the pairing for subsets that contain d and at least one other index. The remaining singleton has a plus sign and contributes one. Thus every union member contributes exactly one, and every element outside contributes zero.

Summing these element contributions over a finite universe containing the union proves the formula. This argument handles arbitrary membership patterns, not just the displayed examples; it does not require a later binomial identity. In the display with three memberships, B pairs with AB, C with AC, and BC with ABC, leaving A unpaired.

Four sets require sixteen exact membership patterns

The four-set example has one labelled object for each four-bit membership word. Its bits say whether it belongs to A,B,C,D in that order. Thus there are sixteen objects; 0000 is outside all four and the other fifteen are in the union.

Every single set contains eight objects. Each of the six distinct pair intersections has four; each of the four triple intersections has two; the all-four intersection has one. The alternating count is 4 × 8 − 6 × 4 + 4 × 2 − 1 = 15.

The grid uses one box per exact pattern, including zero-count patterns when applicable. It does not claim that four ordinary circles realise all sixteen regions. A word such as 1010 means A and C only; 1111 contributes 4 − 6 + 4 − 1 = 1 to the union formula. Exactly one has four objects, and none has one.

A numerical formula cannot make impossible data into sets

Suppose a ten-element universe is reported to have |A| = |B| = |C| = 5, |A ∩ B| = 4, |A ∩ C| = 4, |B ∩ C| = 1 and |A ∩ B ∩ C| = 0. Every pair size is at most each corresponding single size, and the candidate union 15 − 4 − 4 − 1 = 6 lies between five and ten. These simple bounds do not establish consistency.

The A-only region would have size |A| − |A ∩ B| − |A ∩ C| + |A ∩ B ∩ C| = 5 − 4 − 4 + 0 = −3. A region cannot contain minus three elements. The reported intersections therefore cannot arise from any such three sets; six is an invalid candidate, not a valid union count.

For three sets, reconstruct all eight exact regions. The triple region is the given triple count; each pair-only region is its inclusive pair count minus the triple; A only is the expression above, with analogous formulas for B and C; outside is the universe size minus the union. Every region count must be a nonnegative integer.

If these eight reconstructed counts are nonnegative integers, they also suffice for an abstract finite model: make disjoint groups of those sizes, then give each group exactly the memberships named by its region. Their counts reproduce the reported singles and intersections. This establishes numerical feasibility, not whether a real survey measured those values correctly.

Count onto functions by excluding missing target values

A function assigns exactly one target value to each labelled input. It is onto when every target value is assigned to at least one input. Distinct functions differ at some input; they are not counted again merely because we describe their assignments in another order.

First take three inputs and targets A,B. A length-three word records their outputs in the fixed input order, giving 2³ = 8 functions. Missing A permits only BBB, and missing B permits only AAA. No function misses both targets because the input set is nonempty. There are 8 − 1 − 1 + 0 = 6 onto functions.

Now take four inputs and targets A,B,C. The universe contains 3⁴ = 81 functions. Let M_A,M_B,M_C be the bad sets of functions missing the indicated target. Each bad set has 2⁴ = 16 functions. Each inclusive pair intersection has 1⁴ = 1 function: all inputs use the remaining target. Missing all three permits zero functions.

The bad union has 3 × 16 − 3 × 1 + 0 = 45 functions. Its complement contains 81 − 45 = 36 onto functions. Every intersection count comes from the same labelled-input, labelled-target universe; changing those conventions would change the problem.

This application uses positive input and target sizes. If the input set is empty, there is one empty function to any target set, and it is onto only when the target set is empty. If inputs are nonempty and the target set is empty, there are no functions. These boundaries should be handled directly rather than hiding them in an unexplained 0⁰ expression.

Check the wanted set before substituting numbers

Name one distinct outcome and a finite universe when complements are used. Define the sets by genuine properties of those same outcomes. Identify inclusive intersections, count every distinct index subset with its correct sign, and check reconstructed region sizes and union bounds.

Use the explorer to predict union, none or exactly-one counts for the same inventory. Then compare the revealed table and the alternating formula. The impossible-data case asks for a consistency check, while the function cases ask for the complement of a union of bad properties.

A complete element-by-element proof explains the general rule. A finite display is a useful check of an example; enumerating a few masks alone does not prove the formula for every number of sets.

Worked examples

Try it yourself

1. A and B lie in a ten-object universe and each have size 7. What is the smallest possible overlap? What union size does that minimum give?

   Show the answer and reasoning

   The overlap is at least 4; at overlap 4 the union has 10 members.

   The union cannot exceed 10, so 7 + 7 − |A ∩ B| ≤ 10. Four shared objects and three unique to each set realise the boundary.

2. Three finite sets are equal and each has size 5. Use the full three-set formula.

   Show the answer and reasoning

   The union count is 15 − 15 + 5 = 5.

   Every pair and the triple are the same five-element set. Indexed pair terms are retained even when their resulting intersections are equal.

3. A ∩ B has seven elements and A ∩ B ∩ C has two. How many are in A and B only? Is seven the pair-only count?

   Show the answer and reasoning

   There are 7 − 2 = 5 in A and B only. Seven is the inclusive count.

   Every triple member belongs to the pair intersection, so remove the triple group once to impose absence from C.

4. What net contribution does a triple member receive from the union formula and from the exactly-one formula?

   Show the answer and reasoning

   Union: 3 − 3 + 1 = 1. Exactly one: 3 − 6 + 3 = 0.

   The formulas answer different membership questions. A triple member is wanted in the union but excluded from exactly one.

5. In a universe of size 20, the three-set union has size 14. Does 20 − 14 count exactly one membership?

   Show the answer and reasoning

   No. It counts six elements in none of the three sets.

   The union includes all members with at least one membership, so its complement contains only zero-membership elements. Single-only region data would be needed to count exactly one.

6. In the sixteen-pattern four-set model, interpret 1010 and count at least one, none and exactly one.

   Show the answer and reasoning

   1010 means A and C only. The counts are 15,1 and 4.

   Only 0000 has no membership, and exactly four words have a single 1. All other nonzero words remain in the union, including 1111.

7. For an element in A,B,C, distinguish A. List the cancelling index-subset pairs and the remaining term.

   Show the answer and reasoning

   B pairs with AB; C with AC; BC with ABC. The singleton A remains with sign +1.

   Adding A changes subset size by one and reverses the sign. These pairs and A exhaust every nonempty subset of {A,B,C}.

8. Single sizes are 5,5,5, pairs AB, AC, BC are 4,4,1 and the triple is 0. Find a negative atom even though the candidate union size is 6.

   Show the answer and reasoning

   A only would have 5 − 4 − 4 + 0 = −3 elements.

   A ∩ B and A ∩ C are disjoint inside A when the triple is empty, yet together would contain eight members of a five-element set. The reports cannot describe finite sets.

9. How many functions from three labelled inputs to targets A,B use both targets? Name the excluded functions.

   Show the answer and reasoning

   There are 2³ − 2 = 6 onto functions. AAA and BBB are excluded.

   Every function is one three-letter output word. Missing A or B gives one constant word each, and no function misses both when inputs exist.

10. How many functions from an empty input set to {A,B} exist, and how many are onto? What changes if the target set is empty too?

    Show the answer and reasoning

    There is one empty function to {A,B}, but none is onto. Between two empty sets there is one function and it is onto.

    No input needs an output assignment, so the empty function exists uniquely. It reaches no target, which covers all targets exactly when there are no targets.

What to carry forward

• Shared elements must finish with one count, not be deleted from the union.
• Inclusive pair intersections include higher overlaps; exact regions exclude other memberships.
• Alternate every distinct nonempty index subset for a finite indexed family, including repeated equal sets.
• Opposite-sign subset pairs cancel for an arbitrary element, leaving its singleton contribution one.
• Complement counts none in a specified finite universe; exactly one needs different coefficients or exact regions.
• Nonnegative integer atom counts test three-set numerical feasibility; an attractive formula value cannot rescue impossible data.
• Onto functions can be counted by excluding genuine missing-target sets in one clearly defined function universe.