# Set Complement inverts Subsets

Jump to navigation Jump to search

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

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

$\blacksquare$

## Proof 2

 $\displaystyle S$ $\subseteq$ $\displaystyle T$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle (x \in S$ $\implies$ $\displaystyle x \in T)$ Definition of Subset $\displaystyle \leadstoandfrom \ \$ $\displaystyle (x \notin T$ $\implies$ $\displaystyle x \notin S)$ Rule of Transposition $\displaystyle \leadstoandfrom \ \$ $\displaystyle (x \in \map \complement T$ $\implies$ $\displaystyle x \in \map \complement S)$ Definition of Set Complement $\displaystyle \map \complement T$ $\subseteq$ $\displaystyle \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$