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

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Then:

$\overline {T_1 \cup T_2} = \overline T_1 \cap \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 \cup T_2} = \map \complement {T_1} \cap \map \complement {T_2}$


Corollary

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


Proof 1

\(\ds \map \complement {T_1 \cup T_2}\) \(=\) \(\ds \mathbb U \setminus \paren {T_1 \cup T_2}\) Definition of Set Complement
\(\ds \) \(=\) \(\ds \paren {\mathbb U \setminus T_1} \cap \paren {\mathbb U \setminus T_2}\) De Morgan's Laws: Difference with Union
\(\ds \) \(=\) \(\ds \map \complement {T_1} \cap \map \complement {T_2}\) Definition of Set Complement

$\blacksquare$


Proof 2

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

By definition of set equality:

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

$\blacksquare$


Demonstration by Venn Diagram

DeMorganComplementUnion.png

$\overline T_1$ is depicted in yellow and $\overline T_2$ is depicted in red.

Their intersection, $\overline T_1 \cap \overline T_2$, is depicted in orange.

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


Source of Name

This entry was named for Augustus De Morgan.


Sources