Table of Contents
Let’s introduce a fundamental theorem regarding the existence of mappings that create identity mappings.
Theorem
Let \(f\) be a mapping from \(A\) to \(B\).
- If \(f\) is surjective, then and only then there exists a mapping \(s: B \rightarrow A\) such that \(f \circ s = I_B\).
- If \(f\) is injective, then and only then there exists a mapping \(r: B \rightarrow A\) such that \(r \circ f = I_A\).
Proof
-
If \(f \circ s = I_B\), then for any \(b \in B\), \(f(s(b)) = b\). Therefore, \(f\) is surjective.
Let \(f: A \rightarrow B\) be surjective. Define \(s(b)\) for \(b \in B\) such that \(s(b) \in f^{-1}(b)\). By the Axiom of Choice, such \(s(b)\) can be defined. Then, for any \(b \in B\), \(f(s(b)) = b\).
-
If \(r \circ f = I_A\), then if \(f(a_1) = f(a_2)\) for any elements \(a_1\), \(a_2\) of \(A\), it follows that \(a_1 = r(f(a_1)) = r(f(a_2)) = a_2\). Therefore, \(f\) is injective.
Let \(f: A \rightarrow B\) be injective. For \(b \in B\), if \(b \in f(A)\), there exists an element \(a \in A\) such that \(b = f(a)\). Define \(r\) using that \(a\) as \(r(b) = a\). If \(b \not\in f(A)\), pick an element \(a_0\) from \(A\) and define \(r(b) = a_0\). Then, for any \(a \in A\), \(r(f(a)) = a\).
Corollary
Let \(A\) and \(B\) be two sets. The necessary and sufficient condition for the existence of an injective mapping from \(A\) to \(B\) is the existence of a surjective mapping from \(B\) to \(A\).
Proof
If there exists an injective mapping \(\varphi: A \rightarrow B\), then by Theorem 2, a mapping \(\psi: B \rightarrow A\) exists such that \(\psi \circ \varphi = I_A\). \(\psi\) is surjective according to Theorem 1.
If there exists a surjective mapping \(\psi: B \rightarrow A\), then by Theorem 1, a mapping \(\varphi: A \rightarrow B\) exists such that \(\psi \circ \varphi = I_A\). \(\varphi\) is injective according to Theorem 2.