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

Wir modellieren das Abzählen einer Menge mathematisch als eine bijektive Abbildung zwischen einer Menge der Form und Wir wollen zeigen, dass dabei das unabhängig von der gewählten Abbildung ist. Um dies klar begründen zu können, müssen wir uns etwas genauer mit Abbildungen beschäftigen. Abbildungen können auf recht unterschiedliche Arten dargestellt werden. Zu nennen sind (vollständige oder unvollständige) Wertetabellen, der Graph einer Abbildung, Säulen- und Kuchendiagramme, Pfeildiagramme, Höhenlinien, Animationen. Eine besondere Rolle spielen funktionale Vorschriften, mit denen häufig Abbildungen festgelegt werden, das sind Ausdrücke der Form

Wir wollen zu zwei gegebenen Nummerierungen einer Menge also zu zwei bijektiven Abbildungen

und

zeigen, dass

ist. Da bei einer Bijektion sich die Elemente der beiden Mengen eindeutig entsprechen, führt dies zu einer eindeutigen Entsprechung zwischen

Mit diesem Trick, dem die Hintereinanderschaltung von Abbildungen und die Umkehrabbildung einer bijektiven Abbildung zugrunde liegt, kann man also unter Umgehung der Menge direkt diese Teilmengen der natürlichen Zahlen untereinander vergleichen.

Definition

Es seien und Mengen und

und

Abbildungen. Dann heißt die Abbildung

die Hintereinanderschaltung der Abbildungen

Eine Hintereinanderschaltung kann man sich durch ein Diagramm der Form

gut veranschaulichen.

Beispiel

Die Wertetabelle

beschreibt, welche Person der Bearbeitungsgruppe

welche Aufgabe federführend macht und die Wertetabelle

mit den möglichen Werten beschreibt, wie viel Lust die Personen in dieser Woche haben (hat Megalust, hat Superlust, hat Lust, hat wenig Lust, hat Unlust). Die zusammengesetzte Abbildung beschreibt dann, mit wie viel Lust die verschiedenen Aufgaben bearbeitet werden, die zugehörige Wertetabelle ist

Wenn die Abbildungen durch funktionale Ausdrücke gegeben sind, so erhält man die zusammengesetzte Abbildung, in den man den einen funktionalen Ausdruck in den anderen funktionalen Ausdruck einsetzt. Damit ist folgendes gemeint: Wenn

Funktionen sind, die durch

gegeben sind, so besitzt die zusammengesetzte Funktion (also in der Ausführung zuerst!) die Vorschrift

In der anderen Reihenfolge ergibt sich

Hier haben wir die beiden Funktionen mit unterschiedlichen Variablen geschrieben, was die Einsetzung dann erleichtert hat. Häufig muss man zuerst eine sinnvolle Umbenennung durchführen.

Lemma

Es seien und Mengen und es seien

und

Abbildungen.

Dann ist

Beweis

Zwei Abbildungen

sind genau dann gleich, wenn für jedes

die Gleichheit

gilt. Es sei also

Dann ist

$\Box$

Lemma

Es seien und Mengen und

und

Abbildungen mit der Hintereinanderschaltung Dann gelten folgende Eigenschaften.

1. Wenn injektiv sind, so ist auch injektiv.
2. Wenn surjektiv sind, so ist auch surjektiv.
3. Wenn bijektiv sind, so ist auch bijektiv.

Beweis

1. Es seien mit gegeben. Aufgrund der Injektivität von folgt und aufgrund der Injektivität von folgt was die Injektivität von bedeutet.
2. Sei gegeben. Aufgrund der Surjektivität von gibt es ein mit Aufgrund der Surjektivität von gibt es ein mit Insgesamt ist es gibt also ein Urbild von und somit ist die Gesamtabbildung surjektiv.
3. Folgt aus (1) und (2).

$\Box$

Definition

Es sei eine Menge. Dann heißt die Abbildung

die also jedes Element

auf sich selbst schickt, die identische Abbildung oder Identität auf Sie wird mit oder bezeichnet.

Die Identität ist natürlich bijektiv. Umgekehrt kann man zu einer bijektiven Abbildung eine Abbildung derart angeben, dass die Verknüpfung die Identität ergibt.

Definition

Es sei

eine bijektive Abbildung. Dann heißt die Abbildung

die jedes Element

auf das eindeutig bestimmte Element

mit

abbildet, die Umkehrabbildung zu

Die Umkehrabbildung zu wird mit bezeichnet. Es gilt die charakteristische Eigenschaft, dass sowohl als auch die Identität (auf den jeweiligen Mengen) sind.

Beispiel

Die Nummerierung der Schüler durch Heino,

ist bijektiv und hat daher eine eindeutig bestimmte Umkehrabbildung. Die Wertetabelle dieser Umkehrabbildung ist

Bei einem natürlichen Zählvorgang kann man sich darüber streiten, ob die Zahlen den Personen oder die Personen eher den Zahlen zugeordnet wird. Bei einer bijektiven Abbildung liegt eine Entsprechung vor.

Wir erwähnen noch die konstanten Abbildungen.

Definition

Es seien

Mengen und es sei

ein Element. Dann heißt die Abbildung

die also jedes Element

auf abbildet, die konstante Abbildung zum Wert

Wir kehren zu dem Problem zurück, warum die Anzahl einer endlichen Menge wohldefiniert ist, warum es also egal ist, in welcher Reihenfolge man zählt.

Lemma

Es sei

eine natürliche Zahl mit dem Vorgänger es sei also

Es sei

ein fixiertes Element.

Dann gibt es eine bijektive Abbildung zwischen und

Beweis

Wir definieren eine Abbildung

durch

Dies ist eine wohldefinierte Abbildung, da die Bilder echt unterhalb von oder echt oberhalb von liegen, niemals aber gleich sind, und da maximal der Nachfolger von also erreicht wird.

Die Abbildung ist injektiv: Wenn

beide unterhalb von liegen, so werden beide Elemente auf sich selbst abgebildet. Wenn beide oberhalb von liegen, so werden beide auf ihren Nachfolger abgebildet, und das Nachfolgernehmen ist injektiv (dies ist die Eigenschaft, dass der Vorgänger eindeutig bestimmt ist). Wenn unterhalb von und oberhalb von (oder umgekehrt) liegt, so ist erst recht oberhalb von und somit von verschieden.

Die Abbildung ist auch surjektiv. Die Zahlen echt unterhalb von werden durch sich selbst erreicht und die Zahlen echt oberhalb von (und unterhalb von einschließlich) kann man als

mit oberhalb von (einschließlich) und echt unterhalb von also maximal gleich schreiben. Insgesamt ist also eine Bijektion.

$\Box$

Satz

Wenn eine Menge ist und wenn

und

bijektive Abbildungen sind,

so ist

Die Anzahl einer endlichen Menge ist also wohldefiniert.

Beweis

Es seien die bijektiven Abbildungen

und

gegeben. Da man bijektive Abbildungen umkehren kann und da die Hintereinanderschaltung von bijektiven Abbildungen nach Lemma 6.4  (3) wieder bijektiv ist, ist auch

bijektiv. Wir müssen also nur die endlichen Standardmengen untereinander vergleichen. Wir müssen also zeigen, dass wenn eine bijektive Abbildung

vorliegt, dass dann

ist. Dies zeigen wir durch Induktion nach Wenn

ist, so ist die Menge links leer und somit muss auch die rechte Menge leer sein, also ist dann auch

Es seien nun nicht sodass sie also jeweils einen Vorgänger haben. Es sei der Vorgänger von und der Vorgänger von Diese Zahlen sind eindeutig bestimmt, da die Nachfolgerabbildung injektiv ist. Wir setzen

Dann gibt es nach der Herausnahme von bzw. eine bijektive Abbildung

Nach Lemma 6.9 gibt es eine bijektive Abbildung zwischen

Somit gibt es dann auch insgesamt eine bijektive Abbildung zwischen

Nach Induktionsvoraussetzung ist

also auch

$\Box$

Mit natürlichen Zahlen kann man nicht nur endliche Mengen zählen, sondern auch Prozesse. Wenn ein Einzelprozess wohldefiniert ist, wie beispielsweise das Nachfolgernehmen in einem Modell der natürlichen Zahlen, oder das Umlegen eines Apfel von einem Haufen auf einen anderen Haufen, oder auf einer Leiter eine Sprosse nach oben steigen, so kann man mit den natürlichen Zahlen angeben, wie oft der Prozess durchgeführt wird oder werden soll. Dies eröffnet eine Vielzahl von Möglichkeiten, komplexere mathematische Konzepte dadurch festzulegen, dass gesagt wird, wie oft ein gewisser grundlegenderer Prozess durchgeführt werden soll. In diesem Sinne kann die Addition von zwei natürlichen Zahlen dadurch eingeführt werden, dass die eine Zahl angibt, wie oft von der anderen Zahl ausgehend der Nachfolger genommen werden soll, die Multiplikation von zwei natürlichen Zahlen kann dadurch eingeführt werden, dass die eine Zahl angibt, wie oft die andere Zahl zur addiert werden soll (die Anzahl der Summanden ist durch die erste Zahl festgelegt), die Potenzierung von zwei natürlichen Zahlen kann dadurch eingeführt werden, dass die eine Zahl angibt, wie oft die andere Zahl mit sich selbst multipliziert werden soll (Anzahl der Faktoren). Wenn eine Strecke und eine natürliche Zahl gegeben ist, so kann man die Strecke fach Hintereinanderlegen. Dabei entsteht eine Strecke, die mal so lang wie die Ausgangsstrecke ist. Geometrisch kann man dies dadurch durchführen, dass man die Stecke zu einer Geraden verlängert und dann mit Hilfe eines Zirkels die Strecke mal umschlägt.

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.

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

Definition

Eine Menge mit einem ausgezeichneten Element

(die) und einer (Nachfolger)-Abbildung

heißt natürliche Zahlen (oder für die natürlichen Zahlen), wenn die folgenden 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 vorletzten 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 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 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 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

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.

Wir wollen zeigen, dass je zwei Modelle für die Dedekind-Peano-Axiome 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, gilt generell

für alle

Speziell gilt

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 (siehe Aufgabe 7.11), da das Nachfolgernehmen in 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 und sprechen von den

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.

Die natürlichen Zahlen sind dadurch ausgezeichnet, dass man jede natürliche Zahl ausgehend von der 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 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 eine Konfiguration von 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 (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 klein ist, so findet man relativ schnell die Antwort.

Doch schon bei etwas größerem (?) 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 Geraden Geraden werden. Angenommen, man weiß aus irgendeinem Grund, was die maximale Anzahl der Schnittpunkte bei 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 Geraden lautet.

Dieser Übergang ist in der Tat einfach zu verstehen. Die neue Gerade kann höchstens jede der alten Geraden in genau einem Punkt schneiden, deshalb kommen höchstens 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 neue Schnittpunkte. Von daher ergibt sich die (vorläufige) Formel

bzw.

also einfach die Summe der ersten 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 sinnvoll. Für gegebene reelle Zahlen bedeutet

Dabei hängen im Allgemeinen die in einer formelhaften Weise von ab, beispielsweise ist im Beispiel

es könnte aber auch etwas wie

oder

vorliegen. Der te Summand der Summe ist jedenfalls dabei nennt man den des Summanden. Entsprechend ist das definiert, nämlich durch

Beispiel

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

Für kleinere Zahlen 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 um 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 hinzu. Auf der rechten Seite haben wir den Übergang von nach Wenn wir zeigen können, dass die Differenz zwischen diesen beiden Brüchen ebenfalls 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 etwa für

Durch den Differenzenvergleich gilt es auch für das nächste also für

durch den Differenzenvergleich gilt es für das nächste 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.

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

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, sodass

gilt.

$\Box$

Der Nachweis von (der Gültigkeit von)

heißt dabei der  und der Schluss von  auf  heißt der  oder  Innerhalb des Induktionsschlusses nennt man die Gültigkeit von  auch die  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.

Wir begründen nun die Gleichheit

mit dem Induktionsprinzip.

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 dann 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, siehe beispielsweise Aufgabe 7.17.

Wir führen nun die Addition und die Multiplikation von natürlichen Zahlen ein. Dabei müssen wir uns kurz klar machen, um was für eine Struktur es sich überhaupt handelt. Bei der Addition (der Multiplikation) wird zwei natürlichen Zahlen

eine neue Zahl, ihre Summe (ihr Produkt $a\cdot b$) zugeordnet. In der vierten Vorlesung haben wir schon aus zwei Mengen ihre Vereinigung bzw. ihren Durchschnitt gebildet. In der sechsten Vorlesung haben wir Abbildungen hintereinandergeschaltet und so eine neue Abbildung bekommen. Für diese Situationen gibt es das Konzept der Verknüpfung. Um dies angemessen formulieren zu können, benötigen wir die Produktmenge.

Definition

Es seien zwei Mengen

gegeben. Dann nennt man die Menge

die Produktmenge der beiden Mengen.

Die Elemente der Produktmenge nennt man und schreibt Dabei kommt es wesentlich auf die Reihenfolge an. Die Produktmenge besteht also aus allen Paarkombinationen, wo in der ersten ein Element der ersten Menge und in der zweiten Komponente ein Element der zweiten Menge steht. Zwei Paare sind genau dann gleich, wenn sie in beiden Komponenten gleich sind. Bei einer Produktmenge können natürlich auch beide Mengen gleich sein. Dann ist es verlockend, die Reihenfolge zu verwechseln, und also besonders wichtig, darauf zu achten, dies nicht zu tun. Wenn eine der beiden Mengen leer ist, so ist auch die Produktmenge leer.

Beispiel

Es sei die Menge aller Vornamen (sagen wir der Vornamen, die in einer bestimmten Grundmenge an Personen wirklich vorkommen) und die Menge aller Nachnamen. Dann ist

die Menge aller Namen. Elemente davon sind in Paarschreibweise beispielsweise und Aus einem Namen lässt sich einfach der Vorname und der Nachname herauslesen, indem man entweder auf die erste oder auf die zweite Komponente des Namens schaut. Auch wenn alle Vornamen und Nachnamen für sich genommen vorkommen, so muss natürlich nicht jeder daraus gebastelte mögliche Name wirklich vorkommen. Bei der Produktmenge werden eben alle Kombinationsmöglichkeiten aus den beiden beteiligten Mengen genommen.

Beispiel

Ein Schachbrett (genauer: die Menge der Felder auf einem Schachbrett, auf denen eine Figur stehen kann) ist die Produktmenge

Jedes Feld ist ein Paar, beispielsweise Da die beteiligten Mengen verschieden sind, kann man statt der Paarschreibweise einfach schreiben. Diese Notation ist der Ausgangspunkt für die Beschreibung von Stellungen und von ganzen Partien.

Beispiel

Bei zwei reellen Intervallen

ist die Produktmenge einfach das Rechteck

Allerdings muss man bei einem Rechteck im Hinterkopf behalten, welche Seite das erste und welche Seite das zweite Intervall ist. Für schreibt man häufig auch

Man kann auch mehrfache Produktmengen bilden, wie etwa

Für eine Abbildung

ist der Graph diejenige Teilmenge von

die durch alle Paare der Form gegeben sind. Diese Definition überträgt sich auf beliebige Abbildungen. Es existiert also stets ein Graph unabhängig von seiner zeichnerischen Realisierbarkeit. Diese hängt davon ab, ob man die Produktmenge aus Definitionsmenge und Wertemenge gut visualisieren kann.

Definition

Es seien

Mengen und es sei

eine Abbildung. Dann nennt man

den Graphen der Abbildung

Definition

Eine Verknüpfung auf einer Menge ist eine Abbildung

Statt Verknüpfung sagt man auch Das Verknüpfungszeichen ist hier einigermaßen willkürlich gewählt, um vorschnelle Assoziationen zu vermeiden. In vielen konkreten Situation steht hier

Das Element heißt dann auch das der Operation. Da das Ergebnis wieder zur Ausgangsmenge gehört, kann man es weiter verknüpfen mit weiteren Elementen. Dies erfordert im Allgemeinen Klammerungen, um zu wissen, in welcher Reihenfolge welche Elemente miteinander verknüpft werden sollen. Im Allgemeinen ist

Definition

Eine Verknüpfung

auf einer Menge heißt assoziativ wenn für alle

die Gleichheit

gilt.

Man sagt auch, dass für die Verknüpfung das oder die gilt.

Definition

Eine Verknüpfung

auf einer Menge heißt kommutativ wenn für alle

die Gleichheit

gilt.

Man sagt auch, dass für die Verknüpfung das oder das gilt. Die Addition und die Multiplikation auf den natürlichen Zahlen sind beide assoziativ und kommutativ.

Definition

Es sei eine Menge mit einer Verknüpfung

gegeben. Dann heißt ein Element

neutrales Element der Verknüpfung, wenn für alle

die Gleichheit

gilt.

Bei der Addition auf den natürlichen Zahlen ist das neutrale Element und bei der Multiplikation auf den natürlichen Zahlen ist das neutrale Element. Deshalb ist es in der abstrakten Formulierung sinnvoll, eine unbelastete Bezeichnung zu wählen. Wenn die Verknüpfung kommutativ ist, so muss man die Eigenschaft des neutralen Elementes nur von einer Seite überprüfen.

Die Addition auf den natürlichen Zahlen ist eine vertraute Operation und es gibt viele Möglichkeiten, sie einzuführen. Je nach Kontext und Absicht sind unterschiedliche Ansätze besser geeignet. Zur rechnerischen Definition der Addition ist etwa das schriftliche Addieren im Dezimalsystem besonders effektiv, während zum Nachweis der Assoziativität die inhaltliche Interpretation als disjunkte Vereinigung von Mengen sinnvoll ist. Um ein klares Fundament zu haben, muss man sich bei einem systematisches Aufbau der Mathematik dafür entscheiden, was man als Definition nimmt, und dann beweisen, dass der gewählte Zugang auch andere Charakterisierungen erlaubt und somit mit anderen Zugängen übereinstimmt.

Wir wollen die Addition auf den natürlichen Zahlen definieren, und zwar allein unter Bezug auf das Nachfolgernehmen, das das Zählen charakterisiert. Das Nachfolgernehmen ist ein Prozess, den man iterieren kann. Sowohl der Startwert des Nachfolgernehmens als auch die Anzahl, wie oft ein Nachfolger genommen werden soll, wird durch natürliche Zahlen beschrieben. Die fache Durchführung eines Prozesses bedeutet, dass er so oft durchgeführt wird, wie es die Menge vorgibt.

Definition

Die Summe

zweier 

natürlicher Zahlen

ist diejenige natürliche Zahl, die man erhält, wenn man von ausgehend fach den Nachfolger nimmt.

Die Operation heißt die und die beteiligten Zahlen nennt man die Nach dieser Definition wird also ausgehend von der Nachfolgerprozess fach durchgeführt. Bei

ist dies als der nullte Nachfolger, also als selbst, zu verstehen. Bei

ist dies der erste Nachfolger, ist also die erste Zahl nach Die Summe ist also mit Nachfolgerstrichen. Wenn umgekehrt

ist, so ist der te Nachfolger der gleich Man beachte, dass hier die Addition in einer Weise definiert wird, in der die Kommutativität keineswegs offensichtlich ist, das wird sich aber gleich ergeben.

Lemma

Für die Addition der natürlichen Zahlen (mit der in Definition 8.10 festgelegten Addition) gelten die folgenden Aussagen.

1. für alle d.h. ist das neutrale Element der Addition.
2. für alle ().
3. Die Addition ist kommutativ.
4. Die Addition ist assoziativ.
5. Aus einer Gleichung folgt ().

Beweis

1. Die Gleichungen links und rechts sind unmittelbar klar, da der te Nachfolger der gleich ist.
2. Die Ausdrücke besagen prozesstheoretisch das gleiche: Links geht man von der Zahl aus und nimmt einmal öfters als mal den Nachfolger. In der Mitte bestimmt man fach den Nachfolger von und nimmt von diesem Ergebnis den Nachfolger. Rechts nimmt man von den Nachfolger und davon dann fach den Nachfolger.
3. Es ist für alle zu zeigen. Diese Gleichungen zeigen wir durch Induktion über für alle Bei steht beidseitig nach Teil (1). Es sei die Gleichheit nun für ein (und alle) schon bewiesen. Dann ist unter Verwendung der Induktionsvoraussetzung und Teil (2) die Gleichung gilt also auch für
4. Wir beweisen die Assoziativität, also die Gleichheit durch Induktion über (für alle gleichzeitig). Mit der Regel aus (2) und der Induktionsvoraussetzung ergibt sich direkt
5. Die Abziehregel beweisen wir ebenfalls durch Induktion über Der Fall ist klar. Es sei also die Aussage für ein schon bewiesen und sei eine Gleichung der Form gegeben. Dann ist nach der Umlegungsregel auch Nach der Induktionsvoraussetzung ist somit Da die Nachfolgerabbildung injektiv ist, ergibt sich

$\Box$

Für einige alternative Begründungen siehe die Aufgaben. Teil (2) kann man auch so verstehen, dass man eine Summe dadurch berechnen kann, dass man sukzessive den ersten Summanden um eins erhöht (also den Nachfolger nimmt) und den zweiten um eins vermindert (also den Vorgänger nimmt), falls

ist. Dies macht man so lange, bis der zweite Summand ist. Der dabei entstandene neue erste Summand ist die Summe. Statt Umlegungsregel sagt man auch

oder man spricht von einer  was auch oft bei Rechnungen effektiv eingesetzt wird, wenn man etwa

rechnet. Die folgende Aussage besagt, dass durch das Umlegungsprinzip die Addition bereits festgelegt ist.

Satz

Auf den natürlichen Zahlen

gibt es genau eine Verknüpfung

mit

Beweis

Die Addition erfüllt nach Lemma 8.11  (1, 2) diese Eigenschaften.

Es seien zwei Verknüpfungen

auf gegeben, die beide diese charakteristischen Eigenschaften erfüllen. Es ist zu zeigen, dass dann diese beiden Verknüpfungen überhaupt übereinstimmen. Wir müssen also die Gleichheit

für alle

beweisen. Dies machen wir durch Induktion über (für beliebige). Bei

ist wegen

die Aussage richtig. Es sei die Aussage nun für ein bestimmtes schon bewiesen. Dann ist mit der charakteristischen Eigenschaft und der Induktionsvoraussetzung

$\Box$

Lemma

Es seien natürliche Zahlen. Dann ist

nur bei

und

möglich.

Beweis

Wenn

wäre, so wäre ein Nachfolger einer natürlichen Zahl (nämlich der te Nachfolger von), was für die ausgeschlossen ist. Also ist

Wegen

ist auch der erste Summand gleich

$\Box$

Die Standardinterpretation der und wichtigste Motivation für die Addition zweier natürlicher Zahlen ist, dass sie die Anzahl der Vereinigung von zwei disjunkten endlichen Mengen angibt. Wenn man zwei Körbe von Äpfeln hat und diese zusammenschüttet, so ist die Gesamtanzahl gerade die Summe der beiden Einzelanzahlen. Es ist möglich, die Addition von natürlichen Zahlen darüber zu definieren. Vorteile sind die unmittelbare Anschauung, Nachteile, dass man eine Zahl durch eine endliche Menge repräsentieren muss, und nicht klar ist, welche man nehmen soll und es nicht selbstverständlich ist, dass unterschiedliche gleichgroße disjunkte Mengen nach Vereinigung gleichgroß sind (was heißt das?). Der Vorteil bei unserer Definition ist, dass man die Addition auf einen elementareren Prozess, nämlich den Prozess des Zählens bzw. Nachfolgernehmens zurückführt. Dies erlaubt es, Gesetzmäßigkeiten zu beweisen, indem sie per Induktion auf elementare Schritte zurückgeführt werden. Beide Konzepte sind wichtig, und natürlich will man, unabhängig davon, wie man die Addition nun eingeführt hat, schnell wissen, dass die beiden Konzepte übereinstimmen. Dazu ist es hilfreich, im Vereinigungskonzept auch Einzelschritte zu erkennen. Dies ist wieder das Umlegungsprinzip: Die Vereinigung kann man sich so vorstellen, dass schrittweise ein Element (ein Apfel) der zweiten Menge in die erste Menge umgelegt wird, siehe auch Aufgabe 4.15 und Aufgabe 5.16.

Bei einem solchen Einzelschritt erhöht sich die erste Anzahl um eins (Nachfolger) und die zweite Anzahl verringert sich um eins (Vorgänger). Das deckt sich mit Lemma 8.11  (2).

Satz

Es seien

disjunkte endliche Mengen mit

Elementen.

Dann besitzt ihre Vereinigung

gerade  Elemente. 

Beweis

Die Voraussetzung besagt, dass es eine bijektive Abbildung

und eine bijektive Abbildung

gibt. Die Abbildung

ist nach Aufgabe 8.34 bijektiv, sei die Umkehrabbildung. Somit ist nach Lemma 6.4  (3)

ebenfalls bijektiv. Wir definieren nun eine Abbildung

durch

Diese Abbildung ist surjektiv, da jedes Element aus durch den ersten Fall und jedes Element aus durch den zweiten Fall abgedeckt ist. Die Injektivität sieht man so. Wenn

gegeben sind, und das eine Element zu und das andere zu gehört, so ist

und

(oder umgekehrt) und sie sind verschieden wegen der Disjunktheit von

Wenn hingegen

aus der gleichen Teilmenge des Definitionsbereiches kommen, so ergibt sich die Verschiedenheit von

aus der Injektivität von bzw. von Insgesamt erhalten wir also eine bijektive Abbildung

sodass die Anzahl von gleich ist.

$\Box$

Bemerkung  

Das Zählen von natürlichen Zahlen kann man auch auf dem Zahlenstrahl realisieren, indem man ausgehend von einem Startpunkt schrittweise um eine Strecke einer fixierten Länge (Einheitsstrecke) nach rechts hüpft (wie in der fünften Vorlesung erwähnt) Die Addition bedeutet in diesem Modell, dass man vom Punkt ausgehend mal nach rechts hüpft. Das Umlegeprinzip bedeutet in diesem Kontext, dass man von dem einen Punkt aus nach rechts und vom anderen Punkt aus simultan nach links hüpft, bis der letztere Punkt im Nullpunkt landet. Die Addition bedeutet hier einfach, dass man die beiden gegebenen Punkte mit ihren Pfeilen (Vektoren) vom Nullpunkt aus identifiziert und dann diese Pfeile hintereinanderlegt. Dieses Modell hat den Vorteil, dass in ihm auch die Addition von rationalen Zahlen oder reellen Zahlen in gleicher Weise beschrieben werden kann.

Später werden wir in Satz 15.6 beweisen, dass die Addition mit dem schriftlichen Addieren ausgerechnet werden kann, dass also der Algorithmus des schriftlichen Addierens korrekt ist.

Zur Definition der Multiplikation verwenden wir wieder das Prinzip, dass man mit natürlichen Zahlen zählen kann. Die Addition haben wir bereits zur Verfügung und insbesondere können wir eine natürliche Zahl mit sich selbst addieren. Wir können auch Summen der Form

benutzen und können dabei, wegen der Assoziativität der Addition, auf Klammern verzichten. Die Anzahl der Summanden ist dabei eine wohldefinierte natürliche Zahl. Dies nehmen wir zur Grundlage für die Multiplikation.

Definition

Das Produkt

zweier 

natürlicher Zahlen ist definiert als die fache Summe der Zahl mit sich selbst.

Wichtig ist hier, dass die Anzahl der Summanden angibt, also wie oft zu nehmen ist, und nicht die Anzahl der Additionen (die Anzahl des Pluszeichens), die dabei auszuführen sind. Diese Anzahl ist um eins kleiner. Es spricht aber auch einiges dafür, dass man von ausgeht und dazu dann fach die Operation durchführt. Dann hat man

und fach den gleichen Prozess. Die beiden Zahlen

heißen das Ergebnis heißt das die Verknüpfung heißt

Wenn man die Addition beherrscht, so ist es einfach, die Multiplikation auszuführen und eine Tabelle für kleine Zahlen aufzustellen. Die Multiplikationstabelle für zwei Zahlen zwischen

das sogenannte lässt sich so erstellen (auch in anderen Systemen). Man kann dann grundsätzlich sämtliche Multiplikationen im Zehnersystem darauf zurückführen, was im schriftlichen Multiplizieren ausgenutzt wird, siehe die sechzehnte Vorlesung. Um große Zahlen effektiv miteinander multiplizieren zu können, muss man das kleine Einmaleins auswendig kennen. Eigentlich sollte man die aus dem kleinen Einmaleins herausnehmen, da die Zehnerreihe sich im Dezimalsystem auf kleinere Rechungen zurückführen lässt.

Für die soeben eingeführte Multiplikation möchte man die vertrauten Eigenschaften wie beispielsweise die Kommutativität etablieren. Dies geschieht in folgendem Lemma.

Lemma

Für die Multiplikation der natürlichen Zahlen (mit der in der Definition 9.1 festgelegten Multiplikation)

gelten folgende Aussagen.

1. Es gilt für alle
2. Es gilt für alle d.h. ist das neutrale Element für die Multiplikation.
3. Es ist und für alle
4. Die Multiplikation ist kommutativ.
5. Für beliebige gilt (Distributivgesetz).
6. Die Multiplikation ist assoziativ.

Beweis

1. Die zweite Gleichung ist klar, da unabhängig davon, wie oft die mit sich selbst addiert wird, stets herauskommt. Die erste Gleichung kann man als eine Konvention oder auch als Teil der Definition ansehen: Eine Summe, in der überhaupt keine Zahl vorkommt (die leere Summe), ist als zu interpretieren.
2. Die erste Gleichung ist klar, der Ausdruck besagt einfach, dass die Zahl einmal dasteht. Die zweite Gleichung bedeutet, dass die fache Addition der mit sich selbst gleich ist. Dies zeigen wir durch Induktion nach wobei der Induktionsanfang (für) klar ist. Es sei die Aussage also schon für bewiesen. Der Unterschied zwischen besteht darin, dass im zweiten Fall einmal mehr dasteht. Somit ist
3. Die linke Gleichung ergibt sich unmittelbar aus der Definition. Die rechte Gleichung ergibt sich aus

4. Die Kommutativität beweisen wir durch Induktion nach und zwar beweisen wir die Behauptung für alle Der Fall ist klar, da dann beidseitig steht. Es sei die Gesamtaussage also für ein bestimmtes und beliebiges bereits bewiesen. Dann ist unter Verwendung von (3) und der Induktionsvoraussetzung
5. Das Distributivgesetz beweisen wir durch Induktion nach für beliebige Der Fall ist klar, da beidseitig rauskommt. Unter Verwendung der Induktionsvoraussetzung und Teil (3) ergibt sich

6. Das Assoziativitätsgesetz beweisen wir durch Induktion nach dem ersten Faktor (wobei der Induktionsanfang wieder klar ist) unter Verwendung des Distributivgesetzes und Teil (3).

$\Box$

Es gilt insbesondere

und die rekursive Beziehung

Diese Eigenschaft nennen wir die sie ist ein Spezialfall des Distributivgesetzes. Ihre inhaltliche Bedeutung ist, dass sich die Anzahl der Elemente in einer Produktmenge (Tabelle) mit Reihen und Spalten um erhöht, wenn man eine zusätzliche Reihe anlegt. Diese beiden Eigenschaften legen bereits die Multiplikationsverknüpfung eindeutig fest.

Satz

Auf den natürlichen Zahlen

gibt es eine eindeutig bestimmte Verknüpfung

die

erfüllt.

Beweis

Es seien

zwei Verknüpfungen auf die beide diese Eigenschaften erfüllen. Wir müssen

für alle

zeigen. Wir führen Induktion nach Der Induktionsanfang ist klar, da wegen der ersten charakteristischen Eigenschaft

ist. Es sei die Aussage für ein gewisses schon bewiesen. Dann ist unter Verwendung der Induktionsvoraussetzung und der zweiten charakteristischen Eigenschaft

$\Box$

Die folgende Eigenschaft heißt

Lemma

Das Produkt zweier natürlicher Zahlen ist nur dann gleich wenn einer der Faktoren ist.

Beweis

Wir zeigen, dass mit

auch das Produkt von verschieden ist. Das Produkt ist

und hier steht mindestens ein Summand. Aus Lemma 8.13 und

folgt, dass diese Summe nicht ist.

$\Box$

Die folgende Eigenschaft heißt

Lemma

Aus einer Gleichung

mit

und mit

folgt

Beweis

Wir führen Induktion nach Bei

ist

nach Lemma 9.2  (1). Also ist

und wegen

folgt mit Lemma 9.4 daraus

Es sei die Aussage für ein (und beliebige

und) bewiesen. Die Aussage ist für den Nachfolger zu zeigen. Die Bedingung

kann bei

wegen Lemma 9.4 nicht gelten. Also ist ein Nachfolger, sagen wir

Somit ist

Aus der Abziehregel folgt

und aus der Induktionsvoraussetzung folgt

also

$\Box$

Satz

Es seien

endliche Mengen mit

Elementen.

Dann besitzt die Produktmenge genau Elemente.

Beweis

Wir führen Induktion über also die Anzahl von Wenn

ist, so ist leer und damit ist auch die Produktmenge leer, hat also ebenfalls Elemente, was nach Lemma 9.2  (1) mit dem Produkt übereinstimmt. Dies sichert den Induktionsanfang. Wenn

ist, so besteht aus genau einem Element, sagen wir und alle Elemente der Produktmenge haben die Form mit diesem einen und einem beliebigen

Somit ist

eine bijektive Abbildung und hat genau so viele Elemente wie nämlich Dies stimmt nach Lemma 9.2  (2) mit dem Produkt überein. Es sei nun die Aussage für alle Mengen mit Elementen (und beliebige endliche Mengen) bewiesen und es liege eine elementige Menge vor. Es sei

ein fixiertes Element und wir betrachten die disjunkte Zerlegung

Die Menge besitzt dann Elemente, sodass wir auf diese Menge die Induktionsvoraussetzung anwenden können. Ferner ist

und diese Vereinigung ist disjunkt (die erste Komponente eines Paares ist entweder oder nicht). Daher ist nach Satz 8.14 die Anzahl von gleich der Summe der Anzahlen der beiden Bestandteile, also nach der Induktionsvoraussetzung, dem einelementigen Spezialfall und Lemma 9.2  (3) gleich

$\Box$

Wir geben noch einen zweiten Beweis für die vorstehende Aussage.

Wir behaupten, dass die Abbildung

bijektiv ist. Zum Beweis der Surjektivität sei

vorgegeben. Dieses (ganzzahlige) Intervall kann man in die disjunkten Intervalle

unterteilen. Das Element gehört somit zu einem dieser Intervalle, d.h. es gibt ein mit

mit zwischen

Dann ist

mit einem zwischen

und gehört somit zum Bild. Zum Beweis der Injektivität seien

gegeben, die auf das gleiche Element abbilden. Es gilt also

Da

beide zu gehören, sind die Summen jeweils maximal gleich

Daher können die Zahlen nur dann gleich sein, wenn

und dann nach der Abziehregel auch

ist.

Definition

Zu einer natürlichen Zahl und einer natürlichen Zahl nennt man die fache Multiplikation von mit sich selbst

(Faktoren) die te Potenz von Sie wird mit bezeichnet.

Die Zahl heißt in diesem Zusammenhang die der Potenz und der Bei

ist dies als

zu verstehen. Dies gilt auch für also

wobei man hier häufig auf eine Festlegung verzichtet. Für positive Exponenten ist jedenfalls

Wie gesagt, der Exponent bestimmt die Anzahl der Faktoren

die Anzahl der auszuführenden Multiplikationen ist um eins kleiner. Man kann aber auch von ausgehen und die Potenz als

auffassen.

Bei fixiertem Exponenten bilden die Potenzen

die Menge aller ten Potenzen. Bei

ist das die Menge der Quadratzahlen, bei

die Menge der Kubikzahlen. Bei fixierter Basis bilden die Potenzen

die Menge aller er Potenzen, also alle Zweierpotenzen, alle Dreierpotenzen, u.s.w.

Als Rechenregeln für das Potenzieren halten wir die folgenden Eigenschaften fest.

Lemma

Für das Potenzieren gelten die folgenden Eigenschaften, wobei

und

seien.

Beweis

Siehe Aufgabe 9.22.

$\Box$

Definition

Eine Zahl der Form mit

heißt Quadratzahl

Wir wollen auf den natürlichen Zahlen die Größer- bzw. genauer die Größergleich-Ordnung einführen.

Definition

Eine Relation auf einer Menge ist eine Teilmenge der Produktmenge also

Statt

schreibt man man sagt, dass in der Relation zu steht, typische Symbole für sind

Definition

Eine Relation

auf einer Menge  heißt Ordnungsrelation oder Ordnung wenn folgende drei Bedingungen erfüllt sind.

1. Es ist für alle
2. Aus und folgt stets
3. Aus und folgt

Diese Eigenschaften heißen der Reihe nach und

Definition

Eine Ordnungsrelation

auf einer Menge  heißt lineare Ordnung 

(oder totale Ordnung), wenn zu je zwei Elementen

die Beziehung

gilt.

Definition

Man sagt, dass eine natürliche Zahl größergleich einer natürlichen Zahl ist, geschrieben

wenn man von aus durch endlichfaches Nachfolgernehmen zu gelangt.

Statt

schreibt man auch

(gesprochen kleinergleich). Die Schreibweise

bedeutet

und

Lemma

Für natürliche Zahlen

gilt   

genau dann, wenn es ein

mit

gibt.

Beweis

Die Zahl gibt an, wie oft man von aus den Nachfolger nehmen muss, um zu zu gelangen.

$\Box$

Lemma

Für die Größergleich-Relation in den natürlichen Zahlen gelten die folgenden Aussagen.

1. Es ist für alle
2. Es ist oder
3. Bei gilt oder

Beweis

Wir verwenden die Charakterisierung aus Lemma 10.5.

1. Ist klar wegen
2. Wir zeigen die Aussage oder für alle durch Induktion über Für ist die Aussage klar. Es sei also angenommen, dass die Aussage für ein bestimmtes gelte. Dann ist oder Im ersten Fall ist dann und insbesondere Im zweiten Fall ist mit einem und damit
3. Wird ähnlich wie (2) bewiesen, siehe Aufgabe 10.6.

$\Box$

Satz

Auf den natürlichen Zahlen

ist durch die Größergleich-Relation eine totale Ordnung definiert.

Beweis

Wir verwenden die Charakterisierung mit der Addition. Wegen

ist

Wenn

und

ist, so bedeutet dies, dass es natürliche Zahlen mit

und

gibt. Dann gilt insgesamt

und somit ist auch

Aus

und

ergibt sich

und

und somit

Dies ist nach der Abziehregel nur bei

möglich, und dies ist wiederum, da kein Nachfolger ist, nur bei

möglich. Die Aussage

oder

beweisen wir durch Induktion über (für jedes feste), wobei der Induktionsanfang wegen

klar ist. Die Aussage gelte also für ein bestimmtes Wenn die erste Möglichkeit gilt, also

so gilt wegen

erst recht

Wenn die zweite Möglichkeit gilt, also

so gibt es zwei Möglichkeiten. Bei

ist

und die Gesamtaussage gilt für Andernfalls ist

und somit ist nach Lemma 10.6  (3)

und die Gesamtaussage gilt erneut.

$\Box$

Wir begründen nun, dass die Ordnungsrelation mit der Addition und der Multiplikation verträglich ist.

Satz

Es seien natürliche Zahlen. Dann gelten folgende Aussagen.

1. Es ist genau dann, wenn ist.
2. Aus und folgt
3. Aus folgt
4. Aus und folgt
5. Aus und folgt

Beweis

1. Wir beweisen die Aussagen mit Lemma 10.5. Nach Voraussetzung gibt es ein mit Dann ist auch was bedeutet.
2. Zweifache Anwendung von Teil (1) liefert sodass die Transitivität den Schluss ergibt.
3. Die Voraussetzung bedeutet wieder mit einem Dann ist mit dem Distributivgesetz also
4. Aus den Voraussetzungen und Teil (3) ergibt sich
5. Sei Wir beweisen die Kontraposition, dass aus der Größerbeziehung die Größerbeziehung folgt. Es sei also Dann ist und somit ist nach Teil (3) und Teil (2) also

$\Box$

Die algorithmische Bestimmung der Ordnungsrelation im Dezimalsystem werden wir in Korollar 15.4 beschreiben.

Definition

Zu einer endlichen nichtleeren Teilmenge

heißt das Maximum von wenn

ist und wenn

für alle

gilt.

Definition

Zu einer nichtleeren Teilmenge

heißt das Minimum von wenn

ist und wenn

für alle

gilt.

Die leere Menge besitzt weder ein Maximum noch ein Minimum. Die Gesamtmenge besitzt das Minimum und kein Maximum.

Aus dem Induktionsprinzip folgt die nächste wichtige Eigenschaft, die besagt, dass die natürlichen Zahlen sind. 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. Es sei die Aussage nun für alle

schon bewiesen. Wir müssen beweisen. Es 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

$\Box$

Definition

Für natürliche Zahlen

ist diejenige natürliche Zahl für die

gilt. Sie heißt die Differenz zwischen und

Man mache sich hier die Logik dieser Definition klar: Die Voraussetzung

bedeutet nach Lemma 10.5 die Existenz einer natürlichen Zahl mit

Dieses ist aufgrund der Abziehregel durch diese Eigenschaft eindeutig bestimmt. Die Differenz gibt an, wie oft man von aus den Nachfolger nehmen muss, um zu zu gelangen. Die charakteristische Eigenschaft ist die Gleichheit

Dabei ist die einzige Lösung für die Gleichung

Ferner ist

Wenn eine Gleichung

gegeben ist, so sagt man beim Übergang zu

auch, dass (beidseitig) abgezogen wird.

Für

ist der Ausdruck innerhalb der natürlichen Zahlen nicht definiert. Da zu

stets

oder

gilt, ist einer der beiden Ausdrücke

eine wohldefinierte natürliche Zahl. Oft nennt man auch diese Zahl, die sich ergibt, wenn man die beiden Zahlen richtig geordnet hat, die Differenz der beiden Zahlen.

Für die Differenz können wir einfach eine mengentheoretische Interpretation angeben.

Satz

Es sei eine endliche Menge mit Elementen und es sei

eine Teilmenge, die Elemente besitze.

Dann besitzt

genau Elemente.

Beweis

Es ist

eine disjunkte Zerlegung. Daher gilt nach Satz 8.14

Somit erfüllt die charakteristische Eigenschaft der Differenz und ist daher gleich

$\Box$

Lemma

1. Für natürliche Zahlen mit ist Insbesondere ist und
2. Für natürliche Zahlen mit und ist Insbesondere ist bei stets
3. Bei ist und es ist

Beweis

Siehe Aufgabe 10.25.

$\Box$

Die folgende Aussage ist das Distributivgesetz für die Differenz.

Lemma

Es seien natürliche Zahlen mit

Dann ist

Beweis

Nach Satz 10.8 ist mit

auch

sodass wohldefiniert ist. Es ist

und daher ist nach dem Distributivgesetz für die Addition und die Multiplikation

Also ist

$\Box$