Surjection iff Right Cancellable
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$
Also see
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets: Exercise $8.10 \ \text{(a)}$
- 1967: George McCarty: Topology: An Introduction with Application to Topological Groups ... (previous) ... (next): Chapter $\text{I}$: Sets and Functions: Problem $\text{BB}$: Categorical Matters
- 1968: Ian D. Macdonald: The Theory of Groups ... (previous) ... (next): Appendix: Elementary set and number theory
- 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability ... (previous) ... (next): Appendix $\text{A}.5$: Identity, One-one, and Onto Functions: Proposition $\text{A}.5.1: 2 \ \text{(e)}$