Surjection iff Right Cancellable/Sufficient Condition

Theorem

Let $f$ be a mapping which is right cancellable.

Then $f$ is a surjection.

Proof 1

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

Then:

$\exists y_1 \in Y: \neg \exists x \in X: \map f x = y_1$

Let $Z = \set {a, b}$.

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

$\map {h_1} y = a: y \in Y$

$\map {h_2} y = \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$.

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

Let $f: X \to Y$ be a right cancellable mapping.

Let $Y$ contain exactly one element.

Then by definition $Y$ is a singleton.

From Mapping to Singleton is Surjection it follows that $f$ is a surjection.

So let $Y$ contain 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: \map h x = \begin{cases}

x & : x \in \Img f \\ a & : x \notin \Img f \end{cases}$

$k: Y \to Y: \forall x \in Y: \map k x = \begin{cases}

x & : x \in \Img f \\ b & : x \notin \Img f \end{cases}$

It is clear that:

$\forall y \in X: \map h {\map f y} = \map f y = \map k {\map f y}$

and so:

$h \circ f = k \circ f$

But by hypothesis, $f$ is right cancellable.

Thus $h = k$.

Aiming for a contradiction, suppose $Y \ne \Img f$.

Then:

$\Img f \subsetneq Y$

That is:

$\exists x \in Y: x \notin \Img f$

It follows that:

$a = \map h x = \map k x = b$

But we posited that $a \ne b$.

From this contradiction we conclude that:

$Y = \Img f$

So, by definition, $f$ must be a surjection.

$\blacksquare$