Benutzer:Bocardodarapti/Arbeitsseite/BEU

\Box

„Der Mensch tut alles, um sich vor der wahren Arbeit des Nachdenkens zu drücken“

Thomas Alva Edison

Lemma

Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen und ${}N$ eine endliche Menge mit ${}n$ Elementen. Es sei ${}m>n$ .

Dann gibt es keine injektive Abbildung

$M\longrightarrow N.$

Beweis

Wir nehmen an, dass es eine injektive Abbildung

\varphi \colon M\longrightarrow N

gibt. Es sei ${}T=\varphi (M)\subseteq N$ das Bild von ${}M$ unter der Abbildung ${}\varphi$ . Dann ergibt sich eine Bijektion

{\tilde {\varphi }}\colon M\longrightarrow T,

da sich die Injektivität überträgt und da eine Abbildung immer surjektiv auf ihr Bild ist. Daher haben ${}M$ und ${}T$ gleich viele Elemente. Nach Aufgabe ist die Anzahl einer Teilmenge stets kleiner oder gleich der Anzahl der Menge. Also ist ${}m\leq n$ im Widerspruch zur Voraussetzung.

\Box

Die vorstehende Aussage heißt Schubfachprinzip (oder Taubenschlagprinzip). Es besagt, dass wenn man ${}m$ Tauben auf ${}n$ Plätze verteilt mit ${}m>n$ , dass dann in mindestens einem Platz mindestens zwei Tauben landen.

Lemma

Seien ${}M$ und ${}N$ endliche Mengen mit ${}n$ Elementen. Dann sind für eine Abbildung

F\colon M\longrightarrow N

die Begriffe injektiv, surjektiv und bijektiv äquivalent.

Beweis

Wir führen Induktion über die Anzahl ${}n$ der beiden Mengen ${}M$ und ${}N$ . Bei ${}n=0$ gibt es nur die leere Abbildung (von der leeren Menge in die leere Menge), und diese erfüllt alle drei Eigenschaften. Es sei nun ${}n\geq 1$ und die Aussage für alle endlichen Mengen ${}M$ mit einer Anzahl ${}<n$ bewiesen. Es muss lediglich die Äquivalenz von injektiv und surjektiv gezeigt werden. Es sei zunächst ${}F$ injektiv. Wir wählen ein Element ${}x\in M$ und setzen ${}y=F(x)$ . Wir setzen

M'=M\setminus \{x\}{\text{ und }}N'=N\setminus \{y\}.

Beide Mengen haben nach Fakt ${}n-1$ Elemente, und somit kann man darauf die Induktionsvoraussetzung anwenden. Es sei

F'\colon M'\longrightarrow N',\,x\longmapsto F(x).

Diese Abbildung ist wohldefiniert, da wegen der Injektivität nur das Element ${}x$ auf ${}y$ abgebildet wird, alle anderen Elemente aus ${}M'$ werden auf andere Elemente abgebildet, d.h. sie landen in ${}N'$ . Die Injektivität von ${}F$ überträgt sich auf die Teilmenge ${}M'$ . Nach der Induktionsvoraussetzung ist also ${}F'$ surjektiv. Damit ist aber insgesamt ${}F$ surjektiv, da einerseits ${}y$ im Bild liegt (mit ${}x$ als Urbild) und da andererseits jedes Element ${}z\neq y$ zu ${}N'$ gehört und damit ein Urbild in ${}M'$ besitzt.

Es sei nun ${}F$ surjektiv. Sei ${}x\in M$ beliebig und ${}y=F(x)$ . Wir betrachten die Einschränkung

F'\colon M'=M\setminus \{x\}\longrightarrow N.

Diese Abbildung kann nicht surjektiv sein. Andernfalls würde sich nämlich der Widerspruch (hier geht auch Aufgabe ein)

{}n={\#\left(M\right)}>{\#\left(M\setminus \{x\}\right)}\geq {\#\left(F(M\setminus \{x\})\right)}={\#\left(N\right)}=n\,

ergeben. Daher muss ${}y$ im Bild von ${}F'$ fehlen, und das heißt, dass eine surjektive Abbildung

M\setminus \{x\}\longrightarrow N\setminus \{y\}

vorliegt. Beide Mengen besitzen ${}n-1$ Elemente, so dass nach der Induktionsvoraussetzung hier eine Bijektion vorliegt. Damit ist auch die ursprüngliche Abbildung eine Bijektion.

\Box