Proof strategy for $(=>)$: If $g \circ f = id_A$, then f onto $\iff$ g 1-1. [Chartrand 3Ed P239 9.72]

Question

For nonempty sets A and B and functions f : A → B and g : B → A, suppose that $g \circ f =$ the identity function on A. $(♦)$

(d) $(=>)$ Assume that $f$ is onto. This means there exist $a_1, a_2\in A$ such that $f(a_1)=b_1$ and $f(a_2)=b_2$, , where $b_i\in B$

Suppose that $g(b_1)=g(b_2)$. Substitute $b_i$ with the above equations for $f(a_i)$: $ g(f(a_1))=g(f(a_2))$. By virtue of (♦), we have $a_1=a_2$.

What's the proof strategy? I'm not asking about the proofs, but they both look guileful and wily. For example, how would one determine when to apply $f$ or $g$? I realise that the proof leverages $(♦)$.

Answer 1

This is one of those cases where the proof strategy is just to write down your conclusion and your premise, and at every step just write down the first thing you can do with the tools you are given.

Always start by writing down the premise:

Suppose that $g \circ f = id$ and $f$ is onto.

We would like to show that $g$ is one-to-one, which means $g(a) = g(b) \implies a = b$. To show this, start with the premise:

Suppose that $b_1,b_2 \in B$ and $g(b_1) = g(b_2)$.

Now what? Well, there aren't very many possible options at this point as we only have a few symbols. We have some $b_1,b_2$ - what can we do with them? We have to use the premise somewhere, which is that $f$ is onto. Even if we don't see immediately how it's useful, there's only one thing we can say:

Since $f$ is onto, there exists $a_1,a_2 \in A$ with $f(a_1) = b_1$, $f(a_2) = b_2$.

What now? There's only one thing we know about $b_1,b_2$, and one thing we know about $a_1,a_2$, so put them together and rewrite what we have.

Then $g(f(a_1)) = g(f(a_2))$.

But then we're already finished.

But $g\circ f = id$, so $a_1 = g(f(a_1)$ and $a_2 = g(f(a_2)$, and so $a_1 = a_2$.

Tim Gowers has written some nice blog posts about this kind of proof. You don't have to be clever - just write down the premise and then keep writing down something you can do with the symbols you currently have according to what you know at that point. In my experience students mainly have trouble getting the logical form of the argument right rather than coming up with the individual steps.

Answer 2

This is not a real answer but more an alternative proof. If it is useless in this context then please let me know. In that case I will delete the answer.

If $g\circ f=id$ then $g$ is surjective since $g\left(f\left(a\right)\right)=a$ for each $a\in A$. So if $g$ is injective as well then it is bijective (i.e. isomorphic in the category of sets) and, as its inverse, $f$ is bijective too.

If $g\circ f=id$ then $f$ is injective since $f\left(a\right)=f\left(b\right)$ leads to $a=g\left(f\left(a\right)\right)=g\left(f\left(b\right)\right)=b$. So if $f$ is surjective as well then it is bijective (i.e. isomorphic in the category of sets) and, as its inverse, $g$ is bijective too.