Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I/Vorlesung 7/kontrolle

„Ich will jeden Spieler jeden Tag ein bisschen besser machen“

Jürgen Klinsmann

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 Referenznummer erstellen

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 vorvorletzten 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 Satz 7.2 ändern

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 ***** {{:Kurs:Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Dedekind-Peano-Axiome/Nachfolger/Iterationen/Fixpunktfrei/Aufgabe/Aufgabereferenznummer/Dedekind-Peano-Axiome/Nachfolger/Iterationen/Fixpunktfrei/Aufgabe/Aufgabereferenznummer}}), 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

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

Die folgende Aussage und ihr Beweis begründen das Beweisprinzip der vollständigen Induktion. Wir schreiben ${}n+1$ für den Nachfolger.

Satz Referenznummer erstellen

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.

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. Das folgende Standardbeispiel für einen Induktionsbeweis verwendet das Summenzeichen. Für gegebene (natürliche, 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 typischerweise die ${}a_{k}$ in einer formelhaften Weise von ${}k$ ab. 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}\,.$

Aufgabe

Beweise durch Induktion die folgende Formel für ${}n\geq 1$.

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

Lösung

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$, sodass 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 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. Im vorstehenden Beispiel gibt es die elegantere und einsichtigere Lösung, die Zahlen einmal aufsteigend und einmal absteigend untereinander hinzuschreiben, also

$1\,\,\,\,\,\,\,\,\,\,\,\,2\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,3\,\,\,\,\ldots \,\,\,\,n-2\,\,\,\,n-1\,\,\,\,n$

$n\,\,\,\,\,n-1\,\,\,\,\,\,n-2\,\,\,\,\ldots \,\,\,\,3\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,2\,\,\,\,\,\,\,\,\,\,\,\,1$

Spaltenweise ergibt sich ${}n+1$, und diese Summe kommt ${}n$-mal vor. Also ist

${}2{\left(\sum _{i=1}^{n}i\right)}=n{\left(n+1\right)}\,.$

Aufgabe

Zeige durch vollständige Induktion, dass für jedes ${}n\in \mathbb {N}$ die Zahl

$6^{n+2}+7^{2n+1}$

ein Vielfaches von ${}43$ ist.

Lösung

Induktionsanfang. Für ${}n=0$ ist

${}6^{2}+7=43\,$

ein Vielfaches von ${}43$. Induktionsschritt. Es sei nun die Aussage für ${}n$ bewiesen und betrachten wir den Ausdruck für ${}n+1$. Dieser ist

${}{\begin{aligned}6^{n+1+2}+7^{2(n+1)+1}&=6\cdot 6^{n+2}+7^{2}\cdot 7^{2n+1}\\&=6\cdot 6^{n+2}+(6+43)7^{2n+1}\\&=6{\left(6^{n+2}+7^{2n+1}\right)}+43\cdot 7^{2n+1}\\&=6\cdot 43\cdot s+43\cdot 7^{2n+1}\\&=43\cdot {\left(6\cdot s+7^{2n+1}\right)},\end{aligned}}$

wobei im vorletzten Schritt die Induktionsvoraussetzung verwendet wurde (nämlich die Eigenschaft, dass $6^{n+2}+7^{2n+1}$ ein Vielfaches von ${}43$ ist). Daher ist diese Zahl ein Vielfaches von ${}43$.

Aus dem Induktionsprinzip folgt die nächste wichtige Eigenschaft. Vom intuitiven Standpunkt her ist sie selbstverständlich, wir führen sie aber trotzdem auf das Induktionsprinzip zurück. Es geht in diesem Beweis weniger dadrum, sich über die Satzaussage zu vergewissern, sondern vielmehr Einblicke in mathematisches Argumentieren zu gewinnen. Es ist auch ein Beispiel dafür, wie man eine Aussage über Teilmengen zu einer Aussage über natürliche Zahlen macht, um das Induktionsprinzip anwenden zu können.

Lemma Lemma 7.6 ändern

Jede nichtleere Teilmenge ${}M\subseteq \mathbb {N}$

besitzt ein Minimum.

Beweis

Wir betrachten die Aussage

${}A(n)$ = Alle Teilmengen von ${}\mathbb {N}$, die ${}n$ enthalten, besitzen ein Minimum.

Da jede nichtleere Teilmenge mindestens ein ${}n\in \mathbb {N}$ besitzt, ist die Aussage des Satzes äquivalent zur Gültigkeit von ${}A(n)$ für alle ${}n$. Diese Aussage können wir durch Induktion beweisen. Die Aussage ${}A(0)$ besagt, dass jede Teilmenge ${}M\subseteq \mathbb {N}$, die die ${}0$ enthält, auch ein Minimum enthält. Dies ist aber klar, da dann eben ${}0$ das Minimum ist. Es sei die Aussage ${}A(k)$ nun für alle ${}k\leq n$ schon bewiesen. Wir müssen ${}A(n+1)$ beweisen. Es sei also ${}M\subseteq \mathbb {N}$ eine Teilmenge, die ${}n+1$ enthält. Wenn ${}M$ auch eine Zahl ${}k<n+1$ besitzt, so besitzt ${}M$ nach der Induktionsvoraussetzung ein Minimum. Andernfalls besitzt ${}M$ keine Zahl, die kleiner als ${}n+1$ ist. Dann ist aber ${}n+1$ das Minimum von ${}M$.

$\Box$

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