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

  • Thread starter AdrianZ
  • Start date
  • #1
319
0

Homework Statement


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.


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.
 

Answers and Replies

  • #2
22,089
3,286
Seems ok.
 

Related Threads on Prove that f is surjective iff f has a right inverse. (Axiom of choice)

Replies
1
Views
713
Replies
8
Views
6K
  • Last Post
Replies
5
Views
1K
Replies
0
Views
1K
  • Last Post
Replies
7
Views
1K
Replies
3
Views
860
Replies
4
Views
5K
  • Last Post
Replies
1
Views
739
Top