My proof of the link between the injectivity and the existence of left inverse looks exactly like this one:

The "hard" part is that we just pick elements at random and construct our inverse based on them.

The proof of the link between surjectivity and the exitence of right inverse may be done in similar way. The hard part again is that you have to pick at random one from the pontentialy many fibers of each element.

Is there a way to prove this without having to pick elements at random?