# Set Complement inverts Subsets

## Theorem

Let $S$ and $T$ be sets.

Then:

$S \subseteq T \iff \map \complement T \subseteq \map \complement S$

where:

$S \subseteq T$ denotes that $S$ is a subset of $T$
$\complement$ denotes set complement.

### Corollary

$S \subseteq \map \complement T \iff T \subseteq \map \complement S$

## Proof 1

 $\ds S$ $\subseteq$ $\ds T$ $\ds \leadstoandfrom \ \$ $\ds S \cap T$ $=$ $\ds S$ Intersection with Subset is Subset‎ $\ds \leadstoandfrom \ \$ $\ds \map \complement {S \cap T}$ $=$ $\ds \map \complement S$ Complement of Complement $\ds \leadstoandfrom \ \$ $\ds \map \complement S \cup \map \complement T$ $=$ $\ds \map \complement S$ De Morgan's Laws: Complement of Intersection $\ds \leadstoandfrom \ \$ $\ds \map \complement T$ $\subseteq$ $\ds \map \complement S$ Union with Superset is Superset

$\blacksquare$

## Proof 2

 $\ds S$ $\subseteq$ $\ds T$ $\ds \leadstoandfrom \ \$ $\ds (x \in S$ $\implies$ $\ds x \in T)$ Definition of Subset $\ds \leadstoandfrom \ \$ $\ds (x \notin T$ $\implies$ $\ds x \notin S)$ Rule of Transposition $\ds \leadstoandfrom \ \$ $\ds (x \in \map \complement T$ $\implies$ $\ds x \in \map \complement S)$ Definition of Set Complement $\ds \map \complement T$ $\subseteq$ $\ds \map \complement S$ Definition of Subset

$\blacksquare$

## Proof 3

By definition of set complement:

$\map \complement T := \relcomp {\mathbb U} T$

where:

$\mathbb U$ is the universe
$\relcomp {\mathbb U} T$ denotes the complement of $T$ relative to $\mathbb U$.

Thus the statement can be expressed as:

$S \subseteq T \iff \relcomp {\mathbb U} T \subseteq \relcomp {\mathbb U} S$

The result then follows from Relative Complement inverts Subsets.

$\blacksquare$