Subset equals Preimage of Image implies Injection

From ProofWiki
Jump to navigation Jump to search


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$.


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

Then $f$ is an injection.

Proof 1

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:

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

So $f$ is an injection.


Proof 2

Suppose that $f$ is not an injection.

Then two elements of $S$ map to the same one element of $T$.

That is:

$\exists a_1, a_2 \in S, b \in T: \map f {a_1} = \map f {a_2} = b$

Let $A = \set {a_1}$.


\(\displaystyle \map {f^\to} A\) \(=\) \(\displaystyle \set b\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map {f^\gets} {\map {f^\to} A}\) \(\supseteq\) \(\displaystyle \set {a_1, a_2}\) Definition of Preimage of Subset under Mapping
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map {f^\gets} {\map {f^\to} A}\) \(\supsetneqq\) \(\displaystyle A\) as $A = \set {a_1}$

So by the Rule of Transposition:

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

implies that $f$ is an injection.


Also see