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

Math Help - Injective, Surjective, Bijective

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    24

    Injective, Surjective, Bijective

    Ok I'm up to the next step in set theory and am having trouble determining if set relations are injective, sirjective or bijective.

    Say we are matching the members of a set "A" to a set "B"

    Injective means that every member of "A" has a unique matching member in "B". You won't get two "A"s pointing to one "B", but you could have a "B" without a matching "A"

    Surjective means that every "B" has at least one matching "A" (maybe more than one).

    Bijective means both. So we have a perfect 1-1 relationship


    Let
    A = {1,2,3,4,5}and B = {0,6,7,8,9}
    (a) How many functions f: A =>B are there?
    (b) How many injective functions f : A => B are there?
    (c) How many surjective functions f : A =>B are there?
    (d) How many bijective functions f : A =>B such that f(3) = 6 are there?



    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Have you tried any of these?
    This is a nice set of problems.
    Are you simply asking us for the answers? Or do you need help?
    If you need help, show us what you dont understand. We can deal with that.
    But, I hope that none of us simply gives out the answers to prove we can do them
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    24
    Sorry that was rude of me. I will post up my thoughts (I don't really have answers) later tonight. Sorry again.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2009
    Posts
    24
    Quote Originally Posted by TTim View Post
    Let
    A = {1,2,3,4,5}and B = {0,6,7,8,9}

    (a) How many functions f: A =>B are there?
    (b) How many injective functions f : A => B are there?
    (c) How many surjective functions f : A =>B are there?
    (d) How many bijective functions f : A =>B such that f(3) = 6 are there?


    OK I have looked at this and have no clue how to do it. The functions
    f(A) = 0, f(A) = 6, f(A) = 7 etc is all I can come up with.

    Are there any procedural ways to find these functions? Any hints, tips appreciated.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Part a) is asking, "how many ways can we define f:A \mapsto B"?
    How many different values can f(1) have?
    How many different values can f(2) have?
    How many different values can f(3) have?
    etc.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2009
    Posts
    24
    Quote Originally Posted by Plato View Post
    Part a) is asking, "how many ways can we define f:A \mapsto B"?
    How many different values can f(1) have?
    How many different values can f(2) have?
    How many different values can f(3) have?
    etc.
    5? for f(1) to map to B it needs to equal 0,6,7,8or 9? Same with the rest...

    Do I have to have every element A map to some element B? I.e. I can't have an A map to something that isn't in B?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by TTim View Post
    5? for f(1) to map to B it needs to equal 0,6,7,8or 9? Same with the rest...?
    Yes. So the answer to a) is 5^5.
    Now, what is different about b)?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Mar 2009
    Posts
    24
    Quote Originally Posted by Plato View Post
    Yes. So the answer to a) is 5^5.
    Now, what is different about b)?
    I'm lost already. How is it 5^5? Are you saying
    f(1) --> 0
    f(2) --> 6
    f(3) --> 7
    f(4) --> 8
    f(5) --> 9

    would be a function as would

    f(1) --> 0
    f(2) --> 6
    f(3) --> 7
    f(4) --> 9
    f(5) --> 8

    as well as

    f(1) --> 6
    f(2) --> 6
    f(3) --> 6
    f(4) --> 6
    f(5) --> 6

    as wells as

    f(1) --> 6
    f(2) --> 6
    f(3) --> 6
    f(4) --> 6
    f(5) --> 0

    All of these are mapping from A to B but how can you confirm if a function actually exists that exhibits this mapping property?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by TTim View Post
    I'm lost already. How is it 5^5? Are you saying
    f(1) --> 0
    f(2) --> 6
    f(3) --> 7
    f(4) --> 8
    f(5) --> 9

    would be a function as would

    f(1) --> 0
    f(2) --> 6
    f(3) --> 7
    f(4) --> 9
    f(5) --> 8

    as well as

    f(1) --> 6
    f(2) --> 6
    f(3) --> 6
    f(4) --> 6
    f(5) --> 6

    as wells as

    f(1) --> 6
    f(2) --> 6
    f(3) --> 6
    f(4) --> 6
    f(5) --> 0

    All of these are mapping from A to B but how can you confirm if a function actually exists that exhibits this mapping property?
    it is 5^5 since you have 5 elements in the domain, each of which can map to any of the 5 elements in the codomain. thus, you have 5 choices for each of the 5 inputs, so in all you have 5*5*5*5*5 = 5^5 choices of mappings.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Suppose that set A has j elements and set B has k elements.
    How many functions are there from A to B? ANSWER k^j.
    Reason: for each one of the j elements in A we have k choices for its image in B.

    How many functions are there from B to A? ANSWER j^k.
    How many functions are there from A to A? ANSWER j^j.
    How many functions are there from B to B? ANSWER k^k.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Mar 2009
    Posts
    24
    Quote Originally Posted by Plato View Post
    Suppose that set A has j elements and set B has k elements.
    How many functions are there from A to B? ANSWER k^j.
    Reason: for each one of the j elements in A we have k choices for its image in B.

    How many functions are there from B to A? ANSWER j^k.
    How many functions are there from A to A? ANSWER j^j.
    How many functions are there from B to B? ANSWER k^k.
    Alright cool, if asked to provide one of the 3125 functions would it be possible to determine that function?


    So we have 5^5 functions. Injective and surjective functions will obviously form different subsets of the wholse set of the functions.

    Injective functions - Each A will need to have a unique B. Seeing as both sets are the same cardinality for a function to be surjective it must be injective and vice versa?

    There will be 5(5x4x3x2x1) = 600 bijective functions? (Clutching at straws here)
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by TTim View Post
    Alright cool, if asked to provide one of the 3125 functions would it be possible to determine that function?
    So we have 5^5 functions. Injective and surjective functions will obviously form different subsets of the wholse set of the functions.

    Injective functions - Each A will need to have a unique B. Seeing as both sets are the same cardinality for a function to be surjective it must be injective and vice versa?

    There will be 5(5x4x3x2x1) = 600 bijective functions? (Clutching at straws here)
    NO NO NO
    Not all function are surjections, injections or bijections.

    In your question the answer to part b is (5)(4)(3)(2)(1)=120
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Mar 2009
    Posts
    24
    Quote Originally Posted by Plato View Post
    NO NO NO
    Not all function are surjections, injections or bijections.

    In your question the answer to part b is (5)(4)(3)(2)(1)=120
    I understand that not all the functions are surjections, injections or bijections. But I fell as if there is something weird happening because both sets have the same number of elements.

    Ok...

    I'll make some statements about what I think.

    1. A and B have the same cardinalty.
    2. Because of 1 any function that is injective is surjective. I.e. seeing as every A has a unique matching B this means that every B is mapped onto by one A?
    3. surjectivity does not imply injectivity
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by TTim View Post
    1. A and B have the same cardinalty.
    2. Because of 1 any function that is injective is surjective. I.e. seeing as every A has a unique matching B this means that every B is mapped onto by one A?
    3. surjectivity does not imply injectivity
    Those statemants are correct. Let |A| stand for the cardinality of set A.
    Then if |A|=|B|=k then there are (k!) bijections from A to B. [That is k factorial].
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Mar 2009
    Posts
    90
    So, to sum up for cardinality:
    for a function  f:A \rightarrow B

    if the function is injective then:
    the codomain is atleast as big as the domain. \mid A \mid \leq \mid B \mid
    and the number of possible functions is  \frac{\mid B \mid !}{(\mid B \mid-\mid A \mid)!}

    if the function is surjective then:
    the domain is at least as big as the codomain. The opposite of above. \mid A \mid \geq \mid B \mid
    This means that every element b in the codomain B is an image of at least one element a in the domain A.
    and the number of possible functions is  \frac{\mid A \mid !}{(\mid A \mid-\mid B \mid)!}

    and bijective is  \mid A \mid = \mid B \mid

    Something wrong with my probability?
    Last edited by bmp05; April 2nd 2009 at 04:52 AM.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. total, injective, surjective, and bijective functions
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 24th 2010, 12:12 AM
  2. Surjective, Injective, Bijective
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 4th 2009, 01:36 PM
  3. Replies: 1
    Last Post: September 21st 2009, 08:01 PM
  4. Is f injective? Surjective? Bijective?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 3rd 2009, 03:27 AM
  5. injective, surjective or bijective (no2)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 16th 2009, 01:58 AM

Search Tags


/mathhelpforum @mathhelpforum