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]


This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

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

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint
© 2018 Powered by BooOfProofs, All rights reserved.