Preimage of Image under Left-Total Relation is Superset
Jump to navigation
Jump to search
Theorem
Let $\RR \subseteq S \times T$ be a left-total relation.
Then:
- $A \subseteq S \implies A \subseteq \paren {\RR^{-1} \circ \RR} \sqbrk A$
where:
- $\RR \sqbrk A$ denotes the image of $A$ under $\RR$
- $\RR^{-1} \sqbrk A$ denotes the preimage of $A$ under $\RR$
- $\RR^{-1} \circ \RR$ denotes composition of $\RR^{-1}$ and $\RR$.
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 {\RR^\gets \circ \RR^\to} } A$
Proof
Suppose $A \subseteq S$.
We have:
| \(\ds x\) | \(\in\) | \(\ds A\) | ||||||||||||
| \(\ds \leadsto \ \ \) | \(\ds \set x\) | \(\subseteq\) | \(\ds A\) | Singleton of Element is Subset | ||||||||||
| \(\ds \leadsto \ \ \) | \(\ds \RR \sqbrk {\set x}\) | \(\subseteq\) | \(\ds \RR \sqbrk A\) | Image of Subset under Relation is Subset of Image | ||||||||||
| \(\ds \leadsto \ \ \) | \(\ds \RR^{-1} \sqbrk {\RR \sqbrk {\set x} }\) | \(\subseteq\) | \(\ds \RR^{-1} \sqbrk {\RR \sqbrk A}\) | Image of Subset under Relation is Subset of Image: Corollary 1 |
Then we have that $\RR$ is a left-total relation.
Thus:
- $\exists t \in T: \tuple {x, t} \in \RR$
Hence by definition of inverse relation:
- $\exists t \in T: \tuple {t, x} \in \RR^{-1}$
Hence:
| \(\ds \leadsto \ \ \) | \(\ds x\) | \(\in\) | \(\ds \RR^{-1} \sqbrk {\RR \sqbrk A}\) | Definition of Relation | ||||||||||
| \(\ds \leadsto \ \ \) | \(\ds x\) | \(\in\) | \(\ds \paren {\RR^{-1} \circ \RR} \sqbrk A\) | Definition of Composition of Relations |
So by definition of subset:
- $A \subseteq S \implies A \subseteq \paren {\RR^{-1} \circ \RR} \sqbrk A$
$\blacksquare$