Satz von Tennenbaum

Der Satz von Tennenbaum (nach Stanley Tennenbaum) ist ein Ergebnis der mathematischen Logik. Er besagt, dass kein abzählbares Nichtstandardmodell der Peano-Arithmetik berechenbar sein kann. Dabei heißt eine Struktur $M$ in der Sprache der Peano-Arithmetik berechenbar, wenn es berechenbare Funktionen $\oplus$ und $\otimes$ von $N\times N$ nach $N$ , eine berechenbare binäre Relation $\prec$ auf $N$ und Konstanten $n_{0},n_{1}$ gibt, sodass $N$ mit diesen Objekten isomorph zu $M$ ist:

(N,\oplus ,\otimes ,\prec ,n_{0},n_{1})\equiv M

Während Addition und Multiplikation in keinem Nichtstandardmodell berechenbar sind, gibt es Nichtstandardmodelle, in denen die Ordnung und die Nachfolgerfunktion berechenbar sind. Für Nichtstandardmodelle der „wahren“ Arithmetik, das heißt der Theorie von $\mathbb {N}$ in Logik erster Stufe, gilt analog, dass diese nicht arithmetisch sind.[1]

Beweisskizze

Der Beweis benutzt die Tatsache, dass Nichtstandardmodelle zusätzlich zu den natürlichen Zahlen auch „unendliche“ Nichtstandard-Zahlen enthalten und dass es für jedes Nichtstandardmodell $M$ eine Nichtstandard-Zahl $a$ gibt, die im folgenden Sinne eine unentscheidbare Menge $A$ kodiert: $A$ ist genau die Menge der natürlichen Zahlen $n$ , sodass die $n$ -te Primzahl in $M$ die Zahl $a$ teilt:

A={\bigl \{}\,n\in \mathbb {N} \,{\big |}\,M\models \exists k\ (p_{n}\cdot k=a)\,{\bigr \}}

,

wobei $p_{n}$ die $n$ -te Primzahl ist.

Wäre nun $M$ ein berechenbares Nichtstandardmodell, dann wäre insbesondere die Addition berechenbar. Damit ließe sich durch Division mit Rest ermitteln, ob eine gegebene Zahl $n$ die Nichtstandardzahl $a$ teilt. Damit wäre auch die unentscheidbare Menge $A$ entscheidbar.

Literatur

George Boolos, John P. Burgess und Richard Jeffrey: Computability and Logic. 4. Auflage. Cambridge University Press, 2002, ISBN 0-521-70146-5.
Richard Kaye: Models of Peano arithmetic. Oxford University Press, 1991. ISBN 0-19-853213-X.

Weblinks

Richard Kaye, Tennenbaum's Theorem for Models of Arithmetic (PDF-Datei; 163 kB)

Einzelnachweise

Joseph R. Shoenfield: Mathematical Logic. Addison-Wesley, 1967. 234

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Joseph R. Shoenfield: Mathematical Logic. Addison-Wesley, 1967. 234