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

In summary, for a function f: A → B, f is surjective if and only if there exists a function g: B → A such that fog=iB, where i is the identity function. This can be proven using the axiom of choice, where g is defined as g(y)=h(f-1[{y}]) and g is shown to be a right inverse for f. Conversely, if there exists a function g with fog(iB), then f is onto.
  • #1
AdrianZ
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.
 
Physics news on Phys.org
  • #2
Seems ok.
 

1. What does it mean for a function to be surjective?

A function is considered surjective if every element in the range of the function has at least one corresponding element in the domain. In other words, every output value is mapped to by at least one input value.

2. What is a right inverse of a function?

A right inverse of a function is another function that, when composed with the original function, results in the identity function. In other words, it "undoes" the original function, mapping each output value back to its corresponding input value.

3. How does the Axiom of Choice relate to this statement?

The Axiom of Choice is a mathematical axiom that states that, given a collection of non-empty sets, it is possible to choose one element from each set. In this statement, the Axiom of Choice is used to prove that a function being surjective is equivalent to having a right inverse.

4. Can you provide an example of a function that is surjective but does not have a right inverse?

Yes, consider the function f: R → R defined by f(x) = x2. This function is surjective, as every real number has a square root. However, it does not have a right inverse as it is not one-to-one (two different input values can result in the same output value).

5. Why is it important to prove this statement?

Proving that a function is surjective if and only if it has a right inverse is useful in many areas of mathematics, particularly in abstract algebra and functional analysis. It helps us understand the relationship between these two properties and provides a useful tool for solving problems involving surjectivity and right inverses.

Similar threads

  • Calculus and Beyond Homework Help
Replies
8
Views
347
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
151
  • Calculus and Beyond Homework Help
Replies
3
Views
637
  • Calculus and Beyond Homework Help
Replies
3
Views
466
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
717
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
761
Back
Top