# If the diagram is commutative, $f$ is one-one and $g$ is onto.

Let $f:A \to B$ , $g:B \to A$, and $\operatorname{id}:A \to A$ be the identity. If the diagram

$\hspace{4cm}$

commutes, prove that ${ f}$ is one-one and ${ g}$ is onto.

THEOREM If the diagram above commutes, then $f$ is one-one and $g$ is onto.

PROOF The commutativity of the diagram implies that

$${g f}(x)=x \;; \forall x\in A$$

thus $gf$ is one-one and onto.

$(1)$ $f$ is one-one. Assume that ${ f}(x)={ f}(y)$.Then

$${ f}(x)={ f}(y)$$

$${ gf}(x)={ gf}(y)$$

$$x=y$$

so that ${ f}$ is one-one.

$(2)$ $g$ is onto. If it wasn't the case $gf$ wouldn't be onto, which is impossible.

I don't know wether the last "proof" is right. I can see why it must be the case but I'm not able to exlain it and give a clear proof like that of $f$ being one-one which seems very clear.

-
An absolutely watertight way to prove that $g$ is onto to take $a\in A$, and show that there is a $b\in B$ for which $g(b)=a$, and this should not be hard to find ... –  Old John Jul 6 '12 at 19:33
For sure, $f(A)\subseteq B$. –  Sigur Jul 6 '12 at 19:37
@Sigur Sorry, yes. I was overthinking it too much! –  Pedro Tamaroff Jul 6 '12 at 19:38
Start with $a\in A$ (on the right of the diagram). Then pull back to $a\in A$ on the left of the diagram. Then apply $f$ to this element $a$, –  Old John Jul 6 '12 at 19:38
You might find helpful this post. –  Bill Dubuque Jul 6 '12 at 19:43

Theorem. Let $A$ and $B$ be sets. Consider the following three statements:

1. $f\colon A\to B$ is one-to-one.
2. There exists $g\colon B\to A$ such that $gf = \mathrm{id}_A$ ($f$ has a left inverse).
3. For every set $C$ and every functions $h,k\colon C\to A$, if $fh = fk$ then $h=k$ ($f$ is left-cancellable).

Then 2$\implies$3$\iff$1. Moreover, if $A$ is nonempty, then 1$\implies$2 so all three are equivalent.

Proof. 2$\implies$3. Let $h,k\colon C\to A$ be such that $fh = fk$. Let $g$ be the function guaranteed by 2. Then $$h = \mathrm{id}_Ah = (gf)h = g(fh) = g(fk) = (gf)k = \mathrm{id}_Ak = k.$$ Thus, $f$ is left-cancellable.

3$\implies$1. Let $a,a'\in A$ be such that $f(a)=f(a')$. We need to prove that $a=a'$. Let $C=\{0\}$, $h\colon C\to A$ be given by $h(0)=a$, and $k\colon C\to A$ be given by $k(0)=a'$. Then $fh(0) = f(a) = f(a') = fk(0)$. so $fh=fk$. Since $f$ is left-cancellable, we conclude that $h=k$. Hence $a = h(0) = k(0) = a'$, proving that $f$ is one-to-one.

1$\implies$3. Let $C$ be a set and $h,k\colon C\to A$ be such that $fh = fk$. We need to show that $h=k$. Let $c\in C$. Then $f(h(c)) = f(k(c))$; since $f$ is one-to-one, we conclude that $h(c)=k(c)$. Since $h(c)=k(c)$ for all $c\in C$, it follows that $h=k$.

1$\implies$2 if $A$ is nonempty and $B$ are nonempty. Since $A$ is nonempty, there exists $a_0\in A$. Define $g\colon B\to A$ as follows: $$g(b) = \left\{\begin{array}{ll} a &\text{if }b\in f(A)\text{ and }f(a)=b;\\ a_0&\text{if }b\notin f(A). \end{array}\right.$$ This is well-defined, since $f(a)=f(a')=b$ implies $a=a'$. And if $b\in f(A)$, then there exists $a\in A$ such that $f(a)=b$. Now, let $a\in A$. Then $g(f(a)) = a$, so $gf = \mathrm{id}_A$, as desired. $\Box$

In particular, given a function $f\colon A\to B$, if a $g$ exists that makes the diagram commute, then $f$ is one-to-one. Conversely, if $f$ is one-to-one and $A$ is nonempty (or $A$ and $B$ are both empty), then we can find a $g$ that makes the diagram commute.

Here's the dual:

Theorem. Let $A$ and $B$ be sets. Consider the following three statements:

1. $f\colon A\to B$ is onto.
2. There exists $g\colon B\to A$ such that $fg=\mathrm{id}_B$ ($f$ has a right inverse).
3. For every set $C$ and every functions $h,k\colon B\to C$, if $hf = kf$, then $h=k$ ($f$ is right-cancellable).

Then 2$\implies$3$\iff$1. Moreover, the implication 1$\implies$2 is equivalent to the Axiom of Choice.

Proof. 2$\implies$3 Let $C$ be a set and let $h,k\colon B\to C$ be such that $hf=kf$. Let $g$ be the function guaranteed by 2; then: $$h = h\mathrm{id}_B = h(fg) = (hf)g =(kf)g = k(fg) = k\mathrm{id}_B = k.$$

3$\implies$1. Let $C=\{0,1\}$ and define $h\colon B\to C$ by $h(b)=1$ for all $b$, and $$k(b) = \left\{\begin{array}{ll} 1 & \text{if }b\in f(A);\\ 0 &\text{if }b\notin f(A). \end{array}\right.$$ Then $hf = kf$, hence by 3 we have $h=k$. Therefore, $k(b)=1$ for all $b\in B$, hence $f(A)=B$; that is, $f$ is onto.

1$\implies$3. Suppose that $C$ is a set and $h,k\colon B\to C$ are functions such that $hf = kf$. Let $b\in B$; we need to show $h(b)=k(b)$. Since $f$ is onto, there exists $a\in A$ such that $f(a)=b$. Therefore, $$h(b) = h(f(a)) = hf(a) = kf(a) = k(b).$$ Thus, $h=k$.

If the Axiom of Choice holds, then 1$\implies$2: If $f$ is onto, then for every $b\in B$, the set $f^{-1}(b) = \{a\in A\mid f(a)=b\}$ is nonempty. By the Axiom of choice, there exists a function $g\colon B\to \cup_{b\in B} f^{-1}(b)$ such that $g(b)\in f^{-1}(b)$ for each $b\in B$. I claim that $fg=\mathrm{id}_B$. Indeed, for every $b\in B$, $g(b)\in f^{-1}(b)$, so $f(g(b))=b$.

If 1$\implies$2 holds, then the Axiom of Choice holds. Let $\mathcal{X}=\{A_i\}_{i\in I}$ be a nonempty family ($I\neq\varnothing$) of nonempty sets ($A_i\neq\varnothing$ for each $I\in I$). We need to show that there exists a function $g\colon I\to\cup_{i\in I}A_i$ such that $g(i)\in A_i$ for each $i\in I$.

Let $B_i = A_i\times\{i\}$. Note that the family $\mathcal{Y}=\{B_i\}_{i\in I}$ consists of pairwise distinct sets. Let $Y=\cup_{i\in I}B_i$, an define $f\colon Y\to I$ by $f(b_i,i) = i$ (projection onto the second component). The map is onto, since each $A_i$ is nonempty, so $B_i\neq\varnothing$. By our assumption that 1$\implies$2, there exists $h\colon I\to Y$ such that $h(i)\in B_i$ for each $i\in I$. Let $\pi_i\colon B_i\to A_i$ be the projection onto the first coordinate, $\pi_i(b_i,i) = b_i$. Define $g\colon I\to \cup_{i\in I}A_i$ by $$g(i) = \pi_i\circ h (i).$$ Since $h(i)\in B_i=A_i\times\{i\}$, then $\pi_i\circ h(i) \in A_i$. This holds for each $i$, so $g$ is the desired choice function. $\Box$

In particular, if the diagram commutes, then $g$ is onto. Conversely, assuming the axiom of choice, if $g$ is onto, then we can find an $f$ that fits into the diagram and makes it commute.

-
Thank you so much! I'll read this with some more time. –  Pedro Tamaroff Jul 6 '12 at 21:03
I'm reading this now, as promised. Thank you again, Arturo. –  Pedro Tamaroff Jul 23 '12 at 2:30
$fg=\operatorname{id}_A$ should read $fg=\operatorname{id}_B$, correct? –  Pedro Tamaroff Jul 23 '12 at 2:36
Also $(hf)g=(kf)g=k(fh)$ should read $(hf)g=(kf)g=k(fg)$-. The Axiom of Choice part is still fuzzy, but that is my fault. –  Pedro Tamaroff Jul 23 '12 at 3:00
@Peter: Yes on the first two; fixed. –  Arturo Magidin Jul 23 '12 at 4:05

For $a\in A$, take $b=f(a)\in B$ such that $g(b)=g(f(a))=a$.

-