Subset equals Preimage of Image implies Injection/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $f: S \to T$ be a mapping.

Let $f^\to: \powerset S \to \powerset T$ be the direct image mapping of $f$.

Similarly, let $f^\gets: \powerset T \to \powerset S$ be the inverse image mapping of $f$.


Let:

$\forall A \in \powerset S: A = \map {\paren {f^\gets \circ f^\to} } A$

Then $f$ is an injection.


Proof

Let $f$ be such that:

$\forall A \in \powerset S: A = \map {\paren {f^\gets \circ f^\to} } A$

In particular, it holds for all subsets of $A$ which are singletons.


Now, consider any $x, y \in A$.

We have:

\(\ds \map f x\) \(=\) \(\ds \map f y\)
\(\ds \leadsto \ \ \) \(\ds \set {\map f x}\) \(=\) \(\ds \set {\map f y}\)
\(\ds \leadsto \ \ \) \(\ds \map {f^\to} {\set x}\) \(=\) \(\ds \map {f^\to} {\set y}\) Definition of Direct Image Mapping of Mapping
\(\ds \leadsto \ \ \) \(\ds \set x\) \(=\) \(\ds \map {f^\gets} {\map {f^\to} {\set x} }\) by hypothesis: $A = \map {\paren {f^\gets \circ f^\to} } A$
\(\ds \) \(=\) \(\ds \map {f^\gets} {\map {f^\to} {\set y} }\)
\(\ds \) \(=\) \(\ds \set y\) by hypothesis: $A = \map {\paren {f^\gets \circ f^\to} } A$
\(\ds \leadsto \ \ \) \(\ds x\) \(=\) \(\ds y\)

So $f$ is an injection.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Subset_equals_Preimage_of_Image_implies_Injection/Proof_1&oldid=417552"