Peano-Arithmetik

Die Peano-Arithmetik (erster Stufe) ist eine Theorie der Arithmetik, also der Natürlichen Zahlen, innerhalb der Prädikatenlogik erster Stufe. Als Axiome werden die Peano-Axiome verwendet, wobei das Induktionsaxiom durch ein Axiomenschema ersetzt werden muss. Da in der Prädikatenlogik erster Stufe keine Aussage über Mengen von Objekten möglich ist, benötigt man für jede Formel ϕ(x,y₁,...,y_k) das Axiom

$\forall y_1 ... \forall y_k (\phi(0,y_1,...,y_k) \land \forall x ( \phi(x,y_1,...,y_k)\rightarrow\phi(x+1,y_1,...,y_k)) \rightarrow \forall x \phi(x,y_1,...,y_k))$

Andere erststufige Formalisierungen der natürlichen Zahlen, die mit der Peano-Arithmetik verwandt sind, sind beispielsweise die Robinson-Arithmetik und die Primitiv rekursive Arithmetik, die auch Teile der Peano-Axiome benutzen.

Unvollständigkeit

Nach den Gödelschen Unvollständigkeitssätzen ist die Peano-Arithmetik unvollständig, das heißt, es gibt Formeln in ihrer Sprache, die sie weder beweisen noch widerlegen kann. Im Beweis des ersten Unvollständigkeitssatzes konstruiert Gödel eine nur dem Beweiszweck dienende, eher künstliche Formel, die ihre eigene Unbeweisbarkeit behauptet. Daneben gibt es aber auch natürlichere mathematische Aussagen, von denen bekannt ist, dass sie weder beweisbar noch widerlegbar sind. Zu diesen zählen gemäß dem zweiten Unvollständigkeitssatz die Konsistenz der Peano-Arithmetik ebenso wie der Satz von Goodstein und die transfinite Induktion bis zur Ordinalzahl ε₀.

Nichtstandardmodelle

Modelltheoretisch entspricht der Unvollständigkeit der Arithmetik die Existenz von Nichtstandardmodellen, die zum Standardmodell $\N$ nicht isomorph sind. Die natürlichen Zahlen sind durch diese Theorie also nicht eindeutig bestimmt. Nach dem Löwenheim-Skolem-Theorem hat die Arithmetik Modelle für jede unendliche Kardinalzahl. Aus dem Kompaktheitssatz folgt zudem die Existenz von abzählbaren Nichtstandardmodelle der Arithmetik, wie Thoralf Skolem 1934 zeigte. Dazu betrachte man mit Φ als der Axiomenmenge der Peano-Arithmetik die abzählbare Aussagenmenge $\Phi\cup\{\neg x=n|n\in\{\mathbf{0},\mathbf{1}, \dots\}\}$, deren endliche Teilmengen alle erfüllbar sind.

Alle abzählbaren Nichtstandardmodelle haben den Ordnungstyp ω + η·π , wobei ω der Ordnungstyp der natürlichen Zahlen ist, π der Ordnungstyp der ganzen Zahlen und η der Ordnungstyp der rationalen Zahlen. Dies entspricht einer Kopie der natürlichen Zahlen gefolgt von einer abzählbar unendlichen, dichten Menge von Kopien der ganzen Zahlen. Darüber hinaus lässt sich die Struktur der Nichtstandardmodelle nur eingeschränkt untersuchen. Nach dem Satz von Tennenbaum gibt es kein abzählbares Nichtstandardmodell, in dem Addition oder Multiplikation berechenbar sind.

Konsistenz

1900 stellte David Hilbert als zweites der sogenannten hilbertschen Probleme das Problem, die Konsistenz der Peano-Axiome nur mit finiten Mitteln zu beweisen. 1931 bewies Kurt Gödel seinen Unvollständigkeitssatz, der zeigt, dass ein solcher Konsistenzbeweis mit den Mitteln der Peano-Arithmetik und damit auch mit schwächeren Mitteln nicht möglich ist. Ein Beweis in der stärkeren, aber nicht als finit anerkannten Zermelo-Fraenkel-Mengenlehre ist dagegen möglich. Ob dennoch ein finiter Beweis möglich ist, hängt von der Definition „finiter“ Mittel ab. Es wurden verschiedene Beweise publiziert, die die Konsistenz der Arithmetik mit Mitteln beweisen, die in der Peano-Arithmetik selbst nicht beweisbar sind, von vielen Mathematikern aber trotzdem als finit anerkannt werden. 1936 veröffentlichte Gerhard Gentzen einen Konsistenzbeweis mithilfe transfiniter Induktion bis ε₀. 1958 führte Gödel die Konsistenz auf ein typentheoretisches System zurück. Die meisten Mathematiker halten die Peano-Axiome heute für konsistent.

Literatur

• H.-.D- Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik (5. Auflage). Spektrum, 2007.
• Gerhard Gentzen: Die Widerspruchsfreiheit der reinen Zahlentheorie. In: Mathematische Annalen 112, 1936, Seite 132–213.
• Kurt Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik, 38. 1931, Seite 173–98.
• Kurt Gödel: Über eine bisher noch nicht benüzte Erweiterung des finiten Standpunktes. In: Dialectica 12, 1958, Seite 280–87.
• Richard Kaye: Models of Peano arithmetic. Oxford University Press, 1991. ISBN 0-19-853213-X.