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

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 \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

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

$\blacksquare$


Proof 2

\(\displaystyle \) \(\) \(\displaystyle x \in \overline {T_1 \cap T_2}\)
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle x \notin \paren {T_1 \cap T_2}\) Definition of Set Complement
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle \neg \paren {x \in T_1 \land x \in T_2}\) Definition of Set Intersection
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle \neg \paren {x \in T_1} \lor \neg \paren {x \in T_2}\) De Morgan's Laws (Logic): Disjunction of Negations
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle x \in \overline {T_1} \lor x \in \overline {T_2}\) Definition of Set Complement
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle 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

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

$\blacksquare$


Demonstration by Venn Diagram

DeMorganComplementIntersection.png

$\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.


Sources



Retrieved from "https://proofwiki.org/w/index.php?title=De_Morgan%27s_Laws_(Set_Theory)/Set_Complement/Complement_of_Intersection&oldid=445725"