Show a functions inverse is injective iff f is surjective

Tags:
1. Aug 29, 2015

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.

2. Aug 29, 2015

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.

3. Aug 30, 2015

HallsofIvy

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

4. Aug 30, 2015

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.

5. Aug 30, 2015

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.

Last edited: Aug 30, 2015
6. Aug 30, 2015

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.

7. Aug 30, 2015

DeldotB

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?

8. Aug 30, 2015

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.

9. Aug 30, 2015

DeldotB

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

10. Sep 2, 2015

gill1109

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 ...

11. Sep 2, 2015