1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove that f is surjective iff f has a right inverse. (Axiom of choice)

  1. Mar 16, 2012 #1
    1. The problem statement, all variables and given/known data
    Suppose f: A → B is a function. Show that f is surjective if and only if there exists g: B→A such that fog=iB, where i is the identity function.

    3. The attempt at a solution
    Well, I believe for a rigorous proof we need to use the axiom of choice, but because I have never worked with the axiom of choice before I need you guys to check if my proof is rigorous and correct.
    1) Assume that f is onto.
    Define the set ∏={f-1[{y}] : y ε B} (ε represents the membership relation). That means ∏ is the set of all pre-images of f restricted to the element y in B. It's obvious that ∏ is a family of sets and because its members are non-empty sets (since f is onto) we could apply the axiom of choice to it.
    Axiom of choice tells us that there exists a function h: ∏ → U∏. It's obvious that U∏=A.
    Now let's define: g:B → A , g(y)=h(f-1[{y}]). We should show that it's well-defined.
    Which means if y=z then g(y)=g(z), but it's obvious, since if y=z then y and z are the same element in B, hence f-1[{y}]=f-1[{z}], since h is a function (AC), h(f-1[{y}])=h(f-1[{z}]) which means g(y)=g(z).
    Now we need to prove that g is a right inverse for f.
    Well, let's see what fog does to an arbitrary element y in B. by definition, g(y)=h(f-1[{y}]), then fog(y)=f(h(f-1[{y}])). Now let's see what's happening when fog acts on y. first it gives us the set of pre-image of y, then h chooses one element in f-1[{y}], then f acts on it and it's again sent to y! That's it. It proves that fog(y)=y and since y was arbitrary we conclude that fog=iB.

    Now, suppose that there exists a function g such that fog(y)=y. We want to show that f is onto. For any y in B, we have: fog(y)=f(g(y))=y; now if we set g(y)=x we clearly see that for any y ε B, there exists x=g(y) such that f(x)=y which proves that f is onto.
  2. jcsd
  3. Mar 16, 2012 #2
    Seems ok.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook