💻 computer science

Four Paradoxes and a Proof Assistant: Burali-Forti, Diaconescu, Reynolds, and Hurkens in the coq-paradoxes library

Dit artikel analyseert de vier paradoxen die zijn geautomatiseerd in de coq-paradoxes-bibliotheek om te demonstreren hoe zij gezamenlijk de noodzakelijke ontwerpgrenzen van de Rocq-kern definiëren—specifiek wat betreft impredicativiteit, grote eliminatie en universumbeperkingen—door de precieze redenen te illustreren waarom het systeem bepaalde constructies moet afwijzen om consistentie te handhaven.

Oorspronkelijke auteurs: Bernardo Alonso

Gepubliceerd 2026-05-28

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Bernardo Alonso

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een zeer strenge, zeer slimme robot-architect voor met de naam Rocq. Zijn taak is het bouwen van logische structuren (wiskundige bewijzen) die gegarandeerd veilig en consistent zijn. Hij crasht nooit, liegt nooit en produceert nooit een tegenstrijdigheid.

Maar hoe weet je dat de robot zijn werk correct uitvoert? Je kijkt niet alleen toe terwijl hij bouwt; je probeert hem te misleiden. Je probeert hem een blauwdruk te geven die er naar uit ziet alsof hij zou moeten werken, maar die in werkelijkheid een verborgen valkuil bevat die ervoor zou zorgen dat het hele gebouw instort.

Dit artikel gaat over een speciale bibliotheek van "val-blauwdrukken" genaamd coq-paradoxes. Het bevat vier specifieke pogingen om de logica van de robot te breken. Het artikel betoogt dat dit niet zomaar raadsels of curiositeiten zijn; het zijn eigenlijk het veiligheidshandboek van de robot, omgekeerd geschreven. Ze tonen precies aan waar de regels van de robot zijn getrokken om rampen te voorkomen.

Hier is een uiteenzetting van de vier valkuilen en wat ze ons leren, met behulp van eenvoudige analogieën:

1. De Burali-Forti-val: De "Doos die Zichzelf Bevat"

De Val: Stel je een bibliotheek voor waar elk boek een label heeft dat de eigen inhoud beschrijft. De paradox probeert een "Hoofdcatalogus" te creëren die elk enkel boek in de bibliotheek opnoemt, inclusief de Hoofdcatalogus zelf.
Het Probleem: Als de catalogus een boek is, moet hij zichzelf opnoemen. Maar als hij zichzelf opnoemt, verandert de grootte van de bibliotheek, wat de catalogus verandert, wat de bibliotheek verandert... het is een lus die de regels van grootte doorbreekt.
De Les: De robot (Rocq) heeft een regel over Universe-hiërarchie. Hij zegt: "Een doos kan niet in een doos zitten die even groot is als zichzelf." De robot weigert de Hoofdcatalogus te bouwen omdat de wiskunde aangeeft dat de "binnenste doos" kleiner moet zijn dan de "buitenste doos". Deze valkuil bewijst dat de robot correct een strikte groottebeperking afdwingt om oneindige lussen te voorkomen.

2. De Diaconescu-val: De "Magische Muntwerper"

De Val: Stel je een machine voor die een "winnaar" kan kiezen uit elke groep van gelijkgestemde opties (zoals het kiezen van een vertegenwoordiger uit een groep identieke tweelingen). De paradox zegt: "Als je me deze machine geeft, kan ik hem dwingen me het antwoord te geven op elke ja/nee-vraag (zoals 'Is de lucht blauw?') zonder het antwoord daadwerkelijk te kennen."
Het Probleem: In een constructief systeem (waar je het antwoord moet bouwen, niet alleen raden), is het hebben van een machine die winnaars kiest uit gelijkgestemde opties te krachtig. Het dwingt het systeem stiekem om "Of A is waar OF A is onwaar" te accepteren voor alles, zelfs dingen die we nog niet kunnen bewijzen.
De Les: De robot heeft een regel over Grote Eliminatie. Hij zegt: "Je kunt een winnaar kiezen uit een groep getallen, maar je kunt dat niet gebruiken om magisch een filosofische waarheid te beslissen." Deze valkuil toont aan dat als de robot dit soort "magische keuze" zou toestaan, het per ongeluk het vermogen van het systeem zou breken om onderscheid te maken tussen dingen die we weten en dingen die we niet weten.

3. De Reynolds-val: Het "Woordenboek dat Niet Kan Bestaan"

De Val: Stel je voor dat je probeert een woordenboek te maken waar elke mogelijke definitie een woord is in het woordenboek. De paradox probeert een "Universeel Woordenboek" te bouwen dat elke mogelijke zin afbeeldt op één enkel woord.
Het Probleem: Dit is als proberen een kaart van de hele wereld op één postzegel te passen. De wiskunde bewijst dat als je probeert alle mogelijke logische uitspraken te comprimeren tot één enkel type object, je een tegenstrijdigheid creëert (vergelijkbaar met hoe je niet alle mogelijke lijsten kunt opnoemen).
De Les: De robot heeft een regel over Impredicatitiviteit (het toestaan dat een definitie verwijst naar de hele groep waar hij toe behoort). De robot staat dit toe voor "Proposities" (eenvoudige waar/onwaar uitspraken), maar trekt elders een harde lijn. Deze valkuil toont aan dat als de robot dit soort "universeel woordenboek" zou toestaan voor complexe typen, het hele systeem zou instorten.

4. De Hurkens-val: De "Zelfreferentiële Spiegel"

De Val: Dit is de meest complexe. Stel je een spiegel voor die een reflectie weerspiegelt, die een reflectie weerspiegelt, voor altijd. De paradox probeert een systeem te bouwen waar je naar een "klein" object kunt kijken (zoals een boolean waar/onwaar) en het kunt gebruiken om een "groot" object te definiëren (zoals een heel universum van typen), en dat grote object vervolgens weer kunt gebruiken om het kleine opnieuw te definiëren.
Het Probleem: Het is een "zelfreferentiële lus" die het vermogen combineert om naar grote en kleine dingen te kijken op een manier die een logische paradox creëert. Het is als een slang die zijn eigen staart eet, maar de staart is gemaakt van het eigen lichaam van de slang.
De Les: De robot heeft een regel over Impredicatitiviteit in Set. Hij zegt: "Je kunt zelfreferentieel zijn met eenvoudige waar/onwaar uitspraken, maar je kunt dat niet mengen met grote, complexe typen." Deze valkuil bewijst dat als de robot deze mix zou toestaan, het onmogelijk zou zijn om het systeem consistent te houden.

Het Grote Plaatje: Waarom Dit Belangrijk Is

Het artikel betoogt dat we deze vier bestanden niet moeten zien als "mislukte wiskunde". In plaats daarvan moeten we ze zien als bewijs van het succes van de robot.

Negatieve Specificatie: Denk aan deze bestanden als een "Gezocht"-poster voor een crimineel. De crimineel is "Inconsistentie". De poster toont de crimineel niet; hij toont de exacte omstandigheden waaronder de crimineel zou verschijnen.
De Grens: De robot (Rocq) heeft drie onzichtbare lijnen in het zand getrokken:
1. Groottebeperkingen: Je kunt geen doos in een doos van dezelfde grootte plaatsen.
2. Keuzebeperkingen: Je kunt een eenvoudige keuze niet gebruiken om een complexe waarheid af te dwingen.
3. Reflectiebeperkingen: Je kunt eenvoudige zelfreferenties niet mengen met complexe typen.

Elke keer dat een gebruiker probeert een structuur te bouwen die een van deze lijnen overschrijdt, stopt de robot hen. Deze vier bestanden zijn het bewijs dat de robot precies doet wat hij is ontworpen te doen: weigeren om iets te bouwen dat uiteindelijk zou instorten.

Kortom, het artikel zegt: "We hebben geprobeerd het systeem te breken met deze vier slimme trucs. Het systeem zei 'Nee.' Dat 'Nee' is het belangrijkste deel van het systeem, omdat het alles veilig houdt."

Technische Samenvatting: Vier Paradoxen en een Bewijsassistent

Probleemstelling
Het artikel behandelt de fundamentele grenzen van de Calculus of Inductive Constructions (CIC), de typetheorie die de Rocq-bewijsassistent (voorheen Coq) onderbouwt. Hoewel de consistentie van CIC goed is vastgesteld, worden de specifieke ontwerpkeuzes die inconsistentie voorkomen – met name wat betreft impredicatieve, universumbeperkingen en grote eliminatie – vaak behandeld als abstracte engineeringbeperkingen. De coq-paradoxes-bibliotheek, die bij Rocq wordt geleverd, bevat vier gemecaniseerde afleidingen van False (Burali-Forti, Diaconescu, Reynolds en Hurkens) die steunen op hypothesen die door de Rocq-kern worden afgewezen. Het centrale probleem is deze afleidingen niet louter te interpreteren als historische curiositeiten of geïsoleerde inconsistenties, maar als een "negatieve specificatie" die precies aangeeft waar de kern zijn grenzen moet trekken om geldigheid te handhaven.

Methodologie
Het artikel hanteert een nauwgezette lezing van de broncode binnen de coq-paradoxes-bibliotheek, met name door vier bestanden te analyseren: BuraliForti.v, diaconescu.v, Reynolds.v en Hurkens_Set.v. De methodologie omvat:

Ontleden van Gedeelde Mechanismen: Analyseren van Logics.v om het toegankelijkheidspredikaat (ACC) en de infrastructuur voor welgeordendheid te begrijpen die door meerdere paradoxen wordt gebruikt.
Traceer Afleidingen: De logische stappen in elk bestand volgen om de specifieke hypothese te identificeren (bijvoorbeeld een universeel type van relaties, een keuzeprincipe of een injectie van Prop naar een enkel predikaat) die leidt tot een tegenstrijdigheid.
Koppelen aan Kernafwijzingen: Het punt van tegenstrijdigheid in de formalisatie correleren met het specifieke mechanisme in de Rocq-kern (universumrekenkunde, eliminatieregels of impredicatieve checks) dat voorkomt dat de constructie compileert.
Synthetiseren van Ontwerpkeuzes: De bevindingen aggregeren om drie verenigde randvoorwaarden af te leiden die het gedrag van de kern regelen.

Belangrijkste Bijdragen en Resultaten

Het artikel analyseert vier specifieke paradoxen en toont aan hoe elke paradox een distincte kwetsbaarheid in de typetheorie blootlegt als bepaalde ontwerpkeuzes zouden worden gewijzigd:

Burali-Forti Paradox (BuraliForti.v):
- Mechanisme: Gaat uit van een universeel type van relaties $A_0$ en een injectie $i_0$ die relaties afbeeldt op elementen van $A_0$ . Dit maakt de constructie mogelijk van een "ordinaal van alle ordinalen" ( $\Omega$ ) die in zichzelf is ingebed.
- Kernafwijzing: De paradox steunt op het instantiëren van $A_0$ met zichzelf. De Rocq-kern handhaaft een strikte universumstratificatie ( $Type_j < Type_i$ ) om te voorkomen dat een type zijn eigen afbeelding bevat. De constructie veroorzaakt een "Universe Inconsistency"-fout omdat het universumniveau dat vereist is voor het binnenste type ten minste zo groot moet zijn als het buitenste type, wat de cumulatieve beperkingen van de kern schendt.
- Resultaat: Vestigt de noodzaak van universumhiërarchie-beperkingen om zelfrefererende typedefinities te voorkomen die leiden tot vastpunt-tegenstrijdigheden.
Diaconescu Paradox (diaconescu.v):
- Mechanisme: Gebruikt een getypeerde versie van het Axioma van de Keuze (Tchoice) op een equivalentierelatie over bool gedefinieerd door een predikaat $P$ . De keuzefunctie $f: bool \to bool$ wordt gebruikt om $P$ te beslissen door $f(\text{true})$ en $f(\text{false})$ te vergelijken.
- Kernafwijzing: Het argument onttrekt een computationele beslissing (een functie in Set) aan een existentieel bewijs in Prop. Dit vormt "grote eliminatie" van Prop naar Set.
- Resultaat: Toont aan dat het toestaan van het Axioma van de Keuze in Set (of grote eliminatie van Prop naar Set) de Wet van het Uitgesloten Midden (LEM) in het constructieve systeem forceert. De kern beperkt grote eliminatie om deze import van klassieke logica naar de computationele laag te voorkomen.
Reynolds Paradox (Reynolds.v):
- Mechanisme: Herformuleert Reynolds' resultaat dat System F geen verzamelingstheoretisch model heeft. Het gaat uit van een injectie $I: Prop \to Heyt$ (waarbij $Heyt$ een enkel predikaat is) en construeert een pre-initiële algebra (Church-codering) voor een functor $\Phi$ . Met behulp van Lawvere's vastpuntstelling leidt het een vast punt voor negatie af, wat leidt tot False.
- Kernafwijzing: De constructie steunt op de impredicatieve aard van Prop (kwantificeren over alle predicaten binnen Prop). De paradox vereist echter een injectie van Prop naar een enkel predikaat, wat de kern op universumgronden afwijst voordat de logische tegenstrijdigheid kan worden bereikt.
- Resultaat: Benadrukt de rol van impredicatieve aard in Prop. Hoewel Prop impredicatief is, verhindert de kern de specifieke structurele injecties die zouden toelaten dat Cantors diagonaalargument de universum van predicaten doet instorten.
Hurkens Paradox (Hurkens_Set.v):
- Mechanisme: Een aanpassing van Hurkens' vereenvoudiging van Girards paradox. Het gaat uit van een retractie tussen Prop en bool (via dubbele negatie) en gebruikt de impredicatieve aard van Set (indien ingeschakeld) gecombineerd met grote eliminatie om een zelfrefererende welgeordende relatie te construeren die leidt tot False.
- Kernafwijzing: De paradox vereist zowel impredicatieve aard in Set als grote eliminatie (het extraheren van booleans uit propositionele inhoud). De standaard Rocq-kern houdt Set predicatief en beperkt grote eliminatie vanuit Prop.
- Resultaat: Toont aan dat de combinatie van impredicatieve aard en grote eliminatie in Set inconsistent is met klassieke logica (LEM). De beslissing van de kern om Set predicatief te houden en eliminatie te beperken, is de veiligheidsmaatregel.

Betekenis en Aanspraken

Het artikel betoogt dat het coq-paradoxes-pakket dient als een negatieve specificatie van de Rocq-kern. In plaats van louter inconsistenties op te sommen, biedt het pakket een formeel bewijs door middel van een mislukt voorbeeld van de geldigheid van de kern.

Drie Randvoorwaarden: Het artikel synthetiseert de vier paradoxen tot drie specifieke ontwerpkeuzes die door de kern worden afgedwongen:
1. Universumhiërarchie: Voorkomt dat types over zichzelf kwantificeren op een manier die vastpunten creëert (Burali-Forti).
2. Plaatsing van Impredicatieve Aard: Beperkt impredicatieve kwantificatie tot Prop (en optioneel Set met voorbehoud), waardoor de Reynolds- en Hurkens-tegenstrijdigheden worden voorkomen.
3. Discipline van Grote Eliminatie: Beperkt het extraheren van computationele inhoud (zoals bool of functies in Set) uit propositionele bewijzen, waardoor de Diaconescu- en Hurkens-tegenstrijdigheden worden voorkomen.
Meta-mathematische Rol: Het artikel claimt dat het pakket een uniek stukje meta-mathematica is dat binnen het systeem dat het documenteert is geschreven. Het bewijst geen stellingen voor toepassing, maar bewijst de onvoldaanheid van specifieke hypothesen. De "weigeren" van de kern blijkt een gevolg te zijn van uniforme beleidslijnen (universumrekenkunde, eliminatieregels) in plaats van ad-hoc-oplossingen.
Conclusie: De betekenis ligt in het aantonen dat de weigering van de Rocq-kern om deze constructies te compileren niet willekeurig is, maar het precieze structurele mechanisme is dat vereist is om de consistentie van CIC te handhaven. Het pakket valideert dat de ontwerpkeuzes van de kern om de "juiste redenen" worden gemaakt, en trekt effectief de grens van het systeem van buiten naar binnen.