Welcome guest
You're not logged in.
151 users online, thereof 1 logged in

## 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)

### Bibliography (further reading)

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