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→A such that f∘s=IB.
- If f is injective, then and only then there exists a mapping r:B→A such that r∘f=IA.
Proof
-
If f∘s=IB, then for any b∈B, f(s(b))=b. Therefore, f is surjective.
Let f:A→B be surjective. Define s(b) for b∈B such that s(b)∈f−1(b). By the Axiom of Choice, such s(b) can be defined. Then, for any b∈B, f(s(b))=b.
-
If r∘f=IA, then if f(a1)=f(a2) for any elements a1, a2 of A, it follows that a1=r(f(a1))=r(f(a2))=a2. Therefore, f is injective.
Let f:A→B be injective. For b∈B, if b∈f(A), there exists an element a∈A such that b=f(a). Define r using that a as r(b)=a. If b∉f(A), pick an element a0 from A and define r(b)=a0. Then, for any a∈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 φ:A→B, then by Theorem 2, a mapping ψ:B→A exists such that ψ∘φ=IA. ψ is surjective according to Theorem 1.
If there exists a surjective mapping ψ:B→A, then by Theorem 1, a mapping φ:A→B exists such that ψ∘φ=IA. φ is injective according to Theorem 2.