De Morgan's Laws for Set Difference

Theorem

Let $A,B,C$ be any set

Then

$$\begin{array}{rl}A-(B\cup C)& =(A-B)\cap (A-C)\\ A-(B\cap C)& =(A-B)\cup (A-B)\end{array}$$

Proof

First law

$A-(B\cup C)=(A-B)\cap (A-C)$

Prove $x\in A-(B\cup C)⟺x\in (A-B)\cap (A-C)$

($\Rightarrow$) Assume $x\in A-(B\cup C)$

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

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

• Then $x\in A-B$ and $x\in A-C$
• So $(x\in A\wedge x\notin B)$ and $(x\in A\wedge x\notin C)$
• Thus $x\in A$ and $x\notin B$ and $x\notin C$
• Therefore $x\in A$ and $\neg (x\in B\vee x\in C)$
• So $x\in A$ and $x\notin B\cup C$
• Thus $x\in A-(B\cup C)$

Second law

$A-(B\cap C)=(A-B)\cup (A-C)$

Prove $x\in A-(B\cap C)⟺x\in (A-B)\cup (A-C)$

($\Rightarrow$) Assume $x\in A-(B\cap C)$

• Then $x\in A$ and $x\notin B\cap C$
• So $x\in A$ and $\neg (x\in B\wedge x\in C)$
• Thus $x\in A$ and $(x\notin B\vee x\notin C)$
• Case 1: $x\in A$ and $x\notin B$, so $x\in A-B$
• Case 2: $x\in A$ and $x\notin C$, so $x\in A-C$
• Therefore $x\in (A-B)\cup (A-C)$

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

• Then $x\in A-B$ or $x\in A-C$
• Case 1: $x\in A-B$, so $x\in A$ and $x\notin B$, thus $x\notin B\cap C$
• Case 2: $x\in A-C$, so $x\in A$ and $x\notin C$, thus $x\notin B\cap C$
• In both cases: $x\in A$ and $x\notin B\cap C$
• Therefore $x\in A-(B\cap C)$