Preimage of Image of Injection

Theorem

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

Let $f_g: \mathcal P \left({S}\right) \to \mathcal P \left({T}\right)$ be the mapping induced by $g$.

Similarly, Let $f_{g^{-1}}: \mathcal P \left({T}\right) \to \mathcal P \left({S}\right)$ be the mapping induced by the inverse $g^{-1}$.

Then:

$\forall A \in \mathcal P \left({S}\right): A = \left({f_{g^{-1}} \circ f_g}\right) \left({A}\right)$

iff $f$ is an injection.

Proof

Sufficient Condition

Let $f$ be such that:

$\forall A \in \mathcal P \left({S}\right): A = \left({f_{g^{-1}} \circ f_g}\right) \left({A}\right)$

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

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

We have:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle f \left({x}\right) = f \left({y}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle f_g \left({\left\{ {x}\right\} }\right) = \left\{ {f \left({x}\right)}\right\} = \left\{ {f \left({y}\right)}\right\} = f_g \left({\left\{ {y}\right\} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition of induced mapping
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \left\{ {x}\right\} = f_{g^{-1} } \left({f_g \left({\left\{ {x}\right\} }\right)}\right) = f_{g^{-1} } \left({f_g \left({\left\{ {y}\right\} }\right)}\right) = \left\{ {y}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by hypothesis: $A = \left({f_{g^{-1} } \circ f_g}\right) \left({A}\right)$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle x = y\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

So $f$ is an injection.

$\Box$

Necessary Condition

Let $f$ be an injection.

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

$\forall A \in \mathcal P \left({S}\right): A \subseteq \left({f_{g^{-1}} \circ f_g}\right) \left({A}\right)$

by dint of $f$ being a relation.

So what we need to do is show that:

$\forall A \in \mathcal P \left({S}\right): \left({f_{g^{-1}} \circ f_g}\right) \left({A}\right) \subseteq A$

Take any $A \in \mathcal P \left({S}\right)$.

Let $x \in A$.

We have:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle f \left({x}\right)\)	\(\in\)	\(\displaystyle f_g \left({A}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \exists y \in A: f \left({x}\right)\)	\(=\)	\(\displaystyle f \left({y}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle x\)	\(=\)	\(\displaystyle y \in A\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Thus we see that:

$\left({f_{g^{-1}} \circ f_g}\right) \left({A}\right) \subseteq A$

and hence the result:

$\forall A \in \mathcal P \left({S}\right): A = \left({f_{g^{-1}} \circ f_g}\right) \left({A}\right)$

$\blacksquare$

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 10$: Inverses and Composites
• T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 5$: Theorem $5.8$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.5$: Proposition $\text{A}.5.1: \ 1 \ \text{(c)}$