Set Complement inverts Subsets

From ProofWiki
Jump to navigation Jump to search


Let $S$ and $T$ be sets.


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


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


$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


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


Proof 3

By definition of set complement:

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


$\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.