Abstract algebra proof: composition of mappings

[calvino]

define right-inverse of a mapping B to be mapping A, such that B * A= identity (iota). Where the operation * is composition. Note that B is A's left-inverse.

QUESTION:

Assume S is a nonempty set and that A is an element of M(S) -the set of all mappings S->S.

a) Prove A has a left inverse relative to * iff A is one-one
b) Prove that A has a right inverse relative to * iff A is onto.


ANSWER:
I answered a) to the best of my ability, using firstly a theorem that states (B*A is 1-1) -> A is 1-1. Then, I simply constructed B from A (since A is 1-1) to prove the converse.

b) on the other hand, i found a little harder. Once again, i used a theorem that said A*B is onto -> A is onto. Now, though, I can't seem to prove the converse. The question is, how can i construct B, knowing only that A is onto? any help would be greatly appreciated.

 

[AKG]

B will not be unique. For any s in S, define A^-1({s}) as {s' in S : A(s') = s}. Pick a mapping B that satisfies $B(s) \in A^{-1}(\{s\})$. Then A*B(s) = A(x) for some x in A^-1({s}) = {s' in S : A(s') = s}. So x is some element of S whose image under A is s, so A(x) = s, as desired. Some examples:

1) A is also 1-1. Well in this case, |A^-1({s})| = 1 for every s in S, so B is unique. You would denote the unique element of A^-1({s}) simply as A^-1(s).

2) S = R, A(x) = xsin(x). Then A^-1({0}) = {2k$\pi$ : k in Z}. You have many choices for B(0), i.e. the B(0) = 2k$\pi$ is a valid choice for each different k in Z. And you'll have many available choices for B(x) for each x in R. In this case, you can choose B(x) to be the smallest non-negative element of A^-1({x}). You could check that this is a well-defined choice (that A^-1({x}) does have a smallest non-negative element, unlike the set {1, 1/2, 1/3, 1/4, 1/5, ...}) but that would probably not be directly related to what you're studying.

In general, however, A might be some very messy, unnatural function, and there may be no obvious or generalizable choice for B(x), but it's hard for me to give you an example because for A to be onto but not 1-1, S must be infinite, and for me to define a function A on an infinite set is only reasonably possible when A is not messy. If it followed no obvious rule, then I'd just have to list all the pairs (x, A(x)) and I couldn't possibly do that.