# Confusion surrounding functions

Hey there Mathematics,

Slightly confused over some of the things in my quiz and was wondering if I could get an explanation:

I thought with the first question that it's just one-to-one from X to Y and onto from Y to X, as Y would make sure all the elements within x were mapped to (or is this a trick question, since f(X)->Y : Y cannot map to X?)

If |X| = 3 and |Y| = 5, which of the following exist?

A) one-to-one function from X into Y

B) An onto function from X onto Y

C) one-to-one function from Y into X

D) An onto function from Y onto X

and

If |X| = 2 and |Y| = 3, how many functions are there from X into Y?

the numbers range 0 - 9

• Your observations concerning the first question are correct. For the second one, notice that if $X = \{x_1, x_2\}$, then you have $3$ choices where to map $x_1$ and $3$ choices where to map $x_2$. Hence, there are $3 \times 3 = 9$ functions from $X$ into $Y$. – Amateur Apr 6 '14 at 2:51

## 1 Answer

Here are some things to consider-

A one-to-one function states that $f(a) = f(b) \implies a = b$. What happens if $|X| > |Y|$? By the pidgeonhole principle, won't you have at least two elements in $X$ mapping to the same element in $Y$? So an injection gives you that $|X| \leq |Y|$.

Similarly, consider an onto function. That states that every element in $Y$ is covered. So what happens if $|Y| > |X|$? Then you will have an uncovered element, right? So onto gives us that $|Y| \leq |X|$.

And so bijection can occur only when $|X| = |Y|$.

And so your initial intuition was correct.