MathLabs
TheoremProved

Inclusion–exclusion for two sets

Statement

For finite sets AA, BB: ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|

Why is it true?

Every element of A∪BA\cup B falls into exactly one of three disjoint groups: only in AA, only in BB, or in both; adding ∣A∣+∣B∣|A|+|B| counts the "both" group twice, so one copy must be removed.

Proof sketch

Partition A∪BA\cup B into three pairwise disjoint pieces: A∖BA\setminus B (in AA only), B∖AB\setminus A (in BB only), and A∩BA\cap B (in both). Since these pieces are disjoint and cover A∪BA\cup B, ∣A∪B∣=∣A∖B∣+∣B∖A∣+∣A∩B∣|A\cup B|=|A\setminus B|+|B\setminus A|+|A\cap B|.

Now observe that AA itself splits into the disjoint pieces A∖BA\setminus B and A∩BA\cap B, so ∣A∣=∣A∖B∣+∣A∩B∣|A|=|A\setminus B|+|A\cap B|, which means ∣A∖B∣=∣A∣−∣A∩B∣|A\setminus B|=|A|-|A\cap B|. Symmetrically, ∣B∖A∣=∣B∣−∣A∩B∣|B\setminus A|=|B|-|A\cap B|.

Substituting these two expressions back into the first equation gives ∣A∪B∣=(∣A∣−∣A∩B∣)+(∣B∣−∣A∩B∣)+∣A∩B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=(|A|-|A\cap B|)+(|B|-|A\cap B|)+|A\cap B|=|A|+|B|-|A\cap B|, which is exactly ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|.

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. Wikipedia contributors (2024). Inclusion–exclusion principle
  2. James Maynard (2015). Small gaps between primes · arXiv:1311.4600
  3. Richard A. Brualdi (2017). Introductory Combinatorics (Classic Version), 5th edition