# Subsets of Disjoint Sets are Disjoint

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$