Subset of Preimage under Relation is Preimage of Subset

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathcal R \subseteq S \times T$ be a relation.

Let $X \subseteq S, Y \subseteq T$.


Then:

$X \subseteq \mathcal R^{-1} \sqbrk Y \iff \mathcal R \sqbrk X \subseteq Y$


In the language of direct image mappings, this can be written:

$X \subseteq \map {\mathcal R^\gets} Y \iff \map {\mathcal R^\to} X \subseteq Y$


Corollary

If $f: S \to T$ is a mapping, the same result holds:


$X \subseteq f^{-1} \sqbrk Y \iff f \sqbrk X \subseteq Y$


This can be expressed in the language and notation of direct image mappings and inverse image mappings as:

$\forall X \in \powerset S, Y \in \powerset T: X \subseteq \map {f^\gets} Y \iff \map {f^\to} X \subseteq Y$


Proof

As $\mathcal R$ is a relation, then so is its inverse $\mathcal R^{-1}$.


Let $\mathcal R \sqbrk X \subseteq Y$.


Thus:

\(\displaystyle \mathcal R \sqbrk X\) \(\subseteq\) \(\displaystyle Y\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \mathcal R^{-1} \sqbrk {\mathcal R \sqbrk X}\) \(\subseteq\) \(\displaystyle \mathcal R^{-1} \sqbrk Y\) Image of Subset under Relation is Subset of Image: Corollary 1
\(\displaystyle \leadsto \ \ \) \(\displaystyle X\) \(\subseteq\) \(\displaystyle \mathcal R^{-1} \sqbrk Y\) Image of Preimage under Relation is Subset, Subset Relation is Transitive

So:

$\mathcal R \sqbrk X \subseteq Y \implies X \subseteq \mathcal R^{-1} \sqbrk Y$

$\Box$


Now let $X \subseteq \mathcal R^{-1} \sqbrk Y$.


The same argument applies:

\(\displaystyle X\) \(\subseteq\) \(\displaystyle \mathcal R^{-1} \sqbrk Y\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \mathcal R \sqbrk X\) \(\subseteq\) \(\displaystyle \mathcal R \sqbrk {\mathcal R^{-1} \sqbrk Y}\) Image of Subset under Relation is Subset of Image
\(\displaystyle \leadsto \ \ \) \(\displaystyle \mathcal R \sqbrk X\) \(\subseteq\) \(\displaystyle Y\) Image of Preimage under Relation is Subset, Subset Relation is Transitive

So:

$X \subseteq \mathcal R^{-1} \sqbrk Y \implies \mathcal R \sqbrk X \subseteq Y$

$\Box$


Thus we have:

$X \subseteq \mathcal R^{-1} \sqbrk Y \implies \mathcal R \sqbrk X \subseteq Y$
$\mathcal R \sqbrk X \subseteq Y \implies X \subseteq \mathcal R^{-1} \sqbrk Y$

Hence the result.

$\blacksquare$