Let $f:A \to B$ be a function between sets. > [!proposition]+ Proposition. ([[characterization of injectivity and surjectivity in Set]]) > The following are equivalent: > 1. $f$ is an [[injection]]; > 2. $f$ has a [[inverse map|left-inverse]]; > 3. $f$ is a [[monomorphism]]. > > The following are equivalent: > 1. $f$ is [[surjection]]; > 2. $f$ has a [[inverse map|right-inverse]]; > 3. $f$ is an [[epimorphism]]. ^proposition > [!proof]+ Proof. ([[characterization of injectivity and surjectivity in Set]]) > That $1 \iff 2$ in each case is already shown [[inverse map#^equivalence|here]]. Thus we stick to showing $1 \iff 3$ (using that $1 \iff 2$ as needed). > > **Monomorphism $\iff$ injection.** > $\to.$ Suppose $f$ is a [[monomorphism]]. Let $f(a')$, $f(a'')$ in $B$ such that $f(a')=f(a'')$. Let $Z=\{ p \}$ and define $\alpha':Z \to A$ as $p \mapsto a'$. Likewise define $\alpha'':Z \to A$ as $p \mapsto a''$. Since $f \circ \alpha' \equiv f(a')$, $f \circ \alpha'' \equiv f(a'')$, and $f(a')=f(a'')$, we conclude by monomorphism definition that $\alpha'=\alpha''$. It follows that $a'=a''$. > > $\leftarrow.$ Suppose $f$ is an [[injection]]; let $g$ be a [[inverse map|left-inverse]], $g \circ f = \id_{A}$. Let $Z$ and $\alpha', \alpha'':Z \to A$ be arbitrary. Suppose $f \circ \alpha'=f \circ \alpha''$. Then $g \circ (f \circ \alpha') = g \circ (f \circ \alpha'')$ > which, exploiting [[associative|associativity]] of function composition, entails $\alpha'=\alpha''$. > > **Epimorphism $\iff$ Surjection.** > $\to.$ Suppose $f: A \to B$ is an [[epimorphism]], but not a [[surjection]]. Then there exists $b' \in B$ such that $f(a) \neq b'$ for all $a \in A$. Thus if we let $Z$ be the two-point set $\{ x,y \}$ and define $\alpha',\alpha'':B \to Z$ to be equal with the exception that $\alpha'(b'):=x$ and $\alpha''(b')=y$, it will be the case that $\alpha' \circ f(a)=\alpha'' \circ f(a)$ despite the fact that $\alpha' \neq \alpha''$. > > $\leftarrow$. Suppose $f:A \to B$ is a [[surjection]]; let $g:B \to A$ be a [[inverse map|right-inverse]], $f \circ g = \id_{B}$. Suppose $\alpha' \circ f = \alpha'' \circ f$. Then $\alpha' \circ (f \circ g) = \alpha'' \circ (f \circ g)=\alpha' \iff \alpha' \circ \id = \alpha'' \circ \id$ > and hence $\alpha'=\alpha''$. ^proof #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags > GROUP BY file.tags as Tag > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags > GROUP BY file.tags as Tag #reformatrevisebatch02