Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Vorlesung 13

Aus Wikiversity
Zur Navigation springen Zur Suche springen



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 letzen Vorlesung gesehen haben. In dieser Vorlesung geben wie einen Einblick, welche wichtigen Eigenschaften der natürlichen Zahlen bereits aus den erststufigen Peano-Axiomen folgen.


Definition  

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.22. Nach Aufgabe ***** 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 Konstruktionen 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).


Definition  

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:

  1. ist ein kommutatives Monoid.
  2. ist ein kommutatives Monoid.
  3. Es gilt das Distributivgesetz, also
    für alle .



Lemma  

Beweis  

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. Sei die Aussage also für ein bewiesen. Dann ist nach Axiom 12.10  (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, so dass 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.10  (4), die Induktionsvoraussetzung und einmal die Vorüberlegung angewendet haben. Für die weiteren Eigenschaften siehe Aufgabe 13.3, Aufgabe 13.4 und Aufgabe 13.16.




Lemma  

In einem Peano-Halbring

gilt für jedes die Eigenschaft: Entweder ist oder es gibt ein mit .

Beweis  

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. Sei also die Aussage für ein gewisses schon bewiesen, und sie ist für zu beweisen. Bei ist , so dass man nehmen kann. Bei ist

und somit kann man nehmen.




Lemma  

In einem Peano-Halbring

gilt die folgende Abzieh- bzw. Kürzungsregel.

  1. Für alle folgt aus die Gleichheit .
  2. Für alle mit folgt aus die Gleichheit .

Beweis  

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.10  (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.10  (4) gilt daher

und nach Axiom 12.10  (2) folgt

Die Induktionsvoraussetzung liefert

Für die Kürzungsregel siehe Aufgabe 13.6.


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 .



Lemma  

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.

Beweis  

Die Reflexivität folgt direkt aus Axiom 12.10  (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 Fakt ***** beispielsweise gelten und damit

ein Widerspruch zu Axiom 12.10  (1). Dass das kleinste Element ist, folgt direkt aus Axiom 12.10  (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. Sei die Aussage nun für ein bewiesen. Bei gilt erst recht . Sei also , wobei wir uns direkt auf beschränken können. Dies bedeutet und und somit . Also ist .




Satz  

In einem Peano-Halbring erfüllt

das Wohlordnungsprinzip für erststufige Ausdrücke. D.h. für jeden Ausdruck in der freien Variablen gilt

Beweis  

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



Satz  

Sei ein Peano-Halbring und .

Dann gibt es zu jedem eindeutig bestimmte mit[2] , , und mit

Beweis  

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 gelten. Dann ist

so dass das Geforderte leisten. Für die Eindeutigkeit siehe Aufgabe *****.


Beispiel  

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

und die Eigenschaft, ein größter gemeinsamer Teiler von und zu sein, durch

Damit setzen wir

Dies ist ein Ausdruck mit der einzigen freien Variablen , der inhaltlich besagt, dass für jedes Element unterhalb von der größte gemeinsame Teiler von und als Linearkombination aus und darstellbar ist. Dieser Ausdruck gilt innerhalb der natürlichen Zahlen (also für ), es handelt sich um das Lemma von Bezout. 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 für eine Primzahl (aus ) nehmen, die den Leitkoeffizienten von nicht teilt. Wegen ist auch . Der größte gemeinsame Teiler von und ist dann , doch die ist nicht als Linearkombination von und dem Polynom darstellbar (wenn man modulo geht, so verändert sich der Grad von 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
  1. Wir bezeichnen hier und im Folgenden die Variable und das ihr in einer Belegung zugewiesene Element mit dem gleichen Symbol.
  2. 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 2014) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)