De Morgan's Laws for Set Complements

Theorem

Let $A,B$ be any set

Then

$$\begin{array}{r}(A\cap B{)}^C=A^C\cup B^C\\ (A\cup B{)}^C=A^C\cap B^C\end{array}$$

Proof

First law

$(A\cap B{)}^C=A^C\cup B^C$

Prove $x\in (A\cap B{)}^C⟺x\in A^C\cup B^C$

($\Rightarrow$) Assume $x\in (A\cap B{)}^C$

• Then $x\notin A\cap B$
• So $\neg (x\in A\wedge x\in B)$
• By logic: $\neg (x\in A)\vee \neg (x\in B)$
• Thus $x\notin A$ or $x\notin B$
• Therefore $x\in A^C$ or $x\in B^C$
• So $x\in A^C\cup B^C$

($\Leftarrow$) Assume $x\in A^C\cup B^C$

• Then $x\in A^C$ or $x\in B^C$
• So $x\notin A$ or $x\notin B$
• Thus $\neg (x\in A\wedge x\in B)$
• Therefore $x\notin A\cap B$
• So $x\in (A\cap B{)}^C$

Second law

$(A\cup B{)}^C=A^C\cap B^C$

Prove $x\in (A\cup B{)}^C⟺x\in A^C\cap B^C$

($\Rightarrow$) Assume $x\in (A\cup B{)}^C$

• Then $x\notin A\cup B$
• So $\neg (x\in A\vee x\in B)$
• By logic: $\neg (x\in A)\wedge \neg (x\in B)$
• Thus $x\notin A$ and $x\notin B$
• Therefore $x\in A^C$ and $x\in B^C$
• So $x\in A^C\cap B^C$

($\Leftarrow$) Assume $x\in A^C\cap B^C$

• Then $x\in A^C$ and $x\in B^C$
• So $x\notin A$ and $x\notin B$
• Thus $\neg (x\in A\vee x\in B)$
• Therefore $x\notin A\cup B$
• So $x\in (A\cup B{)}^C$