De Morgan's Laws (Set Theory)

From ProofWiki
Jump to: navigation, search

This proof is about De Morgan's Laws in the context of set theory. For other uses, see De Morgan's Laws.

Theorem

De Morgan's laws, or the De Morgan formulas, etc. are a collection of results in set theory as follows.


Set Difference

Let $S, T_1, T_2$ be sets.

Let:

$T_1 \cap T_2$ denote set intersection
$T_1 \cup T_2$ denote set union.

Then:

Difference with Intersection

$S \setminus \left({T_1 \cap T_2}\right) = \left({S \setminus T_1}\right) \cup \left({S \setminus T_2}\right)$


Difference with Union

$S \setminus \left({T_1 \cup T_2}\right) = \left({S \setminus T_1}\right) \cap \left({S \setminus T_2}\right)$


DeMorganMinusIntersection.png DeMorganMinusUnion.png

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:

Difference with Intersection

$\displaystyle S \setminus \bigcap \mathbb T = \bigcup_{T' \mathop \in \mathbb T} \left({S \setminus T'}\right)$

where:

$\displaystyle \bigcap \mathbb T := \left\{{x: \forall T' \in \mathbb T: x \in T'}\right\}$

that is, the intersection of $\mathbb T$


Difference with Union

$\displaystyle S \setminus \bigcup \mathbb T = \bigcap_{T' \mathop \in \mathbb T} \left({S \setminus T'}\right)$

where:

$\displaystyle \bigcup \mathbb T := \left\{{x: \exists T' \in \mathbb T: x \in T'}\right\}$

that is, the union of $\mathbb T$.


Family of Sets

Let $S$ and $T$ be sets.

Let $\left\langle{T_i}\right\rangle_{i \mathop \in I}$ be a family of subsets of $T$.


Then:

Difference with Intersection

$\displaystyle S \setminus \bigcap_{i \mathop \in I} T_i = \bigcup_{i \mathop \in I} \left({S \setminus T_i}\right)$

where:

$\displaystyle \bigcup_{i \mathop \in I} T_i := \left\{{x: \exists i \in I: x \in T_i}\right\}$

that is, the union of $\left\langle{T_i}\right\rangle_{i \mathop \in I}$.


Difference with Union

$\displaystyle S \setminus \bigcup_{i \mathop \in I} T_i = \bigcap_{i \mathop \in I} \left({S \setminus T_i}\right)$

where:

$\displaystyle \bigcap_{i \mathop \in I} T_i := \left\{{x: \forall i \in I: x \in T_i}\right\}$

that is, the intersection of $\left\langle{T_i}\right\rangle_{i \mathop \in I}$


Relative Complement

Let $S, T_1, T_2$ be sets such that $T_1, T_2$ are both subsets of $S$.


Then, using the notation of the relative complement:

Complement of Intersection

$\complement_S \left({T_1 \cap T_2}\right) = \complement_S \left({T_1}\right) \cup \complement_S \left({T_2}\right)$


Complement of Union

$\complement_S \left({T_1 \cup T_2}\right) = \complement_S \left({T_1}\right) \cap \complement_S \left({T_2}\right)$


General Case

Let $S$ be a set.

Let $T$ be a subset of $S$.

Let $\mathcal P \left({T}\right)$ be the power set of $T$.

Let $\mathbb T \subseteq \mathcal P \left({T}\right)$.


Then:

Complement of Intersection

$\displaystyle \complement_S \left({\bigcap \mathbb T}\right) = \bigcup_{H \mathop \in \mathbb T} \complement_S \left({H}\right)$


Complement of Union

$\displaystyle \complement_S \left({\bigcup \mathbb T}\right) = \bigcap_{H \mathop \in \mathbb T} \complement_S \left({H}\right)$


Family of Sets

Let $S$ be a set.

Let $\left\langle{S_i}\right\rangle_{i \in I}$ be a family of subsets of $S$.


Then:

Complement of Intersection

$\displaystyle \complement_S \left({\bigcap_{i \mathop \in I} \mathbb S_i}\right) = \bigcup_{i \mathop \in I} \complement_S \left({S_i}\right)$


Complement of Union

$\displaystyle \complement_S \left({\bigcup_{i \mathop \in I} \mathbb S_i}\right) = \bigcap_{i \mathop \in I} \complement_S \left({S_i}\right)$


Set Complement

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

Let $\overline T_1$ denote the set complement of $T_1$.


Then:

Complement of Intersection

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


Complement of Union

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


DeMorganComplementIntersection.png DeMorganComplementUnion.png


General Case

Let $\mathbb T$ be a set of sets, all of which are subsets of a universe $\mathbb U$.


Then:

Complement of Intersection

$\displaystyle \complement \left({\bigcap \mathbb T}\right) = \bigcup_{H \mathop \in \mathbb T} \complement \left({H}\right)$


Complement of Union

$\displaystyle \complement \left({\bigcup \mathbb T}\right) = \bigcap_{H \mathop \in \mathbb T} \complement \left({H}\right)$


Family of Sets

Let $\left\langle{S_i}\right\rangle_{i \in I}$ be a family of sets, all of which are subsets of a universe $\mathbb U$.

Then:

Complement of Intersection

$\displaystyle \complement \left({\bigcap_{i \mathop \in I} S_i}\right) = \bigcup_{i \mathop \in I} \complement \left({S_i}\right)$


Complement of Union

$\displaystyle \complement \left({\bigcup_{i \mathop \in I} S_i}\right) = \bigcap_{i \mathop \in I} \complement \left({S_i}\right)$



Source of Name

This entry was named for Augustus De Morgan.

Strictly speaking, these are not the actual laws he devised, but an application of those laws in the context of set theory.


Also known as

This result is known by some authors, for example A.N. Kolmogorov and S.V. Fomin‎: Introductory Real Analysis (1968), as the duality principle.


Also see