Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Math Help - Properties of injective functions

  1. #1
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1

    Properties of injective functions

    Hi.

    problem:
    Show that if f:A\rightarrow B is injective and E\subseteq A, then f^{-1}(f(E))=E.

    I worked with this for a while but was unable to come up with a good answer.
    After a bit of searching, I fould an article on planetmath which answers this question, but I do not understand it completely.
    Here's what it says:

    Theorem. Suppose f:A\rightarrow B is an injection. Then, for all C\subseteq A, it is the case that f^{-1}(f(C))=C.
    Proof. It follows from the definition of f^{-1} that C\subseteq f^{-1}(f(C)), whether or not f happens to be injective.
    Hence, all that need to be shown is that f^{-1}(f(C))\subseteq C.
    Assume the contrary. Then there would exist x\in f^{-1}(f(C)) such that x\notin C.
    By definition x\in f^{-1}(f(C)) means f(x)\in f(C), so there exists y\in A such that f(x)=f(y).
    Since f is injective, one would have x=y, which is impossible because y is supposed to belong to C but x is not supposed to belong to C.

    I do not see why y is supposed to belong to C. What am I missing here?

    Thanks!
    Last edited by Mollier; June 5th 2010 at 12:10 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Mollier View Post
    Hi.

    problem:
    Show that if f:A\rightarrow B is injective and E\subseteq A, then f^{-1}(f(E))=E.

    I worked with this for a while but was unable to come up with a good answer.
    After a bit of searching, I would an article on planetmath which answers this question, but I do not understand it completely.
    Here's what it says:

    Suppose Theorem. f:A\rightarrow B is an injection. Then, for all C\subseteq A, it is the case that f^{-1}(f(C))=C.
    Proof. It follows from the definition of f^{-1} that C\subseteq f^{-1}(f(C)), whether or not f happens to be injective.
    Hence, all that need to be shown is that f^{-1}(f(C))\subseteq C.
    Assume the contrary. Then there would exist x\in f^{-1}(f(C)) such that x\notin C.
    By definition x\in f^{-1}(f(C)) means f(x)\in f(C), so there exists y\in A such that f(x)=f(y).
    Since f is injective, one would have x=y, which is impossible because y is supposed to belong to C but x is not supposed to belong to C.

    I do not see why y is supposed to belong to C. What am I missing here?

    Thanks!
    I don't like how that's said exactly, allow me to say it slightly different.

    Suppose that x\in f^{-1}(f(C)) but x\notin C. Then clearly I have that f(x)\in f(C), right? But f(C)=\left\{f(x):x\in C\right\} and so f(x)=f(y) for some y\in C (since that's what everything in f(C) "looks" like!). But, since y\in C and x\notin C we clearly must have that x\ne y but since f(x)=f(y) this contradicts injectivity.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    I've found that places like PlanetMath and Wikipedia usually don't give the clearest explanations. Here's my approach: the statement f^{-1}(f(E))=E is equivalent to f^{-1}(f(E))\subseteq E and E\subseteq f^{-1}(f(E)) which we prove separaretly as follows.

    (I) x\in f^{-1}(f(E)) \Rightarrow f(x)\in f(E). Hence, f(x)=f(e) for some e\in E. But f is injective and so x=e. That is, x\in E and so f^{-1}(f(E))\subseteq E.

    (II) Let x\in E. Then f(x)\in f(E). Hence, x\in f^{-1}(f(E)) and so E\subseteq f^{-1}(f(E)). (This part doesn't require injectivity.)

    The proof by contradiction given in planetmath is completely unnecessary. There's an unwritten rule in mathematics that direct proofs are to be preferred over indirect ones. In other words, don't prove something by contradiction if you have a direct proof available.

    Finally, in answer to your question: y is in C because f(C)=\{ f(y):y\in C \}. (I think there's a typo in planetmath;the A should be a C.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by ojones View Post
    There's an unwritten rule in mathematics that direct proofs are to be preferred over indirect ones..
    Oh, yeah. Why haven't I ever seen this law? :P
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    Drexel28: You will not "see" this law, you will hear it if you mix in the right circles. Do you have a doctorate in mathematics?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by ojones View Post
    Do you have a doctorate in mathematics?
    Haha, either that is a huge compliment or your being condescending, but no.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    Drexel28: I didn't mean to sound condescending. What I mean is that grad school is where you start to learn the differences between good and bad proofs. At the undergraduate level, instructors are just happy to see a proof!

    One reason why direct proofs are preferred over indirect ones is because they often give more information. For example, proving the existece of something with a direct proof requires producing the object or providing an algorithm to find it. A proof by contradiction tells you only that the object exists and nothing more.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Quote Originally Posted by Drexel28 View Post
    Suppose that x\in f^{-1}(f(C)) but x\notin C. Then clearly I have that f(x)\in f(C), right?
    Actually that is not completely clear to me. x\notin C means to me that x\in A. f(x) is then somewhere in B.
    I don't see why it has to be in f(C). Care to explain a bit more? Thanks.
    Ojones: Again, I do not see how x\in f^{-1}(f(E)) implies that f(x)\in f(E). Why can't f(x) go somewhere else in B?
    I feel stupid for asking this as I'm sure it should be obvious, but I still don't have a good grasp of the obvious
    Thanks!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    This is just the definition of the preimage of a set: if B^\prime \subseteq B then f^{-1}(B^\prime )=\{ a\in A : f(a)\in B^\prime \}.

    Hence, f^{-1}(f(C))=\{ a\in A : f(a)\in f(C)\}. Hence x\in f^{-1}(f(C)) \Rightarrow f(x)\in f(C). Drexel28 is using the same fact.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by ojones View Post
    One reason why direct proofs are preferred over indirect ones is because they often give more information. For example, proving the existece of something with a direct proof requires producing the object or providing an algorithm to find it. A proof by contradiction tells you only that the object exists and nothing more.
    That is total nonsense.
    To quote R L Moore “a proof is a proof”
    All other considerations are simply matters of style.
    The answer.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Quote Originally Posted by ojones View Post
    This is just the definition of the preimage of a set: if B^\prime \subseteq B then f^{-1}(B^\prime )=\{ a\in A : f(a)\in B^\prime \}.

    Hence, f^{-1}(f(C))=\{ a\in A : f(a)\in f(C)\}. Hence x\in f^{-1}(f(C)) \Rightarrow f(x)\in f(C). Drexel28 is using the same fact.
    Aha, now I get it
    Thanks!
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Oct 2007
    From
    London / Cambridge
    Posts
    591
    I think you should now answer the natural following questions.

    Prove that a function is surjective if and only if it has a right inverse. and hence deduce that bijective functions are invertible.

    Bobak
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    Plato:

    "Proofs by contradiction should not be used if a direct proof is available" - Paul Halmos on mathematical writing.

    "All students are enjoined in the strongest possible terms to eschew proofs by contradiction!" - Halsey Royden in Real Analysis.
    Last edited by ojones; June 6th 2010 at 09:27 PM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    " A quotation doesn't establish anything." --Joe the plumber circa 1922
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Quote Originally Posted by bobak View Post
    I think you should now answer the natural following questions.
    Bobak
    My book states the following:
    If f:A\Rightarrow B (surjective) and H\subseteq B, then f(f^{-1}(H))=H.

    I try to prove this in a way similiar to the proof ojones gave.

    1.
    Let f(x)\in f(f^{-1}(H)). Then f(x)=f(a) for some a\in A and f(a)\in H. Hence f(x)\in H and so f(f^{-1}(H))\subseteq H.

    2.
    Let f(x)\in H. There exist some x\in A such that x\in f^{-1}(H). Hence, f(x)\in f(f^{-1}(H)) and so H\subseteq f(f^{-1}(H)).

    Doesn't look as convincing as I would like, but it's the best I can do.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. injective functions
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: November 21st 2009, 11:34 AM
  2. Injective functions
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: November 19th 2009, 05:05 PM
  3. Prooving surjective and injective functions
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 20th 2009, 01:51 PM
  4. injective functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 31st 2008, 09:32 AM
  5. Injective Functions
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 24th 2007, 12:53 AM

Search Tags


/mathhelpforum @mathhelpforum