Show a functions inverse is injective iff f is surjective

Click For Summary

Discussion Overview

The discussion revolves around the proof that the inverse function \( f^{-1} \) is injective if and only if the function \( f \) is surjective. Participants explore definitions and implications related to functions, their inverses, and the properties of injectivity and surjectivity, with a focus on the context of functions from sets and their power sets.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Homework-related

Main Points Raised

  • Some participants suggest starting the proof by clarifying the definitions of "P(E)", "injective", and "surjective".
  • One participant argues that surjectivity does not imply injectivity, particularly when the set \( E \) has fewer elements than \( F \), leading to potential issues with the existence of \( f^{-1} \).
  • Another participant notes that if \( f \) is surjective but not injective, then multiple elements in \( E \) could map to the same element in \( F \), complicating the definition of \( f^{-1} \).
  • Some participants emphasize the importance of understanding that \( f^{-1} \) is being considered as a function from power sets, which alters the implications of injectivity and surjectivity.
  • One participant provides an example illustrating how two elements in \( E \) can map to the same element in \( F \), leading to a non-injective inverse.
  • Another participant suggests using the terms "one-to-one" and "onto" instead of "injective" and "surjective" for clarity, and outlines a potential approach for proving both directions of the statement.

Areas of Agreement / Disagreement

Participants express differing views on the implications of surjectivity for injectivity, with no consensus reached on the proof's validity or the conditions under which the inverse function exists.

Contextual Notes

Participants note that the existence of the inverse function \( f^{-1} \) is contingent on the relationship between the sizes of sets \( E \) and \( F \), and that the definitions of injectivity and surjectivity must be carefully applied in the context of power sets.

DeldotB
Messages
117
Reaction score
8
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.
 
Physics news on Phys.org
I don't think f surjective implies f^-1 injective by imagining the cases if E has less elements than F. Not sure nevertheless.
 
Start by writing out the definitions of "P(E)", "injective", and "surjective".
 
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.
 
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:
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.
 
Geofleur said:
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?
 
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.
 
Geofleur said:
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..
 
  • #10
DeldotB said:
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 ...
 
  • #11
Or was this a homework question? If so, wrong forum...
 

Similar threads

Undergrad On injectivity of two-sided Laplace transform
  • · Replies 5 ·
Replies
5
Views
3K
Graduate Injection from finite set to equally sized set is surjection
  • · Replies 13 ·
Replies
13
Views
5K
MHB How can we show that the inverse is bijective?
  • · Replies 14 ·
Replies
14
Views
3K
MHB How to remember set theory properties?
  • · Replies 4 ·
Replies
4
Views
3K
MHB Proving Existence of Surjective Function F from P(N)\N to P(N)
  • · Replies 1 ·
Replies
1
Views
2K
Graduate What {in,sur}jectivity of composite map implies for components
  • · Replies 3 ·
Replies
3
Views
3K
MHB Show that there exists a bijection
  • · Replies 8 ·
Replies
8
Views
2K
Graduate Prove set S is countable iff there exists a surjective/injective function
  • · Replies 2 ·
Replies
2
Views
14K
Undergrad Homemorphism in quotient topology
  • · Replies 5 ·
Replies
5
Views
2K
F bijective <=> f has an inverse
  • · Replies 7 ·
Replies
7
Views
3K