# Surjection iff Right Cancellable

Jump to navigation Jump to search

## Theorem

Let $f$ be a mapping.

Then $f$ is a surjection if and only if $f$ is right cancellable.

## Necessary Condition

### Proof 1

Let $f: X \to Y$ be surjective.

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

As $f$ is a surjection:

$\Img f = Y$

by definition.

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

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

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 \paren y = h_2 \paren y$.

So, let $y \in Y$.

As $f$ is surjective:

$\exists x \in X: y = f \paren x$

Thus:

 $\ds h_1 \paren y$ $=$ $\ds h_1 \paren {f \paren x}$ Definition of $y$ $\ds$ $=$ $\ds h_1 \circ f \paren x$ Definition of Composition of Mappings $\ds$ $=$ $\ds h_2 \circ f \paren x$ By Hypothesis $\ds$ $=$ $\ds h_2 \paren {f \paren x}$ Definition of Composition of Mappings $\ds$ $=$ $\ds h_2 \paren y$ Definition of $y$

Thus $h_1 \paren y = h_2 \paren y$ and thus $f$ is right cancellable.

$\blacksquare$

### Proof 2

Let $f: X \to Y$ be 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:

 $\ds h$ $=$ $\ds h \circ I_Y$ $\ds$ $=$ $\ds h \circ \paren {f \circ g}$ $\ds$ $=$ $\ds \paren {h \circ f} \circ g$ Composition of Mappings is Associative $\ds$ $=$ $\ds \paren {k \circ f} \circ g$ by hypothesis $\ds$ $=$ $\ds k \circ \paren {f \circ g}$ Composition of Mappings is Associative $\ds$ $=$ $\ds k \circ I_Y$ $\ds$ $=$ $\ds k$

Thus $f$ is right cancellable.

So surjectivity implies right cancellability.

$\blacksquare$

## Sufficient Condition

### 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$