Subset of Preimage under Relation is Preimage of Subset

Theorem

Let $\RR \subseteq S \times T$ be a relation.

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

Then:

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

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

$X \subseteq \map {\RR^\gets} Y \iff \map {\RR^\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 $\RR$ is a relation, then so is its inverse $\RR^{-1}$.

Let $\RR \sqbrk X \subseteq Y$.

Thus:

\(\ds \RR \sqbrk X\)

\(\subseteq\)

\(\ds Y\)

\(\ds \leadsto \ \ \)

\(\ds \RR^{-1} \sqbrk {\RR \sqbrk X}\)

\(\subseteq\)

\(\ds \RR^{-1} \sqbrk Y\)

Image of Subset under Relation is Subset of Image: Corollary $1$

\(\ds \leadsto \ \ \)

\(\ds X\)

\(\subseteq\)

\(\ds \RR^{-1} \sqbrk Y\)

Image of Preimage under Relation is Subset, Subset Relation is Transitive

So:

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

$\Box$

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

The same argument applies:

\(\ds X\)

\(\subseteq\)

\(\ds \RR^{-1} \sqbrk Y\)

\(\ds \leadsto \ \ \)

\(\ds \RR \sqbrk X\)

\(\subseteq\)

\(\ds \RR \sqbrk {\RR^{-1} \sqbrk Y}\)

Image of Subset under Relation is Subset of Image

\(\ds \leadsto \ \ \)

\(\ds \RR \sqbrk X\)

\(\subseteq\)

\(\ds Y\)

Image of Preimage under Relation is Subset, Subset Relation is Transitive

So:

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

$\Box$

Thus we have:

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

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

Hence the result.

$\blacksquare$