Results 1 to 7 of 7

Math Help - Error in thought:How many onto functions there from a set of 4 element to 2 elements?

  1. #1
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Error in thought:How many onto functions there from a set of 4 element to 2 elements?

    There's a math problem in the book Discrete Mathematics with Applications(2nd Edition) by Susanna S. Epp is something like this:


    How many onto functions are there from a set with four elements to a set with two elements?

    Definition of onto function is:

    Let F be a function from a set X to a set Y. F is onto(or surjective) if, and only if, given any element y in
    Y it is possible to find an element x in X with the property that y = F(x).

    Symbolically:

     F:X\to Y\; is\; onto\; \Leftrightarrow \forall y\in Y,\; \exists x\in X\; such\; that\; F(x)\; =\; y.


    Now back to the math problem. I did this.



    Let the element of the domain be called M = \{a,b,c,d\} and the elements of the co-domain be called
    N = \{u,v\} Now there \binom{4}{2} + \binom{4}{2} = 6 + 6 = 12 ways to select 2 elements of M and and associate with set N. I added twice because there are two elements in N and 1 for each element of N



    Also there are \binom{4}{3}+\binom{4}{3} = 4 + 4 = 8 ways to select 3 elements of M and associate with set N. Again because there are two elements in N and added twice.



    So the total number of onto function from a set with four elements to a set with two elements is: 12 + 8 = 20. But the answer in the book is 14.



    What am i doing wrong? Is it possible for someone to kindly look into the problem and figure out the error in my thinking?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

    Quote Originally Posted by x3bnm View Post
    So the total number of onto function from a set with four elements to a set with two elements is: 12 + 8 = 20. But the answer in the book is 14.
    Consider A=\{1,2,3,4\},\;B=\{a,b\} then, any map f:A\to B can be considered as an arrangement , for example aaaa,\;aaab,\ldots, \;baab,\ldots,bbbb . All are onto except aaaa and bbbb . Hence, we have 2^4-2=14 onto maps.
    Last edited by FernandoRevilla; August 14th 2011 at 09:34 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

    You are over counting by repeating some selections.

    If N\ge K then the number of surjection from a set of N elements to a set of K is:
    {\text{Surj}}(N,K) = \sum\limits_{j = 0}^K {\left( { - 1} \right)^j \binom{K}{j}\left( {K - j} \right)^N }.

    So \text{Surj}(4,2)=14.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

    Thanks FernandoRevilla and Plato for explanation.

    Plato you're right i'm counting some selection multiple times. My mistake. Sorry. Thanks again.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

    Quote Originally Posted by Plato View Post
    You are over counting by repeating some selections.

    If N\ge K then the number of surjection from a set of N elements to a set of K is:
    {\text{Surj}}(N,K) = \sum\limits_{j = 0}^K {\left( { - 1} \right)^j \binom{K}{j}\left( {K - j} \right)^N }.

    So \text{Surj}(4,2)=14.
    Sorry for reopening this thread but Plato how did you come up with this formula?


    I can't find this formula in my book. Is there a proof somewhere?

    I like to know it. My curious mind can't help it.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

    Quote Originally Posted by x3bnm View Post
    I like to know it. My curious mind can't help it.
    This is an example of using the inclusion/exclusion principle. I know that it is in Epp's book. Count the function that leave out one of the final set, the two of the final set, then three ETC. So we end up adding and subtracting each of those. I no longer have a copy of her book. But I am positive this idea is in that text.
    Last edited by Plato; August 14th 2011 at 11:59 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Error in thought:How many onto functions there from a set of 4 element to 2 eleme

    Quote Originally Posted by Plato View Post
    This is an example of using the inclusion/exclusion principle. I know that it is in Epp's book. Count the function that leave out one of the final set, the two of the final set, then three ETC. So we end up adding and subtracting each of those. I no longer have a copy of her book. But I am positive this idea is in that text.
    Thanks Plato. It's on page 299-300 of Epp's book for those who are interested.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Orbits of an element and the Stabilizer of the element
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 24th 2011, 05:41 AM
  2. Replies: 2
    Last Post: April 30th 2011, 09:45 AM
  3. functions like the error function
    Posted in the Statistics Forum
    Replies: 1
    Last Post: November 25th 2010, 04:43 AM
  4. Replies: 0
    Last Post: October 28th 2010, 11:37 PM
  5. Replies: 3
    Last Post: March 23rd 2010, 07:05 PM

/mathhelpforum @mathhelpforum