On a Theorem by Bezboruah & Shepherdson

Each language version is independently generated for its own context, not a direct translation.

Hier is een uitleg van het artikel van Albert Visser, vertaald naar eenvoudig Nederlands met behulp van creatieve analogieën.

De Kern: Een Wiskundige Ruzie over "Te Dikke" Regels

Stel je voor dat wiskundigen een enorme, onbreekbare muur hebben gebouwd. Deze muur heet de Tweede Onvolledigheidsstelling van Gödel. De boodschap van deze muur is simpel: "Als een wiskundig systeem sterk genoeg is om rekenen te doen, kan het nooit bewijzen dat het zelf geen fouten maakt."

In 1976 deden twee wiskundigen, Bezboruah en Shepherdson, een poging om deze muur te doorbreken, maar dan voor een heel klein, zwak systeem genaamd Q (of PA-). Ze zeiden: "Zelfs dit kleine systeem kan niet bewijzen dat het veilig is."

Maar toen kwam een grote autoriteit in het veld, Georg Kreisel, en zei: "Stop! Dat is niet interessant. Het systeem Q is zo zwak dat de zin 'ik ben veilig' in dat systeem eigenlijk niets betekent. Het is alsof je vraagt of een lepel een auto kan rijden. De lepel is te simpel om dat woord 'auto' te begrijpen."

Bezboruah en Shepherdson publiceerden hun werk toch, maar met een excuus in de introductie. Ze voelden zich een beetje schuldig omdat Kreisel zo'n grote naam was.

Albert Visser (de auteur van dit artikel) zegt nu: "Kreisel had ongelijk. Laten we die excuus-mentaliteit vergeten en kijken wat er echt gebeurt."

De Analogieën

1. De Taal van de Lopen (Kreisel's Bezwaar)

Kreisel's argument was als volgt: Stel je voor dat je een taal spreekt die alleen woorden kent als "rood", "blauw" en "groen". Als je nu vraagt: "Is deze zin grammaticaal correct?", dan is dat een vraag die je taal niet kan beantwoorden, omdat je taal geen woorden heeft voor "grammatica".

Kreisel zei: "In het systeem Q is de zin 'Q is consistent' alsof je in die taal vraagt of de zin grammaticaal correct is. Het systeem heeft niet de 'grammatica-regels' (de wiskundige eigenschappen) om te begrijpen wat consistentie is. Dus het is een zin zonder betekenis."

Visser's tegenwerping:
Visser vergelijkt dit met een situatie waarin we in het Nederlands (een sterke taal) een zin hebben die we ook in het Pools (een zwakke taal) kunnen zeggen. Als we vragen: "Kan de Pools spreker deze zin begrijpen?", dan is het antwoord misschien "nee", maar dat betekent niet dat de zin in het Pools geen betekenis heeft. De betekenis komt van de context (de echte wereld), niet alleen van de beperkte taal van de spreker.
Visser zegt: "We moeten niet eisen dat een klein systeem alle regels zelf kan bewijzen om de zin 'ik ben veilig' zinvol te maken. De zin is zinvol, zelfs als het systeem te dom is om het te bewijzen."

2. De Twee Manieren om de Muur te Bekijken

Visser vergelijkt het werk van Bezboruah & Shepherdson met een moderne versie van Gödel's theorema (van Pavel Pudlák) als twee verschillende manieren om een berg te beklimmen.

De moderne weg (Pudlák): Dit is als een dure helikopter. Je gebruikt geavanceerde technologie (interpretaties, complexe logica) om bovenop de berg te komen. Het werkt voor bijna elke berg, maar het is zwaar en complex.
De oude weg (Bezboruah & Shepherdson): Dit is als het klimmen met een touw en een ladder. Het is veel ruwer, werkt alleen voor specifieke, kleine rotsen (zwakke systemen), maar het is een prachtige, pure technische uitdaging. Het laat zien hoe je met minimale middelen een groot probleem oplost.

Visser vindt dat we beide wegen moeten waarderen. De oude weg is niet "dom" of "zinloos" omdat hij anders is; hij leert ons iets anders over de structuur van wiskunde.

3. De Magische Code (Het Bewijs)

In het laatste deel van het artikel doet Visser iets heel cooles. Hij pakt het bewijs van Bezboruah & Shepherdson en maakt het slimmer.

Stel je voor dat je een lange rij blokken moet bouwen om een muur neer te halen. De originele methode gebruikte een specifieke manier om blokken te coderen (de $\beta$ -functie). Visser zegt: "Laten we een andere manier proberen, gebaseerd op een oude idee van Markov."

Hij gebruikt matrices (vierkante getallenborden) als blokken.

Hij neemt twee speciale matrices, laten we ze A en B noemen.
Hij bouwt een lange keten: A, A, A... (veel A's) en dan B, B, B... (veel B's).
In een normaal universum (de echte wiskunde) is deze keten geen geldig "bewijs" van een fout.
Maar Visser bouwt een speciaal, vreemd universum (een wiskundig model) waar deze keten wel als een geldig bewijs van een fout telt.

Het is alsof je een puzzelstukje hebt dat in de echte wereld niet past, maar in een "droomwereld" perfect in de gleuf schuift en de hele constructie doet instorten. Dit bewijst dat het kleine systeem (PA-) inderdaad niet kan bewijzen dat het veilig is, omdat er een wereld bestaat waarin het wel fouten maakt, zonder dat het systeem dat kan zien.

Wat is de Conclusie?

Kreisel had ongelijk: Het is heel belangrijk en interessant om te kijken of zelfs de allerzwakste wiskundige systemen hun eigen veiligheid kunnen bewijzen. Het is niet "zinloos" alleen omdat het systeem klein is.
Twee verschillende theorema's: Er is de "grote, moderne" versie van Gödel (Pudlák) en de "kleine, technische" versie (Bezboruah & Shepherdson). Ze zijn verschillend, maar beide waardevol.
Nieuw bewijs: Visser heeft een nieuw, slimmer bewijs gemaakt voor de oude theorie, waarbij hij matrices gebruikt in plaats van de oude methoden. Dit laat zien dat de wiskunde nog steeds verrassingen heeft, zelfs voor oude problemen.

Kortom: Visser zegt: "Stop met excuses maken voor het werk van Bezboruah en Shepherdson. Het is een prachtige, technische prestatie die ons leert dat zelfs de kleinste wiskundige systemen diep verborgen geheimen hebben die ze zelf niet kunnen onthullen."

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het artikel "On a Theorem by Bezboruah & Shepherdson" van Albert Visser, geschreven in het Nederlands.

Titel: Over een stelling van Bezboruah & Shepherdson

Auteur: Albert Visser
Onderwerp: Wiskundige logica, onvolledigheidsstellingen, theorieën van zwakke arithmetica.

1. Het Probleem en de Achtergrond

Het artikel behandelt een specifieke onvolledigheidsresultaat bewezen door Bezboruah en Shepherdson in 1976 ([BS76]). Hun stelling stelt dat de zwakke theorie PA⁻ (de theorie van het niet-negatieve deel van een discreet geordende commutatieve ring) de consistentie van geen enkele theorie kan bewijzen, mits aan bepaalde voorwaarden voor de codering van syntax wordt voldaan.

De Kern van het Debat:

Kreisel's Objection: Georg Kreisel betoogde dat dit resultaat betekenisloos is. Zijn argument was dat in een zo zwakke theorie als Q (Robinson's arithmetica) of PA⁻, de gebruikelijke formules die consistentie uitdrukken ( $con(Q)$ ), niet de betekenis van consistentie hebben. Kreisel stelde dat een bewijspredicaat alleen als "intensioneel correct" kan worden beschouwd als de theorie de Hilbert-Bernays- of Löb-condities kan verifiëren. Omdat Q deze condities niet kan bewijzen, zou $con(Q)$ in Q slechts een algebraïsche eigenschap uitdrukken en geen echte consistentie.
Visser's Positie: Visser betoogt dat Kreisel's argument "niet waterdicht" is. Hij stelt dat de betekenis van formules niet per se moet variëren met de theorie waarin ze worden gebruikt. Zelfs als Q de eigenschappen van het bewijspredicaat niet kan afleiden, kan de formule nog steeds de consistentie van Q uitdrukken binnen een bredere semantische context (zoals de ware arithmetiek). Visser verdedigt het belang van het technische uitdaging om de onvolledigheidsstelling voor zulke zwakke systemen te bewijzen.

2. Methodologie

Visser gebruikt een combinatie van filosofische analyse, modeltheoretische constructies en algebraïsche coderingstechnieken.

Vergelijking met Pudlák: Visser vergelijkt het resultaat van Bezboruah & Shepherdson met de moderne uitbreiding van de Tweede Onvolledigheidsstelling door Pavel Pudlák. Pudlák toonde aan dat als een theorie $U$ interpreteerbaar is in $Q + con(U)$ , dan is $U$ inconsistent. Dit maakt gebruik van het feit dat $Q$ de theorie $S^1_2$ (een theorie voor polynoom-tijd berekenbaarheid) kan interpreteren op een definieerbare "snede" (cut).
Modelconstructie: Het centrale bewijs in het artikel (sectie 4) is een nieuwe, zelfstandige bewijstechniek voor het resultaat van Bezboruah & Shepherdson. Visser construeert specifieke niet-standaard modellen van ware arithmetiek om een "vals bewijs" van inconsistentie te creëren binnen een submodel dat voldoet aan de axioma's van PA⁻.
Coderingstechniek (Markov Coding): In plaats van de traditionele $\beta$ -functie van Gödel, gebruikt Visser een codering gebaseerd op de Markov-codering. Deze is gebaseerd op de isomorfie tussen de groep $SL_2(\mathbb{N})$ (2x2 matrices met gehele getallen en determinant 1) en de vrije monoid op twee generatoren.

3. Belangrijkste Bijdragen en Resultaten

A. Verdediging van het Bezboruah-Shepherdson Theorema

Visser weerlegt Kreisel's kritiek en bevestigt dat het resultaat zinvol is. Hij toont aan dat zelfs in zeer zwakke systemen, onder specifieke coderingsvoorwaarden, de consistentiestelling niet bewijsbaar is.

B. Vergelijking met Pudlák's Stelling

Visser analyseert de verschillen tussen de twee benaderingen:

Scope: Pudlák's resultaat is breder (geldt voor interpretaties en is robuust tegenover variaties in Gödel-codering), maar vereist sterkere theorieën om de interpretatie te bewijzen. Het resultaat van Bezboruah & Shepherdson is specifieker voor PA⁻ en Q, maar vereist strikte voorwaarden voor de codering (zoals de $\beta$ -functie of Markov-codering).
Generalisatie: Pudlák's bewijs generaliseert naar interpretaties; het resultaat van Bezboruah & Shepherdson doet dit niet direct.
Technische Details: Het Bezboruah-Shepherdson-resultaat is afhankelijk van de specifieke vorm van de bewijssystemen (Hilbert-stijl) en de codering, terwijl Pudlák's aanpak minder gevoelig is voor de details van de Gödel-codering.

C. Nieuw Bewijs met Markov-codering (Hoofdstuk 4)

Dit is het meest technische deel van het artikel. Visser bewijst een variant van het Bezboruah-Shepherdson-theorema voor PA⁻ plus alle ware universele zinnen, gebruikmakend van Markov-codering.

De Constructie:
- Er worden twee niet-standaard modellen $M$ en $N$ van ware arithmetiek overwogen, waarbij $N$ een elementaire einduitbreiding is van $M$ .
- Er worden elementen $a \in M \setminus N$ en $b \in N \setminus M$ gekozen.
- Er wordt een matrix $\beta = [n]^a [m]^b$ geconstrueerd, waarbij $[n]$ en $[m]$ specifieke matrices zijn die corresponderen met de Gödel-codes van axioma's en conclusies.
- Er wordt een submodel $K$ geconstrueerd (een discret geordende commutatieve ring) dat gegenereerd wordt door de ring-operaties op de elementen van $\beta$ .
Het Resultaat:
- In het model $K$ is de rij $\beta$ een geldig bewijs van $\bot$ (onwaarheid) in de theorie BeSh (een zeer zwakke theorie met axioma $\bot \to \bot$ en modus ponens).
- Echter, het "switchpunt" waar het bewijs overgaat van axioma's naar afgeleide zinnen (het punt waar de rij van $a$ naar $b$ gaat), is niet aanwezig in $K$ .
- Hierdoor ziet $K$ de rij $\beta$ als een geldig bewijs van $\bot$ , terwijl $\bot$ in werkelijkheid niet bewijsbaar is.
- Dit betekent dat $K$ (en dus PA⁻) de consistentie van BeSh niet kan bewijzen.

D. Rol van ChatGPT

Visser geeft eerlijk toe dat hij ChatGPT heeft gebruikt om de recursieve vergelijkingen voor de rij $s_{n,m}$ (gerelateerd aan de eigenwaarden van de matrices) af te leiden en om een voorloper van een cruciale schatting in het bewijs van Lemma 4.3 te vinden. Dit versnelde het proces aanzienlijk.

4. Significatie en Conclusie

Didactische Waarde: Het artikel toont aan dat het bewijzen van onvolledigheidsstellingen voor zwakke theorieën zoals Q en PA⁻ een waardevolle technische uitdaging blijft, ondanks Kreisel's scepticisme. De constructie van modellen die inconsistentie "zien" terwijl deze er niet is, biedt inzicht in de grenzen van zwakke systemen.
Technische Innovatie: De toepassing van Markov-codering (via $SL_2(\mathbb{Z})$ ) als alternatief voor de $\beta$ -functie toont aan dat het resultaat robuuster is dan gedacht en afhankelijk is van de keuze van de codering, maar niet uitsluitend van de $\beta$ -functie.
Filosofische Implicatie: Visser concludeert dat de vraag of de Tweede Onvolledigheidsstelling geldt voor Q zinvol is, zelfs als Q de Hilbert-Bernays-condities niet kan bewijzen. De betekenis van consistentie is niet afhankelijk van de bewijskracht van het systeem waarin de consistentiestelling wordt geformuleerd.

Samenvattend biedt dit artikel een verdediging van een verwaarloosd klassiek resultaat, een vergelijking met moderne ontwikkelingen, en een nieuw, elegant bewijs dat algebraïsche structuren (matrices) gebruikt om logische onvolledigheid in zwakke systemen te demonstreren.