Tập hợp và các phép toán

Giống như phép nhân phân phối trên phép cộng trong đại số thông thường, phép giao phân phối trên phép hợp trong đại số tập hợp. Điều này cho phép viết lại một bộ lọc như "thuộc danh mục $A$, và (đang giảm giá $B$ hoặc hàng mới $C$)" thành hai bộ lọc riêng lẻ dễ quản lý hơn rồi hợp lại, đúng như cách bộ lập kế hoạch truy vấn của cơ sở dữ liệu và công cụ tìm kiếm đơn giản hóa các bộ lọc logic.

Ta chứng minh hai tập bằng nhau bằng cách chỉ ra cả hai bao hàm thức, dùng một phần tử tùy ý $x_0$ (kỹ thuật "đuổi phần tử").

(Chiều thuận, $\subseteq$) Giả sử $x_0 \in A \cap (B \cup C)$. Theo định nghĩa của giao, điều này nghĩa là $x_0 \in A$ và $x_0 \in B \cup C$. Theo định nghĩa của hợp, $x_0 \in B \cup C$ nghĩa là $x_0 \in B$ hoặc $x_0 \in C$. Xét hai trường hợp riêng. Trường hợp 1: $x_0 \in B$. Kết hợp với $x_0 \in A$, ta có $x_0 \in A \cap B$. Trường hợp 2: $x_0 \in C$. Kết hợp với $x_0 \in A$, ta có $x_0 \in A \cap C$. Trong cả hai trường hợp, $x_0$ nằm trong $x_0 \in A \cap B$ hoặc trong $x_0 \in A \cap C$, do đó $x_0 \in (A \cap B) \cup (A \cap C)$.

(Chiều ngược, $\supseteq$) Giả sử $x_0 \in (A \cap B) \cup (A \cap C)$. Theo định nghĩa của hợp, điều này nghĩa là $x_0 \in A \cap B$ hoặc $x_0 \in A \cap C$. Nếu $x_0 \in A \cap B$, thì $x_0 \in A$ và $x_0 \in B$, do đó $x_0 \in B \cup C$ (vì $x_0$ thuộc $B$ nên thuộc $B$ hoặc $C$), suy ra $x_0 \in A \cap (B \cup C)$. Nếu thay vào đó $x_0 \in A \cap C$, thì $x_0 \in A$ và $x_0 \in C$, do đó $x_0 \in B \cup C$, và lại suy ra $x_0 \in A \cap (B \cup C)$.

Vì mọi phần tử của vế trái đều nằm trong vế phải và ngược lại, hai tập chứa đúng cùng các phần tử, nên $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$. Chứng minh hoàn tất.

Cộng đơn giản $|A|$ và $|B|$ sẽ đếm hai lần mọi phần tử thuộc cả hai tập, nên trừ đi $|A \cap B|$ một lần sẽ sửa lại phần đếm thừa đó. Đây chính là phép tính đằng sau việc đọc biểu đồ Venn hai vòng tròn từ dữ liệu khảo sát: những người thích cả cà phê lẫn trà không được đếm hai lần khi hỏi có bao nhiêu người thích ít nhất một trong hai.

Ý tưởng then chốt là tách $A \cup B$ thành ba phần rời nhau đôi một rồi đếm mỗi phần đúng một lần.

Trước tiên, tách mỗi tập bằng tập kia: $A = (A \setminus B) \cup (A \cap B)$ và $B = (B \setminus A) \cup (A \cap B)$. Trong mỗi đẳng thức, hai phần ở vế phải rời nhau, vì $(A\setminus B) \cap (A \cap B) = \varnothing$ (một phần tử ở ngoài $B$ không thể đồng thời ở trong $B$) và tương tự $(B\setminus A) \cap (A \cap B) = \varnothing$. Vì kích thước một tập hữu hạn bằng tổng kích thước các phần rời nhau tạo thành nó, ta có $|A| = |A \setminus B| + |A \cap B|$ và $|B| = |B \setminus A| + |A \cap B|$.

Tiếp theo, để ý rằng chính $A \cup B$ tách thành ba phần rời nhau đôi một: $A \cup B = (A \setminus B) \cup (B \setminus A) \cup (A \cap B)$. Thật vậy $A\setminus B$, $B\setminus A$, $A\cap B$ rời nhau đôi một (một phần tử thuộc $A\setminus B$ thì không thuộc $B$, do đó không thuộc $A \cap B$ hay $B \setminus A$; tương tự cho các phần còn lại), và hợp của chúng đúng bằng các phần tử thuộc $A$ hoặc thuộc $B$. Đếm theo cách chia này cho $|A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B|$.

Cuối cùng thay vào: từ $|A| = |A \setminus B| + |A \cap B|$ ta có $|A \setminus B|$ $= |A| - |A\cap B|$, và từ $|B| = |B \setminus A| + |A \cap B|$ ta có $|B \setminus A|$ $= |B| - |A\cap B|$. Thay cả hai vào $|A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B|$ cho $|A \cup B| = (|A| - |A\cap B|) + (|B| - |A\cap B|) + |A\cap B| = |A| + |B| - |A\cap B|$, đúng là $|A \cup B| = |A| + |B| - |A \cap B|$. Chứng minh hoàn tất.