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

Aus Wikiversity
Wechseln zu: Navigation, Suche
„Ich will jeden Spieler jeden Tag ein bisschen besser machen“

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 kann man addieren, multiplizieren, potenzieren, teilweise abziehen, es gibt die Größergleich-Relation, 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. Dies ist lediglich eine weitere Präzisierung des Zählvorgangs in der Sprache der Mengen und Abbildungen.


Definition  

Eine Menge mit einem ausgezeichneten Element (die Null) und einer (Nachfolger)-Abbildung

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 ist kein Nachfolger (die Null liegt also nicht im Bild der Nachfolgerabbildung).
  2. Jedes ist Nachfolger höchstens eines Elementes (d.h. die Nachfolgerabbildung ist injektiv).
  3. Für jede Teilmenge gilt: Wenn die beiden Eigenschaften
    • ,
    • mit jedem Element ist auch ,

    gelten, so ist .

Man mache sich klar, dass diese Bedingungen den Bedingungen der vorvorletzten Vorlesung entsprechen. Dabei ist die jeweilige Menge, bezeichnet die Nachfolgerabbildung und das Startsymbol (dort hatten wir zumeist 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 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 Mengen, Abbildungen, Injektivität. 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).

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

Hier stehen also alle Elemente, die von 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 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 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

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



Satz  

Es seien und Modelle für die natürlichen Zahlen.

Dann gibt es genau eine (bijektive) Abbildung

die das Zählen (also die und die Nachfolgerabbildung) respektiert.

Beweis  

Da die Abbildung insbesondere die Null respektieren soll, muss

sein. Da die Abbildung die Nachfolgerabbildungen respektieren soll, muss

gelten. Aus dem gleichen Grund muss unter Verwendung des schon Bewiesenen

Ebenso muss

u.s.w gelten. Hier hat man keine Wahlmöglichkeiten, alles ist durch die Nachfolgereigenschaft bestimmt. Da jedes Element aus von aus durch die Nachfolgerabbildung schließlich und genau einmal erreicht wird, ist dies eine wohldefinierte Abbildung von nach .

Zum Nachweis der Surjektivität betrachten wir die Menge

Wir müssen zeigen, dass

ist. Dazu wenden wir das Induktionsaxiom für an. Wegen

gehört . Wenn ist, so ist also

für ein . Wegen der Verträglichkeit mit der Nachfolgerabbildung ist

d.h. auch . Daher ist unter dem Nachfolger abgeschlossen und nach dem Induktionsaxiom ist also . Zum Nachweis der Injektivität seien verschieden. und zwar sei ein (direkter oder) höherer Nachfolger von . Dann ist der entsprechende Nachfolger von und insbesondere davon verschieden, da das Nachfolgernehmen in injektiv ist.


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



Satz  

Für jede natürliche Zahl sei eine Aussage gegeben. Es gelte

  1. ist wahr.
  2. Für alle gilt: wenn gilt, so ist auch wahr.

Dann gilt für alle .

Beweis  

Es sei

Wir wollen zeigen, dass ist, denn genau dies bedeutet, dass die Aussage für alle gilt. Nach der ersten Bedingung ist

Nach der zweiten Voraussetzung gilt für , dass aus stets folgt. Damit erfüllt beide Voraussetzungen im Induktionsprinzip für Mengen, so dass gilt.


Der Nachweis von (der Gültigkeit von) heißt dabei der Induktionsanfang und der Schluss von auf heißt der Induktionsschluss oder Induktionsschritt. Innerhalb des Induktionsschlusses nennt man die Gültigkeit von auch die Induktionsvoraussetzung. In manchen Situationen ist die Aussage erst für für ein gewisses (definiert oder) wahr. Dann beweist man im Induktionsanfang die Aussage und den Induktionsschritt führt man für alle 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 bedeutet

Dabei hängen im Allgemeinen die in einer formelhaften Weise von ab. Entsprechend ist das Produktzeichen definiert, nämlich durch


Aufgabe

Beweise durch Induktion die folgende Formel für .


Lösung

Beim Induktionsanfang ist , daher besteht die Summe links nur aus einem Summanden, nämlich der , und daher ist die Summe . Die rechte Seite ist , so dass die Formel für stimmt.

Für den Induktionsschritt setzen wir voraus, dass die Formel für ein gilt, und müssen zeigen, dass sie auch für gilt. Dabei ist beliebig. Es ist

Dabei haben wir für die zweite Gleichheit die Induktionsvoraussetzung verwendet. Der zuletzt erhaltene Term ist die rechte Seite der Formel für , 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

Spaltenweise ergibt sich , und diese Summe kommt -mal vor. Also ist


Aufgabe

Zeige durch vollständige Induktion, dass für jedes die Zahl

ein Vielfaches von ist.


Lösung

Für ist

ein Vielfaches von . Sei nun die Aussage für bewiesen und betrachten wir den Ausdruck für . Dieser ist

wobei im letzten Schritt die Induktionsvoraussetzung verwendet wurde (nämlich die Eigenschaft, dass ein Vielfaches von ist). Daher ist diese Zahl ein Vielfaches von .


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  

Jede nichtleere Teilmenge

besitzt ein Minimum.

Beweis  

Wir betrachten die Aussage

= Alle Teilmengen von , die enthalten, besitzen ein Minimum.

Da jede nichtleere Teilmenge mindestens ein besitzt, ist die Aussage des Satzes äquivalent zur Gültigkeit von für alle . Diese Aussage können wir durch Induktion beweisen. Die Aussage besagt, dass jede Teilmenge , die die enthält, auch ein Minimum enthält. Dies ist aber klar, da dann eben das Minimum ist. Sei die Aussage nun für alle schon bewiesen. Wir müssen beweisen. Sei also eine Teilmenge, die enthält. Wenn auch eine Zahl besitzt, so besitzt nach der Induktionsvoraussetzung ein Minimum. Andernfalls besitzt keine Zahl, die kleiner als ist. Dann ist aber das Minimum von .


<< | Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)