TheoremProved
Inclusion–exclusion for two sets
Statement
For finite sets , :
Why is it true?
Every element of falls into exactly one of three disjoint groups: only in , only in , or in both; adding counts the "both" group twice, so one copy must be removed.
Proof sketch
Partition into three pairwise disjoint pieces: (in only), (in only), and (in both). Since these pieces are disjoint and cover , .
Now observe that itself splits into the disjoint pieces and , so , which means . Symmetrically, .
Substituting these two expressions back into the first equation gives , which is exactly .
Topics that use this theorem
Step-by-step proofs
No step-by-step proof yet for this theorem.
References
- Wikipedia contributors (2024). Inclusion–exclusion principle
- James Maynard (2015). Small gaps between primes · arXiv:1311.4600
- Richard A. Brualdi (2017). Introductory Combinatorics (Classic Version), 5th edition