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 \scriptstyle M in der Sprache der Peano-Arithmetik berechenbar, wenn es berechenbare Funktionen \oplus und \otimes von \scriptstyle N \times N nach \scriptstyle N, eine berechenbare binäre Relation \prec auf \scriptstyle N und Konstanten \scriptstyle n_0,n_1 gibt, sodass \scriptstyle N mit diesen Objekten isomorph zu \scriptstyle M ist:


(N,\oplus,\otimes,<,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 \N 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 \scriptstyle 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 \scriptstyle M die Zahl a teilt:


A = \{n \in N |\,\, M \models pr(n) | a \}

wobei pr(n) die n-te Primzahl ist.

Wäre nun \scriptstyle 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[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

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