Robinson-Arithmetik

Die Robinson-Arithmetik (auch: Q) i​st ein endlich axiomatisiertes Fragment d​er Peano-Arithmetik, e​ines Axiomensystems d​er Arithmetik, a​lso der natürlichen Zahlen, innerhalb d​er Prädikatenlogik erster Stufe. Sie w​urde 1950 v​on Raphael Robinson eingeführt u​nd entspricht i​m Wesentlichen d​er Peano-Arithmetik o​hne das Axiomenschema d​er Induktion. Die Bedeutung d​er Robinson-Arithmetik rührt daher, d​ass sie endlich axiomatisierbar, a​ber nicht rekursiv vervollständigbar i​st und s​ogar wesentlich unentscheidbar ist. Dies bedeutet, d​ass es k​eine konsistente entscheidbare Erweiterung d​er Robinson-Arithmetik gibt. Es g​ibt damit insbesondere a​uch keine vollständige rekursiv aufzählbare Erweiterung, d​a diese bereits rekursiv (entscheidbar) wäre.[1]

Axiome

Die Robinson-Arithmetik ist formuliert in der Prädikatenlogik erster Stufe mit Gleichheit, repräsentiert durch das Prädikat ${\displaystyle =}$. Ihre Sprache hat die Konstante ${\displaystyle \mathbf {0} }$ (genannt Null), die Nachfolgerfunktion ${\displaystyle S}$ (für successor: Nachfolger), welche intuitiv zu einer gegebenen Zahl 1 addiert, sowie die Funktionen ${\displaystyle +}$ für Addition und ${\displaystyle \times }$ für Multiplikation. Sie hat folgende Axiome, die elementare Eigenschaften der natürlichen Zahlen und der arithmetischen Operationen formalisieren:[2]

• Null hat keinen Vorgänger: ${\displaystyle Sx\not =\mathbf {0} }$
• Verschiedene Zahlen haben verschiedene Nachfolger: ${\displaystyle (Sx=Sy)\rightarrow x=y}$
• Jede Zahl ist gleich Null oder hat einen Vorgänger: ${\displaystyle y=\mathbf {0} \vee \exists x(Sx=y)}$
• Rekursive Definition von Addition und Multiplikation:
  • ${\displaystyle x+\mathbf {0} =x}$
  • ${\displaystyle x+Sy=S(x+y)}$
  • ${\displaystyle x\times \mathbf {0} =\mathbf {0} }$
  • ${\displaystyle x\times Sy=(x\times y)+x}$

Bedeutsamkeit für die Mathematische Logik

Die Robinson-Arithmetik spielt insbesondere beim Beweis des ersten Gödelschen Unvollständigkeitssatzes eine Rolle, da sich innerhalb von Q und ebenso in konsistenten axiomatischen Erweiterungen von Q die Beziehung „… ist ein Beweis der Formel …“ repräsentieren lässt.[3]

Dabei bedeutet Repräsentierbarkeit eines Prädikats ${\displaystyle P}$, dass es eine Formel ${\displaystyle \alpha =\alpha (x_{1},\ldots ,x_{n})}$ gibt, so dass für alle natürlichen Zahlen ${\displaystyle a_{1},\ldots ,a_{n}}$ gilt:

(+) falls ${\displaystyle P(a_{1},\ldots ,a_{n})}$ der Fall ist, dann ist die Aussage ${\displaystyle \alpha ({\underline {a_{1}}},\ldots ,{\underline {a_{n}}})}$ in Q beweisbar,

(-) falls ${\displaystyle P(a_{1},\ldots ,a_{n})}$ nicht zutrifft, dann ist die Aussage ${\displaystyle \neg \alpha ({\underline {a_{1}}},\ldots ,{\underline {a_{n}}})}$ in Q beweisbar.[4]

Der Term ${\displaystyle {\underline {a}}}$ ist dabei wie folgt definiert:

${\displaystyle {\underline {0}}=\mathbf {0} }$,

${\displaystyle {\underline {n+1}}=S{\underline {n}}}$.[5]

Das zugehörige Beweisbarkeitsprädikat „… ist beweisbar“ (d. h. „es gibt ein ${\displaystyle b}$, das ein Beweis der Formel … ist“) ist nicht in Q repräsentierbar, weil keine seiner negativen Instanzen („die Formel … ist nicht beweisbar“) in Q beweisbar ist. Es kann jedoch durch eine Σ₁-Formel ausgedrückt werden, und daher folgt aus der Σ₁-Vollständigkeit von Q,[6] dass jede seiner positiven Instanzen beweisbar ist. Unter Σ₁-Vollständigkeit ist hier zu verstehen, dass jede Σ₁-Aussage (der Sprache von Q), die für die natürlichen Zahlen gilt, auch in Q beweisbar ist.[7]

Q ist bereits in relativ schwachen Subtheorien von ZFC interpretierbar, etwa im sogenannten Tarski-Fragment TF,[8] das nur aus folgenden drei Axiomen besteht: dem Extensionalitätsaxiom (auch Axiom der Bestimmtheit), dem Leermengenaxiom (auch Nullmengenaxiom: die leere Menge existiert) und dem Axiom, welches für zwei Mengen ${\displaystyle x}$, ${\displaystyle y}$ die Existenz der adjungierten Menge ${\displaystyle x\cup \{y\}}$ fordert.

Literatur

• A. Bezboruah, John C. Shepherdson: Gödel’s Second Incompleteness Theorem for Q. In: Journal of Symbolic Logic. Band 41, Nr. 2, 1976, S. 503–512, JSTOR:2272251.
• George S. Boolos, John P. Burgess, Richard C. Jeffrey: Computability and Logic. 5. Auflage. Cambridge University Press, Cambridge etc. 2007.
• Petr Hájek, Pavel Pudlák: Metamathematics of first-order arithmetic. 2. Auflage. Springer-Verlag, 1998.
• Raphael Robinson: An Essentially Undecidable Axiom System. In: Proceedings of the International Congress of Mathematics. 1950, S. 729–730.
• Alfred Tarski, Andrzej Mostowski, Raphael Robinson: Undecidable theories. North Holland, 1953.
• Hans Hermes: Einführung in die mathematische Logik. 2. Auflage. B. G. Teubner Stuttgart, 1969.
• Wolfgang Rautenberg: Einführung in die Mathematische Logik. 3. Auflage. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2, doi:10.1007/978-3-8348-9530-1.
• Donald Monk: Mathematical Logic (= Graduate Texts in Mathematics. Band 37). Springer, New York 1976, ISBN 0-387-90170-1.

Einzelnachweise

1. Rautenberg (2008), Satz 6.4.4, S. 191
2. George Boolos, John P. Burgess, Richard Jeffrey: Computability and Logic. 4. Auflage. Cambridge University Press, 2002, ISBN 0-521-70146-5, S. 56.
3. W. Rautenberg (2008), S. 186.
4. W. Rautenberg (2008), S. 184.
5. W. Rautenberg (2008), S. 83.
6. W. Rautenberg (2008), S. 190.
7. W. Rautenberg (2008), S. 186.
8. D. Monk (1976), S. 283–290.