Kurs:Grundkurs Mathematik (Osnabrück 2022-2023)/Teil I/Vorlesung 7

... dass jeder und jede meint, dass Vorli ihn oder sie ganz besonders mag.

In der vorletzten Vorlesung haben wir uns zuerst mit dem Zählen in dem Sinne beschäftigt, dass auf eine natürliche Zahl eine eindeutig bestimmte natürliche Zahl, nämlich ihr Nachfolger, folgt. In dieser und den folgenden Vorlesungen werden wir sehen, dass diese Eigenschaft die natürlichen Zahlen auszeichnet und dass man alle anderen Eigenschaften der natürlichen Zahlen, wie beispielsweise die Rechengesetze, letztlich darauf zurückführen kann. Auf dieser Eigenschaft der natürlichen Zahlen beruht auch das Beweisprinzip der vollständigen Induktion.

Die Dedekind-Peano-Axiome

In den natürlichen Zahlen ${}\mathbb {N}$ kann man addieren, multiplizieren, potenzieren, teilweise abziehen, es gibt die Größergleich-Relation, die Teilbarkeit, usw. Man kann sich nun fragen, welche Abhängigkeiten (logische Hierarchien) 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. Dies ist lediglich eine weitere Präzisierung des Zählvorgangs in der Sprache der Mengen und Abbildungen.

Richard Dedekind (1831 -1916)

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$.

Man mache sich klar, dass diese Bedingungen den Bedingungen der vorletzten Vorlesung entsprechen. Dabei ist ${}N$ die jeweilige Menge, ${}\prime$ bezeichnet die Nachfolgerabbildung und ${}0$ das Startsymbol (dort hatten wir zumeist ${}1$ als Startsymbol gewählt). Jedes Dedekind-Peano-Modell sieht ähnlich aus wie eine der dort aufgelisteten Möglichkeiten. 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, oder ein komplexeres Bildungsgesetz) 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, dann auch die beiden jeweiligen Nachfolger verschieden sind. Die dritte Eigenschaft, die man auch das Induktionsprinzip für Mengen nennt, besagt, dass wenn man bei ${}0$ anfängt und keinen einzelnen Zählvorgang auslässt, dass man dann vollständig alle natürlichen Zahlen abzählt.

Es sei erwähnt, dass solche Überlegungen, die natürlichen Zahlen grundlegend zu begründen, manchmal eher verwirrend als hilfreich sein können. Statt des intuitiven Zählens arbeiten wir mit den abstrakten Konzepten Mengen, Abbildungen, Injektivität. Bei den natürlichen Zahlen ist es erfahrungsgemäß nicht gefährlich, der Zähl-Intuition zu vertrauen und mit einer naiven Vorstellung davon zu arbeiten (dies gilt für die reellen Zahlen nicht in dieser Deutlichkeit).

Wir benennen explizit die intellektuelle Leistungen, die durch die axiomatische Fixierung der natürlichen Zahlen erbracht wird.

1. Es werden kurz und präzise die entscheidenden strukturellen Eigenschaften der natürlichen Zahlen fixiert.
2. Diese Eigenschaften werden begrifflich explizit gemacht.
3. Die natürlichen Zahlen liegen als ein Konzept vor, das unabhängig von bestimmten Symbolen und Benennungen ist.
4. Es kann bewiesen werden, dass durch diese Eigenschaften die natürlichen Zahlen eindeutig festgelegt sind.
5. Der Zugang ermöglicht, andere Operationen darauf zurückzuführen, also komplexere Strukturen auf einfachere zurückzuführen.
6. Der Zugang (insbesondere die Verankerung im Zählen und die darauf aufbauende Entwicklung der weiteren Rechenoperationen) weist eine große Übereinstimmung mit dem natürlichen Lernprozess auf!
7. Die begriffliche Fixierung ermöglicht es, über den Zugang zu reflektieren und sich darüber auszutauschen.

In einem Dedekind-Peano-Modell gibt es die untereinander verschiedenen Elemente

$0,0^{\prime },0^{\prime \prime },0^{\prime \prime \prime },....$

Hier stehen also alle Elemente, die von ${}0$ aus in endlich vielen Schritten (man denke an die Abzählung endlicher Prozesse) erreicht werden können (formal-mengentheoretisch ist diese Definition problematisch, da sie Bezug auf eine endliche Ausführung nimmt). Das Induktionsaxiom sichert, dass dies bereits alle Elemente des Modells sind. Die angegebene Teilmenge enthält ja die ${}0$ und mit jedem Element auch deren Nachfolger, also ist es die Gesamtmenge.

Ausgehend von den Peano-Axiomen kann man eine Addition auf der Menge der natürlichen Zahlen definieren, wobei die Nachfolgerfunktion der Addition mit ${}1=0'$ entspricht. Die Definierbarkeit beruht selbst auf dem Induktionsprinzip. Ebenso kann man eine Multiplikation definieren und die üblichen Eigenschaften wie Kommutativität und Assoziativität nachweisen. Dies werden wir in den nächsten Vorlesungen ausführen.

Isomorphieprinzip

Wir wollen zeigen, dass je zwei Modelle für die Dedekind-Peano-Axiome „isomorph“ sind, dass es also zwischen ihnen eine strukturerhaltende Bijektion gibt. Man stelle sich beispielsweise einerseits das Strichmodell, andererseits das Dezimalzahlmodell der natürlichen Zahlen vor, die beide mit ihren Nullen und ihrer Nachfolgerabbildung die Dedekind-Peano-Axiome erfüllen. Dann gibt es bereits, und zwar allein aufgrund der Tatsache der Dedekind-Peano-Axiome, eine eindeutige Entsprechung zwischen diesen beiden Mengen. Eine Strichfolge entspricht also eindeutig einer Zahl im Dezimalsystem.

	Strichsystem	Zehnersystem	Dreiersystem	Eurosystem
	${}0$	${}0$	${}0$	${}0$
	${}{|}$	${}1$	${}1$	${}1$
	${}{|}{|}$	${}2$	${}2$	${}10$
	${}{|}{|}{|}$	${}3$	${}10$	${}11$
	${}{|}{|}{|}{|}$	${}4$	${}11$	${}20$
	${}{|}{|}{|}{|}{|}$	${}5$	${}12$	${}100$
	${}{|}{|}{|}{|}{|}{|}$	${}6$	${}20$	${}101$
	${}{|}{|}{|}{|}{|}{|}{|}$	${}7$	${}21$	${}110$
	${}{|}{|}{|}{|}{|}{|}{|}{|}$	${}8$	${}22$	${}111$
	${}{|}{|}{|}{|}{|}{|}{|}{|}{|}$	${}9$	${}100$	${}120$
	${}{|}{|}{|}{|}{|}{|}{|}{|}{|}{|}$	${}10$	${}101$	${}1000$

Die Entsprechung in der Tabelle entsteht dadurch, dass man in jeder Spalte unabhängig voneinander im jeweiligen System (gleichschnell) zählt.

Satz

Es seien ${}(N_{1},0_{1},\prime )$ und ${}(N_{2},0_{2},\star )$ Modelle für die natürlichen Zahlen.

Dann gibt es genau eine (bijektive) Abbildung

$\varphi \colon N_{1}\longrightarrow N_{2},$

die das Zählen (also die ${}0$ und die Nachfolgerabbildung) respektiert.

Beweis

Da die Abbildung ${}\varphi$ insbesondere die Null respektieren soll, muss

${}\varphi (0_{1})=0_{2}\,$

sein. Da die Abbildung die Nachfolgerabbildungen respektieren soll, gilt generell

${}\varphi (x^{\prime })=(\varphi (x))^{\star }\,$

für alle ${}x\in N_{1}$. Speziell gilt

${}\varphi (0_{1}^{\prime })={\left(\varphi (0_{1})\right)}^{\star }=0_{2}^{\star }\,.$

Aus dem gleichen Grund muss unter Verwendung des schon Bewiesenen

${}\varphi {\left(0_{1}^{\prime \prime }\right)}=\varphi {\left((0_{1}^{\prime })^{\prime }\right)}={\left(\varphi (0_{1}^{\prime })\right)}^{\star }={\left(0_{2}^{\star }\right)}^{\star }=0_{2}^{\star \star }\,.$

Ebenso muss

${}\varphi {\left(0_{1}^{\prime \prime \prime }\right)}=0_{2}^{\star \star \star }\,,$

${}\varphi {\left(0_{1}^{\prime \prime \prime \prime }\right)}=0_{2}^{\star \star \star \star }\,,$

u.s.w gelten. Hier hat man keine Wahlmöglichkeiten, alles ist durch die Nachfolgereigenschaft bestimmt. Da jedes Element ${}\neq 0_{1}$ aus ${}N_{1}$ von ${}0_{1}$ aus durch die Nachfolgerabbildung ${}\prime$ schließlich und genau einmal erreicht wird, ist dies eine wohldefinierte Abbildung von ${}N_{1}$ nach ${}N_{2}$.

Zum Nachweis der Surjektivität betrachten wir die Menge

${}T={\left\{y\in N_{2}\mid {\text{ Es gibt }}x\in N_{1}{\text{ mit }}y=\varphi (x)\right\}}\,.$

Wir müssen zeigen, dass

${}T=N_{2}\,$

ist. Dazu wenden wir das Induktionsaxiom für ${}N_{2}$ an. Wegen

${}\varphi (0_{1})=0_{2}\,$

gehört ${}0_{2}\in T$. Wenn ${}y\in T$ ist, so ist also

${}y=\varphi (x)\,$

für ein ${}x\in N_{1}$. Wegen der Verträglichkeit mit der Nachfolgerabbildung ist

${}y^{\star }=\varphi (x^{\prime })\,,$

d.h. auch ${}y^{\star }\in T$. Daher ist ${}T$ unter dem Nachfolger abgeschlossen und nach dem Induktionsaxiom ist also ${}T=N_{2}$. Zum Nachweis der Injektivität seien ${}x,{\tilde {x}}\in N_{1}$ verschieden. und zwar sei ${}{\tilde {x}}$ ein (direkter oder) höherer Nachfolger von ${}x$. Dann ist ${}\varphi ({\tilde {x}})$ der entsprechende Nachfolger von ${}\varphi (x)$ und insbesondere davon verschieden (siehe Aufgabe 7.11), da das Nachfolgernehmen in ${}N_{2}$ injektiv ist.

$\Box$

Es gibt also im Wesentlichen, d.h. wenn man von den Benennungen absieht, genau eine Menge von natürlichen Zahlen. Für das im Wesentlichen eindeutig bestimmte Modell der Dedekind-Peano-Axiome verwenden wir das Symbol ${}\mathbb {N}$ und sprechen von den natürlichen Zahlen.

Es sei bemerkt, dass die Konstruktion der bijektiven Abbildung zwischen zwei Modellen im Beweis zu Satz 7.2 über den Nachfolger für praktische Zwecke nicht gut geeignet ist. Wenn man von einer natürlichen Zahl, die im Zehnersystem gegeben ist, die Darstellung im Dreiersystem ausrechnen möchte, so müsste man gemäß dieser Methode im Dreiersystem so lange zählen, wie es die im Zehnersystem gegebene Zahl vorgibt. Da gibt es deutlich effektivere Methoden, die wir später kennenlernen werden.

Das Induktionsprinzip für Aussagen

Die natürlichen Zahlen sind dadurch ausgezeichnet, dass man jede natürliche Zahl ausgehend von der ${}0$ durch den Zählprozess (das sukzessive Nachfolgernehmen) erreichen kann. Daher können mathematische Aussagen, die von natürlichen Zahlen abhängen, mit dem Beweisprinzip der vollständigen Induktion bewiesen werden. Das folgende Beispiel soll an dieses Argumentationsschema heranführen. Um dieses Beweisprinzip anhand von substantiellem Material demonstrieren zu können, greifen wir etwas vor und setzen die Addition, die Multiplikation und die Größergleichrelation von natürlichen Zahlen voraus.

Beispiel

Wir betrachten in der Ebene ${}E$ eine Konfiguration von ${}n$ Geraden und fragen uns, was die maximale Anzahl an Schnittpunkten ist, die eine solche Konfiguration haben kann. Dabei ist es egal, ob wir uns die Ebene als einen ${}\mathbb {R} ^{2}$ (eine kartesische Ebene mit Koordinaten) oder einfach elementargeometrisch vorstellen, wichtig ist im Moment allein, dass sich zwei Geraden in genau einem Punkt schneiden können oder aber parallel sein können. Wenn ${}n$ klein ist, so findet man relativ schnell die Antwort.

${}n$	${}0$	${}1$	${}2$	${}3$	${}4$	${}5$	${}n$
${}S(n)$	${}0$	${}0$	${}1$	${}3$	${}6$	${}?$	${}?$

Doch schon bei etwas größerem ${}n$ (${}n=5,10,\ldots$?) kann man ins Grübeln kommen, da man sich die Situation irgendwann nicht mehr präzise vorstellen kann. Aus einer präzisen Vorstellung wird eine Vorstellung von vielen Geraden mit vielen Schnittpunkten, woraus man aber keine exakte Anzahl der Schnittpunkte ablesen kann. Ein sinnvoller Ansatz zum Verständnis des Problems ist es, sich zu fragen, was eigentlich passiert, wenn eine neue Gerade hinzukommt, wenn also aus ${}n$ Geraden ${}n+1$ Geraden werden. Angenommen, man weiß aus irgendeinem Grund, was die maximale Anzahl der Schnittpunkte bei ${}n$ Geraden ist, im besten Fall hat man dafür eine Formel. Wenn man dann versteht, wie viele neue Schnittpunkte maximal bei der Hinzunahme von einer neuen Geraden hinzukommen, so weiß man, wie die Anzahl der maximalen Schnittpunkte von ${}n+1$ Geraden lautet.

Dieser Übergang ist in der Tat einfach zu verstehen. Die neue Gerade kann höchstens jede der ${}n$ alten Geraden in genau einem Punkt schneiden, deshalb kommen höchstens ${}n$ neue Schnittpunkte hinzu. Wenn man die neue Gerade so wählt, dass sie zu keiner der gegebenen Geraden parallel ist (was möglich ist, da es unendlich viele Richtungen gibt) und ferner so wählt, dass die neuen Schnittpunkte von den schon gegebenen Schnittpunkten der Konfiguration verschieden sind (was man erreichen kann, indem man die neue Gerade parallel verschiebt, um den alten Schnittpunkten auszuweichen), so erhält man genau ${}n$ neue Schnittpunkte. Von daher ergibt sich die (vorläufige) Formel

${}S(n+1)=1+2+3+\cdots +n-2+n-1+n\,$

bzw.

${}S(n)=1+2+3+\cdots +n-3+n-2+n-1\,,$

also einfach die Summe der ersten ${}n-1$ natürlichen Zahlen.

Im vorstehenden Beispiel liegt eine Summe vor, wobei die Anzahl der Summanden selbst variieren kann. Für eine solche Situation ist das Summenzeichen sinnvoll. Für gegebene reelle Zahlen ${}a_{1},\ldots ,a_{n}$ bedeutet

${}\sum _{k=1}^{n}a_{k}:=a_{1}+a_{2}+\cdots +a_{n-1}+a_{n}\,.$

Dabei hängen im Allgemeinen die ${}a_{k}$ in einer formelhaften Weise von ${}k$ ab, beispielsweise ist im Beispiel ${}a_{k}=k$, es könnte aber auch etwas wie ${}a_{k}=2k+1$ oder ${}a_{k}=k^{2}$ vorliegen. Der ${}k$-te Summand der Summe ist jedenfalls ${}a_{k}$, dabei nennt man ${}k$ den Index des Summanden. Entsprechend ist das Produktzeichen definiert, nämlich durch

${}\prod _{k=1}^{n}a_{k}:=a_{1}\cdot a_{2}{\cdots }a_{n-1}\cdot a_{n}\,.$

Beispiel

Wir möchten für die Summe der ersten ${}n$ Zahlen, die die maximale Anzahl der Schnittpunkte in einer Konfiguration aus ${}n+1$ Geraden angibt, eine einfachere Formel angeben. Und zwar behaupten wir, dass

${}\sum _{k=1}^{n}k={\frac {n(n+1)}{2}}\,.$

Für kleinere Zahlen ${}n$ stimmt dies aus dem einfachen Grund, dass links und rechts dasselbe herauskommt. Um die Gleichung allgemein zu beweisen, überlegen wir uns, was links und was rechts passiert, wenn wir das ${}n$ um ${}1$ erhöhen, so wie wir in Beispiel 7.3 die Geradenkonfiguration um eine zusätzliche Gerade verkompliziert haben. Auf der linken Seite kommt einfach der zusätzliche Summand ${}n+1$ hinzu. Auf der rechten Seite haben wir den Übergang von ${}{\frac {n(n+1)}{2}}$ nach ${}{\frac {(n+1)(n+1+1)}{2}}$. Wenn wir zeigen können, dass die Differenz zwischen diesen beiden Brüchen ebenfalls ${}n+1$ ist, so verhält sich die rechte Seite genauso wie die linke Seite. Dann kann man so schließen: die Gleichung gilt für die kleinen ${}n$, etwa für ${}n=1$. Durch den Differenzenvergleich gilt es auch für das nächste ${}n$, also für ${}n=2$, durch den Differenzenvergleich gilt es für das nächste ${}n$, u.s.w. Da dieses Argument immer funktioniert, und da man jede natürliche Zahl irgendwann durch sukzessives Nachfolgernehmen erreicht, gilt die Formel für jede natürliche Zahl.

Eine Visualisierung des Induktionsprinzips. Wenn die Steine nah beieinander stehen und der erste umgestoßen wird, so fallen alle Steine um.

Die folgende Aussage begründet das Prinzip der vollständigen Induktion ausgehend von den Dedekind-Peano-Axiomen. Wir schreiben ${}n+1$ für den Nachfolger von ${}n$.

Satz

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$

Der Nachweis von (der Gültigkeit von) ${}A(0)$ heißt dabei der Induktionsanfang und der Schluss von ${}A(n)$ auf ${}A(n+1)$ heißt der Induktionsschluss oder Induktionsschritt. Innerhalb des Induktionsschlusses nennt man die Gültigkeit von ${}A(n)$ auch die Induktionsvoraussetzung. In manchen Situationen ist die Aussage ${}A(n)$ erst für ${}n\geq n_{0}$ für ein gewisses ${}n_{0}$ (definiert oder) wahr. Dann beweist man im Induktionsanfang die Aussage ${}A(n_{0})$ und den Induktionsschritt führt man für alle ${}n\geq n_{0}$ durch.

Wir begründen nun die Gleichheit

${}\sum _{k=1}^{n}k={\frac {n(n+1)}{2}}\,.$

mit dem Induktionsprinzip.

Beim Induktionsanfang ist ${}n=1$, daher besteht die Summe links nur aus einem Summanden, nämlich der ${}1$, und daher ist die Summe ${}1$. Die rechte Seite ist ${}{\frac {1\cdot 2}{2}}=1$, so dass die Formel für ${}n=1$ stimmt.

Für den Induktionsschritt setzen wir voraus, dass die Formel für ein ${}n\geq 1$ gilt, und müssen zeigen, dass sie dann auch für ${}n+1$ gilt. Dabei ist ${}n$ beliebig. Es ist

${}{\begin{aligned}\sum _{k=1}^{n+1}k&={\left(\sum _{k=1}^{n}k\right)}+n+1\\&={\frac {n(n+1)}{2}}+n+1\\&={\frac {n(n+1)+2(n+1)}{2}}\\&={\frac {(n+2)(n+1)}{2}}.\end{aligned}}$

Dabei haben wir für die zweite Gleichheit die Induktionsvoraussetzung verwendet. Der zuletzt erhaltene Term ist die rechte Seite der Formel für ${}n+1$, also ist die Formel bewiesen.

Aussagen, die durch Induktion bewiesen werden können, können manchmal auch auf andere Art bewiesen werden, siehe beispielsweise Aufgabe 7.17.

Fußnoten

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