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:

• $T_1 \cap T_2$ denotes set intersection
• $T_1 \cup T_2$ denotes set union.

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)$

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\ ' \in \mathbb T} \left({S \setminus T\ '}\right)$

$(2): \quad \displaystyle S \setminus \bigcup \mathbb T = \bigcap_{T\ ' \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$.

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 \left({x \in S}\right) \land \left({x \notin \left({T_1 \cap T_2}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Set Difference
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\iff\)	\(\displaystyle \left({x \in S}\right) \land \left({\neg \left({x \in T_1 \land x \in T_2}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Set Intersection
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\iff\)	\(\displaystyle \left({x \in S}\right) \land \left({x \notin T_1 \lor x \notin T_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	De Morgan's Laws (Logic)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\iff\)	\(\displaystyle \left({x \in S \land x \notin T_1}\right) \lor \left({x \in S \land x \notin T_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Rule of Distribution
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\iff\)	\(\displaystyle x \in \left({S \setminus T_1}\right) \cup \left({S \setminus T_2}\right)\)	\(\displaystyle \)	\(\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 \left({x \in S}\right) \land \left({x \notin \left({T_1 \cup T_2}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Set Difference
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\iff\)	\(\displaystyle \left({x \in S}\right) \land \left({\neg \left({x \in T_1 \lor x \in T_2}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Set Union
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\iff\)	\(\displaystyle \left({x \in S}\right) \land \left({x \notin T_1 \land x \notin T_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	De Morgan's Laws (Logic)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\iff\)	\(\displaystyle \left({x \in S \land x \notin T_1}\right) \land \left({x \in S \land x \notin T_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Rules of Idempotence, Commutation and Association
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\iff\)	\(\displaystyle x \in \left({S \setminus T_1}\right) \cap \left({S \setminus T_2}\right)\)	\(\displaystyle \)	\(\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.

Sources

• W.E. Deskins: Abstract Algebra (1964): $\S 1.1$: Theorem $1.8$, Exercise $1.1: 8 \ \text{(h)}$
• Steven A. Gaal: Point Set Topology (1964)... (previous)... (next): Introduction to Set Theory: $1$. Elementary Operations on Sets
• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 1.6$: Example $21$
• J.A. Green: Sets and Groups (1965)... (previous)... (next): Exercise $1.6$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $3.4 \ \text{(a)}$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 8 \ \text{(e), (f)}$
• Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (1993): $\S 1.2$: Exercise $1.2.2 \ \text{(iv), (v)}$
• René L. Schilling: Measures, Integrals and Martingales (2005)... (previous)... (next) $\S 2$: Problem $1 \ \text{(iv), (v)}$