Escaping Tennenbaum's Theorem and a Strong Jump Inversion Theorem

Cet article résout une question ouverte en démontrant que le théorème de Tennenbaum est fragile pour des fragments intermédiaires de l'arithmétique de Peano, en construisant des modèles non standards calculables pour des théories définissablement équivalentes à « PA plus toutes les vérités $\Pi^0_n$ » grâce à un nouveau théorème général d'inversion forte du saut.

L'essentiel

Titre : Échapper à la prison de Tennenbaum et le grand tour de magie des mathématiques

Imaginez que les mathématiques soient un immense château de cartes. Il y a une règle fondamentale, découverte par un mathématicien nommé Stanley Tennenbaum, qui dit : « Si vous essayez de construire une version de l'arithmétique (les nombres et le calcul) qui n'est pas celle que nous connaissons (avec des nombres infinis), vous ne pourrez jamais la faire fonctionner avec un ordinateur. »

C'est comme si l'univers interdisait aux ordinateurs de calculer avec des nombres "étranges". C'est le Théorème de Tennenbaum.

Mais, dans ce papier, l'auteur, Duarte Maia, nous dit : « Attendez une minute ! Cette règle dépend de la façon dont on dessine les règles du jeu. Si on change légèrement les outils qu'on utilise pour décrire les nombres, on peut tromper la règle et construire un ordinateur capable de faire ces calculs "étranges" ! »

Voici comment il y arrive, étape par étape.

---

1. Le problème : La signature du jeu

Pour comprendre, imaginez que vous décrivez un jeu de société.

• Version A : Vous dites "Il y a un pion, un dé, et une case".
• Version B : Vous dites "Il y a un pion, un dé, et une case, mais on appelle la case 'le but'".

C'est la même chose, juste des mots différents. En mathématiques, on appelle cela une signature. Le théorème de Tennenbaum dit : "Avec la signature classique (les nombres, l'addition, la multiplication), pas d'ordinateur possible pour les modèles bizarres."

Mais Maia montre qu'en changeant la "signature" (en utilisant des mots ou des symboles différents pour dire la même chose), on peut contourner l'interdiction. C'est comme si, au lieu d'interdire de construire une maison avec des briques rouges, on vous disait : "Vous ne pouvez pas construire de maison avec des briques rouges, mais vous pouvez le faire avec des briques bleues qui sont en fait exactement les mêmes, juste peintes différemment."

2. L'outil magique : Le "Déchet" (Trash)

Pour réussir ce tour de passe-passe, Maia utilise une technique très astucieuse qu'il appelle la propriété "QETP" (Quantifier Elimination and Trash Existence Property).

L'analogie du chantier de construction :
Imaginez que vous essayez de construire une réplique parfaite d'un château (un modèle mathématique) en utilisant des robots.

• Le robot a un problème : il fait des erreurs. Parfois, il pose une brique au mauvais endroit, ou il ajoute une pierre qui ne devrait pas être là. C'est ce qu'on appelle des "éléments déchet" (trash).
• Dans les constructions classiques, si le robot fait une erreur, tout s'effondre.
• Mais Maia a inventé un robot spécial qui a une boîte à déchet magique. Quand le robot pose une pierre au mauvais endroit, il ne la jette pas. Il la met dans la "boîte à déchet" et l'utilise plus tard pour construire une partie du château qui était prévue pour être vide !

Le secret :
Le robot travaille d'abord avec un "super-cerveau" (une machine très puissante, appelée $0'$ en mathématiques) qui voit toutes les erreurs et sait exactement où les réparer. Maia prouve que, grâce à cette boîte à déchet intelligente, on peut transformer ce travail complexe (fait par le super-cerveau) en un travail simple que n'importe quel ordinateur standard peut faire.

C'est comme si vous aviez un architecte génie qui dessine un plan parfait en tenant compte de toutes les erreurs possibles, et qui vous dit : "Ne t'inquiète pas, si tu poses cette brique ici, elle servira plus tard pour combler un trou ailleurs." Grâce à cette flexibilité, le plan complexe devient simple.

3. La grande découverte : Les théories "PA + Vérités"

Maia va plus loin. Il ne se contente pas de tromper la règle pour les nombres de base. Il s'attaque à des théories encore plus complexes : "L'arithmétique de Peano + toutes les vérités mathématiques d'un certain niveau".

Imaginez que vous avez un livre de règles (la théorie).

• Le livre de base est simple.
• Le livre "PA + Vérités" contient des règles supplémentaires très complexes, comme des énigmes de niveau expert.

La question était : "Peut-on construire un ordinateur qui joue à ce jeu complexe avec des nombres bizarres ?"
La réponse de Maia est OUI.

Il construit une série de théories (comme une échelle) où chaque échelon ajoute un peu plus de complexité. Pour chaque échelon, il trouve un moyen de "déguiser" la théorie pour qu'elle ressemble à quelque chose de simple, permettant ainsi à un ordinateur de la gérer.

L'analogie du déguisement :
C'est comme si vous vouliez entrer dans un club interdit pour les adultes.

1. Vous ne pouvez pas entrer en tant qu'adulte (c'est le théorème de Tennenbaum).
2. Mais Maia vous dit : "Si vous vous déguisez en enfant avec un masque très spécifique (changement de signature), et que vous avez une carte d'entrée spéciale (la propriété QETP), le portier vous laissera passer."
3. Il montre qu'on peut faire ce déguisement pour des niveaux de complexité de plus en plus élevés.

4. Pourquoi est-ce important ?

Ce papier est important pour deux raisons :

1. Il brise un mythe : Il montre que l'impossibilité de calculer certains modèles mathématiques n'est pas une loi absolue de l'univers, mais une limitation de notre façon de les décrire. Si on change de langage, on peut faire l'impossible.
2. Il donne un nouvel outil : Maia a créé un "moule" universel (le théorème 2.3.1). C'est comme une clé anglaise universelle. Au lieu de devoir inventer une nouvelle méthode pour chaque problème mathématique difficile, les chercheurs peuvent maintenant utiliser ce "moule" pour résoudre plein d'autres énigmes sur la façon dont les ordinateurs peuvent (ou ne peuvent pas) manipuler des structures mathématiques.

En résumé

Imaginez que les mathématiques soient un labyrinthe. Le théorème de Tennenbaum disait : "Il n'y a pas de chemin pour traverser ce labyrinthe avec un robot."
Duarte Maia a dit : "En fait, si vous changez la carte du labyrinthe (la signature) et que vous utilisez un système de portes secrètes (la propriété QETP), vous pouvez guider le robot à travers le labyrinthe, même s'il fait des erreurs en cours de route."

C'est une victoire de la logique et de la créativité : parfois, pour résoudre un problème impossible, il faut juste changer la façon dont on le pose.

Résumé technique

Voici un résumé technique détaillé du papier de Duarte Maia, Escaping Tennenbaum's Theorem and a Strong Jump Inversion Theorem, rédigé en français.

1. Problématique et Contexte

Le théorème de Tennenbaum :
Le point de départ de l'article est le célèbre théorème de Stanley Tennenbaum (1959), qui stipule qu'aucun modèle non-standard de l'arithmétique de Peano (PA) n'est calculable. En fait, dans tout modèle non-standard de PA, ni l'addition ni la multiplication ne peuvent être des fonctions calculables.

La dépendance à la signature :
L'auteur souligne que ce résultat dépend fortement du choix de la signature (l'ensemble des symboles de relation et de fonction utilisés). En 2022, Fedor Pakhomov a démontré qu'il existe une théorie $T_S$, définitionnellement équivalente à PA (c'est-à-dire qu'elle peut définir les mêmes objets et relations, mais avec des symboles différents), qui admet un modèle non-standard calculable. Cela montre que l'impossibilité de Tennenbaum n'est pas une propriété intrinsèque de la théorie de l'arithmétique elle-même, mais de sa formulation spécifique.

La question ouverte de Pakhomov :
Pakhomov a posé la question suivante : Existe-t-il des théories définitionnellement équivalentes à « PA plus toutes les vérités $\Pi_n$ » (pour un $n$ fixé) qui admettent un modèle non-standard calculable ? La réponse était connue pour le cas limite ($n \to \infty$, c'est-à-dire l'arithmétique vraie), mais le cas partiel restait ouvert.

2. Méthodologie

L'article développe une méthodologie en deux volets principaux :

A. Un théorème général d'inversion de saut (Strong Jump Inversion)

L'auteur extrait une généralisation puissante des techniques utilisées par Pakhomov. Il définit une nouvelle classe de structures et une propriété model-théorique pour établir un théorème d'inversion de saut fort.

• Structures $0'$-calculables à types énumérables (0'-computable c.e.-typed structures) :
  Au lieu de considérer une structure comme un ensemble calculable avec un diagramme atomique calculable, l'auteur introduit une notion plus faible adaptée aux signatures infinies ou complexes. Une telle structure est donnée par une fonction $0'$-calculable qui, pour tout tuple d'éléments, fournit un indice énumérable (c.e.) de son type atomique. Cela permet de gérer les "fausses" informations ou les éléments éphémères dans une construction limite.

• La propriété QETP (Quantifier Elimination and Trash Existence Property) :
  C'est la condition clé sur une structure $D$ (sur une signature étendue $L'$) pour qu'elle admette un modèle calculable sur une sous-signature $L$. La propriété QETP exige l'existence de trois fonctions/formules :

  1. $\chi$ (Élimination de quantificateurs) : Pour toute formule sans quantificateur $q(\vec{x}, \vec{y})$, il existe une formule $\chi_q(\vec{x})$ dans la signature étendue qui est équivalente à $\exists \vec{y} q(\vec{x}, \vec{y})$.
  2. $\tau$ (Propriété de "poubelle" ou "genericité") : Une fonction $0'$-calculable qui, pour un type donné, identifie des éléments "génériques" ou "poubelles" (trash) qui peuvent être réutilisés ou déplacés sans violer les contraintes de la structure. Cela permet de corriger les erreurs de construction en réaffectant des éléments indésirables.
  3. $\varepsilon_\tau$ : Une fonction qui vérifie l'existence de tels éléments génériques compatibles avec de nouvelles contraintes.

• Le Théorème 2.3.1 :
  Si $D$ est une structure $0'$-calculable à types énumérables satisfaisant la QETP, alors sa réducte$D \upharpoonright L$ admet un modèle isomorphe qui est calculable. Ce résultat est uniforme et se relativise.

B. Construction de théories hiérarchiques

Pour répondre à la question de Pakhomov, l'auteur généralise la construction de Pakhomov en définissant une séquence imbriquée de théories $T_0 \subseteq T_1 \subseteq T_2 \dots$ dans la théorie des ensembles finis ($ZF_{fin} + TC$).

• Chaque théorie $T_n$ introduit de nouveaux prédicats $S_0, \dots, S_n$ de plus en plus complexes (dearité croissante).
• Ces prédicats agissent comme des "témoins" pour les relations d'appartenance ou d'inclusion, permettant une flexibilité extrême lors de la construction de modèles.
• La construction utilise une récurrence sur la hiérarchie de von Neumann pour garantir que pour toute prescription de relations sur un nouvel élément, il existe un élément réel satisfaisant cette prescription.

3. Résultats Clés

1. Théorème d'Inversion de Saut Fort (Théorème 2.3.1) :
   C'est le résultat technique central. Il unifie et généralise plusieurs résultats connus de la littérature (relations d'équivalence, algèbres de Boole, ordres linéaires, arbres) en fournissant un cadre unique pour prouver l'existence de modèles calculables à partir de modèles $0'$-calculables, sous réserve de la propriété QETP.

2. Réponse à la question de Pakhomov (Théorème 4.2.6) :
   Pour tout entier $n$, il existe une théorie définitionnellement équivalente à « PA + toutes les vérités $\Pi_n$ » qui admet un modèle non-standard calculable.

   • Preuve : En utilisant le théorème 4.2.1, l'auteur construit une théorie $T_{n+1}$ dont le modèle $0^{(n+1)}$-calculable (via le théorème de complétude calculable) peut être réduit, étape par étape, à un modèle calculable en utilisant l'inversion de saut itérée.

3. Généralisation de la construction de Pakhomov :
   L'article montre que la flexibilité de la relation $S$ de Pakhomov peut être itérée. On peut construire des théories avec des prédicats $S_0, S_1, \dots$ où chaque niveau permet de "descendre" d'un saut de complexité (de $X'$ à $X$) tout en conservant l'équivalence définitionnelle avec des fragments de l'arithmétique.

4. Applications aux structures classiques :
   Le papier démontre que le théorème 2.3.1 permet de retrouver des résultats classiques comme :

   • L'existence d'un modèle calculable pour une relation d'équivalence avec une infinité de classes infinies (si le modèle enrichi est $0'$-calculable).
   • L'existence d'un modèle calculable pour un ordre linéaire avec successeurs (si le modèle enrichi est $0'$-calculable).
   • Le théorème de Khisamiev sur les groupes abéliens sans torsion présentés de manière énumérable.

4. Signification et Impact

• Nuance du théorème de Tennenbaum : L'article renforce l'idée que l'impossibilité de Tennenbaum est une propriété de la signature standard de PA ($+, \times, 0, 1, <$) et non de la théorie mathématique sous-jacente. En changeant la signature (via des prédicats auxiliaires flexibles), on peut contourner l'obstacle de la calculabilité même pour des théories très fortes (incluant des vérités $\Pi_n$).
• Outil unificateur : La notion de QETP et le théorème 2.3.1 offrent un cadre puissant pour la théorie des structures calculables. Ils permettent de "boîte noire" (black-box) les preuves complexes d'injury finie (finite injury arguments) souvent utilisées dans ce domaine, en les remplaçant par la vérification de conditions model-théoriques (existence de $\chi, \tau, \varepsilon_\tau$).
• Nouvelles directions : L'article ouvre la voie à l'étude du "spectre non-standard" (l'ensemble des degrés de Turing qui calculent des modèles non-standard) pour différentes signatures. Il pose également des questions sur l'existence de théories "naturelles" (étudiées par des mathématiciens non-logiciens) qui échapperaient au théorème de Tennenbaum.

En résumé, Duarte Maia fournit une réponse affirmative à une question ouverte majeure en logique mathématique, tout en développant un outil théorique général (le théorème d'inversion de saut fort) qui simplifie et généralise de nombreux résultats existants en théorie des structures calculables.