Set Complement inverts Subsets

From ProofWiki
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$


Sources