# De Morgan's Laws (Set Theory)/Set Difference

## Theorem

Let $S, T_1, T_2$ be sets.

Then:

• $S \setminus \left({T_1 \cap T_2}\right) = \left({S \setminus T_1}\right) \cup \left({S \setminus T_2}\right)$
• $S \setminus \left({T_1 \cup T_2}\right) = \left({S \setminus T_1}\right) \cap \left({S \setminus T_2}\right)$

where:

### General Case

Let $S$ and $T$ be sets.

Let $\mathcal P \left({T}\right)$ be the power set of $T$.

Let $\mathbb T \subseteq \mathcal P \left({T}\right)$.

Then:

$(1): \quad \displaystyle S \setminus \bigcap \mathbb T = \bigcup_{T\,' \mathop \in \mathbb T} \left({S \setminus T\,'}\right)$
$(2): \quad \displaystyle S \setminus \bigcup \mathbb T = \bigcap_{T\,' \mathop \in \mathbb T} \left({S \setminus T\,'}\right)$

where:

$\displaystyle \bigcap \mathbb T := \left\{{x: \forall T\,' \in \mathbb T: x \in T\,'}\right\}$

i.e. the intersection of $\mathbb T$

$\displaystyle \bigcup \mathbb T := \left\{{x: \exists T\,' \in \mathbb T: x \in T\,'}\right\}$

i.e. the union of $\mathbb T$.

### Family of Sets

Let $S$ and $T$ be sets.

Let $\left\langle{T_i}\right\rangle_{i \in I}$ be a family of subsets of $T$.

Then:

$(1): \quad \displaystyle S \setminus \bigcap_{i \mathop \in I} T_i = \bigcup_{i \mathop \in I} \left({S \setminus T_i}\right)$
$(2): \quad \displaystyle S \setminus \bigcup_{i \mathop \in I} T_i = \bigcap_{i \mathop \in I} \left({S \setminus T_i}\right)$

where:

$\displaystyle \bigcap_{i \mathop \in I} T_i := \left\{{x: \forall i \in I: x \in T_i}\right\}$

i.e. the intersection of $\left\langle{T_i}\right\rangle_{i \in I}$

$\displaystyle \bigcup_{i \mathop \in I} T_i := \left\{{x: \exists i \in I: x \in T_i}\right\}$

i.e. the union of $\left\langle{T_i}\right\rangle_{i \in I}$.

## Corollary

Suppose that $T_1 \subseteq S$.

Then:

$S \setminus \left({T_1 \cap T_2}\right) = \left({S \setminus T_1}\right) \cup \left({T_1 \setminus T_2}\right)$

## Proof

• $S \setminus \left({T_1 \cap T_2}\right) = \left({S \setminus T_1}\right) \cup \left({S \setminus T_2}\right)$:

 $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle x \in S \setminus \left({T_1 \cap T_2}\right)$$ $$\iff$$ $$\displaystyle$$ $$\displaystyle \left({x \in S}\right) \land \left({x \notin \left({T_1 \cap T_2}\right)}\right)$$ $$\displaystyle$$ $$\displaystyle$$ Definition of Set Difference $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\iff$$ $$\displaystyle$$ $$\displaystyle \left({x \in S}\right) \land \left({\neg \left({x \in T_1 \land x \in T_2}\right)}\right)$$ $$\displaystyle$$ $$\displaystyle$$ Definition of Set Intersection $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\iff$$ $$\displaystyle$$ $$\displaystyle \left({x \in S}\right) \land \left({x \notin T_1 \lor x \notin T_2}\right)$$ $$\displaystyle$$ $$\displaystyle$$ De Morgan's Laws: Disjunction of Negations $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\iff$$ $$\displaystyle$$ $$\displaystyle \left({x \in S \land x \notin T_1}\right) \lor \left({x \in S \land x \notin T_2}\right)$$ $$\displaystyle$$ $$\displaystyle$$ Rule of Distribution $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\iff$$ $$\displaystyle$$ $$\displaystyle x \in \left({S \setminus T_1}\right) \cup \left({S \setminus T_2}\right)$$ $$\displaystyle$$ $$\displaystyle$$ Definition of Set Union and Set Difference

So $S \setminus \left({T_1 \cap T_2}\right) = \left({S \setminus T_1}\right) \cup \left({S \setminus T_2}\right)$.

$\blacksquare$

• $S \setminus \left({T_1 \cup T_2}\right) = \left({S \setminus T_1}\right) \cap \left({S \setminus T_2}\right)$:

 $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle x \in S \setminus \left({T_1 \cup T_2}\right)$$ $$\iff$$ $$\displaystyle$$ $$\displaystyle \left({x \in S}\right) \land \left({x \notin \left({T_1 \cup T_2}\right)}\right)$$ $$\displaystyle$$ $$\displaystyle$$ Definition of Set Difference $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\iff$$ $$\displaystyle$$ $$\displaystyle \left({x \in S}\right) \land \left({\neg \left({x \in T_1 \lor x \in T_2}\right)}\right)$$ $$\displaystyle$$ $$\displaystyle$$ Definition of Set Union $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\iff$$ $$\displaystyle$$ $$\displaystyle \left({x \in S}\right) \land \left({x \notin T_1 \land x \notin T_2}\right)$$ $$\displaystyle$$ $$\displaystyle$$ De Morgan's Laws: Conjunction of Negations $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\iff$$ $$\displaystyle$$ $$\displaystyle \left({x \in S \land x \notin T_1}\right) \land \left({x \in S \land x \notin T_2}\right)$$ $$\displaystyle$$ $$\displaystyle$$ Rules of Idempotence, Commutation and Association $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\iff$$ $$\displaystyle$$ $$\displaystyle x \in \left({S \setminus T_1}\right) \cap \left({S \setminus T_2}\right)$$ $$\displaystyle$$ $$\displaystyle$$ Definition of Set Intersection and Set Difference

So $S \setminus \left({T_1 \cup T_2}\right) = \left({S \setminus T_1}\right) \cap \left({S \setminus T_2}\right)$.

$\blacksquare$

## Source of Name

This entry was named for Augustus De Morgan.