Zwei Mengen/Mächtigkeitsbeziehung/Injektiv und Surjektiv/Fakt/Beweis

Beweis

${}(1)\Rightarrow (2)$. Wenn ${}N$ leer ist, so kann man die leere Abbildung ${}\emptyset \rightarrow M$ nehmen. Es sei also  ${}N\neq \emptyset$  und sei

$\varphi \colon M\longrightarrow N$

surjektiv. Zu jedem  ${}y\in N$  gibt es ein  ${}x\in M$  mit  ${}\varphi (x)=y$.  Wir wählen für jedes ${}y$ ein solches ${}x_{y}$ aus und definieren ${}\psi$ durch

$\psi \colon N\longrightarrow M,\,y\longmapsto \psi (y)=x_{y}.$

Wegen  ${}\varphi (\psi (y))=y$  ist ${}\psi$ injektiv.

${}(2)\Rightarrow (1)$. Es sei nun eine injektive Abbildung

$\psi \colon N\longrightarrow M$

gegeben. Diese induziert eine Bijektion zwischen ${}N$ und dem Bild von ${}\psi$, sei ${}\theta \colon N\rightarrow \operatorname {bild} \psi$ diese Abbildung. Wenn ${}N$ leer ist, so sind wir fertig. Es sei also  ${}N\neq \emptyset$  und sei  ${}c\in N$  ein fixiertes Element. Wir definieren

$\varphi \colon M\longrightarrow N$

durch

${}\varphi (x)={\begin{cases}\theta ^{-1}(x),\,{\text{ falls }}x\in \operatorname {bild} \psi \,,\\c{\text{ sonst}}\,.\end{cases}}\,$

Diese Abbildung ist wegen  ${}\varphi (\theta (y))=y$  surjektiv.

Zur bewiesenen Aussage