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

${\displaystyle (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 ${\displaystyle \mathbb {N} }$ in Logik erster Stufe, gilt analog, dass diese nicht arithmetisch sind.