Intersection with Subset is Subset

From ProofWiki
Jump to navigation Jump to search


$S \subseteq T \iff S \cap T = S$


$S \subseteq T$ denotes that $S$ is a subset of $T$
$S \cap T$ denotes the intersection of $S$ and $T$.

Proof 1

Let $S \cap T = S$.

Then by the definition of set equality, $S \subseteq S \cap T$.


\(\ds S \cap T\) \(\subseteq\) \(\ds T\) Intersection is Subset
\(\ds \leadsto \ \ \) \(\ds S\) \(\subseteq\) \(\ds T\) Subset Relation is Transitive

Now let $S \subseteq T$.

From Intersection is Subset we have $S \supseteq S \cap T$.

We also have:

\(\ds S\) \(\subseteq\) \(\ds T\)
\(\ds \leadsto \ \ \) \(\ds S \cap S\) \(\subseteq\) \(\ds T \cap S\) Set Intersection Preserves Subsets
\(\ds \leadsto \ \ \) \(\ds S\) \(\subseteq\) \(\ds S \cap T\) Set Intersection is Idempotent and Intersection is Commutative

So as we have:

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

it follows from the definition of set equality that:

$S \cap T = S$

So we have:

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

and so:

$S \subseteq T \iff S \cap T = S$

from the definition of equivalence.


Proof 2

\(\ds \) \(\) \(\ds S \cap T = S\)
\(\ds \leadstoandfrom \ \ \) \(\ds \) \(\) \(\ds \paren {x \in S \land x \in T \iff x \in S}\) Definition of Set Equality
\(\ds \leadstoandfrom \ \ \) \(\ds \) \(\) \(\ds \paren {x \in S \implies x \in T}\) Conditional iff Biconditional of Antecedent with Conjunction
\(\ds \leadstoandfrom \ \ \) \(\ds \) \(\) \(\ds S \subseteq T\) Definition of Subset


Also see