Intersection is Largest Subset

From ProofWiki
Jump to: navigation, search

Theorem

Let $T_1$ and $T_2$ be sets.

Then $T_1 \cap T_2$ is the largest set contained in both $T_1$ and $T_2$.


That is:

$S \subseteq T_1 \land S \subseteq T_2 \iff S \subseteq T_1 \cap T_2$


Set of Sets

Intersection is Largest Subset/Set of Sets

General Result

Let $T$ be a set.

Let $\mathcal P \left({T}\right)$ be the power set of $T$.

Let $\mathbb T$ be a subset of $\mathcal P \left({T}\right)$.


Then:

$\left({\forall X \in \mathbb T: S \subseteq X}\right) \iff S \subseteq \bigcap \mathbb 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: X \subseteq S_i} \iff X \subseteq \bigcap_{i \mathop \in I} S_i$

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


Proof

Let $S \subseteq T_1 \land S \subseteq T_2$.


Then:

\(\displaystyle x \in S\) \(\leadsto\) \(\displaystyle x \in T_1 \land x \in T_2\) Definition of Subset
\(\displaystyle \) \(\leadsto\) \(\displaystyle x \in T_1 \cap T_2\) Definition of Set Intersection
\(\displaystyle \) \(\leadsto\) \(\displaystyle S \subseteq T_1 \cap T_2\) Definition of Subset


Alternatively:

\(\displaystyle S\) \(\subseteq\) \(\displaystyle T_2\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle S\) \(=\) \(\displaystyle S \cap T_2\) Intersection with Subset is Subset‎
\(\displaystyle \) \(\subseteq\) \(\displaystyle T_1 \cap T_2\) Set Intersection Preserves Subsets


So:

$S \subseteq T_1 \land S \subseteq T_2 \implies S \subseteq T_1 \cap T_2$.


Now let $S \subseteq T_1 \cap T_2$.

From Intersection is Subset we have $T_1 \cap T_2 \subseteq T_1$ and $T_1 \cap T_2\subseteq T_2$.

From Subset Relation is Transitive, it follows directly that $S \subseteq T_1$ and $S \subseteq T_2$.

So $S \subseteq T_1 \cap T_2 \implies S \subseteq T_1 \land S \subseteq T_2$.


From the above, we have:

$S \subseteq T_1 \land S \subseteq T_2 \implies S \subseteq T_1 \cap T_2$
$S \subseteq T_1 \cap T_2 \implies S \subseteq T_1 \land S \subseteq T_2$


Thus $S \subseteq T_1 \land S \subseteq T_2 \iff S \subseteq T_1 \cap T_2$ from the definition of equivalence.

$\blacksquare$


Also see


Sources