# De Morgan's Laws (Set Theory)/Set Complement/Complement of Intersection

## Theorem

Let $T_1, T_2$ be subsets of a universe $\mathbb U$.

Then:

$\overline {T_1 \cap T_2} = \overline T_1 \cup \overline T_2$

where $\overline T_1$ is the set complement of $T_1$.

It is arguable that this notation may be easier to follow:

$\map \complement {T_1 \cap T_2} = \map \complement {T_1} \cup \map \complement {T_2}$

## Proof 1

 $\ds \overline {T_1 \cap T_2}$ $=$ $\ds \mathbb U \setminus \paren {T_1 \cap T_2}$ Definition of Set Complement $\ds$ $=$ $\ds \paren {\mathbb U \setminus T_1} \cup \paren {\mathbb U \setminus T_2}$ De Morgan's Laws: Difference with Intersection $\ds$ $=$ $\ds \overline {T_1} \cup \overline {T_2}$ Definition of Set Complement

$\blacksquare$

## Proof 2

 $\ds$  $\ds x \in \overline {T_1 \cap T_2}$ $\ds$ $\leadstoandfrom$ $\ds x \notin \paren {T_1 \cap T_2}$ Definition of Set Complement $\ds$ $\leadstoandfrom$ $\ds \neg \paren {x \in T_1 \land x \in T_2}$ Definition of Set Intersection $\ds$ $\leadstoandfrom$ $\ds \neg \paren {x \in T_1} \lor \neg \paren {x \in T_2}$ De Morgan's Laws (Logic): Disjunction of Negations $\ds$ $\leadstoandfrom$ $\ds x \in \overline {T_1} \lor x \in \overline {T_2}$ Definition of Set Complement $\ds$ $\leadstoandfrom$ $\ds x \in \overline {T_1} \cup \overline {T_2}$

By definition of set equality:

$\overline {T_1 \cap T_2} = \overline {T_1} \cup \overline {T_2}$

$\blacksquare$

## Proof 3

 $\ds \map \complement {\map \complement A \cup \map \complement B}$ $=$ $\ds \map \complement {\map \complement A} \cap \map \complement {\map \complement B}$ De Morgan's Laws: Complement of Union $\ds$ $=$ $\ds A \cap B$ Complement of Complement $\ds \leadstoandfrom \ \$ $\ds \map \complement {\map \complement {\map \complement A \cup \map \complement B} }$ $=$ $\ds \map \complement {A \cap B}$ taking complements of both sides $\ds \leadstoandfrom \ \$ $\ds \map \complement A \cup \map \complement B$ $=$ $\ds \map \complement {A \cap B}$ Complement of Complement

$\blacksquare$

## Demonstration by Venn Diagram $\overline T_1$ is depicted in yellow and $\overline T_2$ is depicted in red.

Their intersection, where they overlap, is depicted in orange.

Their union $\overline T_1 \cup \overline T_2$ is the total shaded area: yellow, red and orange.

As can be seen by inspection, this also equals the complement of the intersection of $T_1$ and $T_2$.

## Source of Name

This entry was named for Augustus De Morgan.