Subsets of Disjoint Sets are Disjoint

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be disjoint sets.

Let $S' \subseteq S$ and $T' \subseteq T$.


Then $S'$ and $T'$ are disjoint.


Proof

Let $S \cap T = \O$.

Let $S' \subseteq S$ and $T' \subseteq T$.


Aiming for a contradiction, suppose $S' \cap T' \ne \O$.


Then:

\(\displaystyle \exists x\) \(\in\) \(\displaystyle S' \cap T'\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\in\) \(\displaystyle S'\) Definition of Set Intersection
\(\, \displaystyle \land \, \) \(\displaystyle x\) \(\in\) \(\displaystyle T'\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\in\) \(\displaystyle S\) Definition of Subset
\(\, \displaystyle \land \, \) \(\displaystyle x\) \(\in\) \(\displaystyle T\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\in\) \(\displaystyle S \cap T\) Definition of Set Intersection
\(\displaystyle \leadsto \ \ \) \(\displaystyle S \cap T\) \(\ne\) \(\displaystyle \O\) Definition of Set Intersection


From this contradiction:

$S' \cap T' = \O$


Hence the result by definition of disjoint sets.

$\blacksquare$


Sources