Show a functions inverse is injective iff f is surjective

[DeldotB]

Hello all,

Can anyone give me a pointer on how to start this proof?:

$$f:E\rightarrow F$$ we consider $$f^{-1}$$ as a function from P(F) to P(E).

Show f^(-1) is injective iff f is surjective.

 

[jk22]

I don't think f surjective implies f^-1 injective by imagining the cases if E has less elements than F. Not sure nevertheless.

 

[HallsofIvy]

Start by writing out the definitions of "P(E)", "injective", and "surjective".

 

[Geofleur]

The problem statement bothers me a little, because $f^{-1}$ need not exist. Imagine the case where the set E has more elements than the set F, and where every element in F has something mapped to it (draw a picture!). Then f is surjective, and f is not injective. Then some point in F will have two points in E mapped to it. The inverse to $f$ would not exist. Not unless you allow the inverse image of a point in F to be a set in E, but that's not usually done when defining an inverse function.

 

[Geofleur]

I just noticed that the function is from E to F, but the inverse is being considered as a function between power sets, and that makes a big difference! The problem statement makes sense to me now.

 

[Geofleur]

I would start by drawing pictures of some special cases. Try to see why the theorem has to be true before proving it formally. Also note, as above, that the inverse of a point in F is allowed to be a set in E.

 

[DeldotB]

I just noticed that the function is from E to F, but the inverse is being considered as a function between power sets, and that makes a big difference! The problem statement makes sense to me now.

Sorry, I need to be clear about the notation: P(F) and P(E) denote the set of all sets of F and E. What you said in your previous post is exactly what I was thinking. If F was smaller than E and f was surjective, then there would be multiple elements in F that were mapped to by the same element in E. So f^(-1) would NOT be injectve...how could this be true?

 

[Geofleur]

Suppose, for example, that a,b, and c are elements of E, and that d and e are elements of F. We could have f(a) = d, f(b) = d, and f(c) = e. I tried to insert a picture of this but it seems like PF doesn't really have a mechanism for inserting pictures from your computer, so I recommend drawing your own. Both a and b get mapped to d, so $f^{-1}(d) = \{a, b\}$, which is itself an element of P(E). Actually, since $f^{-1}$ is being considered as a function from P(F) to P(E), I should really write $f^{-1}(\{d\})=\{a,b\}$. $f^{-1}$ takes a subset of F and spits out a subset of E.

 

[DeldotB]

Suppose, for example, that a,b, and c are elements of E, and that d and e are elements of F. We could have f(a) = d, f(b) = d, and f(c) = e. I tried to insert a picture of this but it seems like PF doesn't really have a mechanism for inserting pictures from your computer, so I recommend drawing your own. Both a and b get mapped to d, so $f^{-1}(d) = \{a, b\}$, which is itself an element of P(E). Actually, since $f^{-1}$ is being considered as a function from P(F) to P(E), I should really write $f^{-1}(\{d\})=\{a,b\}$. $f^{-1}$ takes a subset of F and spits out a subset of E.

ahh ok, this makes much sense! Well, I'll try to work on a proof..

 

[gill1109]

Hello all,

Can anyone give me a pointer on how to start this proof?:

$$f:E\rightarrow F$$ we consider $$f^{-1}$$ as a function from P(F) to P(E).

Show f^(-1) is injective iff f is surjective.

I find it helpful to use the words "one-to-one" and "onto" instead of surjective and injective.
So in one direction we need to know that if f is "onto", which means that every point of F is the image of at least one point of E, and if A and B are different subsets of F, then the set of points in E which map into A is different from the set of points in E which map into B. Well I think that is obvious, and I think it is not difficult to write it out formally.
In the other direction we have to show that if for any A and B contained in F which are different, the sets of points of E which map into A and B are different, then f is "onto". Probably easiest to prove this (if it is true) by contradiction. Assume f is not "onto". Now find two subsets A and B of F which are different, but such that the sets of points which map into A and B are the same. Hm, I think that is not so difficult either ...

 

[gill1109]

Or was this a homework question? If so, wrong forum...