二集合の包除原理

$A\cup B$ を互いに素な三つの部分に分割する:$A\setminus B$($A$ のみ)、$B\setminus A$($B$ のみ)、$A\cap B$(両方)。これらは互いに素で $A\cup B$ を覆うので、$|A\cup B|=|A\setminus B|+|B\setminus A|+|A\cap B|$ となる。

次に、$A$ 自体が互いに素な $A\setminus B$ と $A\cap B$ に分かれることに注目すると、$|A|=|A\setminus B|+|A\cap B|$ となり、$|A\setminus B|=|A|-|A\cap B|$ を得る。同様に $|B\setminus A|=|B|-|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|$ である。