De Morgan's Laws (Set Theory)/Relative Complement
From ProofWiki
Contents |
Theorem
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)$
Proof
Let $T_1, T_2 \subseteq S$.
Then:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle T_1 \cap T_2\) | \(\subseteq\) | \(\displaystyle S\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | from Intersection Subset and Subsets Transitive | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle T_1 \cup T_2\) | \(\subseteq\) | \(\displaystyle S\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Union Smallest |
So we can talk about $\complement_S \left({T_1 \cap T_2}\right)$ and $\complement_S \left({T_1 \cup T_2}\right)$.
Hence the following results are defined:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \complement_S \left({T_1 \cap T_2}\right)\) | \(=\) | \(\displaystyle S \setminus \left({T_1 \cap T_2}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Relative Complement | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \left({S \setminus T_1}\right) \cup \left({S \setminus T_2}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | De Morgan's Laws for Set Difference: see above | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \complement_S \left({T_1}\right) \cup \complement_S \left({T_2}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Relative Complement |
$\blacksquare$
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \complement_S \left({T_1 \cup T_2}\right)\) | \(=\) | \(\displaystyle S \setminus \left({T_1 \cup T_2}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Relative Complement | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \left({S \setminus T_1}\right) \cap \left({S \setminus T_2}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | De Morgan's Laws for Set Difference | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \complement_S \left({T_1}\right) \cap \complement_S \left({T_2}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Relative Complement |
$\blacksquare$
Proof of General Case
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \complement_S \left({\bigcap \mathbb T}\right)\) | \(=\) | \(\displaystyle S \setminus \left({\bigcap \mathbb T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Relative Complement | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \bigcup_{H \in \mathbb T} \left({S \setminus H}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | De Morgan's Laws for Set Difference: General Case | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \bigcup_{H \in \mathbb T} \complement_S \left({H}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Relative Complement |
$\blacksquare$
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \complement_S \left({\bigcup \mathbb T}\right)\) | \(=\) | \(\displaystyle S \setminus \left({\bigcup \mathbb T}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Relative Complement | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \bigcap_{H \in \mathbb T} \left({S \setminus H}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | De Morgan's Laws for Set Difference: General Case | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \bigcap_{H \in \mathbb T} \complement_S \left({H}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Relative Complement |
$\blacksquare$
Source of Name
This entry was named for Augustus De Morgan.
Sources
- Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 5$: Complements and Powers
- Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 3$: Theorem $3.2$
- Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $3.2$
- Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $3.6 \ \text{(c), (d)}$
- T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 1, \ \S 6$: Exercise $2$
- René L. Schilling: Measures, Integrals and Martingales (2005)... (previous)... (next) $\S 2$
