1
$\begingroup$

Prove that for finite set $X$, the function $f:X \to X$ is surjective if and only if it is injective

I have the idea of proof in my mind but find it difficult to translate it into mathematical language.

If $f$ is surjective then every element of $X$ will be hit, but the source and the target are exactly the same, hence it must be that every element in the source hit another element in the target, and no two elements in the source that hit the same target. Hence I prove $f$ is injective. In the same way I can prove the reverse statement.

How can I translate this into rigorous mathematical language?

$\endgroup$
  • 1
    $\begingroup$ First make yourself clear about all definitions involved. For example, what is your definition of "finite set"? Also, when looking for a proof it may sometimes be helpful how the claim fails if one of the premises fails: Can you given an example fo $X$ infinite, $f$ surjective and not injective, or $f$ injective and not surjective? $\endgroup$ – Hagen von Eitzen Nov 27 '15 at 12:05
  • $\begingroup$ Your intuition is good. Have you encountered the Pigeonhole Principle? You might find the following question useful: math.stackexchange.com/questions/989043/… $\endgroup$ – Luke Hamblin Nov 27 '15 at 12:08
  • $\begingroup$ Your argument does not use the finiteness of $X.$ $\endgroup$ – Justpassingby Nov 27 '15 at 12:09
2
$\begingroup$

You can do this by induction over the size of $X$ Or rather prove something stronger: If $f:Y\rightarrow Z$ is a function between sets of equal size, then $f$ is injective if and only if $f$ is surjective

Base: $|Y|=|Z|= 1$ (or possibly $0$ but that is completely trivial), then every function is both surjective and injective.

Induction assumption: If $f:Y\rightarrow Z$ is a function on a sets $Y$ and $Z$ of size $n$ then $f$ is surjective if and only if $f$ is injective.

Induction step: Assume $f:X\rightarrow W$ where $|X|=|W|=n+1$.

Assume $f$ is injective. Choose an element $a\in X$. The function $g:(X-\{a\})\rightarrow (W-\{f(a)\})$ such that $g(b)=f(b)$ for each $b\in X-\{a\}$ is then also an injective function between two sets of size $n$, and thus by induction assumption $g$ is surjective. However then each element in $W-\{f(a)\}$ is mapped to by something in $X-\{a\}$ and thus $f$ is surjective.

Assume $f$ is surjective. Choose an element $c\in W$ and assume that $f(a)=b$ for some $a\in X$. Again the function $g:(X-\{a\})\rightarrow (W-\{f(a)\})$ such that $g(b)=f(b)$ for each $b\in X-\{a\}$ is then also a surjective function between two sets of size $n$, thus the induction assumption implies that $g$ is injective. As $f(a)$ is not in the range of $g$, this implies that $f$ is injective.

This concludes the induction.

$\endgroup$
0
$\begingroup$

Let $|X| = n$. Suppose we have $x_1, x_2 \in X$ such that $f(x_1) = f(x_2)$. Now we should have another $n - 1$ distinct values of $f(x)$. By Pigeonhole Principle for the rest $n - 2$ elements of $X$ we can have no more than $n - 2$ distinct values of $f(x)$. Thus, $f(x_1) \neq f(x_2)$ for all $x_1, x_2$.

$\endgroup$
0
$\begingroup$

As $Card (X)= \sum _{y\in f(X)} Card(f^{-1}(y)$, we have $Card(X)-Card(f(X))= \sum _{y\in f(X)} (Card(f^{-1}(y)-1)$ Thus $f$ is onto iff the LHS is $0$ iff for every $y\in f(X)$, $Card(f^{-1}(y)=1$ iff $f$ is injective.

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