Théorème de Tennenbaum - Tennenbaum's theorem

À ne pas confondre avec la construction par Tennenbaum d'une copie calculable n'ayant pas de chaînes ascendantes ou descendantes infinies calculables.${\ displaystyle \ omega + \ omega ^ {*}}$

Le théorème de Tennenbaum , du nom de Stanley Tennenbaum qui a présenté le théorème en 1959, est un résultat de la logique mathématique qui déclare qu'aucun modèle non standard dénombrable de l'arithmétique Peano (PA) du premier ordre ne peut être récursif (Kaye 1991: 153ff).

Structures récursives pour PA

Une structure dans le langage de PA est récursive s'il existe des fonctions récursives + et × de à , une relation récursive à deux places <on , et des constantes distinguées telles que ${\ displaystyle M}$${\ displaystyle N \ fois N}$${\ displaystyle N}$${\ displaystyle N}$${\ displaystyle n_ {0}, n_ {1}}$

${\ displaystyle (N, \ oplus, \ otimes, <_ {M}, n_ {0}, n_ {1}) \ equiv M,}$

où indique l' isomorphisme et est l'ensemble des nombres naturels (standard) . Parce que l'isomorphisme doit être une bijection, chaque modèle récursif est dénombrable. Il existe de nombreux modèles non standard dénombrables non isomorphes de PA. ${\ displaystyle \ equiv}$${\ displaystyle N}$

Énoncé du théorème

Le théorème de Tennenbaum déclare qu'aucun modèle non standard dénombrable de PA n'est récursif. De plus, ni l'addition ni la multiplication d'un tel modèle ne peuvent être récursives.

Croquis de preuve

Cette esquisse suit l'argumentation présentée par Kaye (1991). La première étape de la preuve est de montrer que, si M est un modèle non standard dénombrable de PA, puis le système standard de M (défini ci - dessous) contient au moins un ensemble non récursif S . La deuxième étape consiste à montrer que, si l'opération d'addition ou de multiplication sur M était récursive, alors cet ensemble S serait récursif, ce qui est une contradiction.

Par les méthodes utilisées pour le code commandé tuples, chaque élément peut être considéré comme un code pour un ensemble d'éléments de M . En particulier, si nous laissons être le i ème premier de M , alors . Chaque ensemble sera borné en M , mais si x n'est pas standard, alors l'ensemble peut contenir une infinité de nombres naturels standard. Le système standard du modèle est la collection . On peut montrer que le système standard de tout modèle non standard d'AP contient un ensemble non récursif, soit en faisant appel au théorème d'incomplétude, soit en considérant directement une paire d' ensembles récursivement inséparables (Kaye 1991: 154). Ce sont des ensembles de re disjoints afin qu'il n'y ait pas d'ensemble récursif avec et . ${\ displaystyle x \ in M}$${\ displaystyle S_ {x}}$${\ displaystyle p_ {i}}$${\ displaystyle z \ in S_ {x} \ leftrightarrow M \ vDash p_ {z} | x}$${\ displaystyle S_ {x}}$${\ displaystyle S_ {x}}$${\ displaystyle \ {S_ {x} \ cap N: x \ in M ​​\}}$${\ displaystyle A, B \ subseteq N}$${\ displaystyle C \ subseteq N}$${\ displaystyle A \ subseteq C}$${\ displaystyle B \ cap C = \ emptyset}$

Pour cette dernière construction, commencez par une paire d'ensembles A et B inséparables récursivement . Pour un entier naturel x, il existe un y tel que, pour tout i <x , si alors et si alors . Par le débordement des biens, cela signifie que il y a quelques non standard x dans M pour lesquels il existe un (nécessairement non standard) y dans M de sorte que, pour chaque avec , nous avons ${\ displaystyle i \ in A}$${\ displaystyle p_ {i} | y}$${\ displaystyle i \ in B}$${\ displaystyle p_ {i} \ not | y}$${\ displaystyle m \ in M}$${\ displaystyle m <_ {M} x}$

${\ displaystyle M \ vDash (m \ in A \ to p_ {m} | y) \ land (m \ in B \ to p_ {m} \ not | y)}$

Laissez le jeu correspondant dans le système standard de M . Parce que A et B sont re, on peut montrer que et . Donc S est un ensemble séparateur pour A et B , et par le choix de A et B cela signifie que S est non récursif. ${\ displaystyle S = N \ cap S_ {y}}$${\ displaystyle A \ subseteq S}$${\ displaystyle B \ cap S = \ emptyset}$

Maintenant, pour prouver le théorème de Tennenbaum, commencez par un modèle dénombrable non standard M et un élément a dans M de sorte que ce soit non récursif. La méthode de preuve montre qu'en raison de la manière dont le système standard est défini, il est possible de calculer la fonction caractéristique de l'ensemble S en utilisant la fonction d'addition de M comme oracle. En particulier, si est l'élément de M correspondant à 0, et est l'élément de M correspondant à 1, alors pour chacun on peut calculer ( i fois). Pour décider si un nombre n est en S , on calcule d' abord p , le n e premier en N . Ensuite, recherchez un élément y de M pour que ${\ displaystyle S = N \ cap S_ {a}}$${\ displaystyle \ oplus}$${\ displaystyle n_ {0}}$${\ displaystyle n_ {1}}$${\ displaystyle i \ in N}$${\ displaystyle n_ {i} = n_ {1} \ oplus \ cdots \ oplus n_ {1}}$

${\ displaystyle a = \ underbrace {y \ oplus y \ oplus \ cdots \ oplus y} _ {p {\ text {times}}} \ oplus n_ {i}}$

pour certains . Cette recherche s'arrêtera car l' algorithme euclidien peut être appliqué à n'importe quel modèle de PA. Enfin, nous avons si et seulement si le i trouvé dans la recherche était 0. Puisque S n'est pas récursif, cela signifie que l'opération d'addition sur M est non récursive. ${\ displaystyle i <p}$${\ displaystyle n \ in S}$

Un argument similaire montre qu'il est possible de calculer la fonction caractéristique de S en utilisant la multiplication de M comme oracle, de sorte que l'opération de multiplication sur M est également non récursive (Kaye 1991: 154).

Références

• George Boolos , John P. Burgess et Richard Jeffrey (2002) Computability and Logic , 4e éd. La presse de l'Universite de Cambridge. ISBN  0-521-00758-5
• Richard Kaye (1991) Modèles d'arithmétique Peano . Presse d'université d'Oxford. ISBN  0-19-853213-X .
• Richard Kaye (septembre 2011). "Théorème de Tennenbaum pour les modèles d'arithmétique". Dans Juliette Kennedy et Roman Kossak (éd.). Théorie des ensembles, arithmétique et fondements des mathématiques - théorèmes, philosophies (PDF) . Notes de cours en logique. 36 . ISBN 9781107008045.
• Stanley Tennenbaum (1959) Non-Archimedean models for arithmetic , In: Notices of the American Mathematical Society 6, p. 270