Injection iff Left Cancellable

Theorem

A mapping $f$ is an injection iff $f$ is left cancellable.

Proof

From the definition: a mapping $f: Y \to Z$ is left cancellable if:

$\forall X: \forall g_1: X \to Y, g_2: X \to Y: f \circ g_1 = f \circ g_2 \implies g_1 = g_2$

• Suppose $f: Y \to Z$ is injective.

Suppose $g_1: X \to Y, g_2: X \to Y: f \circ g_1 = f \circ g_2$.

Then $\forall x \in X$:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle f \left({g_1 \left({x}\right)}\right)\)	\(=\)	\(\displaystyle f \circ g_1 \left({x}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Composite Mapping
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle f \circ g_2 \left({x}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	By Hypothesis
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle f \left({g_2 \left({x}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Composite Mapping

Thus as $f$ is an injection, $g_1 \left({x}\right) = g_2 \left({x}\right)$ and thus the condition for left cancellability holds.

• Suppose $f: Y \to Z$ is not injective.

Then $\exists y_1 \ne y_2 \in Y: f \left({y_1}\right) = f \left({y_2}\right)$.

For $f$ to be left cancellable, the condition $f \circ g_1 = f \circ g_2 \implies g_1 = g_2$ needs to apply to all mappings $g_1$ and $g_2$, whatever they are. So if we can always create two mappings $g_1$ and $g_2$ such that this condition does not hold, we have proved the supposition.

So, let us create these mappings on the domain $X = Y$.

Let the two mappings $g_1: X \to Y, g_2: X \to Y$ be defined as follows:

$g_1 \left({y}\right) = y: y \in X$

$g_2 \left({y}\right) = \begin{cases} y_2 & : y = y_1 \\ y & : y \ne y_1 \end{cases}$

So, for an arbitrary non-injective mapping $f$, we have created two unequal functions $g_1$ and $g_2$ both of which fulfil the conditions, and therefore $f$ is not left cancellable.

The result follows.

$\blacksquare$

Also see

• Surjection iff Right Cancellable

Sources

• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $8.10$
• George McCarty: Topology: An Introduction with Application to Topological Groups (1967): $\text{I}$: Problem $\text{BB}$
• Ian D. Macdonald: The Theory of Groups (1968): Appendix
• T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 5$: Theorem $5.4$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): Exercise $4.14$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.5$: Proposition $\text{A}.5.1: 1 \ \text{(d)}$