Preimage of Image of Subset under Injection equals Subset

From ProofWiki
Jump to navigation Jump to search


Let $f: S \to T$ be an injection.


$\forall A \subseteq S: A = \paren {f^{-1} \circ f} \sqbrk A$


$f \sqbrk A$ denotes the image of $A$ under $f$
$f^{-1}$ denotes the inverse of $f$
$f^{-1} \circ f$ denotes composition of $f^{-1}$ and $f$.


Let $f$ be an injection.

From Subset of Domain is Subset of Preimage of Image, we have that:

$\forall A \subseteq S: A \subseteq \paren {f^{-1} \circ f} \sqbrk A$

by dint of $f$ being a relation.

So what we need to do is show that:

$\forall A \subseteq S: \paren {f^{-1} \circ f} \sqbrk A \subseteq A$

Take any $A \subseteq S$.

Let $x \in A$.

We have:

\(\displaystyle x\) \(\in\) \(\displaystyle \paren {f^{-1} \circ f} \sqbrk A\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\in\) \(\displaystyle f^{-1} \sqbrk {f \sqbrk A}\) Definition of Composition of Mappings
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f x\) \(\in\) \(\displaystyle f \sqbrk A\) Definition of Inverse of Mapping
\(\displaystyle \leadsto \ \ \) \(\displaystyle \exists y \in A: \ \ \) \(\displaystyle \map f x\) \(=\) \(\displaystyle \map f y\) Definition of Image of Subset under Mapping
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(=\) \(\displaystyle y\) Definition of Injection
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\in\) \(\displaystyle A\) as $y \in A$

Thus we see that:

$\paren {f^{-1} \circ f} \sqbrk A \subseteq A$

and hence the result:

$\forall A \subseteq S: A = \paren {f^{-1} \circ f} \sqbrk A$


Also see