a problem on composition of functions












3












$begingroup$


Let $f colon A to A$ be a function such that $f circ f=f$. If $f$ is one-to-one then prove that $f$ is also onto.



I know in my head that the func. $f$ is $f(x)=x$, but I can't develop a proof for the above statement.










share|cite|improve this question









New contributor




user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    Welcome! What have you tried?
    $endgroup$
    – user458276
    4 hours ago










  • $begingroup$
    Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
    $endgroup$
    – frabala
    4 hours ago












  • $begingroup$
    thank you.. got it..
    $endgroup$
    – user649511
    4 hours ago










  • $begingroup$
    What are the definitions? What does it mean to be onto?
    $endgroup$
    – JavaMan
    4 hours ago










  • $begingroup$
    onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
    $endgroup$
    – user649511
    4 hours ago
















3












$begingroup$


Let $f colon A to A$ be a function such that $f circ f=f$. If $f$ is one-to-one then prove that $f$ is also onto.



I know in my head that the func. $f$ is $f(x)=x$, but I can't develop a proof for the above statement.










share|cite|improve this question









New contributor




user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    Welcome! What have you tried?
    $endgroup$
    – user458276
    4 hours ago










  • $begingroup$
    Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
    $endgroup$
    – frabala
    4 hours ago












  • $begingroup$
    thank you.. got it..
    $endgroup$
    – user649511
    4 hours ago










  • $begingroup$
    What are the definitions? What does it mean to be onto?
    $endgroup$
    – JavaMan
    4 hours ago










  • $begingroup$
    onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
    $endgroup$
    – user649511
    4 hours ago














3












3








3


1



$begingroup$


Let $f colon A to A$ be a function such that $f circ f=f$. If $f$ is one-to-one then prove that $f$ is also onto.



I know in my head that the func. $f$ is $f(x)=x$, but I can't develop a proof for the above statement.










share|cite|improve this question









New contributor




user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




Let $f colon A to A$ be a function such that $f circ f=f$. If $f$ is one-to-one then prove that $f$ is also onto.



I know in my head that the func. $f$ is $f(x)=x$, but I can't develop a proof for the above statement.







functions






share|cite|improve this question









New contributor




user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited 15 mins ago







user649511













New contributor




user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 4 hours ago









user649511user649511

234




234




New contributor




user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • $begingroup$
    Welcome! What have you tried?
    $endgroup$
    – user458276
    4 hours ago










  • $begingroup$
    Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
    $endgroup$
    – frabala
    4 hours ago












  • $begingroup$
    thank you.. got it..
    $endgroup$
    – user649511
    4 hours ago










  • $begingroup$
    What are the definitions? What does it mean to be onto?
    $endgroup$
    – JavaMan
    4 hours ago










  • $begingroup$
    onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
    $endgroup$
    – user649511
    4 hours ago


















  • $begingroup$
    Welcome! What have you tried?
    $endgroup$
    – user458276
    4 hours ago










  • $begingroup$
    Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
    $endgroup$
    – frabala
    4 hours ago












  • $begingroup$
    thank you.. got it..
    $endgroup$
    – user649511
    4 hours ago










  • $begingroup$
    What are the definitions? What does it mean to be onto?
    $endgroup$
    – JavaMan
    4 hours ago










  • $begingroup$
    onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
    $endgroup$
    – user649511
    4 hours ago
















$begingroup$
Welcome! What have you tried?
$endgroup$
– user458276
4 hours ago




$begingroup$
Welcome! What have you tried?
$endgroup$
– user458276
4 hours ago












$begingroup$
Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
$endgroup$
– frabala
4 hours ago






$begingroup$
Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
$endgroup$
– frabala
4 hours ago














$begingroup$
thank you.. got it..
$endgroup$
– user649511
4 hours ago




$begingroup$
thank you.. got it..
$endgroup$
– user649511
4 hours ago












$begingroup$
What are the definitions? What does it mean to be onto?
$endgroup$
– JavaMan
4 hours ago




$begingroup$
What are the definitions? What does it mean to be onto?
$endgroup$
– JavaMan
4 hours ago












$begingroup$
onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
$endgroup$
– user649511
4 hours ago




$begingroup$
onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
$endgroup$
– user649511
4 hours ago










3 Answers
3






active

oldest

votes


















3












$begingroup$

What I like about this problem is that it places no restriction on the carinality $A$; its conclusion binds for some very large sets indeed.



Suppose $f$ is not surjective, and let



$B = f(A) tag 1$



be the image of $A$ under $f$; since



$f circ f = f, tag 2$



it is clear that every element of $B$ is fixed under $f$, for



$b in B Longrightarrow exists c in A, ; b = f(c) Longrightarrow f(b) = f(f(c)) = f(c) = b; tag 3$



furthermore, for $c in A$,



$f(c) = c Longrightarrow c in B; tag 4$



thus $B$ is precisely the set of fixed points of $f$.



We have assumed $f$ not surjective; then by the above we have



$B subsetneq A, tag 5$



which implies



$exists a in A setminus B; tag 6$



if



$b = f(a) in B, tag 7$



then



$f(b) = f(f(a)) = f(a) = b; tag 8$



we note



$B ni b ne a in A setminus B, tag 9$



which contradicts the given hypothesis that $f$ is an injective map. Thus $f$ is in fact surjective.






share|cite|improve this answer











$endgroup$





















    0












    $begingroup$

    We know
    $fcirc f=f$ so $f([f(x)]) =f (x)$.



    Comparing both sides, which shows $[f (x)] = x$ (since $f$ is one-to-one)
    so for all $x$ in codomain of $f$ there is an $x$ in domain such that $f(x) = x$ .. so it is onto.. yay...



    i see someone downvoted the question



    if you feel its a dumb question please know I'm still in school learning relations and functions ! :)






    share|cite|improve this answer










    New contributor




    user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    $endgroup$













    • $begingroup$
      Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
      $endgroup$
      – Graham Kemp
      3 hours ago



















    0












    $begingroup$

    Let $x in A$. Let $y=f(x).$ Then $f(y) = f(f(x)) = (f circ f) (x) = f(x)$ $implies y=x,$ if f was assumed to be injective. So if $f$ was injective then $f(x)=x,$ for all $x in A.$ So $f$ is the identity map on $A.$ But then $f$ is clearly surjective, as claimed.



    QED






    share|cite|improve this answer









    $endgroup$













      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "69"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });






      user649511 is a new contributor. Be nice, and check out our Code of Conduct.










      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3130960%2fa-problem-on-composition-of-functions%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      3 Answers
      3






      active

      oldest

      votes








      3 Answers
      3






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      3












      $begingroup$

      What I like about this problem is that it places no restriction on the carinality $A$; its conclusion binds for some very large sets indeed.



      Suppose $f$ is not surjective, and let



      $B = f(A) tag 1$



      be the image of $A$ under $f$; since



      $f circ f = f, tag 2$



      it is clear that every element of $B$ is fixed under $f$, for



      $b in B Longrightarrow exists c in A, ; b = f(c) Longrightarrow f(b) = f(f(c)) = f(c) = b; tag 3$



      furthermore, for $c in A$,



      $f(c) = c Longrightarrow c in B; tag 4$



      thus $B$ is precisely the set of fixed points of $f$.



      We have assumed $f$ not surjective; then by the above we have



      $B subsetneq A, tag 5$



      which implies



      $exists a in A setminus B; tag 6$



      if



      $b = f(a) in B, tag 7$



      then



      $f(b) = f(f(a)) = f(a) = b; tag 8$



      we note



      $B ni b ne a in A setminus B, tag 9$



      which contradicts the given hypothesis that $f$ is an injective map. Thus $f$ is in fact surjective.






      share|cite|improve this answer











      $endgroup$


















        3












        $begingroup$

        What I like about this problem is that it places no restriction on the carinality $A$; its conclusion binds for some very large sets indeed.



        Suppose $f$ is not surjective, and let



        $B = f(A) tag 1$



        be the image of $A$ under $f$; since



        $f circ f = f, tag 2$



        it is clear that every element of $B$ is fixed under $f$, for



        $b in B Longrightarrow exists c in A, ; b = f(c) Longrightarrow f(b) = f(f(c)) = f(c) = b; tag 3$



        furthermore, for $c in A$,



        $f(c) = c Longrightarrow c in B; tag 4$



        thus $B$ is precisely the set of fixed points of $f$.



        We have assumed $f$ not surjective; then by the above we have



        $B subsetneq A, tag 5$



        which implies



        $exists a in A setminus B; tag 6$



        if



        $b = f(a) in B, tag 7$



        then



        $f(b) = f(f(a)) = f(a) = b; tag 8$



        we note



        $B ni b ne a in A setminus B, tag 9$



        which contradicts the given hypothesis that $f$ is an injective map. Thus $f$ is in fact surjective.






        share|cite|improve this answer











        $endgroup$
















          3












          3








          3





          $begingroup$

          What I like about this problem is that it places no restriction on the carinality $A$; its conclusion binds for some very large sets indeed.



          Suppose $f$ is not surjective, and let



          $B = f(A) tag 1$



          be the image of $A$ under $f$; since



          $f circ f = f, tag 2$



          it is clear that every element of $B$ is fixed under $f$, for



          $b in B Longrightarrow exists c in A, ; b = f(c) Longrightarrow f(b) = f(f(c)) = f(c) = b; tag 3$



          furthermore, for $c in A$,



          $f(c) = c Longrightarrow c in B; tag 4$



          thus $B$ is precisely the set of fixed points of $f$.



          We have assumed $f$ not surjective; then by the above we have



          $B subsetneq A, tag 5$



          which implies



          $exists a in A setminus B; tag 6$



          if



          $b = f(a) in B, tag 7$



          then



          $f(b) = f(f(a)) = f(a) = b; tag 8$



          we note



          $B ni b ne a in A setminus B, tag 9$



          which contradicts the given hypothesis that $f$ is an injective map. Thus $f$ is in fact surjective.






          share|cite|improve this answer











          $endgroup$



          What I like about this problem is that it places no restriction on the carinality $A$; its conclusion binds for some very large sets indeed.



          Suppose $f$ is not surjective, and let



          $B = f(A) tag 1$



          be the image of $A$ under $f$; since



          $f circ f = f, tag 2$



          it is clear that every element of $B$ is fixed under $f$, for



          $b in B Longrightarrow exists c in A, ; b = f(c) Longrightarrow f(b) = f(f(c)) = f(c) = b; tag 3$



          furthermore, for $c in A$,



          $f(c) = c Longrightarrow c in B; tag 4$



          thus $B$ is precisely the set of fixed points of $f$.



          We have assumed $f$ not surjective; then by the above we have



          $B subsetneq A, tag 5$



          which implies



          $exists a in A setminus B; tag 6$



          if



          $b = f(a) in B, tag 7$



          then



          $f(b) = f(f(a)) = f(a) = b; tag 8$



          we note



          $B ni b ne a in A setminus B, tag 9$



          which contradicts the given hypothesis that $f$ is an injective map. Thus $f$ is in fact surjective.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited 1 hour ago

























          answered 1 hour ago









          Robert LewisRobert Lewis

          47.4k23067




          47.4k23067























              0












              $begingroup$

              We know
              $fcirc f=f$ so $f([f(x)]) =f (x)$.



              Comparing both sides, which shows $[f (x)] = x$ (since $f$ is one-to-one)
              so for all $x$ in codomain of $f$ there is an $x$ in domain such that $f(x) = x$ .. so it is onto.. yay...



              i see someone downvoted the question



              if you feel its a dumb question please know I'm still in school learning relations and functions ! :)






              share|cite|improve this answer










              New contributor




              user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.






              $endgroup$













              • $begingroup$
                Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
                $endgroup$
                – Graham Kemp
                3 hours ago
















              0












              $begingroup$

              We know
              $fcirc f=f$ so $f([f(x)]) =f (x)$.



              Comparing both sides, which shows $[f (x)] = x$ (since $f$ is one-to-one)
              so for all $x$ in codomain of $f$ there is an $x$ in domain such that $f(x) = x$ .. so it is onto.. yay...



              i see someone downvoted the question



              if you feel its a dumb question please know I'm still in school learning relations and functions ! :)






              share|cite|improve this answer










              New contributor




              user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.






              $endgroup$













              • $begingroup$
                Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
                $endgroup$
                – Graham Kemp
                3 hours ago














              0












              0








              0





              $begingroup$

              We know
              $fcirc f=f$ so $f([f(x)]) =f (x)$.



              Comparing both sides, which shows $[f (x)] = x$ (since $f$ is one-to-one)
              so for all $x$ in codomain of $f$ there is an $x$ in domain such that $f(x) = x$ .. so it is onto.. yay...



              i see someone downvoted the question



              if you feel its a dumb question please know I'm still in school learning relations and functions ! :)






              share|cite|improve this answer










              New contributor




              user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.






              $endgroup$



              We know
              $fcirc f=f$ so $f([f(x)]) =f (x)$.



              Comparing both sides, which shows $[f (x)] = x$ (since $f$ is one-to-one)
              so for all $x$ in codomain of $f$ there is an $x$ in domain such that $f(x) = x$ .. so it is onto.. yay...



              i see someone downvoted the question



              if you feel its a dumb question please know I'm still in school learning relations and functions ! :)







              share|cite|improve this answer










              New contributor




              user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.









              share|cite|improve this answer



              share|cite|improve this answer








              edited 3 hours ago









              Graham Kemp

              86.2k43478




              86.2k43478






              New contributor




              user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.









              answered 4 hours ago









              user649511user649511

              234




              234




              New contributor




              user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.





              New contributor





              user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.






              user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.












              • $begingroup$
                Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
                $endgroup$
                – Graham Kemp
                3 hours ago


















              • $begingroup$
                Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
                $endgroup$
                – Graham Kemp
                3 hours ago
















              $begingroup$
              Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
              $endgroup$
              – Graham Kemp
              3 hours ago




              $begingroup$
              Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
              $endgroup$
              – Graham Kemp
              3 hours ago











              0












              $begingroup$

              Let $x in A$. Let $y=f(x).$ Then $f(y) = f(f(x)) = (f circ f) (x) = f(x)$ $implies y=x,$ if f was assumed to be injective. So if $f$ was injective then $f(x)=x,$ for all $x in A.$ So $f$ is the identity map on $A.$ But then $f$ is clearly surjective, as claimed.



              QED






              share|cite|improve this answer









              $endgroup$


















                0












                $begingroup$

                Let $x in A$. Let $y=f(x).$ Then $f(y) = f(f(x)) = (f circ f) (x) = f(x)$ $implies y=x,$ if f was assumed to be injective. So if $f$ was injective then $f(x)=x,$ for all $x in A.$ So $f$ is the identity map on $A.$ But then $f$ is clearly surjective, as claimed.



                QED






                share|cite|improve this answer









                $endgroup$
















                  0












                  0








                  0





                  $begingroup$

                  Let $x in A$. Let $y=f(x).$ Then $f(y) = f(f(x)) = (f circ f) (x) = f(x)$ $implies y=x,$ if f was assumed to be injective. So if $f$ was injective then $f(x)=x,$ for all $x in A.$ So $f$ is the identity map on $A.$ But then $f$ is clearly surjective, as claimed.



                  QED






                  share|cite|improve this answer









                  $endgroup$



                  Let $x in A$. Let $y=f(x).$ Then $f(y) = f(f(x)) = (f circ f) (x) = f(x)$ $implies y=x,$ if f was assumed to be injective. So if $f$ was injective then $f(x)=x,$ for all $x in A.$ So $f$ is the identity map on $A.$ But then $f$ is clearly surjective, as claimed.



                  QED







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered 1 hour ago









                  Dbchatto67Dbchatto67

                  1,301219




                  1,301219






















                      user649511 is a new contributor. Be nice, and check out our Code of Conduct.










                      draft saved

                      draft discarded


















                      user649511 is a new contributor. Be nice, and check out our Code of Conduct.













                      user649511 is a new contributor. Be nice, and check out our Code of Conduct.












                      user649511 is a new contributor. Be nice, and check out our Code of Conduct.
















                      Thanks for contributing an answer to Mathematics Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3130960%2fa-problem-on-composition-of-functions%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Усть-Каменогорск

                      Халкинская богословская школа

                      Высокополье (Харьковская область)