De Morgan's Laws (Set Theory)

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.

Then:

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

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

where:

• $T_1 \cap T_2$ denotes set intersection
• $T_1 \cup T_2$ denotes set union.

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:

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

$(2): \quad \displaystyle S \setminus \bigcup \mathbb T = \bigcap_{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\}$

i.e. the intersection of $\mathbb T$

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

i.e. the union of $\mathbb T$.

Family of Sets

Let $S$ and $T$ be sets.

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

Then:

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

$(2): \quad \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\}$

i.e. the intersection of $\left\langle{T_i}\right\rangle_{i \in I}$

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

i.e. the union of $\left\langle{T_i}\right\rangle_{i \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_S \left({T_1 \cap T_2}\right) = \complement_S \left({T_1}\right) \cup \complement_S \left({T_2}\right)$

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

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

$(2): \quad \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:

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

$(2): \quad \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$.

Then:

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

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

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

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

General Case

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

Then:

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

$(2): \quad \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:

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

$(2): \quad \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

• De Morgan's Laws as they arise in logic.