Surjection iff Right Cancellable/Necessary Condition

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $f$ be a surjection.


Then $f$ is right cancellable.


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$

Retrieved from "https://proofwiki.org/w/index.php?title=Surjection_iff_Right_Cancellable/Necessary_Condition&oldid=268465"