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.Rautenberg (2008), Satz 6.4.4, S. 191

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:

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.W. Rautenberg (2008), S. 186.

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.W. Rautenberg (2008), S. 184. Der Term ist dabei wie folgt definiert: , .W. Rautenberg (2008), S. 83.

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,W. Rautenberg (2008), S. 190. 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.W. Rautenberg (2008), S. 186.

Q ist bereits in relativ schwachen Subtheorien von ZFC interpretierbar, etwa im sogenannten Tarski-Fragment TF,D. Monk (1976), S. 283–290. 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

Einzelnachweise

Kategorie:Mathematische Logik