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

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


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


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.