Hey sapsapz
What does idB mean? Does it mean that g(f(x)) = x where x is in B?
Hi there,
I encountered a few questions I really have no idea how to even start approaching... Any help would be much appreaciated!
(id = identity)
Question 1:
prove that if f: A->B is a surjective (onto) function, then there exists a function g: B->A such that f composition g = idB
Question 2:
let f: A->B, g: A->B, h: B->A functions.
prove or disprove:
1. if h composition f = idA then f composition h = idB
2. if h composition f = idA and f is surjective (onto), then f composition h = idB
3. if h composition f = idA and h composition g = idA then g=f.
Thank you (:
I really dont know. Any other hints?
And how can you say that g is necessarily an onto function? If f: A->B is onto, then |A|>=|B|.
In order for g: B->A to be onto, it must be only equality and not greater or equal, right?
Are you talking about question 1? There may not be an onto function from B to A.
First, "f composition g" (g is applied first) is often denoted by , or "f o g" in plain text.
Suppose that one family had twin boys, Alex and Bill. On their birthday the parents planned a party and assigned to all the guests and family members one of the boys to give a present to (of course, not the same boy to every guest). But the boys knew what they wanted especially. Alex liked science, so he wanted a chemistry set. Bill liked sports, so he wanted baseball gear.They decided to each ask one of the guests to give them those gifts. Of course, they had to ask the right person, one who was supposed to give a gift to them personally and not to the other twin according to their parents' arrangement. They did not know the arrangement, but they hoped that Aunt Fiona, who knew everything, would find two appropriate people and relate the boys' requests to them. Will Aunt Fiona be able to do this? What if the number of twins exceeds the number of other people at the party?
Is this correct?
Let f: A->B be onto. We need to prove that exists g: B->A such that for all b in B, f o g (b) = b.
Let b1 be an arbitrary element of B.
f is onto, so there exists (at least one element called) a1 of A such that f(a1)=b1. Lets define g such that g(b1)=a1.
so f o g (b1) = f(g(b1))=f(a1)=b1.
b1 was arbitrary, and so it is true for all b in B. QED.
Dont I encounter a problem because two a elements might go to the same b? Or is it still ok because b is an arbitrary element?
For disproving stuff, counterexamples tend to work well. Try examples where . For instance, let and let . Define so that . Regardless of how they are defined, going from to , you are taking three elements and getting back two elements. So, going back from A to B, you are getting at most two elements of . In other words, for some element , . So, (1) is false.
For (2), let . You want to show that . Since is surjective, you know there exists such that . Additionally, you know that (since you know that composition gives the identity on ). So, . Now, you know what is. So, . Yes, (2) is true.
For (3), consider the same finite example I used in (1) with and . Suppose , , and . Now, suppose and .
As Plato said, you proof of the statement in Question 1 is fine, but this is a great question. In a proof, once you prove (or assume, or are given) the existence of an object, you are allowed to use such object, in particular, to construct other objects and prove other statements about existence. Here you are given that for a given b1 there exists an a1 such that f(a1) = b1. You need to prove the existence of g in the same sense as that of a1. So you are free to use a1 to build a g.
There is a subtlety when the set B is infinite. The rule of logic that allows using an individual object whose existence has been proved does not extend to the infinite case. That is, you can prove infinitely many statements about existence of objects (one for each element of B in this case), but to collect such objects in one structure (a function g) requires a stronger principle, the Axiom of Choice. This axiom is not a prerequisite to doing any mathematics, but it is usually accepted. In fact, the statement in Question 1 is equivalent to the Axiom of Choice. You probably don't have to worry about this in your course.
I am wondering, though, what in my explanation in post #6 made you go from "I really have no idea how to even start" to constructing a correct proof in post #8? What as it that you did not understand before?