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

Jump to navigation
Jump to search

## Contents

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

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

- 1959: E.M. Patterson:
*Topology*(2nd ed.) ... (previous) ... (next): Chapter $\text {II}$: Topological Spaces: $\S 8$. Notations and definitions of set theory - 1964: Steven A. Gaal:
*Point Set Topology*... (previous) ... (next): Introduction to Set Theory: $1$. Elementary Operations on Sets - 1965: A.M. Arthurs:
*Probability Theory*... (previous) ... (next): Chapter $1$: Set Theory: $1.3$: Set operations - 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $1$: The Notation and Terminology of Set Theory: $\S 8 \beta$ - 1971: Robert H. Kasriel:
*Undergraduate Topology*... (previous) ... (next): $\S 1.6$: Set Identities and Other Set Relations - 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Appendix $\text{A}.1$: Sets and Subsets: Theorem $\text{A}.1 \ \text{(b)}$ - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.2$: Sets: Exercise $6$ - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**algebra of sets**: $\text {(x)}$ - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**De Morgan's Laws**

- 2008: Paul Halmos and Steven Givant:
*Introduction to Boolean Algebras*... (previous) ... (next): $\S 2$