Escaping Tennenbaum's Theorem and a Strong Jump Inversion Theorem

De auteurs tonen aan dat Tennenbaums stelling kwetsbaar is voor fragmenten van de Peano-axioma's van intermediaire sterkte door een reeks definities-equivalente theorieën te construeren die computable niet-standaard modellen toelaten, een resultaat dat wordt bereikt via een nieuw algemeen stelling voor sterke jump-inversie.

De kern

Hier is een uitleg van het artikel "Escaping Tennenbaum's Theorem and a Strong Jump Inversion Theorem" van Duarte Maia, vertaald naar eenvoudige, alledaagse taal met creatieve analogieën.

De Grote Droom: Een Perfecte, Simpele Wiskundewereld

Stel je voor dat wiskunde een enorme, complexe stad is. In deze stad wonen getallen en hun regels (zoals optellen en vermenigvuldigen). Wiskundigen noemen dit de "standaardmodellen" van de rekenkunde.

Maar er is ook een vreemde, ondoorzichtige versie van deze stad: een niet-standaard model. Dit is als een stad die er precies hetzelfde uitziet als de echte stad, maar waar de regels op een manier werken die we niet kunnen begrijpen of voorspellen.

Tennenbaum's Theorem (een beroemde wet uit 1959) zegt iets heel strengs:

"Als je een niet-standaard model van de rekenkunde bouwt, dan zijn de regels voor optellen en vermenigvuldigen nooit simpel genoeg om door een computer te worden uitgevoerd. Het is als proberen een ingewikkeld dansje te doen met een computer die alleen maar 'ja' en 'nee' kan zeggen; het lukt gewoon niet."

Kortom: Je kunt geen 'computerspel' maken van deze vreemde wiskundestad. De regels zijn te chaotisch.

De Uitdaging: Kan je de regels veranderen?

De auteur, Duarte Maia, kijkt naar een slimme truc die een andere wiskundige (Fedor Pakhomov) bedacht. Pakhomov zei: "Wat als we de taal van de stad veranderen?"

Stel je voor dat de stad normaal gesproken wordt beschreven met de woorden "optellen" (+) en "vermenigvuldigen" (×). Pakhomov bedacht een nieuwe taal, laten we hem "S-taal" noemen. In deze taal beschrijven we dezelfde stad, maar met een heel ander soort regels. Het is alsof je een huis beschrijft:

• Taal A: "Het heeft 3 slaapkamers en 2 badkamers."
• Taal B: "Het heeft een rode deur, een blauwe muur en een groene vloer."

Het is hetzelfde huis, maar de beschrijving is anders. Pakhomov toonde aan dat je in Taal B (de S-taal) wél een computermodel kunt bouwen van die vreemde stad. De regels zijn in die taal simpel genoeg voor een computer.

Maar er was een probleem: Pakhomov kon dit alleen doen voor de basisversie van de stad. Wat als we de stad nog complexer maken? Wat als we de stad willen bouwen met extra regels voor "alle waarheid" (bijvoorbeeld: "alle waarheid over getallen die je kunt bewijzen met een bepaalde hoeveelheid moeite")?

De vraag was: Kunnen we voor elke niveau van complexiteit een nieuwe taal vinden die simpel genoeg is voor een computer?

Het Nieuwe Geniale Plan: De "Afvalbak"-Truc

Maia's antwoord is een resoluut JA. Hij heeft een nieuwe methode bedacht die werkt als een slimme bouwplaat met een "afvalbak".

1. De Bouwplaat met Fouten (Het 0'-model)

Stel je voor dat je een robot hebt die een stad bouwt. Deze robot is niet perfect; hij maakt soms fouten. Hij plaatst een muur, realiseert zich later dat het verkeerd is, en verwijdert de muur weer.

• In de wiskundetaal noemen we dit een 0'-computabel model. De robot is slim genoeg om fouten te zien en te corrigeren, maar hij heeft een beetje hulp nodig (een "oracle" of een magische gids) om te weten welke fouten hij moet maken.
• Het resultaat is een stad die er perfect uitziet, maar die is gebouwd met veel "schuifbewegingen" en tijdelijke muren.

2. De "Afvalbak" (De Trash-predicate)

Hier komt Maia's genialiteit om de hoek kijken. Hij zegt: "Laten we de robot niet dwingen om alleen de juiste muren te bouwen. Laten we hem toestaan om ook 'afval' te bouwen."

Stel je voor dat de robot een bak heeft met afvalstenen.

• Als de robot een muur moet bouwen, maar hij twijfelt of hij de juiste steen heeft, legt hij eerst een afvalsteen neer.
• Later, als hij merkt dat het een fout was, kan hij die afvalsteen opnieuw gebruiken als een echte steen voor een ander doel.
• De sleutel is dat de taal van de stad zo is ontworpen dat je altijd "ruimte" hebt om afval te verstoppen of om afval om te toveren tot echte stenen.

In het artikel noemen ze dit de QETP (Computable Positive Quantifier Elimination and Trash Existence Property). Klinkt ingewikkeld, maar het betekent simpelweg: "Onze regels zijn zo flexibel dat we elke fout die we maken, kunnen hergebruiken als een nuttig onderdeel van het eindresultaat."

3. De Sprong naar Simpelheid (Jump Inversion)

De "Jump Inversion" is de naam voor de magie die gebeurt als je deze truc toepast.

• De Sprong: De robot (0'-model) heeft een magische gids nodig om fouten te zien.
• De Inversie: Door de "afvalbak-truc" toe te passen, kunnen we een gewone, simpele computer (zonder magische gids) een exacte kopie van die stad laten bouwen.

Het is alsof je een ingewikkeld puzzelspel hebt dat alleen op een supercomputer werkt. Maia zegt: "Als je de regels van het spel een beetje aanpast (de taal verandert) en je toestaat om stukjes 'afval' in het spel te laten, dan kan zelfs een simpele rekenmachine het spel spelen."

Wat betekent dit voor de wereld?

1. Het is niet de wiskunde, maar de taal: Tennenbaum's theorema was niet "onvermijdelijk". Het was afhankelijk van hoe je de wiskunde beschreef. Met de juiste beschrijving (de juiste taal) kun je zelfs de meest complexe, vreemde wiskundestad op een simpele computer laten draaien.
2. Een oneindige ladder: Maia heeft bewezen dat je dit kunt doen voor elk niveau van complexiteit. Of je nu kijkt naar simpele rekenregels of naar de allercomplexste waarheden over getallen: er is altijd een taal te vinden die een computer kan begrijpen.
3. De "Afvalbak" is de sleutel: De kern van zijn bewijs is dat je fouten niet hoeft te zien als een ramp. Als je een systeem bouwt dat fouten kan "opeten" en omzetten in iets nuttigs, kun je complexe problemen oplossen met simpele middelen.

Samenvatting in één zin

Duarte Maia toont aan dat je, door slimme taalveranderingen en door fouten te zien als bruikbare bouwstenen in plaats van als mislukkingen, zelfs de meest onmogelijke wiskundige werelden kunt bouwen op een simpele computer.

Het is alsof je leert dat je niet een perfecte architect hoeft te zijn om een perfect huis te bouwen; je hoeft alleen maar een taal te vinden waarin je "fouten" kunt noemen "nieuwe kamers".

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Escaping Tennenbaum's Theorem and a Strong Jump Inversion Theorem" van Duarte Maia (maart 2026), geschreven in het Nederlands.

1. Probleemstelling en Achtergrond

Tennenbaum's Stelling:
Een fundamenteel resultaat in de rekenbare modeltheorie, bewezen door Stanley Tennenbaum, stelt dat de eerste-orde theorie van Peano-rekenkunde (PA) geen niet-standaard rekenbaar model toelaat. In elk niet-standaard model van PA zijn zowel de optelling als de vermenigvuldiging niet-rekenbaar.

De Rol van het Signatuur:
Traditioneel wordt aangenomen dat dit resultaat inherent is aan de theorie zelf. Echter, Fedor Pakhomov (2022) toonde aan dat Tennenbaum's stelling sterk afhankelijk is van de keuze van het signatuur (de verzameling van symbolen die in de taal worden gebruikt). Pakhomov construeerde een theorie die definitorisch equivalent is aan PA (wat betekent dat de theorieën elkaars symbolen kunnen definiëren en dus dezelfde wiskundige inhoud hebben, maar met een ander taalgebruik), maar die wel een rekenbaar niet-standaard model toelaat.

De Vraag:
Pakhomov stelde de volgende vraag: Bestaan er theorieën die definitorisch equivalent zijn aan "PA plus alle ware $\Pi_n$-zinnen" (waarbij $n$ een vast geheel getal is) die een rekenbaar niet-standaard model toelaten?

• Het is bekend dat voor "ware rekenkunde" (alle ware zinnen) dit onmogelijk is.
• De vraag is of men dit resultaat kan "redden" voor eindige niveaus van de arithmetische hiërarchie ($\Pi_n$).

2. Methodologie

De auteur combineert technieken uit de rekenbare structuurtheorie (computable structure theory) en modeltheorie om een algemeen raamwerk te ontwikkelen dat Pakhomov's specifieke constructie generaliseert.

A. Sterke Jump Inversion (Sterke Spronginversie):
Het artikel introduceert een veralgemeende stelling voor "strong jump inversion". In het kort: als een structuur $A$ uitgebreid met bepaalde extra relaties een $0'$-rekenbaar kopie toelaat, dan toelaat de oorspronkelijke structuur$A$ (zonder die extra relaties) een rekenbaar kopie.

• Dit is een versterking van bestaande resultaten (zoals die voor equivalentierelaties en lineaire ordeningen).
• De auteur definieert een nieuw concept: **$0'$-rekenbare c.e.-getypeerde structuren**. In plaats van een volledige rekenbare diagram te eisen, wordt alleen een$0'$-rekenbare functie vereist die voor elke tupel een recursief opgesomde (c.e.) index voor de atomaire type geeft. Dit is essentieel om om te gaan met oneindige signatures en limiet-gedrag.

B. De QETP (Computable Positive Quantifier Elimination and Trash Existence Property):
Om de jump-inversion-stelling toe te passen, moet een structuur voldoen aan een technisch criterium genaamd QETP. Dit vereist het bestaan van drie specifieke functies/formules:

1. $\chi$ (Quantifier Elimination): Een methode om existentiële kwantificering ($\exists \vec{y} q(\vec{x}, \vec{y})$) om te zetten in een positieve, kwantitatieve formule in een uitgebreider taal.
2. $\tau$ (Trash/Genericiteit): Een functie die bepaalt of een nieuw element "afval" (trash) kan zijn. Dit is cruciaal voor de constructie: als een modelbouwproces een fout maakt en een element toevoegt dat niet past, kan dit element worden "hergebruikt" als een generiek element dat voldoet aan de eisen van de theorie, zonder de structuur te beschadigen.
3. $\varepsilon_\tau$ (Existential Proxy): Een proxy die controleert of er een geldig "afval"-element bestaat dat voldoet aan specifieke eisen, zonder afhankelijk te zijn van de exacte keuze van het element.

C. Generalisatie van Pakhomov's Constructie:
Pakhomov gebruikte een ternaire predikaat $S(x,y,z)$ die fungeerde als "lidmaatschap met getuige" ($x \in y \iff \forall z S(x,y,z)$). Maia generaliseert dit door een geneste reeks predikaten $S_0, S_1, \dots, S_n$ te introduceren.

• $S_0$ correspondeert met de negatie van lidmaatschap.
• $S_{k+1}$ fungeert als een "getuige" voor de negatie van $S_k$.
• Door deze hiërarchie op te bouwen binnen de theorie $ZF_{fin} + TC$ (Zermelo-Fraenkel zonder oneindigheidsaxioma, maar met transitieve sluiting), creëert hij een systeem waar de "flexibiliteit" van de getuigen het mogelijk maakt om fouten in een $0'$-rekenbaar model te corrigeren en een volledig rekenbaar model te construeren.

3. Belangrijkste Resultaten

Hoofdstelling 2.3.1 (General Jump Inversion):
Als $D$ een $0'$-rekenbare c.e.-getypeerde structuur is over een signatuur$L' \supseteq L$die voldoet aan de QETP, dan heeft de reductie$D \upharpoonright L$een rekenbaar kopie. Er bestaat een$0'$-rekenbare isomorfisme tussen de reductie en deze kopie.

Hoofdstelling 4.2.1 (Generalisatie van Pakhomov):
Er bestaat een geneste reeks van consistente, recursief opgesomde (c.e.) theorieën $ZF_{inf} + TC \subseteq T_0 \subseteq T_1 \subseteq \dots$ met de volgende eigenschappen:

• Elke $T_n$ bevat het lidmaatschapspredikaat $\in$ en predikaten $S_0, \dots, S_n$.
• De theorieën zijn conservatief over $ZF_{inf} + TC$.
• $\in$ en $S_n$ zijn definitorisch equivalent binnen $T_n$.
• Cruciaal: Gegeven een $0'$-rekenbaar model van$T_n$(beperkt tot de laatste$k$predikaten), bestaat er een rekenbaar kopie van de reductie naar de laatste$k-1$ predikaten.

Hoofdstelling 4.2.6 (Antwoord op Pakhomov's Vraag):
Voor elk $n$ bestaat er een theorie die definitorisch equivalent is aan "PA plus alle ware $\Pi_n$-zinnen" die een rekenbaar niet-standaard model toelaat.

• Bewijsidee: De theorie "PA + ware $\Pi_n$-zinnen" is een $0^{(n)}$-c.e. theorie. Door de relativisatie van de jump-inversion-stelling$n+1$ keer toe te passen op Pakhomov's constructie, kan men de complexiteit van het model stap voor stap verlagen tot rekenbaar.

Toepassingen op Bestaande Resultaten:
De auteur toont aan dat Theorem 2.3.1 een "black-box" is voor veel bestaande jump-inversion-resultaten, waaronder:

• Equivalentierelaties met oneindig veel oneindige klassen.
• Lineaire ordeningen met een opvolgerrelatie.
• Torsievrije abelse groepen (Khisamiev's stelling).
• Bepaalde soorten bomen.

4. Significatie en Impact

1. Oplossing van een Open Vraag: Het artikel beantwoordt positief de vraag van Pakhomov over de existentie van rekenbare niet-standaard modellen voor theorieën die equivalent zijn aan PA met beperkte waarheid (tot $\Pi_n$). Dit toont aan dat Tennenbaum's stelling niet alleen afhangt van het signatuur, maar ook van de complexiteit van de waarheid die in de theorie wordt geëist.
2. Unificatie van Methoden: De introductie van de QETP en $0'$-rekenbare c.e.-getypeerde structuren biedt een krachtig, unificerend raamwerk. Het vervangt complexe, specifieke "finite injury" constructies (waarbij fouten in een constructie moeten worden hersteld) door een meer abstracte, modeltheoretische verificatie. Als een structuur aan de QETP voldoet, volgt de jump-inversion automatisch.
3. Technische Innovatie: Het gebruik van "trash" (afval) elementen en de specifieke behandeling van negaties in de atomaire types (via c.e. indices in plaats van volledige rekenbare indices) biedt nieuwe inzichten in hoe men om kan gaan met limiet-gedrag in de rekenbare modeltheorie.
4. Toekomstige Richtingen: Het artikel stelt nieuwe vragen, zoals of er "natuurlijke" theorieën (niet door logici bedacht) zijn die aan Tennenbaum ontsnappen, en of de jump-inversion-stelling kan worden versterkt om isomorfismen van lagere complexiteit (bijv. $0''$in plaats van$0'$) te garanderen.

Conclusie:
Duarte Maia heeft bewezen dat de onmogelijkheid van rekenbare niet-standaard modellen voor PA een artefact is van de specifieke combinatie van het signatuur en de volledige waarheid van de theorie. Door de complexiteit van de waarheid te beperken tot $\Pi_n$ en een zorgvuldig gekozen, uitgebreid signatuur te gebruiken, kan men deze barrière doorbreken. De gepresenteerde "Strong Jump Inversion Theorem" is een fundamenteel nieuw instrument in de rekenbare modeltheorie dat de relatie tussen de complexiteit van een structuur en de complexiteit van zijn substructuren (reducties) diepgaand belicht.