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

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


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Set_Complement_inverts_Subsets&oldid=463303"