# 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$

## Sources

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