集合と集合演算

通常の代数で乗法が加法に対して分配するのと同様に、集合の代数では共通部分が和集合に対して分配する。これにより「カテゴリ $A$ に属し、かつ(セール中 $B$ または新着 $C$)」のようなフィルタを、和集合で結合された2つの扱いやすいフィルタに書き換えることができ、これはまさにデータベースや検索エンジンのクエリプランナがブール型フィルタを単純化する方法である。

両方の包含関係を、任意の元 $x_0$ を用いた「元を追跡する」手法によって示すことで、2つの集合が等しいことを証明する。

(順方向、$\subseteq$) $x_0 \in A \cap (B \cup C)$ と仮定する。共通部分の定義により、これは $x_0 \in A$ かつ $x_0 \in B \cup C$ を意味する。和集合の定義により、$x_0 \in B \cup C$ は $x_0 \in B$ または $x_0 \in C$ を意味する。この2つの場合を別々に考える。場合1:$x_0 \in B$。$x_0 \in A$ と合わせると $x_0 \in A \cap B$ が得られる。場合2:$x_0 \in C$。$x_0 \in A$ と合わせると $x_0 \in A \cap C$ が得られる。いずれの場合も $x_0$ は $x_0 \in A \cap B$ または $x_0 \in A \cap C$ に属するので、$x_0 \in (A \cap B) \cup (A \cap C)$ である。

(逆方向、$\supseteq$) $x_0 \in (A \cap B) \cup (A \cap C)$ と仮定する。和集合の定義により、これは $x_0 \in A \cap B$ または $x_0 \in A \cap C$ を意味する。もし $x_0 \in A \cap B$ ならば $x_0 \in A$ かつ $x_0 \in B$ であり、したがって $x_0 \in B \cup C$($x_0$ が $B$ に属するなら $B$ または $C$ に属する)、よって $x_0 \in A \cap (B \cup C)$ となる。もし代わりに $x_0 \in A \cap C$ ならば $x_0 \in A$ かつ $x_0 \in C$ であり、したがって $x_0 \in B \cup C$、よって再び $x_0 \in A \cap (B \cup C)$ となる。

左辺のすべての元が右辺に属し、その逆も成り立つので、2つの集合はまったく同じ元を含む。したがって $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ が成り立ち、証明が完了する。

$|A|$ と $|B|$ を単純に足すと、両方の集合に属するすべての元が二重に数えられてしまうため、$|A \cap B|$ を一度引くことでその重複を修正する。これはまさに、アンケート調査データから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|$ である。これで証明が完了する。