1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mapping of functions

  1. Jul 29, 2006 #1
    There are 2 parts to this question:

    How many functions are there from a set S with n elements to a set T with m elements? Assume n<=m, how many one-to-one functions are there from S to T?


    I am pretty sure that the answer to the first part is mn. So if there are 3 elements in the first set and 4 elements in the 2nd set, then there are a total of 3 X 4 functions.

    But for 1 to 1, it would be (for the same set example used above), 4+3+2 = 9 functions.
    I am unsure on how to come up with the general formula for the mapping of one-to-one functions.


    Any help is appreciated.......:smile:
     
  2. jcsd
  3. Jul 29, 2006 #2

    0rthodontist

    User Avatar
    Science Advisor

    In the first part, each element of the domain can choose from among m elements of the codomain. What does that translate to?

    In the second part, you have to match up the elements in the domain with the elements of the codomain in a one-to-one fashion. Let's say for concreteness that the elements of the domain are 1, 2, ... n. Then you have m elements, n of which you must match up against those numbers in some way. Does order matter?
     
  4. Jul 29, 2006 #3
    no order doesnt matter, only thing is once you map to set T, you cant map to the same element again to satisfy the 1-to-1 requirement
     
  5. Jul 29, 2006 #4

    0rthodontist

    User Avatar
    Science Advisor

    Let's say n = 1...4 and m = 1...7. Then a function might look something like this:
    Code (Text):

    n   m

    1   5
    2   2
    3   4
    4   7

    Leftover m: 1, 3, 6
     
    Let's say that you switch the order that the elements of m are assigned to the elements of n.
    Code (Text):

    n   m

    1   5
    2   4
    3   2
    4   7

    Leftover m: 1, 3, 6
     
    Is this the same function?
     
  6. Jul 29, 2006 #5

    nrqed

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I am pretty sure it would not be considered the same function! f(2) does not give the sam eresult in both cases so it's a different function.
     
  7. Jul 29, 2006 #6

    nrqed

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It depends. do all the elements of S need to be mapped? Must the mapping be onto?
    If all the elements of S must be mapped but there is not other restriction, I would say m^n. You pick one element of S and you can map it to any of the m elements of T. That's m choices. You take the second element of S and you can still map it to any of the m elements of T, that's another m choices, and so on. So m^n, no?
     
  8. Jul 29, 2006 #7
    m^n doesnt work as you cant map to the same value at T, as then it wont be one-to-one.....
     
  9. Jul 29, 2006 #8

    0rthodontist

    User Avatar
    Science Advisor

    So does order matter?

    Another hint: 5247 completely determines the first function I mentioned, and 5427 completely determines the second one I mentioned.
     
  10. Jul 29, 2006 #9
    i am kinda confused now.....

    you are right when u say that f(2) is not the same function. So how do you take in all possibilities..... I cant really see a pattern where i can come up with a formula in terms of n and m
     
  11. Jul 29, 2006 #10
    yeah order does matter as it maps a different function..... but i just cant undersatnd how to work out all the possible funtions there can be
     
  12. Jul 29, 2006 #11

    0rthodontist

    User Avatar
    Science Advisor

    Okay--it's a permutation of some kind. What is it permuting--how many does it permute out of a set of what size?
     
  13. Jul 29, 2006 #12
    thats what i have been trying to use. The set size is m and you are choosing from n. Is it correct in saying P(m,n)
     
  14. Jul 29, 2006 #13

    0rthodontist

    User Avatar
    Science Advisor

    Yes, that's correct.
     
  15. Jul 29, 2006 #14

    nrqed

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I was talking about the *first* question. In that case the function does not have to be one-to-one, no?
     
  16. Jul 29, 2006 #15

    nrqed

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I see what you are saying but it feels to me that it's a bit misleading to talk about "order" here because that plays no role in the problem. it just happens that the elements of the first set are 1, 2,3,4 but since we are talking about mapping discrete elements, order plays no role here. I mean, the elements could have been called "A, epsilon, 7 and aleph" as well without changing the problem at all.
    My point was that two functions are equal if they map all the elements of the first set to the same elements of the second set (order not playing any role here). In your first function above, the element 2 of the first set is mapped to the elemnt 2 of the second set whereas in the second function, the 2 is mapped to 4. I don't see anyway to think of two functions as being equivalent if they don't map the same elements to the same elements.

    Regards

    Patrick
     
  17. Jul 29, 2006 #16

    0rthodontist

    User Avatar
    Science Advisor

    The point is that you are considering only one-to-one functions. If the elements of the first set were as you said, then you could simply order them "A, epsilon, 7, aleph" and each function would still be determined by writing four elements of the second set in some order next to those ordered elements of the first set. Of course, this representation would also satisfy the usual rules for equality of functions. It is just a way for denoting one-to-one functions. Often, as in this case, being able to denote something in a nice way tells you how to count it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Mapping of functions
  1. Function and Mapping (Replies: 9)

  2. Mapping Functions (Replies: 6)

Loading...