Robinson-Arithmetik

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 dem Axiomenschema der Induktion. Die Bedeutung der Robinson-Arithmetik rührt daher, dass sie endlich ist, aber dennoch nicht rekursiv vervollständigbar 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[Bearbeiten]

Die Robinson-Arithmetik ist formuliert in der Prädikatenlogik erster Stufe mit Gleichheit, repräsentiert durch das Prädikat '='. Ihre Sprache hat die Konstante 0 „null“, die Nachfolgerfunktion S (für successor : Nachfolger), welche intuitiv zu einer gegebenen Zahl eins 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: Sx\not= \mathbf{0}
  • Verschiedene Zahlen haben verschiedene Nachfolger: (Sx = Sy) \rightarrow x=y
  • Jede Zahl ist gleich Null oder hat einen Vorgänger: y=\mathbf{0} \vee \exists x(Sx=y)
  • Rekursive Definition von Addition und Multiplikation:
    • x+\mathbf{0} = x
    • x+Sy = S(x+y)
    • x\times \mathbf{0} = \mathbf{0}
    • x\times Sy = (x\times y)+x

Bedeutsamkeit für die Mathematische Logik[Bearbeiten]

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) das Prädikat der Beweisbarkeit einer Formel repräsentieren lässt.[3]

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

(+) falls P(a_1,\ldots ,a_n) der Fall ist, dann ist die Aussage \alpha (\underline{a_1},\ldots, \underline{a_n}) in Q beweisbar,
(-) falls P(a_1,\ldots ,a_n) nicht zutrifft, dann ist die Aussage \neg \alpha (\underline{a_1},\ldots, \underline{a_n}) in Q beweisbar.[4]

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

 \underline{0} = \mathbf{0},
 \underline{n+1} = S\underline{n}.[5]

Da das Beweisbarkeitsprädikat durch eine Σ1-Formel repräsentiert werden kann, liegt seine Repräsentierbarkeit wesentlich an der Σ1-Vollständigkeit von Q,[6] wobei unter Σ1-Vollständigkeit hier zu verstehen ist, 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, das für zwei Mengen x, y die Existenz der (adjungierten) Menge x ∪ {y} fordert.

Einzelnachweise[Bearbeiten]

  1. Rautenberg (2008), Satz 6.4.4, S. 191
  2.  George Boolos, John P. Burgess und Richard Jeffrey: Computability and Logic. 4 Auflage. Cambridge University Press, 2002, ISBN 0-521-70146-5., Seite 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.

Literatur[Bearbeiten]