Erststufige Peanoarithmetik/Folgerungen/Textabschnitt

Definition

Eine Menge ${}M$ mit zwei ausgezeichneten Elementen ${}0$ und ${}1$ und zwei Verknüpfungen ${}+$ und ${}\cdot$ heißt Peano-Halbring, wenn diese Strukturen die erststufigen Peano-Axiome erfüllen.

Neben der Menge der natürlichen Zahlen ${}\mathbb {N}$ 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. 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 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).

Definition

Ein kommutativer Halbring ${}R$ ist eine Menge mit zwei Verknüpfungen ${}+$ und ${}\cdot$ (genannt Addition und Multiplikation) und mit zwei ausgezeichneten Elementen ${}0$ und ${}1$ derart, dass folgende Bedingungen erfüllt sind:

1. ${}(R,+,0)$ ist ein kommutatives Monoid.
2. ${}(R,\cdot ,1)$ ist ein kommutatives Monoid.
3. Es gilt das Distributivgesetz, also

   ${}a\cdot (b+c)=(a\cdot b)+(a\cdot c)\,$

   für alle

   ${}a,b,c\in R$.

Lemma

Ein Peano-Halbring

ist ein kommutativer Halbring.

Beweis

Es sei ${}M$ ein Peano-Halbring. Nur die Eigenschaft, dass ${}0$ das neutrale Element (von rechts) der Addition ist, tritt unmittelbar in den Peano-Axiomen auf. Die (erststufig formulierte) Eigenschaft ${}\forall x{\left(0+x=x\right)}$, also ${}0+x=x$ für alle ${}x\in M$ zeigen wir durch Induktion über ${}x$. Für ${}x=0$ ist dies klar. Es sei die Aussage also für ein ${}x\in M$ bewiesen. Dann ist nach Axiom  (4) und der Induktionsvoraussetzung

${}0+(x+1)=(0+x)+1=x+1\,.$

Wir zeigen zunächst, dass das vierte Axiom, also die Eigenschaft ${}x+(y+1)=(x+y)+1$, auch gilt, wenn man den ersten Summanden erhöht, also

${}(x+1)+y=(x+y)+1\,.$

Dies zeigen wir (für jedes ${}x$) durch Induktion über ${}y$. Der Fall ${}y=0$ ist klar, da ${}0$ neutrales Element ist. Der Übergang von ${}y$ nach ${}y+1$ folgt aus

${}(x+1)+(y+1)=((x+1)+y)+1=((x+y)+1)+1=(x+(y+1))+1\,,$

wobei wir das vierte Axiom und die Induktionsvoraussetzung angewendet haben.

Zum Nachweis der Kommutativität der Addition betrachten wir zu festem ${}y\in M$ die Eigenschaft, dass

${}x+y=y+x\,$

für alle ${}x$ ist. Dies wird erststufig durch

$\forall x(x+y)=(y+x)$

formalisiert, sodass wir also Induktion über ${}y$ anwenden können. Wir müssen also zeigen, dass diese Eigenschaft für ${}y=0$ wahr ist (was stimmt, da ${}0$ von beiden Seiten neutrales Element ist) und dass sie, wenn sie für ein ${}y$ gilt, dann auch für ${}y+1$ gilt. Dies folgt aber aus

${}x+(y+1)=(x+y)+1=(y+x)+1=(y+1)+x\,,$

wobei wir das Axiom  (4), die Induktionsvoraussetzung und einmal die Vorüberlegung angewendet haben. Für die weiteren Eigenschaften siehe Aufgabe, Aufgabe und Aufgabe.

$\Box$

Lemma

In einem Peano-Halbring ${}M$

gilt für jedes ${}x\in M$ die Eigenschaft: Entweder ist ${}x=0$ oder es gibt ein ${}u\in M$ mit ${}x=u+1$.

Beweis

Beide Teilaussagen können wegen des ersten Peano-Axioms nicht zugleich wahr sein. Es geht also um die Aussage

$\forall x{\left({\left(x=0\right)}\vee {\left(\exists u{\left(x=u+1\right)}\right)}\right)},$

die wir durch Induktion beweisen. Der Induktionsanfang für ${}x=0$ ist durch den linken Bestandteil gesichert. Es sei also die Aussage für ein gewisses ${}x$ schon bewiesen, und sie ist für ${}x+1$ zu beweisen. Bei ${}x=0$ ist ${}x+1=0+1$, sodass man ${}u=0$ nehmen kann. Bei ${}x=u+1$ ist

${}x+1=(u+1)+1\,$

und somit kann man ${}u+1$ nehmen.

$\Box$

Lemma

In einem Peano-Halbring ${}M$

gilt die folgende Abzieh- bzw. Kürzungsregel.

1. Für alle ${}x,y,z\in M$ folgt aus ${}x+z=y+z$ die Gleichheit ${}x=y$.
2. Für alle ${}x,y,z\in M$ mit ${}z\neq 0$ folgt aus ${}xz=yz$ die Gleichheit ${}x=y$.

Beweis

Seien ${}x,y\in M$ fixiert. Wir betrachten die Aussage, dass für alle ${}z$ die angegebene Eigenschaft gilt, also dass aus ${}x+z=y+z$ schon ${}x=y$ folgt. Diese Eigenschaft ist erststufig formulierbar. Sie gilt für ${}z=0$ nach Axiom  (3). Nehmen wir an, sie gilt für ein bestimmtes, aber beliebiges ${}z$. Wir müssen die Aussage für ${}z+1$ zeigen. Es ist also

${}x+(z+1)=y+(z+1)\,.$

Aufgrund von Axiom  (4) gilt daher

${}(x+z)+1=(y+z)+1\,$

und nach Axiom  (2) folgt

${}x+z=y+z\,.$

Die Induktionsvoraussetzung liefert

${}x=y\,.$

Für die Kürzungsregel siehe Aufgabe.

$\Box$

In jedem Peano-Halbring lässt sich durch

$x\geq y{\text{ genau dann, wenn es ein }}z{\text{ mit }}x=y+z{\text{ gibt }}$

eine Relation definieren, die sich einfach als eine totale Ordnung nachweisen lässt. Wir schreiben ${}x>y$ als Abkürzung für ${}x\geq y$ und ${}x\neq y$.

Lemma

In einem Peano-Halbring ${}M$ ist ${}\geq$

eine totale Ordnung mit ${}0$ als kleinstem Element. Für jedes ${}x\in M$, ${}x\neq 0$, ist

${}x\geq 1\,.$

Die Ordnung ist mit der Addition und der Multiplikation verträglich.

Beweis

Die Reflexivität folgt direkt aus Axiom  (3). Die Transitivität ergibt sich unmittelbar, da ja ${}x\geq y$ und ${}y\geq z$ bedeutet, dass es ${}u,v\in M$ mit ${}x=y+u$ und mit ${}y=z+v$ gibt, woraus sich

${}x=z+v+u\,,$

also ${}x\geq z$ ergibt. Zum Beweis der Antisymmetrie sei ${}x\geq y$ und ${}y\geq x$, also ${}x=y+u$ und ${}y=x+v$ mit gewissen ${}u,v\in M$. Dann gilt auch

${}x=x+u+v\,.$

Aus der Abziehregel folgt

${}0=u+v\,.$

Wären ${}u,v$ nicht beide ${}0$, so würde nach Fakt beispielsweise ${}u=t+1$ gelten und damit

${}0=(t+v)+1\,,$

ein Widerspruch zu Axiom  (1). Dass ${}0$ das kleinste Element ist, folgt direkt aus Axiom  (3). Die Verträglichkeit mit der Addition ergibt sich direkt, die mit der Multiplikation folgt aus dem Distributivgesetz. Bei ${}x\neq 0$ ist ${}x=t+1$ nach der Vorgängereigenschaft und daher ${}x\geq 1$. Zum Nachweis der totalen Ordnung seien ${}x,y\in M$ gegeben. Wir beweisen die Eigenschaft, dass zu festem ${}x$ für alle ${}y$ die Eigenschaft ${}(x\geq y)\vee (y\geq x)$ gilt, durch Induktion über ${}y$. Bei ${}y=0$ ist dies klar. Es sei die Aussage nun für ein ${}y$ bewiesen. Bei ${}y\geq x$ gilt erst recht ${}y+1\geq x$. Es sei also ${}x\geq y$, wobei wir uns direkt auf ${}x>y$ beschränken können. Dies bedeutet ${}x=y+u$ und ${}u\neq 0$ und somit ${}u\geq 1$. Also ist ${}x\geq y+1$.

$\Box$

Satz

In einem Peano-Halbring ${}M$ erfüllt ${}\geq$

das Wohlordnungsprinzip für erststufige Ausdrücke. D.h. für jeden Ausdruck ${}\alpha \in L^{\{0,1,+,\cdot \}}$ in der freien Variablen ${}x$ gilt

$\exists x\alpha \rightarrow \exists y{\left(\alpha {\frac {y}{x}}\wedge \forall x{\left(\alpha \rightarrow x\geq y\right)}\right)}.$

Beweis

Wir betrachten den Ausdruck

$\forall u{\left(\exists x{\left(\alpha \wedge x\leq u\right)}\rightarrow \exists y{\left(\alpha {\frac {y}{x}}\wedge \forall x{\left(\alpha \rightarrow x\geq y\right)}\right)}\right)}$

und wollen zeigen, dass er in jedem Peano-Halbring gilt. Dies zeigen wir unter Verwendung des Induktionsaxioms und fixieren einen Peano-Halbring ${}M$. Für ${}u=0$ ist die Aussage richtig, da dann, falls der Vordersatz ${}\exists x{\left(\alpha \wedge x\leq 0\right)}$ gilt, dann insbesondere ${}\alpha {\frac {0}{x}}$ in ${}M$ gilt und man im Nachsatz

${}y=0\,$

nehmen kann, da ja ${}0$ das kleinste Element ist. Zum Beweis des Induktionsschrittes müssen wir die Gültigkeit von

$\forall u{\left({\left(\exists x{\left(\alpha \wedge x\leq u\right)}\rightarrow \exists y{\left(\alpha {\frac {y}{x}}\wedge \forall x{\left(\alpha \rightarrow y\leq x\right)}\right)}\right)}\rightarrow {\left(\exists x{\left(\alpha \wedge x\leq u+1\right)}\rightarrow \exists y{\left(\alpha {\frac {y}{x}}\wedge \forall x{\left(\alpha \rightarrow x\geq y\right)}\right)}\right)}\right)}$

zeigen. Es sei also die Aussage für ein bestimmtes ${}u\in M$ (also der Vordersatz links) im Modell wahr. Wir müssen dann den Nachsatz, also die Aussage für ${}u+1$ als wahr erweisen. Es gelte also

$\exists x{\left(\alpha \wedge x\leq u+1\right)}.$

Wenn sogar ${}\exists x{\left(\alpha \wedge x\leq u\right)}$ gilt, so sind wir nach Induktionsvoraussetzung fertig. Es gelte diese Aussage also nicht. Das bedeutet einerseits, dass der Ausdruck ${}\alpha$ für kein Element aus ${}M$ gilt, das kleiner als oder gleich ${}u$ ist, und andererseits, dass ${}\alpha$ gilt, wenn ${}x$ durch ${}u+1$ interpretiert wird. Somit gilt der Ausdruck

$\alpha {\frac {u+1}{x}}\wedge \forall x{\left(\alpha \rightarrow x\geq u+1\right)}$

und damit

$\exists y{\left(\alpha {\frac {y}{x}}\wedge \forall x{\left(\alpha \rightarrow x\geq y\right)}\right)}.$

$\Box$

Die Zahlentheorie beginnt mit der Division mit Rest.

Satz

Es sei ${}M$ ein Peano-Halbring und ${}d\geq 1$.

Dann gibt es zu jedem ${}m\in M$ eindeutig bestimmte ${}q,r\in M$ mit ${}r<d$ und mit

${}m=qd+r\,.$

Beweis

Wir betrachten zum Nachweis der Existenz die erststufige Aussage

$\forall d{\left(d\geq 1\rightarrow \exists q\exists r{\left(m=dq+r\wedge r\leq d\wedge \neg r=d\right)}\right)},$

die ${}m$ als einzige freie Variable besitzt. Für ${}m=0$ ist die Aussage mit ${}q=0$ und

${}r=0\,$

richtig. Zum Beweis des Induktionsschritts sei

${}m=dq+r\,$

mit den angegebenen Eigenschaften. Daher ist

${}m+1=dq+r+1\,.$

Wenn ${}r'=r+1$ kleiner als ${}d$ ist, so erfüllen ${}q,r'$ die geforderten Eigenschaften. Bei ${}r+1\geq d$ muss ${}r+1=d$ nach Aufgabe gelten. Dann ist

${}m+1=dq+r+1=dq+d=d(q+1)\,,$

sodass ${}q+1$ und ${}0$ das Geforderte leisten. Für die Eindeutigkeit siehe Aufgabe.

$\Box$