Subsets of Disjoint Sets are Disjoint

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:

\(\ds \exists x\)

\(\in\)

\(\ds S' \cap T'\)

\(\ds \leadsto \ \ \)

\(\ds x\)

\(\in\)

\(\ds S'\)

Definition of Set Intersection

\(\, \ds \land \, \)

\(\ds x\)

\(\in\)

\(\ds T'\)

\(\ds \leadsto \ \ \)

\(\ds x\)

\(\in\)

\(\ds S\)

Definition of Subset

\(\, \ds \land \, \)

\(\ds x\)

\(\in\)

\(\ds T\)

\(\ds \leadsto \ \ \)

\(\ds x\)

\(\in\)

\(\ds S \cap T\)

Definition of Set Intersection

\(\ds \leadsto \ \ \)

\(\ds S \cap T\)

\(\ne\)

\(\ds \O\)

Definition of Set Intersection

From this contradiction:

$S' \cap T' = \O$

Hence the result by definition of disjoint sets.

$\blacksquare$

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Appendix $\text{A}.1$: Sets and Subsets: Problem Set $\text{A}.1$: $3$