Surjection iff Right Cancellable/Necessary Condition/Proof 1
Theorem
Let $f$ be a surjection.
Then $f$ is right cancellable.
Proof
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$
Sources
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): $\S 25$: Some further results and examples on mappings: Worked Example $1$