De Morgan's Laws (Set Theory)/Set Difference/General Case
Contents |
Theorem
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$.
Proof
First result
$(1): \quad \displaystyle S \setminus \bigcap \mathbb T = \bigcup_{T\ ' \in \mathbb T} \left({S \setminus T\ '}\right)$
Suppose:
- $\displaystyle x \in S \setminus \bigcap \mathbb T$
Note that by Set Difference Subset we have that $x \in S$ (we need this later).
Then:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle x\) | \(\in\) | \(\displaystyle S \setminus \bigcap \mathbb T\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle x\) | \(\notin\) | \(\displaystyle \bigcap \mathbb T\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | by definition of set difference | ||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle \neg (\forall T\ ' \in \mathbb T: (x\) | \(\in\) | \(\displaystyle T\ '))\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | by definition of set intersection | ||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle \exists T\ ' \in \mathbb T: \neg (x\) | \(\in\) | \(\displaystyle T\ ')\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | De Morgan's Laws (Predicate Logic) | ||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle \exists T\ ' \in \mathbb T: x\) | \(\in\) | \(\displaystyle S \setminus T\ '\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | by definition of set difference: note $x \in S$ from above | ||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle x\) | \(\in\) | \(\displaystyle \bigcup_{T\ ' \in \mathbb T} \left({S \setminus T\ '}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | by definition of set union |
Therefore:
- $S \setminus \bigcap \mathbb T = \bigcup_{T\ ' \in \mathbb T} \left({S \setminus T\ '}\right)$
$\blacksquare$
Second result
To prove that: $(2): \quad \displaystyle S \setminus \bigcup \mathbb T = \bigcap_{T\ ' \in \mathbb T} \left({S \setminus T\ '}\right)$
Suppose:
- $\displaystyle x \in S \setminus \bigcup \mathbb T$
Note that by Set Difference Subset we have that $x \in S$ (we need this later).
Then:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle x\) | \(\in\) | \(\displaystyle S \setminus \bigcup \mathbb T\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle x\) | \(\notin\) | \(\displaystyle \bigcup \mathbb T\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | by definition of set difference | ||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle \neg (\exists T\ ' \in \mathbb T: (x\) | \(\in\) | \(\displaystyle T\ '))\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | by definition of set union | ||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle \forall T\ ' \in \mathbb T: \neg (x\) | \(\in\) | \(\displaystyle T\ ')\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | De Morgan's Laws (Predicate Logic) | ||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle \forall T\ ' \in \mathbb T: x\) | \(\in\) | \(\displaystyle S \setminus T\ '\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | by definition of set difference: note $x \in S$ from above | ||
| \(\displaystyle \) | \(\displaystyle \iff\) | \(\displaystyle \) | \(\displaystyle x\) | \(\in\) | \(\displaystyle \bigcap_{T\ ' \in \mathbb T} \left({S \setminus T\ '}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | by definition of set intersection |
Therefore:
- $\displaystyle S \setminus \mathbb T = \bigcap_{T\ ' \in \mathbb T} \left({S \setminus T\ '}\right)$
$\blacksquare$
Caution
It is tempting to set up an argument to prove the general case using induction. While this works, and is a perfectly valid demonstration for an elementary student in how such proofs are crafted, such a proof is inadequate as it is valid only when $\mathbb T$ is finite.
The proof as given above relies only upon De Morgan's laws as applied to predicate logic. Thus the uncountable case has been reduced to a result in logic.
However, for better or worse, the following is an example of how one might achieve this result using induction.
Proof by Induction
Let $\mathbb T = \left\{{T_i: i \in I}\right\}$, where each $T_i$ is a set and $I$ is some finite indexing set.
Then:
- $\displaystyle S \setminus \bigcap_{i \in I} T_i = \bigcup_{i \in I} \left({S \setminus T_i}\right)$
- $\displaystyle S \setminus \bigcup_{i \in I} T_i = \bigcap_{i \in I} \left({S \setminus T_i}\right)$
Let the cardinality $\left|{I}\right|$ of the indexing set $I$ be $n$.
Then by the definition of cardinality, it follows that $I \cong \N^*_n$ and we can express the propositions:
- $\displaystyle S \setminus \bigcap_{i \in I} T_i = \bigcup_{i \in I} \left({S \setminus T_i}\right)$
- $\displaystyle S \setminus \bigcup_{i \in I} T_i = \bigcap_{i \in I} \left({S \setminus T_i}\right)$
as:
- $\displaystyle S \setminus \bigcap_{i = 1}^n T_i = \bigcup_{i = 1}^n \left({S \setminus T_i}\right)$
- $\displaystyle S \setminus \bigcup_{i = 1}^n T_i = \bigcap_{i = 1}^n \left({S \setminus T_i}\right)$
The proof of these is more amenable to proof by Principle of Mathematical Induction.
First result
For all $n \in \N^*$, let $P \left({n}\right)$ be the proposition:
- $\displaystyle S \setminus \bigcap_{i = 1}^n T_i = \bigcup_{i = 1}^n \left({S \setminus T_i}\right)$
- $P(1)$ is true, as this just says $S \setminus T_1 = S \setminus T_1$.
First result: Base Case
- $P(2)$ is the case:
- $S \setminus \left({T_1 \cap T_2}\right) = \left({S \setminus T_1}\right) \cup \left({S \setminus T_2}\right)$
which has been proved.
This is our basis for the induction.
First result: Induction Hypothesis
Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.
So this is our induction hypothesis:
- $\displaystyle S \setminus \bigcap_{i = 1}^k T_i = \bigcup_{i = 1}^k \left({S \setminus T_i}\right)$
First result: Induction Step
Now we need to show:
- $\displaystyle S \setminus \bigcap_{i = 1}^{k+1} T_i = \bigcup_{i = 1}^{k+1} \left({S \setminus T_i}\right)$
This is our induction step:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle S \setminus \bigcap_{i = 1}^{k+1} T_i\) | \(=\) | \(\displaystyle S \setminus \left({\bigcap_{i = 1}^k T_i \cap T_{k+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Intersection is Associative | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \left({S \setminus \bigcap_{i = 1}^k T_i}\right) \cup \left({S \setminus T_{k+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Base case | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \left({\bigcup_{i = 1}^k \left({S \setminus T_i}\right)}\right) \cup \left({S \setminus T_{k+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Induction hypothesis | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \bigcup_{i = 1}^{k+1} \left({S \setminus T_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Union is Associative |
So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\displaystyle S \setminus \bigcap_{i = 1}^n T_i = \bigcup_{i = 1}^n \left({S \setminus T_i}\right)$
i.e.
- $\displaystyle S \setminus \bigcap_{i \in I} T_i = \bigcup_{i \in I} \left({S \setminus T_i}\right)$
$\blacksquare$
Second result
For all $n \in \N^*$, let $P \left({n}\right)$ be the proposition:
- $\displaystyle S \setminus \bigcup_{i = 1}^n T_i = \bigcap_{i = 1}^n \left({S \setminus T_i}\right)$.
- $P(1)$ is true, as this just says $S \setminus T_1 = S \setminus T_1$.
Second result: Base Case
- $P(2)$ is the case:
- $S \setminus \left({T_1 \cup T_2}\right) = \left({S \setminus T_1}\right) \cap \left({S \setminus T_2}\right)$
which has been proved.
This is our basis for the induction.
Second result: Induction Hypothesis
Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.
So this is our induction hypothesis:
- $\displaystyle S \setminus \bigcup_{i = 1}^k T_i = \bigcap_{i = 1}^k \left({S \setminus T_i}\right)$
Second result: Induction Step
Now we need to show:
- $\displaystyle S \setminus \bigcup_{i = 1}^{k+1} T_i = \bigcap_{i = 1}^{k+1} \left({S \setminus T_i}\right)$
This is our induction step:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle S \setminus \bigcup_{i = 1}^{k+1} T_i\) | \(=\) | \(\displaystyle S \setminus \left({\bigcup_{i = 1}^k T_i \cup T_{k+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Union is Associative | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \left({S \setminus \bigcup_{i = 1}^k T_i}\right) \cap \left({S \setminus T_{k+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Base case | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \left({\bigcap_{i = 1}^k \left({S \setminus T_i}\right)}\right) \cap \left({S \setminus T_{k+1} }\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Induction hypothesis | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \bigcap_{i = 1}^{k+1} \left({S \setminus T_i}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Intersection is Associative |
So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\displaystyle S \setminus \bigcup_{i = 1}^n T_i = \bigcap_{i = 1}^n \left({S \setminus T_i}\right)$
i.e.:
- $\displaystyle S \setminus \bigcup_{i \in I} T_i = \bigcap_{i \in I} \left({S \setminus T_i}\right)$
$\blacksquare$
Source of Name
This entry was named for Augustus De Morgan.
Sources
- George McCarty: Topology: An Introduction with Application to Topological Groups (1967): $\text{I}$: Theorem $2 \ \text{(iii), (iv)}$, Exercise $\text{D}$
- A.N. Kolmogorov and S.V. Fomin‎: Introductory Real Analysis (1968): $\S 1.2$
- W.A. Sutherland: Introduction to Metric and Topological Spaces (1975): Notation and Terminology
- Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (1993): $\S 1.4$: Exercise $1.4.5 \ \text{(i), (ii)}$
- H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.2$: Problem $\text{A}.2.2$
