Union with Superset is Superset

From ProofWiki
Jump to navigation Jump to search


$S \subseteq T \iff S \cup T = T$


$S \subseteq T$ denotes that $S$ is a subset of $T$
$S \cup T$ denotes the union of $S$ and $T$.

Proof 1

Let $S \cup T = T$.

Then by definition of set equality:

$S \cup T \subseteq T$


\(\ds S\) \(\subseteq\) \(\ds S \cup T\) Subset of Union
\(\ds \leadsto \ \ \) \(\ds S\) \(\subseteq\) \(\ds T\) Subset Relation is Transitive

Now let $S \subseteq T$.

From Subset of Union, we have $S \cup T \supseteq T$.

We also have:

\(\ds S\) \(\subseteq\) \(\ds T\)
\(\ds \leadsto \ \ \) \(\ds S \cup T\) \(\subseteq\) \(\ds T \cup T\) Set Union Preserves Subsets
\(\ds \leadsto \ \ \) \(\ds S \cup T\) \(\subseteq\) \(\ds T\) Set Union is Idempotent


\(\ds S \cup T\) \(\subseteq\) \(\ds T\)
\(\ds S \cup T\) \(\supseteq\) \(\ds T\)

By definition of set equality:

$S \cup T = T$


\(\ds S \cup T = T\) \(\implies\) \(\ds S \subseteq T\)
\(\ds S \subseteq T\) \(\implies\) \(\ds S \cup T = T\)

and so:

$S \subseteq T \iff S \cup T = T$

from the definition of equivalence.


Proof 2

\(\ds \) \(\) \(\ds S \cup T = T\)
\(\ds \leadstoandfrom \ \ \) \(\ds \) \(\) \(\ds \paren {x \in S \lor x \in T \iff x \in T}\) Definition of Set Equality
\(\ds \leadstoandfrom \ \ \) \(\ds \) \(\) \(\ds \paren {x \in S \implies x \in T}\) Conditional iff Biconditional of Consequent with Disjunction
\(\ds \leadstoandfrom \ \ \) \(\ds \) \(\) \(\ds S \subseteq T\) Definition of Subset


Also see