Direkt zum Inhalt

Lexikon der Mathematik: Arithmetik zweiter Ordnung

(auch Peano-Arithmetik zweiter Stufe genannt, symbolisch PA2).

Das für die Arithmetik Erster Ordnung zugrundegelegte elementare Axiomensystem ist nicht vollständig, und nach dem Unvollständigkeitssatz von Gödel (Beweistheorie) gibt es kein rekursives Axiomensystem, aus dem sich genau die Aussagen beweisen lassen, die in dem Standardmodell gültig sind.

Es ist ein natürliches Bedürfnis, den Rahmen dieser axiomatischen Theorie so zu erweitern, daß man möglichst viele im Standardmodell gültige Aussagen erhält. Eine „radikale“ Methode der Axiomatisierung besteht darin, Quantifizierungen von beliebigen Elementen und Mengen zuzulassen, wie dies bei den Peanoschen Axiomen der Fall ist. Dann läßt sich zwar das Standardmodell bis auf Isomorphie beschreiben, aber die benutzte Logik ist nicht mehr vollständig, d. h., es gibt kein „überschaubares“ System von logischen Axiomen und Ableitungsregeln, so daß aus den Axiomen genau die allgemeingültigen Ausdrücke beweisbar sind (der Gödelsche Satz gilt für diese Logiken nicht).

Damit stehen wesentliche Hilfsmittel aus der Prädikatenlogik nicht mehr zur Verfügung.

Ein nützlicher Kompromiß wird durch die Arithmetik zweiter Ordnung angestrebt. Die benutzte (elementare) Sprache L2 enthält neben den Symbolen S, +, ·, 0, die in der Arithmetik Erster Ordnung verwendet wurden, noch die einstelligen Relationszeichen N, M und das zweistellige Relationszeichen ∈. Das dort formulierte Axiomensystem (i)−(v) wird um die folgenden Axiome (6)−(14) erweitert.

(6) ∀x:(N(x) ∨ M(x)) ∧ ¬∃x(N(x) ∧ M(x)).

Motiv für die Nutzung dieser Axiome ist die Vorstellung, daß der Individuenbereich A jeweils aus zwei Sorten von Individuen besteht, nämlich aus Elementen (den natürlichen Zahlen) und aus gewissen (nicht notwendig allen) Mengen von Elementen. N sondert aus A die Elemente und M die Mengen aus, und Mengen und Elemente sind disjunkt. Weitere Axiome sind:

(7) N(0) (Null ist eine natürliche Zahl),

(8) ∀x(N(x) → N(S(x))) (mit jeder Zahl x ist auch der unmittelbare Nachfolger von x eine natürliche Zahl),

(9) ∀xy(yxN(y) ∧ М(х)) (wenn у, x in der Beziehung ∈ stehen, dann ist у Element und x Menge von Elementen),

(10) Induktionsaxiom

x[M(x) ∧ 0 ∈ x ∧ ∀z(N(z) zx

S(z) ∈ x) → ∀z(N(z) → zx)],

das für jeden Ausdruck ϕ(z) die elementare Fassung

ϕ(0) ∧ ∀z(N(z) ∧ ϕ(z) → ϕ(S(z))) → ∀z(N(z) → ϕ(z))

des Induktionsaxioms impliziert.

Da in dieses Axiomensystem mengentheoretische Begriffe einfließen, benötigt man noch gewisse mengentheoretische Axiome.

(11) Extensionalitätsaxiom

xy(M(x) ∧ M(y) ∧ ∀z(zxzу) → x = у),

(12) Komprehensionsaxiom (Axiomenschema, für jeden Ausdruck ϕ(x) ein Axiom) ∃у(M(у) ∧ ∀x(xу&Ngr;(x) ∧ ϕ(x))), wobei x und у verschiedene Variablen sind und у in ϕ(x) nicht vorkommt.

Die mit S, +,· bezeichneten Funktionen sind zunächst nur für natürliche Zahlen definiert, also nicht in dem gesamten Individuenbereich, was aus formalen Gründen von Bedeutung ist. Daher werden diese Funktionen „künstlich“ durch die folgenden Axiome auch auf Mengen von natürlichen Zahlen erweitert.

(13) ∀x(M(x) → S(x) = 0),

(14) ∀xy(M(x) ∨ M(y) → x + у = 0 ∧ x · у = 0).

(i)–(v) und (6)–(14) ist die axiomatische Grundlage für PA2.

Ist A : = NP(N) die Vereinigung der Mengeder natürlichen Zahlen mit deren Potenzmenge und sind ∈, S, +, ·, 0 der Reihe nach die Elementbeziehung zwischen Zahlen und Mengen von Zahlen, die Nachfolgerfunktion, die Addition, die Multiplikation und das Nullelement von N, dann heißt \({\mathscr{A}}:=\langle A,N,M,\in, S,+,\cdot, 0\rangle \)Standardmodell von PA2. (Die Doppeldeutigkeit von N, ∈, S, +, ·, 0 als Zeichen in der benutzten Sprache und entsprechender Objekte in der Struktur \({\mathscr{A}}\) führt i.allg. nicht zu Verwechslungen.)

Ist ϕ ein Ausdruck aus L2, dann heißt ϕ gültig in PA2, wenn ϕ im Standardmodell gilt. Ein Nichtstandardmodell von PA2 ist eine Struktur

\begin{eqnarray}{\mathscr{A}}* :=\langle A*, N*, M*, \in *, S*, +*, \cdot *, 0* \rangle,\end{eqnarray}

die Modell von PA2 ist, wobei insbesondere A* = N*M*. \({\mathscr{A}}\) ist dann isomorph in \({\mathscr{A}}* \) enthalten, und o.B.d.A. ist N&Ngr;* und \(M* \subseteq {\mathscr{P}}(N* )\). Man vergleiche auch Axiomatische Mengenlehre.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos