- #1
- 858
- 918
Homework Statement
Let there be exactly n elements in X and exactly m elements in Y. How many different functions f: X -> Y can we form? How many different injections, surjections (and bijections for that matter)? (There is no further info on m, n.)
Homework Equations
The Attempt at a Solution
In X we have 2n subsets and in Y we have 2m subsets.
Just to try out where I end up, I'll let X = {a,b,c,d}, Y= {0,1,2,3,4}.
We have 16 subsets of X and for every subset in X we have 32 different subsets in Y. By that logic we could have 2n+m different functions.
First question:
What can we say about, for example f : {a,b,c} -> {0,1,2,3,4}? Since it's a function, no argument can have more than one image. Can such an expression be a function? It can't be surjective, since there doesn't exist an original for every element in the image.
What happens when we consider f : {a,b,c,d} -> {1,2}? Is this a surjection? There exists an original for every element in the image.
Don't want to presume too much. I'd like you to tell me if I am heading in the right direction in my reasoning and if not, where have I made a mistake?
Thanks