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 in der Sprache der Peano-Arithmetik berechenbar, wenn es berechenbare Funktionen und von nach , eine berechenbare binäre Relation auf und Konstanten gibt, sodass mit diesen Objekten isomorph zu ist:

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 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 eine Nichtstandard-Zahl gibt, die im folgenden Sinne eine unentscheidbare Menge kodiert: ist genau die Menge der natürlichen Zahlen , sodass die -te Primzahl in die Zahl teilt:

,

wobei die -te Primzahl ist.

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

Literatur

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

Weblinks

Einzelnachweise

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