imported>Jule Glühwurm: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-03-13T08:56:37Z

growthexperiments-addlink-summary-summary:2|0|0

Neue Seite

Der '''Satz von Tennenbaum''' (nach [[Stanley Tennenbaum]]) ist ein Ergebnis der [[Mathematische Logik|mathematischen Logik]]. Er besagt, dass kein [[Abzählbare Menge|abzählbares]] Nichtstandardmodell der [[Peano-Arithmetik]] [[berechenbar]] sein kann. Dabei heißt eine [[Modelltheorie|Struktur]] <math>M</math> in der Sprache der Peano-Arithmetik berechenbar, wenn es berechenbare Funktionen <math>\oplus</math> und <math>\otimes</math> von <math>N \times N</math> nach <math>N</math>, eine berechenbare binäre Relation <math>\prec</math> auf <math>N</math> und Konstanten <math>n_0,n_1</math> gibt, sodass <math>N</math> mit diesen Objekten [[Isomorphismus|isomorph]] zu <math>M</math> ist:

:<math>
(N,\oplus,\otimes,\prec,n_{0},n_{1}) \equiv M
</math>

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 <math>\N</math> in Logik erster Stufe, gilt analog, dass diese nicht [[Arithmetische Hierarchie|arithmetisch]] sind.<ref>{{Literatur | Autor= Joseph R. Shoenfield| Titel= Mathematical Logic| Verlag= Addison-Wesley| Jahr=1967 }} 234</ref>

== Beweisskizze ==
Der Beweis benutzt die Tatsache, dass Nichtstandardmodelle zusätzlich zu den [[Natürliche Zahl|natürlichen Zahlen]] auch „unendliche“ Nichtstandard-Zahlen enthalten und dass es für jedes Nichtstandardmodell <math>M</math> eine Nichtstandard-Zahl <math>a</math> gibt, die im folgenden Sinne eine [[entscheidbare Menge|unentscheidbare Menge]] <math>A</math> kodiert: <math>A</math> ist genau die Menge der natürlichen Zahlen <math>n</math>, sodass die <math>n</math>-te [[Primzahl]] in <math>M</math> die Zahl <math>a</math> teilt:

: <math>A = \bigl\{\, n \in \N \,\big|\, M \models \exists k\ (p_n \cdot k = a) \,\bigr\}</math>,
wobei <math>p_n</math> die <math>n</math>-te Primzahl ist.

Wäre nun <math>M</math> ein berechenbares Nichtstandardmodell, dann wäre insbesondere die Addition berechenbar. Damit ließe sich durch [[Division mit Rest]] ermitteln, ob eine gegebene Zahl <math>n</math> die Nichtstandardzahl <math>a</math> teilt. Damit wäre auch die unentscheidbare Menge <math>A</math> entscheidbar.

== Literatur ==
* {{Literatur |Autor=[[George Boolos]], John P. Burgess und Richard Jeffrey
|Titel=Computability and Logic
|Verlag= Cambridge University Press
|Jahr=2002
|Auflage = 4
|ISBN=0-521-70146-5}}
* Richard Kaye: ''Models of Peano arithmetic''. Oxford University Press, 1991. ISBN 0-19-853213-X.

== Weblinks ==
* [https://web.mat.bham.ac.uk/R.W.Kaye/papers/tennenbaum/tennenbaum.pdf Richard Kaye, Tennenbaum's Theorem for Models of Arithmetic] (PDF-Datei; 163 kB)

== Einzelnachweise ==
<references/>

[[Kategorie:Mathematische Logik]]
[[Kategorie:Berechenbarkeitstheorie]]
[[Kategorie:Satz (Mathematik)|Tennenbaum, Satz von]]

Satz von Tennenbaum - Versionsgeschichte

imported>Jule Glühwurm: /* growthexperiments-addlink-summary-summary:2|0|0 */