Satz von Tennenbaum

mathematischer Satz

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

Bearbeiten

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

Bearbeiten
Bearbeiten

Einzelnachweise

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