Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Abstract algebra proof: composition of mappings

  1. Sep 29, 2005 #1
    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.


    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.

    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.
  2. jcsd
  3. Sep 29, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    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 [itex]B(s) \in A^{-1}(\{s\})[/itex]. 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[itex]\pi[/itex] : k in Z}. You have many choices for B(0), i.e. the B(0) = 2k[itex]\pi[/itex] 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook