Results 1 to 9 of 9

Math Help - Another functions proof

  1. #1
    Member
    Joined
    Dec 2008
    From
    Auckland, New Zealand
    Posts
    189

    Another functions proof

    Hello, I have a question that I not sure how to proceed on:

    Let X be a nonempty set and let f:X \rightarrow X be a function such that (f \circ f) = f.
    Show that if f is onto then f = 1^{}_{X}.

    I started by saying:

    Suppose f is onto. Then for each y \in X there exists at least one x \in X such that f(x) = y.

    And then I can't think what to do next. The previous question which was where I got to suppose f was one-to-one seemed much easier!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Hint:

    Maybe it is better to start with a contradiction.

    Let f \neq 1^{}_{X}. Then there exists a x1 such that f(x1) = x2 and x1<>x2

    fof(x1) = f(x1) ---- by your definition of f
    also fof(x1) = f(f(x1)) = f(x2)
    thus f(x1) = f(x2) => f is not one-to-one

    Can you try to complete?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Also if you could please confirm that set X is finite - else I'm running into some cotradictions. If anyone else can also please confirm to us that X has to be finite for this result to hold. Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    I'll just leave this blank...
    Last edited by Swlabr; August 24th 2010 at 03:05 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Sorry for all the sutipidity above. You do not need the condition that X is finite.

    Let x be in the range of f. We will prove that f(x) = x for fof = f to hold true.

    Assume otherwise. i.e. f(x) = y where y <> x for some x in the range of f.

    As x is in the range of f, so there exists z such that f(z) = x; z<> x

    consider fof(z) = f(z) = x; also fof(z) = f(f(z)) = f(x) = y; but we assumed y <> x so contradiction !!

    hence every element in the range of f get mapped to itself. as f is onto thus f is identify function.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    No Swlabr - I do not think we need the assumtion that X should be finite. Please see my re-worked proof below. fof = f is a much stronger condition I guess.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by aman_cc View Post
    No Swlabr - I do not think we need the assumtion that X should be finite. Please see my re-worked proof below. fof = f is a much stronger condition I guess.
    yeah - I realised my counter-example wasn't a counter-example...it wasn't a surjection!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    mistake, nvm
    Last edited by Defunkt; August 24th 2010 at 07:45 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1
    Here is direct proof.
    If a\in X then by the given \left( {\exists b \in X} \right)\left[ {f(b) = a} \right].
    Because  f \circ f(b) = f(b) we have  f(a) = f\left( {f(b)} \right) = f(b) = a.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A functions proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 12th 2010, 03:10 AM
  2. Proof regarding 1-1 functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2009, 04:54 PM
  3. Proof using functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2009, 01:25 PM
  4. Proof?(functions)
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 21st 2009, 05:19 AM
  5. Proof regarding functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 13th 2009, 09:42 PM

Search Tags


/mathhelpforum @mathhelpforum