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

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 L₂ 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) ∀x∀y(y ∈ x → N(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) ∧z ∈ x →

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

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

∀x∀y(M(x) ∧ M(y) ∧ ∀z(z ∈ x ↔ z ∈ у) → 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) ∀x∀y(M(x) ∨ M(y) → x + у = 0 ∧ x · у = 0).

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

Ist A : = N ⋃ P(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 PA₂. (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 L₂, dann heißt ϕ gültig in PA₂, wenn ϕ im Standardmodell gilt. Ein Nichtstandardmodell von PA₂ ist eine Struktur

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