0
$\begingroup$

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.$

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ You are brilliant. Thank you so much! $\endgroup$ – Retty Mar 16 '17 at 10:20
  • $\begingroup$ @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$. $\endgroup$ – Student Mar 16 '17 at 10:23
  • $\begingroup$ Funnily enough, that is the next exercise. Thanks again. $\endgroup$ – Retty Mar 16 '17 at 10:27
1
$\begingroup$

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| $$

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.