**Proof**: *(related to "More Characterizations of Finite Sets")*

By hypothesis, $X$ is a finite set.

### Ad $(1)$

- Let $f:X\to X$ be surjective.
- We have to show that $f$ is injective.
- Assume $f$ wasn’t injective. Then there would exist some $v_1,v_2\in X$ with $x_1\neq x_1$ but $f(x_1)=f(x_2).$
- Since, in this case, at least $2$ elements $x_1,x_2$ of $X$ were mapped to a single element $f(x_1)=f(x_2)$ and because $X$ is finite, this would mean that there is an $y\in X$ such that no $x\in X$ are left with $f(x)=y$. But this would contradict the surjectivity of $f$.
- Therefore, $f$ is injective.

### $(2)$

- Let $f:X\to X$ be injective.
- We have to show that $f$ is surjective.
- Assume $f$ wasn’t surjective. Then there would exist some $x_0\in X$ for which there is no $x\in X$ with $f(x)=x_0$, i.e. for the fiber $f^{-1}(x_0)=\emptyset.$
- Since $f$ is injective, we have for all $x_1,x_2\in X$ with $x_1\neq x_2$ that $f(x_1)\neq f(x_2).$
- We can therefore define a function $g:X\to X$ by $$g(x):=\begin{cases}z\in f^{-1}(x)&\text{ if }f^{-1}(x)\neq \emptyset,\\x_0&\text{ else.}\end{cases}$$
- Since for all $y\in X$ we have $y=g(f(y))$, we see that $g$ is surjective, and we have $x_0=g(f(x_0))$.
- By $(1)$, $g$ is injective.
- By definition of bijective functions, $g$ is bijective.
- Since $X$ is finite, $g^{-1}(x_0)$ has no other elements, except of $f(x_0).$
- This means that $f^{-1}(x_0)\neq\emptyset$, in contradiction to $f^{-1}(x_0)=\emptyset.$
- Therefore, $f$ is surjective.

q.e.d

| | | | created: 2019-01-27 11:16:29 | modified: 2019-01-28 07:33:57 | by: *bookofproofs* | references: [577]

(none)

[577] **Knauer Ulrich**: “Diskrete Strukturen – kurz gefasst”, Spektrum Akademischer Verlag, 2001

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint

© 2018 Powered by BooOfProofs, All rights reserved.

© 2018 Powered by BooOfProofs, All rights reserved.