De Morgan's Laws

We are now going to look at two very important laws involving three sets $A$, $B$, and $C$.

Theorem 1 (De Morgan's Law 1): If $A$, $B$, and $C$ are sets, then $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$.

The diagram below illustrates De Morgan's first law.

• Proof: $\Rightarrow$ Let $x \in A \setminus (B \cup C)$. We know that $x \not \in B$ and $x \not \in C$. Therefore, $x \in (A \setminus B)$ and $x \in (A \setminus C)$ so $x \in (A \setminus B) \cap (A \setminus C)$.

• $\Leftarrow$ Now let $x \in (A \setminus B) \cap (A \setminus C)$. We know that $x \in A$ but $x \not \in B$. We also know that $x \in A$ but $x \not \in C$. Therefore, $x \in A$ and $x \not \in (B \cup C)$ so $x \in A \setminus (B \cup C)$. $\blacksquare$

Theorem 2 (De Morgan's Law, 2): If $A$, $B$, and $C$ are sets, then $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$.

The diagram below illustrates De Morgan's second law.

• Proof of Law 2: $\Rightarrow$ Let $x \in A \setminus (B \cap C)$. So $x \in A$ and $x \not \in (B \cap C)$. So $x \in (A \setminus B)$ or $x \in (A \setminus C)$ so $x \in (A \setminus B) \cup (A \setminus C)$.

• $\Leftarrow$ Now let $x \in (A \setminus B) \cup (A \setminus C)$. Therefore, $x \in (A \setminus B)$ or $x \in (A \setminus B)$. So $x \in A$ and $x \not \in B$ or $x \in A$ and $x \not \in C$. So $x \in A$ and $x \not \in (B \cap C)$. Therefore $x \in A \setminus (B \cap C)$. $\blacksquare$