Satz von Tennenbaum

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

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 | Quelltext 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 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 die Zahl a teilt:

wobei pr(n) die n-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 n die Nichtstandardzahl a teilt. Damit wäre auch die unentscheidbare Menge A entscheidbar.

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

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