Proof of the distributive laws for sets

Proof

We show that each side has the same elements as the other. Two sets with the same elements are equal, by the axiom of extensionality. Let $A$, $B$ and $C$ be sets.

1. Let $x \in A \cap (B \cup C)$. By the definition of intersection, $x \in A$ and $x \in B \cup C$. By the definition of union, $x \in B$ or $x \in C$.
2. In step 1, if $x \in B$, then $x \in A \cap B$. If $x \in C$, then $x \in A \cap C$. In both cases $x \in (A \cap B) \cup (A \cap C)$.
3. Conversely, let $x \in (A \cap B) \cup (A \cap C)$. Then $x \in A \cap B$ or $x \in A \cap C$.
4. In step 3, if $x \in A \cap B$, then $x \in A$ and $x \in B \subseteq B \cup C$. If $x \in A \cap C$, then $x \in A$ and $x \in C \subseteq B \cup C$. In both cases $x \in A \cap (B \cup C)$.
5. By steps 2 and 4, the sets $A \cap (B \cup C)$ and $(A \cap B) \cup (A \cap C)$ have the same elements. So they are equal.
6. Let $x \in A \cup (B \cap C)$. Then $x \in A$ or $x \in B \cap C$.
7. In step 6, if $x \in A$, then $x \in A \cup B$ and $x \in A \cup C$. If $x \in B \cap C$, then $x \in B$, so $x \in A \cup B$, and $x \in C$, so $x \in A \cup C$.
8. By step 7, in both cases $x \in (A \cup B) \cap (A \cup C)$.
9. Conversely, let $x \in (A \cup B) \cap (A \cup C)$. Then $x \in A \cup B$ and $x \in A \cup C$. By the law of excluded middle, either $x \in A$ or $x \notin A$.
10. In step 9, if $x \in A$, then $x \in A \cup (B \cap C)$.
11. In step 9, if $x \notin A$, then $x \in A \cup B$ forces $x \in B$, and $x \in A \cup C$ forces $x \in C$. So $x \in B \cap C \subseteq A \cup (B \cap C)$.
12. By steps 8, 10 and 11, the sets $A \cup (B \cap C)$ and $(A \cup B) \cap (A \cup C)$ have the same elements. So they are equal.