2つの集合に対する包除原理

鍵となる考え方は、$A \cup B$ を互いに素な3つの部分に分けて、それぞれを一度だけ数えることである。

まず、各集合をもう一方の集合を使って分割する:$A = (A \setminus B) \cup (A \cap B)$ と $B = (B \setminus A) \cup (A \cap B)$。それぞれの式で右辺の2つの部分は互いに素である。なぜなら $(A\setminus B) \cap (A \cap B) = \varnothing$($B$ の外にある元は同時に $B$ の中にはあり得ない)であり、同様に $(B\setminus A) \cap (A \cap B) = \varnothing$ も成り立つからである。有限集合の大きさは、それを分割する互いに素な部分の大きさの和に等しいので、$|A| = |A \setminus B| + |A \cap B|$ と $|B| = |B \setminus A| + |A \cap B|$ が得られる。

次に、$A \cup B$ 自体が互いに素な3つの部分に分かれることに注目する:$A \cup B = (A \setminus B) \cup (B \setminus A) \cup (A \cap B)$。実際、$A\setminus B$、$B\setminus A$、$A\cap B$ は互いに素であり($A\setminus B$ の元は $B$ に属さないので $A \cap B$ にも $B \setminus A$ にも属さない、他も同様)、それらの和集合はちょうど $A$ または $B$ に属する元全体になる。この分割で数えると $|A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B|$ が得られる。

最後に代入する:$|A| = |A \setminus B| + |A \cap B|$ より $|A \setminus B|$ $= |A| - |A\cap B|$、$|B| = |B \setminus A| + |A \cap B|$ より $|B \setminus A|$ $= |B| - |A\cap B|$ が得られる。両方を $|A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B|$ に代入すると $|A \cup B| = (|A| - |A\cap B|) + (|B| - |A\cap B|) + |A\cap B| = |A| + |B| - |A\cap B|$ となり、これはまさに $|A \cup B| = |A| + |B| - |A \cap B|$ である。これで証明が完了する。