De Morgan's Laws (Set Theory)/Set Difference

From ProofWiki
Jump to: navigation, search

Contents

Theorem

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:

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:

$(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}$.


Corollary

Suppose that $T_1 \subseteq S$.


Then:

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


Proof

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


\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle x \in S \setminus \left({T_1 \cap T_2}\right)\) \(\iff\) \(\displaystyle \) \(\displaystyle \left({x \in S}\right) \land \left({x \notin \left({T_1 \cap T_2}\right)}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Set Difference          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\iff\) \(\displaystyle \) \(\displaystyle \left({x \in S}\right) \land \left({\neg \left({x \in T_1 \land x \in T_2}\right)}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Set Intersection          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\iff\) \(\displaystyle \) \(\displaystyle \left({x \in S}\right) \land \left({x \notin T_1 \lor x \notin T_2}\right)\) \(\displaystyle \) \(\displaystyle \)          De Morgan's Laws: Disjunction of Negations          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\iff\) \(\displaystyle \) \(\displaystyle \left({x \in S \land x \notin T_1}\right) \lor \left({x \in S \land x \notin T_2}\right)\) \(\displaystyle \) \(\displaystyle \)          Rule of Distribution          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\iff\) \(\displaystyle \) \(\displaystyle x \in \left({S \setminus T_1}\right) \cup \left({S \setminus T_2}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Set Union and Set Difference          


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

$\blacksquare$


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


\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle x \in S \setminus \left({T_1 \cup T_2}\right)\) \(\iff\) \(\displaystyle \) \(\displaystyle \left({x \in S}\right) \land \left({x \notin \left({T_1 \cup T_2}\right)}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Set Difference          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\iff\) \(\displaystyle \) \(\displaystyle \left({x \in S}\right) \land \left({\neg \left({x \in T_1 \lor x \in T_2}\right)}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Set Union          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\iff\) \(\displaystyle \) \(\displaystyle \left({x \in S}\right) \land \left({x \notin T_1 \land x \notin T_2}\right)\) \(\displaystyle \) \(\displaystyle \)          De Morgan's Laws: Conjunction of Negations          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\iff\) \(\displaystyle \) \(\displaystyle \left({x \in S \land x \notin T_1}\right) \land \left({x \in S \land x \notin T_2}\right)\) \(\displaystyle \) \(\displaystyle \)          Rules of Idempotence, Commutation and Association          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\iff\) \(\displaystyle \) \(\displaystyle x \in \left({S \setminus T_1}\right) \cap \left({S \setminus T_2}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Set Intersection and Set Difference          


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

$\blacksquare$


Source of Name

This entry was named for Augustus De Morgan.


Sources

Retrieved from "http://www.proofwiki.org/w/index.php?title=De_Morgan%27s_Laws_(Set_Theory)/Set_Difference&oldid=143922"