1. ## A few questions about functions

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 (:

2. ## Re: A few questions about functions

Hey sapsapz

What does idB mean? Does it mean that g(f(x)) = x where x is in B?

3. ## Re: A few questions about functions

Yeah, exactly

4. ## Re: A few questions about functions

Hint: Let g be a function that is also onto: what does that imply about the bi-jectivity between f and g?

5. ## Re: A few questions about functions

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?

6. ## Re: A few questions about functions

Originally Posted by chiro
Hint: Let g be a function that is also onto: what does that imply about the bi-jectivity between f and g?
Are you talking about question 1? There may not be an onto function from B to A.

Originally Posted by sapsapz
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
First, "f composition g" (g is applied first) is often denoted by $f\circ g$, 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?

7. ## Re: A few questions about functions

Thank you!
But mathematically, how can I define a g function that will choose just one of the many guests?

8. ## Re: A few questions about functions

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?

9. ## Re: A few questions about functions

For disproving stuff, counterexamples tend to work well. Try examples where $|A| \neq |B|$. For instance, let $A = \{a,b\}$ and let $B = \{1,2,3\}$. Define $f,h$ so that $(h\circ f) = \mbox{id}_A$. Regardless of how they are defined, going from $B$ to $A$, 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 $B$. In other words, for some element $b \in B$, $(f\circ h)(b) \neq b$. So, (1) is false.

For (2), let $b \in B$. You want to show that $(f\circ h)(b) = b$. Since $f$ is surjective, you know there exists $a \in A$ such that $f(a) = b$. Additionally, you know that $(h\circ f)(a) = h(f(a)) = a$ (since you know that composition gives the identity on $A$). So, $h(f(a)) = h(b) = a$. Now, you know what $h(b)$ is. So, $(f\circ h)(b) = f(h(b)) = f(a) = b$. Yes, (2) is true.

For (3), consider the same finite example I used in (1) with $A = \{a,b\}$ and $B = \{1,2,3\}$. Suppose $f(a) = g(a) = 1$, $f(b) = 2$, and $g(b) = 3$. Now, suppose $h(1)=a$ and $h(2)=h(3) = b$.

10. ## Re: A few questions about functions

Originally Posted by sapsapz
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
Originally Posted by sapsapz
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?
No there is no problem there. That proof works. Good for you.

11. ## Re: A few questions about functions

Originally Posted by Plato
No there is no problem there. That proof works. Good for you.
The OP's proof does not suffice. The OP is given $h$ and told that $(h\circ f)$ gives the identity on $A$ and needs to prove that $(f\circ h)$ gives the identity on $B$. The OP only proved the existence of such a function, but did not prove that the given function $h$ has the same definition as $g$.

12. ## Re: A few questions about functions

Originally Posted by SlipEternal
The OP's proof does not suffice. The OP is given $h$ and told that $(h\circ f)$ gives the identity on $A$ and needs to prove that $(f\circ h)$ gives the identity on $B$. The OP only proved the existence of such a function, but did not prove that the given function $h$ has the same definition as $g$.
Once again you did not read the post carefully. That is question #1 not #2.
There is no h in #1.

13. ## Re: A few questions about functions

Originally Posted by Plato
Once again you did not read the post carefully. That is question #1 not #2.
There is no h in #1.

14. ## Re: A few questions about functions

Originally Posted by sapsapz
But mathematically, how can I define a g function that will choose just one of the many guests?
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?

15. ## Re: A few questions about functions

Thank you all!

Emakarov - It was probably an intuitive understanding of what I was actually being asked to prove.