Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

$\hspace{4cm} $ enter image description here

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.

share|improve this question
2  
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
1  
You might find helpful this post. –  Bill Dubuque Jul 6 '12 at 19:43

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.