Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Vorlesung 13
- Erststufige Peano-Arithmetik - Folgerungen und Ableitungen
Die in der zweiten Stufe formulierten Dedekind-Peano-Axiome legen die natürlichen Zahlen bis auf Isomorphie fest, wie wir in der letzten Vorlesung gesehen haben. In dieser Vorlesung geben wir einen Einblick, welche wichtigen Eigenschaften der natürlichen Zahlen bereits aus den erststufigen Peano-Axiomen (formuliert mit der arithmetischen Symbolmenge ) folgen. Für Mengen, die diese Axiome erfüllen, führen wir einen eigenen Namen ein.
Eine Menge mit zwei ausgezeichneten Elementen und und zwei Verknüpfungen und heißt Peano-Halbring, wenn diese Strukturen die erststufigen Peano-Axiome erfüllen.
Neben der Menge der natürlichen Zahlen gibt es weitere Peano-Halbringe, die allerdings nicht einfach zu konstruieren sind. Die Existenz solcher Modelle ergibt sich als Korollar aus dem Vollständigkeitssatz, siehe Aufgabe 15.11. Nach Aufgabe 13.33 enthält jeder Peano-Halbring ein Modell der natürlichen Zahlen als Teilmenge. Die Elemente dieser Teilmengen sind nicht mit erststufigen Ausdrücken, die aus den ersstufigen Peano-Axiomen folgen, von den anderen Elementen trennbar.
Wir ziehen einige Folgerungen aus den erststufigen Peano-Axiomen, und zwar argumentieren wir „mathematisch“ (also semantisch). D.h. wir zeigen für einen beliebigen Peano-Halbring (also ein mathematisches Objekt, das die Peano-Axiome erfüllt), dass gewisse Eigenschaften gelten müssen, so wie man aus den Gruppenaxiomen oder den Körperaxiomen gewisse Folgerungen zieht. In der Argumentation stellt man sich also einen Peano-Halbring vor, mit einer zugrunde liegenden Menge, einer Addition und einer Multiplikation u.s.w. Als Beweismittel sind nur die Axiome, die den Begriff eines Peano-Halbringes festlegen, erlaubt. Insbesondere darf man sich nicht auf das intendierte Modell, nämlich die natürlichen Zahlen, berufen, da es eben auch andere Peano-Halbringe gibt (obwohl deren Konstruktion schwierig ist). Die Situation ist vergleichbar zur schrittweisen axiomatischen Einführung der reellen Zahlen, wo es darum geht, Eigenschaften aus einer kleinen Menge aus Axiomen zu etablieren, ohne auf die reellen Zahlen selbst Bezug zu nehmen (ein großer Unterschied ist allerdings, dass die Konstruktion der natürlichen Zahlen einfach ist, die der reellen Zahlen aber nicht). Ein wichtiger Unterschied zu anderen mathematischen Konzepten ist, dass mit dem Induktionsschema die Peano-Axiome explizit auf prädikatenlogische Formulierungen Bezug nehmen.
Wir werden später im Rahmen des Vollständigkeitssatzes sehen, dass die hier gezogenen Folgerungen auch aus den Peano-Axiomen ableitbar sind. Der formale Nachweis der Ableitbarkeit ist im Allgemeinen, verglichen mit einem „natürlichen Beweis“, deutlich umständlicher. Wir werden gelegentlich Ableitungsbeweise andeuten.
Die grundlegende allgemeine Struktur, die aus den Peano-Axiomen ableitbar ist, ist die eines kommutativen Halbringes (daher auch der Name Peano-Halbring).
Ein kommutativer Halbring ist eine Menge mit zwei Verknüpfungen und (genannt Addition und Multiplikation) und mit zwei ausgezeichneten Elementen und derart, dass folgende Bedingungen erfüllt sind:
- ist ein kommutatives Monoid.
- ist ein kommutatives Monoid.
- Es gilt das Distributivgesetz, also
für alle
.
Ein Peano-Halbring
ist ein kommutativer Halbring.
Es sei ein Peano-Halbring. Nur die Eigenschaft, dass das neutrale Element (von rechts) der Addition ist, tritt unmittelbar in den Peano-Axiomen auf. Die (erststufig formulierte) Eigenschaft , also für alle [1] zeigen wir durch Induktion über . Für ist dies klar. Es sei die Aussage also für ein bewiesen. Dann ist nach Axiom 12.11 (4) und der Induktionsvoraussetzung
Wir zeigen zunächst, dass das vierte Axiom, also die Eigenschaft , auch gilt, wenn man den ersten Summanden erhöht, also
Dies zeigen wir (für jedes ) durch Induktion über . Der Fall ist klar, da neutrales Element ist. Der Übergang von nach folgt aus
wobei wir das vierte Axiom und die Induktionsvoraussetzung angewendet haben.
Zum Nachweis der Kommutativität der Addition betrachten wir zu festem die Eigenschaft, dass
für alle ist. Dies wird erststufig durch
formalisiert, sodass wir also Induktion über anwenden können. Wir müssen also zeigen, dass diese Eigenschaft für wahr ist (was stimmt, da von beiden Seiten neutrales Element ist) und dass sie, wenn sie für ein gilt, dann auch für gilt. Dies folgt aber aus
wobei wir das Axiom 12.11 (4), die Induktionsvoraussetzung und einmal die Vorüberlegung angewendet haben. Für die weiteren Eigenschaften siehe Aufgabe 13.15, Aufgabe 13.16 und Aufgabe 13.34.
In einem Peano-Halbring
gilt für jedes die Eigenschaft: Entweder ist oder es gibt ein mit .
Beide Teilaussagen können wegen des ersten Peano-Axioms nicht zugleich wahr sein. Es geht also um die Aussage
die wir durch Induktion beweisen. Der Induktionsanfang für ist durch den linken Bestandteil gesichert. Es sei also die Aussage für ein gewisses schon bewiesen, und sie ist für zu beweisen. Bei ist , sodass man nehmen kann. Bei ist
und somit kann man nehmen.
In einem Peano-Halbring
gilt die folgende Abzieh- bzw. Kürzungsregel.
- Für alle folgt aus die Gleichheit .
- Für alle mit folgt aus die Gleichheit .
Seien fixiert. Wir betrachten die Aussage, dass für alle die angegebene Eigenschaft gilt, also dass aus schon folgt. Diese Eigenschaft ist erststufig formulierbar. Sie gilt für nach Axiom 12.11 (3). Nehmen wir an, sie gilt für ein bestimmtes, aber beliebiges . Wir müssen die Aussage für zeigen. Es ist also
Aufgrund von Axiom 12.11 (4) gilt daher
und nach Axiom 12.11 (2) folgt
Die Induktionsvoraussetzung liefert
Für die Kürzungsregel siehe Aufgabe 13.35.
In jedem Peano-Halbring lässt sich durch
eine Relation definieren, die sich einfach als eine totale Ordnung nachweisen lässt. Wir schreiben als Abkürzung für und .
In einem Peano-Halbring ist
eine totale Ordnung mit als kleinstem Element. Für jedes , , ist
Die Ordnung ist mit der Addition und der Multiplikation verträglich.
Die Reflexivität folgt direkt aus Axiom 12.11 (3). Die Transitivität ergibt sich unmittelbar, da ja und bedeutet, dass es mit und mit gibt, woraus sich
also ergibt. Zum Beweis der Antisymmetrie sei und , also und mit gewissen . Dann gilt auch
Aus der Abziehregel folgt
Wären nicht beide , so würde nach Lemma 13.4 beispielsweise gelten und damit
ein Widerspruch zu Axiom 12.11 (1). Dass das kleinste Element ist, folgt direkt aus Axiom 12.11 (3). Die Verträglichkeit mit der Addition ergibt sich direkt, die mit der Multiplikation folgt aus dem Distributivgesetz. Bei ist nach der Vorgängereigenschaft und daher . Zum Nachweis der totalen Ordnung seien gegeben. Wir beweisen die Eigenschaft, dass zu festem für alle die Eigenschaft gilt, durch Induktion über . Bei ist dies klar. Es sei die Aussage nun für ein bewiesen. Bei gilt erst recht . Es sei also , wobei wir uns direkt auf beschränken können. Dies bedeutet und und somit . Also ist .
In einem Peano-Halbring erfüllt
das Wohlordnungsprinzip für erststufige Ausdrücke. D.h. für jeden Ausdruck in der freien Variablen gilt
Wir betrachten den Ausdruck
und wollen zeigen, dass er in jedem Peano-Halbring gilt. Dies zeigen wir unter Verwendung des Induktionsaxioms und fixieren einen Peano-Halbring . Für ist die Aussage richtig, da dann, falls der Vordersatz gilt, dann insbesondere in gilt und man im Nachsatz
nehmen kann, da ja das kleinste Element ist. Zum Beweis des Induktionsschrittes müssen wir die Gültigkeit von
zeigen. Es sei also die Aussage für ein bestimmtes (also der Vordersatz links) im Modell wahr. Wir müssen dann den Nachsatz, also die Aussage für als wahr erweisen. Es gelte also
Wenn sogar gilt, so sind wir nach Induktionsvoraussetzung fertig. Es gelte diese Aussage also nicht. Das bedeutet einerseits, dass der Ausdruck für kein Element aus gilt, das kleiner als oder gleich ist, und andererseits, dass gilt, wenn durch interpretiert wird. Somit gilt der Ausdruck
und damit
Die Zahlentheorie beginnt mit der Division mit Rest.
Wir betrachten zum Nachweis der Existenz die erststufige Aussage
die als einzige freie Variable besitzt. Für ist die Aussage mit und
richtig. Zum Beweis des Induktionsschritts sei
mit den angegebenen Eigenschaften. Daher ist
Wenn kleiner als ist, so erfüllen die geforderten Eigenschaften. Bei muss nach Aufgabe 13.24 gelten. Dann ist
sodass und das Geforderte leisten. Für die Eindeutigkeit siehe Aufgabe 13.20.
Mit der Division mit Rest kann man weitere, aus der elementaren Zahlentheorie bekannte Gesetzmäßigkeiten in jedem Peano-Halbring etablieren, wie die Existenz des größten gemeinsamen Teilers, des kleinsten gemeinsamen Vielfaches, u.s.w. Für die Teilbarkeitsbeziehung schreiben wir . Gemeint ist damit, dass es ein Element mit gibt.
Wir betrachten die Teilmenge
des Polynomrings in der Variablen über , die aus dem Nullpolynom und allen Polynomen besteht, deren Leitkoeffizient zu gehört. Die Menge umfasst die natürlichen Zahlen (als Polynome vom Grad mit nichtnegativem Leitkoeffizient) und sie ist abgeschlossen unter Addition und Multiplikation. Es gelten die erststufigen Peano-Axiome (1)-(6), wie man direkt sieht. Auch gilt die Vorgängereigenschaft, d.h. jedes von verschiedene Element besitzt einen eindeutigen Vorgänger (dies ist der Grund, warum wir abgesehen für den Leitkoeffizienten auch negative Koeffizienten zulassen), siehe Aufgabe 13.30. Dagegen gilt das erststufige Induktionsschema nicht, und die natürlichen Zahlen lassen sich als Teilmenge von erststufig charakterisieren. Zur Vereinfachung der folgenden Formulierung definieren wir die -Relation durch
dies ist eine totale Ordnung nach Aufgabe 14.25. Damit setzen wir
Dies ist ein Ausdruck mit der einzigen freien Variablen , der inhaltlich besagt, dass die Division mit Rest gilt, wenn die beteiligten Eingangsdaten und unterhalb von liegen. Dieser Ausdruck gilt innerhalb der natürlichen Zahlen (also für ). Dagegen gilt sie in nicht, und zwar gilt sie dort nur für die natürlichen Zahlen. Für ein Polynom aus vom Grad kann man nämlich und für eine Primzahl (aus ) nehmen, die den Leitkoeffizienten von nicht teilt. Die Differenz zwischen und einem jeden Vielfachen von ist ein nichtkonstantes Polynom, daher gilt die Division mit Rest dafür nicht.
Wir betrachten nun die Induktionsversion dieser Aussage, also
Der Vordersatz gilt in , da die beschriebene Eigenschaft genau für die natürlichen Zahlen und für alle anderen Elemente nicht gilt, und daher genau dann gilt, wenn sie auch für den Nachfolger gilt (die echten Polynome sind nicht als Nachfolger von natürlichen Zahlen erreichbar). Da der Nachsatz nicht gilt, ergibt sich, dass die Gesamtaussage nicht gilt.
- Fußnoten
- ↑ Wir bezeichnen hier und im Folgenden die Variable und das ihr in einer Belegung zugewiesene Element mit dem gleichen Symbol.
- ↑ Bei der üblichen Formulierung der Division mit Rest über schreibt man , doch ist dies hier überflüssig, da es keine negativen Zahlen in einem Peano-Halbring gibt.
<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2018) | >> |
---|