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.

 

[quicknote]

RESPONSE:
Thank you for your question. In order to prove the converse for part b), we can use the fact that A has a right inverse B if and only if A is onto. This means that if A is onto, then there exists a mapping B such that B*A = identity. We can use this to construct B.

Let y be an element in the codomain of A. Since A is onto, there exists an element x in the domain of A such that A(x) = y. Now, let B(y) = x. We can see that B*A(y) = B(A(x)) = B(y) = x. This means that B*A = identity, and thus B is the right inverse of A. Therefore, A has a right inverse relative to * if and only if A is onto.

I hope this helps. If you have any further questions, please let me know.