# Discrete maths onto and one to one question

If I have \begin{align} X &= \{a, b, c, d, e\} \\ Y &= \{g, h, i\}\\ Z &= \{j, k, l, m, n, o \}\\ \end{align} how do I write an onto function from $X$ to $Y$? Also, how do I write an one to one function from $X$ to $Z$?

Am I right to say that for the one to one function, $X$ to $Z = \{(a,j), (b,k), (c,l), (d,m), (e,n)\}$?

As for the onto function, I have to write out $4! = 24$?

Edit: onto function from $X$ to $Y = \{(a,g),(b,h), (c, i), (d,g), (e, h)\}$ something like this? But as for the one to one function. There's $5$ elements in $X$ and $6$ elements in $Z$, so it's ok leave one out?

-

You have given one example of a one to one function $X\to Z$. There are others, but one is sufficient.

There are $540$ onto functions $X\to Y$, I'm not sure where you got $4!$ from. Again, it seems as if you need only find one example. If you're writing the functions in terms of sets, you need some set of $5$ pairs such that each element of $Y$ is the second entry in one of those pairs. The example you added satisfies this.

-
Are you sure about the $90$? – Thomas Feb 4 '13 at 15:50
No - thanks! But it shouldn't be $60$ either, when you've hit the $3$ elements of $Y$ there are still $2$ elements of $X$ to be mapped to $Y$, and $3$ possible images for each of them, so there are $540$ maps. – Matthew Pressland Feb 4 '13 at 15:54
You are right. Together we found the right one :) – Thomas Feb 4 '13 at 15:55
I find that it usually takes two people to do combinatorics correctly! – Matthew Pressland Feb 4 '13 at 15:59

Your one-to-one function is correct. The idea is just that each element in $Z$ is only reached once and you have defined the function on each element in the domain $X$.

For the onto function that you have suggested in your edit, that is also correct. You reach all the elements and you have defined the function for each element in $X$.

As for the number of onto functions from $X$ to $Z$ note that you have to reach each element in $Y$ and you have to map each element in $X$ to something. So for each element in $Y$ you think about the number of ways that this element can be reached. For example you need to map somethin to $g$ ($5$ ways to do that) then you have will have $4$ ways to map to $h$ and after picking that, you have $3$ ways to map to $i$. Now you have then $5\cdot 4\cdot 3 = 60$ onto functions that map three elements in $X$ to something in $Y$. However, you also need to map the last two elements in $X$ to something in $Y$. Each element can be mapped to any of the three elements in $Y$. So in all you get $5\cdot 4\cdot 3 \cdot 3\cdot 3 = 540$ onto maps.

If you want to make an one-to-one function from $X$ to $Z$ you can leave out an element from $Z$. The important thing is that each element in the range is only reached once. In fact what you see is that you can't make an onto function from $X$ to $Z$.

-