De Morgan's Laws (Set Theory)

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' \in \mathbb T} \left({S \setminus T'}\right)$

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

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 $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 \in \mathbb T} \complement_S \left({H}\right)$

$(2): \quad \displaystyle \complement_S \left({\bigcup \mathbb T}\right) = \bigcap_{H \in \mathbb T} \complement_S \left({H}\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 \in \mathbb T} \complement \left({H}\right)$

$(2): \quad \displaystyle \complement \left({\bigcup \mathbb T}\right) = \bigcap_{H \in \mathbb T} \complement \left({H}\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.

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

Also see

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