Preimage of Image under Relation is Superset

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Then:

$A \subseteq S \implies A \subseteq \paren {\mathcal R^{-1} \circ \mathcal R} \sqbrk A$

where:

$\mathcal R \sqbrk A$ denotes the image of $A$ under $\mathcal R$
$\mathcal R^{-1} \sqbrk A$ denotes the preimage of $A$ under $\mathcal R$
$\mathcal R^{-1} \circ \mathcal R$ denotes composition of $\mathcal R^{-1}$ and $\mathcal R$.


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

$\forall A \in \powerset S: A \subseteq \map {\paren {\mathcal R^\gets \circ \mathcal R^\to} } A$


Proof

Suppose $A \subseteq S$.

We have:

\(\displaystyle x\) \(\in\) \(\displaystyle A\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \set x\) \(\subseteq\) \(\displaystyle A\) Singleton of Element is Subset
\(\displaystyle \leadsto \ \ \) \(\displaystyle \mathcal R \sqbrk {\set x}\) \(\subseteq\) \(\displaystyle \mathcal R \sqbrk A\) Image of Subset under Relation is Subset of Image
\(\displaystyle \leadsto \ \ \) \(\displaystyle \mathcal R^{-1} \sqbrk {\mathcal R \sqbrk {\set x} }\) \(\subseteq\) \(\displaystyle \mathcal R^{-1} \sqbrk {\mathcal R \sqbrk A}\) Image of Subset under Relation is Subset of Image: Corollary 1
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\in\) \(\displaystyle \mathcal R^{-1} \sqbrk {\mathcal R \sqbrk A}\) Definition of Relation
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\in\) \(\displaystyle \paren {\mathcal R^{-1} \circ \mathcal R} \sqbrk A\) Definition of Composition of Relations

So by definition of subset:

$A \subseteq S \implies A \subseteq \paren {\mathcal R^{-1} \circ \mathcal R} \sqbrk A$

$\blacksquare$


Also see