# Showing that if $f$ is surjective, then $m\geq n$ holds (where $m$ and $n$ are the number of elements in the domain and codomain respectively)

Let $X$ and $Y$ be sets with $m$ and $n$ elements respectively and let $f:X\rightarrow Y$ be a function from $X$ to $Y$.

Show that if $f$ is surjective, then $m\geq n$.

I know this should be true since in words a surjective can be seen as:

"For every element in the codomain, there is at least one element of the domain mapping onto it".

I'm having trouble converting this idea into a proof. My guess is I need to show that at least $n$ maps from $Y$ to $X$ are possible for distinct values of $x$. If this is the case, we can assert $m \geq n$.

So far I basically have the definition with quantifiers.

Proof: Show than at least $n$ distinct maps from the codomian, back to the domain are possible.

Since $f$ is surjective, $\forall y \in Y, \exists x \in X : f(x) = y.$

Let us prove this by contradiction, so suppose $f$ is surjective and $m < n$. Since $m < n$, we have that $m + k = n$ for some natural number $k > 0$.

Let us denote the set $X = \{x_1, x_2, \ldots x_m\}$ and $Y = \{y_1, \ldots y_m, y_{m+1}, \ldots, y_{m+k}\}$. Consider the first $m$ elements of $Y$, then without loss of generality, we can assume that $f(x_i) = y_i$ for $i \in \{1, \ldots, m\}$ (we may assume this, since we can simply swithch the indices of the elements to make this work). But then we have that there is no element $x \in X$ such that $f(x) = y_{m+1}$ (since a function maps each $x$ to exactly one element $y \in Y$). Hence the map $f$ is not surjective, which is a contradiction. Therefore, our assumption $m < n$ is false and we find that $m \geq n$.

• You are brilliant. Thank you so much! – Retty Mar 16 '17 at 10:20
• @Retty you are welcome. If you got this, then a nice exercise might be to prove that if $f$ is injective, then we have that $m \leq n$. – Student Mar 16 '17 at 10:23
• Funnily enough, that is the next exercise. Thanks again. – Retty Mar 16 '17 at 10:27

For each $y\in Y$, let $N(y)$ be the number of elements in $X$ that are mapped to $y$.

Then $\sum_{y\in Y} N(y) = |X|$ because every element of $X$ is mapped to some element of $Y$ and the fibers of $f$ partition $X$.

If $f$ is surjective, then $N(y)\ge 1$ for all $y \in Y$. Therefore $$|Y|=\sum_{y\in Y} 1 \le \sum_{y\in Y} N(y) = |X|$$

If $f$ is injective, then $N(y)\le 1$ for all $y \in Y$. Therefore $$|Y|=\sum_{y\in Y} 1 \ge \sum_{y\in Y} N(y) = |X|$$

Hint: The inverse of $f$ lets us define an injection between $Y$ and a subset of $X$.