Union is Smallest Superset

From ProofWiki
Jump to: navigation, search

Theorem

Let $S_1$ and $S_2$ be sets.

Then $S_1 \cup S_2$ is the smallest set containing both $S_1$ and $S_2$.


That is:

$\paren {S_1 \subseteq T} \land \paren {S_2 \subseteq T} \iff \paren {S_1 \cup S_2} \subseteq T$


Set of Sets

Let $T$ be a set.

Let $\mathbb S$ be a set of sets.

Then:

$\displaystyle \left({\forall X \in \mathbb S: X \subseteq T}\right) \iff \bigcup \mathbb S \subseteq T$


General Result

Let $S$ and $T$ be sets.

Let $\powerset S$ denote the power set of $S$.

Let $\mathbb S$ be a subset of $\powerset S$.


Then:

$\displaystyle \paren {\forall X \in \mathbb S: X \subseteq T} \iff \bigcup \mathbb S \subseteq T$


Family of Sets

In the context of a family of sets, the result can be presented as follows:


Let $\family {S_i}_{i \mathop \in I}$ be a family of sets indexed by $I$.


Then for all sets $X$:

$\displaystyle \paren {\forall i \in I: S_i \subseteq X} \iff \bigcup_{i \mathop \in I} S_i \subseteq X$

where $\displaystyle \bigcup_{i \mathop \in I} S_i$ is the union of $\family {S_i}$.


Proof

Necessary Condition

From Union of Subsets is Subset:

$\paren {S_1 \subseteq T} \land \paren {S_2 \subseteq T} \implies \paren {S_1 \cup S_2} \subseteq T$

$\Box$


Sufficient Condition

Let $\paren {S_1 \cup S_2} \subseteq T$:

\(\displaystyle S_1\) \(\subseteq\) \(\displaystyle S_1 \cup S_2\) Set is Subset of Union
\(\displaystyle \paren {S_1 \cup S_2}\) \(\subseteq\) \(\displaystyle T\) by hypothesis
\(\displaystyle \leadsto \ \ \) \(\displaystyle S_1\) \(\subseteq\) \(\displaystyle T\) Subset Relation is Transitive


Similarly for $S_2$:

\(\displaystyle S_2\) \(\subseteq\) \(\displaystyle S_1 \cup S_2\) Set is Subset of Union
\(\displaystyle \paren {S_1 \cup S_2}\) \(\subseteq\) \(\displaystyle T\) by hypothesis
\(\displaystyle \leadsto \ \ \) \(\displaystyle S_2\) \(\subseteq\) \(\displaystyle T\) Subset Relation is Transitive

That is:

$\paren {S_1 \cup S_2} \subseteq T \implies \paren {S_1 \subseteq T} \land \paren {S_2 \subseteq T}$

$\Box$


Thus from the definition of equivalence:

$\paren {S_1 \subseteq T} \land \paren {S_2 \subseteq T} \iff \paren {S_1 \cup S_2} \subseteq T$

$\blacksquare$


Also see