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.

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 $\mathrm{𝟎}$ (genannt Null), die Nachfolgerfunktion $S$ (für successor: Nachfolger), welche intuitiv zu einer gegebenen Zahl 1 addiert, sowie die Funktionen $+$ für Addition und $\times$ für Multiplikation. Sie hat folgende Axiome, die elementare Eigenschaften der natürlichen Zahlen und der arithmetischen Operationen formalisieren:

• Null hat keinen Vorgänger: $Sx=\mathrm{𝟎}$
• Verschiedene Zahlen haben verschiedene Nachfolger: $(Sx=Sy)\to x=y$
• Jede Zahl ist gleich Null oder hat einen Vorgänger: $y=\mathrm{𝟎}\vee \mathrm{\exists }x(Sx=y)$
• Rekursive Definition von Addition und Multiplikation:
  • $x+\mathrm{𝟎}=x$
  • $x+Sy=S(x+y)$
  • $x\times \mathrm{𝟎}=\mathrm{𝟎}$
  • $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.

Dabei bedeutet Repräsentierbarkeit eines Prädikats $P$, dass es eine Formel $\alpha =\alpha (x_1,\dots ,x_n)$ gibt, so dass für alle natürlichen Zahlen $a_1,\dots ,a_n$ gilt:

(+) falls $P(a_1,\dots ,a_n)$ der Fall ist, dann ist die Aussage $\alpha (\underset{\_}{a_1},\dots ,\underset{\_}{a_n})$ in Q beweisbar,

(-) falls $P(a_1,\dots ,a_n)$ nicht zutrifft, dann ist die Aussage $\mathrm{\neg }\alpha (\underset{\_}{a_1},\dots ,\underset{\_}{a_n})$ in Q beweisbar.

Der Term $\underset{\_}{a}$ ist dabei wie folgt definiert:

$\underset{\_}{0}=\mathrm{𝟎}$,

$\underset{\_}{n+1}=S\underset{\_}{n}$.

Das zugehörige Beweisbarkeitsprädikat „… ist beweisbar“ (d. h. „es gibt ein $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, 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.

Q ist bereits in relativ schwachen Subtheorien von ZFC interpretierbar, etwa im sogenannten Tarski-Fragment TF, 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 $x$, $y$ die Existenz der adjungierten Menge $x\cup \{y\}$ fordert.

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur