包除原理
包除原理を一般に証明するため、X を A1, ..., An の上位集合とする。公式はまず恒等式
1 ⋃ A i = ∑ i 1 A i − ∑ i < j 1 A i ∩ A j + ⋯ + ( − 1 ) n − 1 1 ⋂ A i {\displaystyle 1_{\bigcup A_{i}}=\sum _{i}1_{A_{i}}-\sum _{i<j}1_{A_{i}\cap A_{j}}+\cdots +(-1)^{n-1}1_{\bigcap A_{i}}}
を指示関数の変形でもとめ、全ての x ∈ X について足しあわせることで示される。
包除原理とド・モルガンの法則とを合わせることで、共通部分の要素数を計算できる。 A {\displaystyle A} を普遍集合、各 i {\displaystyle i} について A i ⊆ A {\displaystyle A_{i}\subseteq A} とし、 A i ̄ {\displaystyle {\overline {A_{i}}}} が A {\displaystyle A} に関する A i {\displaystyle A_{i}} の補集合を表すものとする。このとき
| ⋂ i = 1 n A i | = | ⋃ i = 1 n A i ̄ | ̄ {\displaystyle \left\vert \bigcap _{i=1}^{n}A_{i}\right\vert ={\overline {\left\vert \bigcup _{i=1}^{n}{\overline {A_{i}}}\right\vert }}}
をえる。こうして、共通部分をもとめる問題を和集合をもとめる問題に帰着させることができる。