Surjection iff Right Cancellable

Theorem

A mapping $f$ is a surjection iff $f$ is right cancellable.

Proof 1

Sufficient Condition

Suppose $f: X \to Y$ is surjective.

Suppose $h_1: Y \to Z, h_2: Y \to Z: h_1 \circ f = h_2 \circ f$.

As $f$ is a surjection, $\operatorname{Im} \left({f}\right) = Y$ by definition.

But in order for $h_1 \circ f$ to be defined, it is necessary that $Y = \operatorname{Dom} \left({h_1}\right)$.

Similarly, for $h_2 \circ f$ to be defined, it is necessary that $Y = \operatorname{Dom} \left({h_2}\right)$.

So it follows that the domains of $h_1$ and $h_2$ are the same.

Also:

• The codomain of $h_1$ equals the codomain of $h_1 \circ f$
• The codomain of $h_2$ equals the codomain of $h_2 \circ f$

again by definition of composition of mappings.

Now, we have shown that the domains and codomains of $h_1$ and $h_2$ are the same.

All we need to do now to prove that $h_1 = h_2$, and therefore that $f$ is right cancellable, is to show that:

$\forall y \in Y: h_1 \left({y}\right) = h_2 \left({y}\right)$.

So, let $y \in Y$.

As $f$ is surjective, $\exists x \in X: y = f \left({x}\right)$. Thus:

	\(\displaystyle \)	\(\displaystyle h_1 \left({y}\right)\)	\(=\)	\(\displaystyle h_1 \left({f \left({x}\right)}\right)\)	\(\displaystyle \)	(definition of $y$)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle h_1 \circ f \left({x}\right)\)	\(\displaystyle \)	Definition of Composite
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle h_2 \circ f \left({x}\right)\)	\(\displaystyle \)	By Hypothesis
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle h_2 \left({f \left({x}\right)}\right)\)	\(\displaystyle \)	Definition of Composite
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle h_2 \left({y}\right)\)	\(\displaystyle \)	(definition of $y$)

Thus $h_1 \left({y}\right) = h_2 \left({y}\right)$ and thus $f$ is right cancellable.

$\Box$

Necessary Condition

Suppose $f$ is a mapping which is not surjective.

Then $\exists y_1 \in Y: \neg \exists x \in X: f \left({x}\right) = y_1$.

Let $Z = \left\{{a, b}\right\}$.

Let $h_1$ and $h_2$ be defined as follows.

• $h_1 \left({y}\right) = a: y \in Y$

• $h_2 \left({y}\right) = \begin{cases} a & : y \ne y_1 \\ b & : y = y_1 \end{cases}$

Thus we have $h_1 \ne h_2$ such that $h_1 \circ f = h_2 \circ f$, and therefore $f$ is not right cancellable.

It follows from the Rule of Transposition that if $f$ is right cancellable, then $f$ must be surjective.

$\blacksquare$

Proof 2

Sufficient Condition

Suppose $f: X \to Y$ is surjective.

Then from Surjection iff Right Inverse:

$\exists g: Y \to X: f \circ g = I_Y$

Suppose $h \circ f = k \circ f$ for two mappings $h: Y \to Z$ and $k: Y \to Z$.

Then:

	\(\displaystyle \)	\(\displaystyle h\)	\(=\)	\(\displaystyle h \circ I_Y\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle h \circ \left({f \circ g}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({h \circ f}\right) \circ g\)	\(\displaystyle \)	Composition of Mappings Associative
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({k \circ f}\right) \circ g\)	\(\displaystyle \)	by hypothesis
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle k \circ \left({f \circ g}\right)\)	\(\displaystyle \)	Composition of Mappings Associative
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle k \circ I_Y\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle k\)	\(\displaystyle \)

Thus $f$ is right cancellable.

So surjectivity implies right cancellability.

$\Box$

Necessary Condition

Now suppose $f: X \to Y$ is a right cancellable mapping.

If $Y$ contains only one element, then by definition $Y$ is a singleton and it automatically follows from Mapping to Singleton is Surjection that $f$ is a surjection.

So we suppose that $Y$ contains at least two elements.

Call those two elements $a$ and $b$, and we note that $a \ne b$.

We define the two mappings $h, k$ as follows:

$h: Y \to Y: \forall x \in Y: h \left({x}\right) = \begin{cases} x & : x \in \operatorname{Im} \left({f}\right) \\ a & : x \notin \operatorname{Im} \left({f}\right) \end{cases}$

$k: Y \to Y: \forall x \in Y: k \left({x}\right) = \begin{cases} x & : x \in \operatorname{Im} \left({f}\right) \\ b & : x \notin \operatorname{Im} \left({f}\right) \end{cases}$

It is clear that:

$\forall y \in X: h \left({f \left({y}\right)}\right) = f \left({y}\right) = k \left({f \left({y}\right)}\right)$

and so $h \circ f = k \circ f$.

But by hypothesis, $f$ is right cancellable.

Thus $h = k$.

Now, suppose $Y \ne \operatorname{Im} \left({f}\right)$, and so $\operatorname{Im} \left({f}\right) \subset Y$.

That is, $\exists x \in Y: x \notin \operatorname{Im} \left({f}\right)$.

It follows that $a = h \left({x}\right) = k \left({x}\right) = b$.

But we posited that $a \ne b$.

From this contradiction we conclude that $Y = \operatorname{Im} \left({f}\right)$

So, by Surjection iff Image equals Codomain, $f$ must be a surjection.

$\blacksquare$

Also see

• Injection iff Left Cancellable

Sources

• 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.6$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 25$: Worked Example $1$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): Exercise $4.16$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.5$: Proposition $\text{A}.5.1: 2 \ \text{(e)}$