Kurs:Mathematik (Osnabrück 2009-2011)/Teil I/Vorlesung 3

Zählen

Der Sekundenanzeiger einer digitalen Uhr besitzt zwei Ziffern und „zählt“ von ${}00$ bis ${}59$ und fängt dann wieder bei ${}00$ an. Bei einem Countdown zählt man von ${}10$ bis ${}0$ und hört dann auf. Das natürliche Zählen startet bei ${}0$ und geht in Einerschritten gegen „unendlich“. Es gibt also verschiedene Arten, zu zählen, und diese wollen wir axiomatisch erfassen mit der Zielsetzung, letztlich das natürliche Zählen zu charakterisieren.

Definition (Zählsystem)

Eine Menge ${}M$ mit einem ausgezeichneten Element ${}0\in M$ und einer (Nachfolger-)Abbildung

$'\colon M\longrightarrow M,\,z\longmapsto z',$

heißt Zählsystem (oder induktives Zählsystem), wenn das folgende Induktionsaxiom erfüllt ist:

Für jede Teilmenge ${}T\subseteq M$ gilt: wenn die beiden Eigenschaften

• ${}0\in T$,

• mit jedem Element ${}z\in T$ ist auch ${}z'\in T$,

gelten, so ist ${}T=M$.

Das Induktionsaxiom hört sich komplizierter an, als es ist. Es fordert einfach, dass man ausgehend vom „Anfangsglied“ ${}0$ durch sukzessives Anwenden der Nachfolgerabbildung letztlich jedes Element in der Menge ${}M$ erhält. Die mengentheoretische Formulierung im Induktionsaxiom ist ein präziser Ersatz für „sukzessive“ und „letztlich“.

Das Zählen in der letzten Stelle eine digitalen Uhr ist ein Zählsystem: die zugrunde liegenden Menge ist

$M=\{0,1,2,3,4,5,6,7,8,9\},$

das ausgezeichnete Element ist ${}0$, und die Nachfolgerabbildung wird

(wenn wir uns hier noch nicht auf die natürlichen Zahlen berufen wollen) durch die Wertetabelle

${}x$	${}0$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$
${}x'$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$	${}0$

gegeben. Ausgehend von ${}0$ erreicht man dabei jedes Element als einen sukzessiven Nachfolger, so dass das Induktionsaxiom erfüllt ist. Die Nachfolgerabbildung ist dabei eine Bijektion.

Auch die folgende Wertetabelle beschreibt ein Zählsystem.

${}x$	${}0$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$
${}x'$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$	${}5$

Von ${}0$ ausgehend wird jedes Element erreicht. Die Nachfolgerabbildung ist nicht injektiv, sondern sowohl ${}4$ als auch ${}9$ werden beide auf ${}5$ abgebildet. Sie ist auch nicht surjektiv, da ${}0$ keinen Vorgänger hat.

Die Peano-Axiome

In den natürlichen Zahlen ${}\mathbb {N}$ kann man zwei Elemente ihrer Größe nach vergleichen, man kann sie addieren, multiplizieren, potenzieren, teilweise abziehen, es gibt die Teilbarkeit, usw. Man kann sich nun fragen, welche Abhängigkeiten zwischen diesen mathematischen Strukturen bestehen und ob man manche davon auf andere, grundlegendere Strukturen zurückführen kann. Dies führt zum axiomatischen Aufbau der natürlichen Zahlen. Mit den Peano-Axiomen werden die natürlichen Zahlen definiert als ein induktives Zählsystem, bei dem die Nachfolgerabbildung injektiv ist und ${}0$ kein Nachfolger ist.

Giuseppe Peano (1858 -1932)

Definition

Eine Menge ${}N$ mit einem ausgezeichneten Element ${}0\in N$ (die Null) und einer (Nachfolger)-Abbildung

$'\colon N\longrightarrow N,\,n\longmapsto n',$

heißt natürliche Zahlen (oder Dedekind-Peano-Modell für die natürlichen Zahlen), wenn die folgenden Dedekind-Peano-Axiome erfüllt sind.

1. Das Element ${}0$ ist kein Nachfolger (die Null liegt also nicht im Bild der Nachfolgerabbildung).
2. Jedes ${}n\in N$ ist Nachfolger höchstens eines Elementes (d.h. die Nachfolgerabbildung ist injektiv).
3. Für jede Teilmenge ${}T\subseteq N$ gilt: Wenn die beiden Eigenschaften
   • ${}0\in T$,
   • mit jedem Element
   ${}n\in T$ ist auch ${}n'\in T$,

gelten, so ist ${}T=N$.

Das heißt, dass die natürlichen Zahlen durch das natürliche Zählen bestimmt sind. Zählen heißt, von einem Startwert ausgehend, nach und nach einen Schritt (einen Strich machen, einen Stab dazulegen, einen Punkt dazumalen) weiterzuzählen. Das „Weiter“-Zählen ist also fundamentaler als eine bestimmte Benennung von Zahlen. Eine natürliche Zahl repräsentiert, wie oft bis zu ihr gezählt werden musste. Die erste Eigenschaft legt den Start fest. Die zweite Eigenschaft besagt, dass wenn zwei Zahlen verschieden sind (oder zwei endliche Mengen mit unterschiedlicher Anzahl vorliegen), dann auch die beiden jeweiligen Nachfolger verschieden sind (die beiden jeweils um ein neues Element erweiterten Mengen ebenfalls eine unterschiedliche Anzahl haben). Die dritte Eigenschaft, die man auch das Induktionsprinzip für Mengen nennt, besagt, dass wenn man bei null anfängt und keinen einzelnen Zählvorgang auslässt, dass man dann vollständig alle natürlichen Zahlen abzählt.

Es sei schon jetzt erwähnt, dass solche Überlegungen, die natürlichen Zahlen grundlegend zu begründen, manchmal eher verwirrend als hilfreich sein können. Bei den natürlichen Zahlen ist es erfahrungsgemäß nicht gefährlich, der Intuition zu vertrauen und mit einer naiven Vorstellung davon zu arbeiten (dies gilt für die reellen Zahlen nicht in dieser Deutlichkeit). Das ist beim Studienanfang jedenfalls wichtiger als Grundlagenfragen. Wir stellen einige Modelle für die natürlichen Zahlen vor.

Beispiel

Wir betrachten die Menge aller endlichen Strichketten, einschließlich der leeren Kette, also

$N=\{\emptyset ,\,{|},\,{|}{|},\,{|}{|}{|},\,{|}{|}{|}{|},\,{|}{|}{|}{|}{|},\,\ldots \}.$

Zwei Strichketten sind genau dann gleich, wenn sie „gleichlang“ sind. Das ausgezeichnete Element ist ${}0=\emptyset$. Die Nachfolgerabbildung ist dadurch gegeben, dass einer Strichkette ${}n$ die um einen Strich verlängerte Strichkette ${}n{|}$ zugeordnet wird.

Beispiel

Wir stellen ein Ziffernmodell (10er Modell) für die natürlichen Zahlen vor, das die Peanoaxiome erfüllt. Das Modell beruht auf endlichen Symbolketten, wobei die zugrunde gelegte Symbolmenge die Ziffernmenge

$Z=\{0,1,2,3,4,5,6,7,8,9\}$

ist. In diesem Modell ist eine natürliche Zahl eine endliche, nichtleere Hintereinanderreihung von Ziffern aus ${}Z$, deren erste Ziffer von der Ziffer ${}0$ verschieden ist, es sei denn, die Gesamtkette ist die ${}0$-Kette, die aus der einzigen Ziffer ${}0$ besteht. Zwei solche Zahlen sind genau dann gleich, wenn die Ziffernfolgen an jeder Ziffer übereinstimmen. Die ${}0$-Kette ist das ausgezeichnete Element.

Die Festlegung der Nachfolgerabbildung erfordert einige Vorbereitungen. Zunächst wird eine Abbildung

$Z\setminus \{9\}\longrightarrow Z,\,z\longmapsto {\tilde {z}},$

durch

${\tilde {0}}=1,{\tilde {1}}=2,{\tilde {2}}=3,{\tilde {3}}=4,{\tilde {4}}=5,{\tilde {5}}=6,{\tilde {6}}=7,{\tilde {7}}=8,{\tilde {8}}=9$

definiert. Ferner setzten wir ${}{\tilde {\emptyset }}=1$. Weiter wird auf der Menge der Ziffernfolgen, in denen ausschließlich die Ziffer ${}9$ vorkommt (wobei die leere Ziffernfolge zugelassen ist) die Abbildung ${}c\mapsto {\bar {c}}$ dadurch definiert, dass jede ${}9$ durch eine ${}0$ ersetzt wird. Man kann nun jede erlaubte endliche Ziffernfolge ${}z$ eindeutig schreiben als die Verkettung ${}z=abc$, wobei ${}c$ eine reine (eventuell leere) Neunerfolge ist, ${}b$ eine einzelne Ziffer ${}\neq 9$ oder leer ist, und ${}a$ eine beliebige endliche (eventuell leere) Ziffernfolge ist, die leer sein muss, wenn auch ${}b$ leer ist. Mit diesen Vorbereitungen definieren wir die Nachfolgerabbildung durch

$z':=(abc)':=a{\tilde {b}}{\bar {c}}.$

Die natürliche Zahlen haben den Sinn, die Größe von zwei endlichen Mengen miteinander zu vergleichen. Wenn man von zwei Mengen feststellen möchte, ob sie „gleich groß“ sind, so braucht man dafür aber zunächst nicht die natürlichen Zahlen als „neutrale Vergleichswerte“, sondern man kann die Mengen direkt untereinander mittels bijektiven Abbildungen vergleichen. Dies führt zum Begriff der Gleichmächtigkeit.

Definition (Gleichmächtigkeit von Mengen)

Zwei Mengen ${}L$ und ${}M$ heißen gleichmächtig, wenn es eine bijektive Abbildung

$\varphi \colon L\longrightarrow M$

gibt.

Ausgehend von der Gleichmächtigkeit von endlichen Mengen gelangt man zu einem weiteren Peano-Modell von natürlichen Zahlen als Äquivalenzklassen von endlichen Mengen, was wir hier nur kurz besprechen werden, siehe auch hier.

Beispiel

Ein Obstverkäufer verfüge über eine unendliche Menge ${}M$ von qualitativ gleichwertigen Äpfeln. Wenn man zu ihm geht und zehn Äpfel bestellt, so hat der Verkäufer verschiedene Möglichkeiten, diesen Wunsch zu verwirklichen, da ja jede Teilmenge seiner Gesamtmenge diesen Wunsch erfüllt, so lange sie eben genau aus ${}10$ Äpfeln besteht. Es sind also alle ${}10$-elementigen Teilmengen hinsichtlich ihrer Anzahl als gleichwertig zu betrachten, auch wenn es sich um jeweils andere Äpfel handelt. Eine wichtige Beobachtung hierbei ist, dass diese Gleichmächtigkeit (Gleichanzahligkeit) zwischen Teilmengen besteht und festgestellt werden kann unabhängig davon, ob man die natürlichen Zahlen schon kennt oder nicht. Sondern zu zwei Teilmengen kann man durch direkten Vergleich untereinander feststellen, ob sie beide aus gleich vielen Äpfeln bestehen oder nicht. Diese Gleichmächtigkeit definiert eine Äquivalenzrelation auf der Menge der endlichen Teilmengen der Gesamtmenge ${}M$.

Es gibt also zu jeder unendlichen Menge ${}M$ auf der Menge ${}{\mathcal {E}}(M)$ der endlichen Teilmengen von ${}M$ die Äquivalenzrelation der Gleichmächtigkeit. Zu jeder endlichen Teilmenge ${}T\subseteq M$ besteht die zugehörige Äquivalenzklasse aus sämtlichen Teilmengen von ${}M$, die man zu ${}T$ in Bijektion bringen kann, die also die gleiche Anzahl wie ${}T$ besitzen. Die leere Menge ist nur zu sich selbst äquivalent, alle einelementigen Teilmengen sind untereinander äquivalent, etc. Die Quotientenmenge zu dieser Äquivalenzrelation, also die Menge der Äquivalenzklassen, ist ein Peano-Modell für die natürlichen Zahlen. Die durch die leere Menge ${}\emptyset$ bestimmte Äquivalenzklasse ${}[\emptyset ]$ wird zum ausgezeichneten Element. Die Nachfolgerabbildung wird dadurch definiert, dass man zu einer Äquivalenzklasse ${}[T]$ die Menge ${}T$ zu einer Menge ${}T'=T\cup \{x\}$ mit ${}x\in M,\,x\not \in T$ erweitert, was möglich ist, da ${}T$ endlich ist und ${}M$ unendlich. Dann setzt man ${}[T]':=[T']$ und zeigt, dass dies unabhängig von der Wahl von ${}x$ und daher eine wohldefinierte Abbildung ist. Diese Quotientenmenge bildet ein Peano-Modell für die natürlichen Zahlen.

Von nun an arbeiten wir mit einem beliebigen Peano-Modell für die natürlichen Zahlen, das wir mit ${}\mathbb {N}$ bezeichnen.

Das Induktionsprinzip für Aussagen

Die folgende Aussage und ihr Beweis begründen das Beweisprinzip der vollständigen Induktion.

Satz (Induktionsprinzip)

Für jede natürliche Zahl ${}n$ sei eine Aussage ${}A(n)$ gegeben. Es gelte

1. ${}A(0)$ ist wahr.
2. Für alle ${}n$ gilt: wenn ${}A(n)$ gilt, so ist auch ${}A(n+1)$ wahr.

Dann gilt ${}A(n)$ für alle ${}n$.

Beweis

Es sei

${}M={\left\{n\in \mathbb {N} \mid A(n){\text{ ist wahr}}\right\}}\,.$

Wir wollen zeigen, dass ${}M=\mathbb {N}$ ist, denn genau dies bedeutet, dass die Aussage für alle ${}n$ gilt. Nach der ersten Bedingung ist

${}0\in M\,.$

Nach der zweiten Voraussetzung gilt für ${}M$, dass aus ${}n\in M$ stets ${}n+1\in M$ folgt. Damit erfüllt ${}M$ beide Voraussetzungen im Induktionsprinzip für Mengen, sodass ${}M=\mathbb {N}$ gilt.

$\Box$

Alle mathematischen Strukturen auf den natürlichen Zahlen kann man ausgehend von den Peanoaxiomen konstruieren und ihre Eigenschaften beweisen. Wir werden dies in dieser Vorlesung nur teilweise tun. Der Haupteinwand gegen eine streng durchgeführte mengentheoretisch-axiomatische Deduktion der Strukturen auf den natürlichen Zahlen aus den Peanoaxiomen heraus liegt darin, dass der Aufwand (und zwar hinsichtlich der Arbeit, der Zeit und der Konzentration) unverhältnismäßig erscheint gegenüber dem Nutzen, Strukturen zu begründen, mit denen die Studierenden seit langem wohlvertraut sind. Weiterhin ist schwer zu vermitteln, dass die Sprache der Mengen fundamentaler als die natürlichen Zahlen selbst sein soll. Allerdings ist es schon eine wichtige Erkenntnis, dass nicht alle Operationen auf den natürlichen Zahlen gleichursprünglich sind, sondern dass es zwischen ihnen Abhängigkeiten und Hierarchien gibt. Wir werden nun schrittweise die wesentlichen Strukturen auf den natürlichen Zahlen einführen und dabei parallel das passende Vokabular wie Ordnungsrelationen oder Verknüpfungen einführen.

Wir beginnen mit der Größergleichbeziehung, die wir ${}\geq$ schreiben. Für zwei natürliche Zahlen ${}k,n\in N$ gilt ${}k\geq n$, wenn man von ${}n$ ausgehend durch wiederholtes Nachfolgernehmen schließlich zu ${}k$ gelangt, also

$k\geq n{\text{ genau dann, wenn }}k=n^{\prime \prime \prime \cdots \prime \prime \prime }.$

Diese Definition ist intuitiv klar, aber nicht streng axiomatisch, da die angedeuteten Punkte (mengentheoretisch) unpräzise sind. Eine mengentheoretische Fundierung dieser Beziehung ist etwas aufwändig, siehe hier. Wir geben uns mit der obigen Einführung zufrieden, betonen aber, dass wir die Größergleichrelation auf die Nachfolgeabbildung zurückführen. Um die wesentlichen Eigenschaften der Größergleichrelation formulieren zu können, brauchen wir den Begriff der Ordnungsrelation.

Ordnungsrelationen

Eine reflexive, transitive und antisymmetrische Relation nennt man eine Ordnung, wofür man häufig ein Symbol wie ${}\geq ,\leq ,\preccurlyeq ,\subseteq$ verwendet.

Definition (Ordnungsrelation)

Eine Relation ${}\preccurlyeq$ auf einer Menge ${}I$ heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

1. Es ist ${}i\preccurlyeq i$ für alle ${}i\in I$.
2. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq k$ folgt stets ${}i\preccurlyeq k$.
3. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq i$ folgt ${}i=j$.

Eine Menge mit einer fixierten Ordnung darauf heißt geordnete Menge. Wenn zusätzlich gilt, dass für je zwei Elemente ${}x\preccurlyeq y$ oder ${}y\preccurlyeq x$ gilt, so spricht man von einer total geordneten Menge.

Beispiel (Inklusionsrelation auf Potenzmenge)

Es sei ${}M$ eine beliebige Menge und ${}R={\mathfrak {P}}\,(M)$ die Potenzmenge davon. Dann sind die Elemente aus ${}R={\mathfrak {P}}\,(M)$ - also die Teilmengen von ${}M$ - durch die Inklusionsbeziehung ${}\subseteq$ geordnet. Die Reflexivität bedeutet einfach, dass eine jede Menge in sich selbst enthalten ist und die Transitivität bedeutet, dass aus ${}T_{1}\subseteq T_{2}$ und ${}T_{2}\subseteq T_{3}$ die Inklusion ${}T_{1}\subseteq T_{3}$ folgt. Die Antisymmetrie ist dabei ein wichtiges Beweisprinzip für die Gleichheit von Mengen: Zwei Mengen ${}T_{1},T_{2}$ sind genau dann gleich, wenn ${}T_{1}\subseteq T_{2}$ und umgekehrt ${}T_{2}\subseteq T_{1}$ gilt.

Beispiel (Teilerbeziehung)

Wir betrachten die positiven ganzen Zahlen ${}\mathbb {N} _{+}$ zusammen mit der Teilbarkeitsbeziehung. Man sagt, dass eine Zahl ${}k$ die Zahl ${}n$ teilt, geschrieben

$k{|}n,$

wenn es eine weitere natürliche Zahl ${}m$ mit

${}n=km$ gibt. Die Bezeichnung ist nicht sonderlich glücklich gewählt, da ein symmetrisches Symbol für eine nichtsymmetrische Relation verwendet wird. Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets ${}n{|}n$ ist, wie ${}m=1$ zeigt. Die Transitivität sieht man so: sei ${}k{|}n$ und ${}n{|}m$ mit ${}n=ak$ und ${}m=bn$. Dann ist ${}m=bn=bak$ und daher ${}k{|}m$. Die Antisymmetrie folgt so: Aus ${}n=ak$ und ${}k=bn$ folgt ${}n=(ab)n$. Da wir uns auf positive natürliche Zahlen beschränken, folgt ${}ab=1$ und daraus ${}a=b=1$. Also ist ${}k=n$ Einfache Beispiele wie $2$ und $3$ zeigen, dass hier keine totale Ordnung vorliegt, da weder ${}2$ von ${}3$ noch umgekehrt geteilt wird.

Die Ordnungsrelation auf den natürlichen Zahlen

Wir kommen nun zu den natürlichen Zahlen zurück.

Lemma

Es sei ${}(\mathbb {N} ,0,')$ ein Peano-Modell der natürlichen Zahlen. Dann ist die Größergleichrelation ${}\geq$ eine totale Ordnung.

Beweis

Die Reflexivität und die Transitivität sind klar. Zum Beweis der Antisymmetrie sei ${}x\leq y$ und ${}y\leq x$, es gibt also endliche Nachfolgerketten ${}\alpha$ und ${}\beta$ (also endliche Strichketten ${}\prime \prime \prime \ldots \prime \prime \prime$) mit ${}y=x^{\alpha }$ und ${}x=y^{\beta }$. Damit ist ${}x^{\alpha \beta }=x$, wobei ${}\gamma =\alpha \beta$ einfach die Hintereinanderkettung der Strichketten bedeutet. Wir haben zu zeigen, dass ${}\gamma$ die leere Strichkette ist (dann ist auch ${}\alpha$ die leere Strichkette und somit ${}x=y$.). Wir zeigen durch Induktion, dass aus ${}x^{\gamma }=x$ folgt, dass ${}\gamma =\emptyset$ ist. Bei ${}x=0$ wäre andernfalls ${}x=x^{\gamma }=(x^{\delta })^{\prime }$, wobei ${}\delta$ aus ${}\gamma$ dadurch entsteht, dass man einen Strich weglässt, was man kann, sobald es mindestens einen Strich in ${}\gamma$ gibt. Doch dann wäre ${}0$ ein Nachfolger. Es sei die Aussage nun für ${}x$ bewiesen und sei ${}x^{\prime }=(x^{\prime })^{\gamma }$. Dies kann man schreiben als ${}x^{\prime }=x^{\gamma \prime }=(x^{\gamma })^{\prime }$. Wegen der Injektivität der Nachfolgerabbildung folgt ${}x=x^{\gamma }$, also ${}\gamma =\emptyset$ nach Induktionsvoraussetzung.

Wir beweisen nun, dass die Ordnung total ist, und zwar beweisen wir durch Induktion über ${}n$ die Aussage, dass für jedes ${}x\in \mathbb {N}$ die Aussage ${}x\geq n$ oder ${}n\geq x$ wahr ist. Bei ${}n=0$ gilt die erste Alternative für jedes ${}x$ und damit die Gesamtaussage. Es sei nun die Aussage für ${}n$ schon bewiesen und betrachten wir ${}n^{\prime }$ und ein beliebiges ${}x$. Nach Induktionsvoraussetzung ist ${}x\geq n$ oder ${}n\geq x$. Bei ${}n\geq x$ ist auch ${}n^{\prime }\geq n\geq x$ und also ${}n^{\prime }\geq x$ wegen der Transitivität. Es sei also ${}n\leq x$. Bei ${}n=x$ sind wir wieder im ersten Fall, sodass wir also ${}n<x$ annehmen dürfen. Daher ist ${}x=n^{\alpha }$ mit einer nichtleeren Strichkette ${}\alpha$, und damit ist ${}x$ auch ein sukzessiver Nachfolger von ${}n^{\prime }$, also ${}x\geq n^{\prime }$.

$\Box$

Zu zwei Elementen ${}n,k\in N$ verwenden wir die abkürzenden Schreibweisen

$\{k,\ldots ,n\}={\left\{x\in N\mid x\geq k{\text{ und }}x\leq n\right\}}.$

Hierbei ist ${}k>n$ zwar erlaubt, führt aber zur leeren Menge. Besonders wichtig sind die Mengen ${}\{1,\ldots ,n\}$, da diese die Parademengen für die ${}n$-elementigen endlichen Mengen sind.

Zählen und endliche Mengen

Definition

Eine Menge ${}M$ heißt endlich mit ${}n$ Elementen, wenn es eine Bijektion

$\{1,\ldots ,n\}\longrightarrow M$

gibt.

Die natürliche Zahl ${}n$ ist dabei nach Aufgabe 3.10 eindeutig bestimmt und heißt die Anzahl (oder die Kardinalität) der Menge. Sie wird mit ${}{\#\left(M\right)}$ oder mit ${}\vert {M}\vert$ bezeichnet. Die bijektive Abbildung

$\{1,\ldots ,n\}\longrightarrow M$

kann man eine Nummerierung der Menge ${}M$ nennen. Eine Menge besitzt also ${}n$ Elemente, wenn man sie mit den natürlichen Zahlen von ${}1$ bis ${}n$ durchnummerieren kann. Zwei endliche Mengen ${}M$ und ${}N$, für die es eine Bijektion

$M\longrightarrow N$

gibt, besitzen die gleiche Anzahl. Dies beruht einfach darauf, dass diese Bijektion verknüpft mit der bijektiven Nummerierung wieder eine Bijektion ist. Eine Menge, die nicht endlich ist, für die es also keine Bijektion mit ${}{\{1,\ldots ,n\}}$ für kein ${}n$ gibt, heißt unendlich.

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 3.12 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 3.20 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, sodass nach der Induktionsvoraussetzung hier eine Bijektion vorliegt. Damit ist auch die ursprüngliche Abbildung eine Bijektion.

$\Box$

Fußnoten

<< | Kurs:Mathematik (Osnabrück 2009-2011)/Teil I | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)