Robinson-Arithmetik

Die Robinson-Arithmetik (auch: Q) ist ein endlich axiomatisiertes Fragment der Peano-Arithmetik, eines Axiomensystems der Arithmetik, also der natürlichen Zahlen, innerhalb der Prädikatenlogik erster Stufe. Sie wurde 1950 von Raphael Robinson eingeführt und entspricht im Wesentlichen der Peano-Arithmetik ohne das Axiomenschema der Induktion. Die Bedeutung der Robinson-Arithmetik rührt daher, dass sie endlich axiomatisierbar, aber nicht rekursiv vervollständigbar ist und sogar wesentlich unentscheidbar ist. Dies bedeutet, dass es keine konsistente entscheidbare Erweiterung der Robinson-Arithmetik gibt. Es gibt damit insbesondere auch keine vollständige rekursiv aufzählbare Erweiterung, da 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 . Ihre Sprache hat die Konstante (genannt Null), die Nachfolgerfunktion (für successor: Nachfolger), welche intuitiv zu einer gegebenen Zahl 1 addiert, sowie die Funktionen für Addition und 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:
  • Verschiedene Zahlen haben verschiedene Nachfolger:
  • Jede Zahl ist gleich Null oder hat einen Vorgänger:
  • Rekursive Definition von Addition und Multiplikation:

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 , dass es eine Formel gibt, so dass für alle natürlichen Zahlen gilt:

(+) falls der Fall ist, dann ist die Aussage in Q beweisbar,
(-) falls nicht zutrifft, dann ist die Aussage in Q beweisbar.[4]

Der Term ist dabei wie folgt definiert:

,
.[5]

Das zugehörige Beweisbarkeitsprädikat „… ist beweisbar“ (d. h. „es gibt ein , 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 Σ1-Formel ausgedrückt werden, und daher folgt aus der Σ1-Vollständigkeit von Q,[6] dass jede seiner positiven Instanzen beweisbar ist. Unter Σ1-Vollständigkeit ist hier zu verstehen, dass jede Σ1-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 , die Existenz der adjungierten Menge fordert.

Literatur

  • Petr Hájek, Pavel Pudlák: Metamathematics of first-order arithmetic. 2. Auflage. Springer-Verlag, 1998.
  • Hans Hermes: Einführung in die mathematische Logik. 2. Auflage. B. G. Teubner Stuttgart, 1969.
  • Donald Monk: Mathematical Logic (= Graduate Texts in Mathematics. Band 37). Springer, New York 1976, ISBN 0-387-90170-1.
  • 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.
  • Alfred Tarski, Andrzej Mostowski, Raphael Robinson: Undecidable theories. North Holland, 1953.
  • 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.
  • Raphael Robinson: An Essentially Undecidable Axiom System. In: Proceedings of the International Congress of Mathematics. 1950, S. 729–730.

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.