💻 computer science

Formalizing the Real Numbers in Homotopy Type Theory with Cubical Agda

Dit artikel presenteert een formalisering van de constructie van Cauchy-reële getallen in Homotopietypetheorie binnen Cubical Agda, en toont aan dat deze aanpak de problemen met aftelbare keuze, setoid-overhead en universe-niveau-tracking die inherent zijn aan andere constructieve definities vermijdt, terwijl het typecontroleert zonder postulaat.

Oorspronkelijke auteurs: Jackson Brough

Gepubliceerd 2026-04-29

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Jackson Brough

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 voor dat je probeert een perfecte, oneindige liniaal te bouwen om alles in het universum te meten. In de wereld van de klassieke wiskunde is deze liniaal eenvoudig te beschrijven: je neemt gewoon alle mogelijke "benaderende" metingen (zoals 3,1; 3,14; 3,141; enzovoort) en zegt: "Als twee reeksen metingen steeds dichter bij elkaar komen, vertegenwoordigen ze hetzelfde punt op de liniaal."

Echter, in Constructieve Wiskunde – een stijl van wiskunde die erop staat dat je het waarover je spreekt daadwerkelijk moet kunnen bouwen of berekenen – stuit deze eenvoudige aanpak op een muur. Om te bewijzen dat je liniaal compleet is, moet je een magische keuze maken: je moet één specifieke meting kiezen uit een oneindige lijst van opties om het uiteindelijke punt te vertegenwoordigen. Constructieve wiskunde zegt: "Geen magie toegestaan. Als je me niet kunt laten zien hoe je het hebt gekozen, heb je de liniaal nog niet gebouwd."

Decennialang moesten wiskundigen compromissen sluiten. Ze gebruikten ofwel "administratieve" trucs die elke berekening rommelig maakten, of ze bouwden de liniaal op een manier die het bijhouden van complexe "universum-niveaus" vereiste (zoals het bijhouden van de score van hoe groot je dozen zijn).

Het Nieuwe Ontwerp (HoTT-boek Reële Getallen)
Dit proefschrift presenteert een nieuw ontwerp voor het bouwen van de liniaal, overgenomen uit het beroemde Homotopy Type Theory (HoTT)-boek. In plaats van de liniaal te bouwen door stukken aan elkaar te lijmen en ze vervolgens glad te strijken, bouwt deze methode de liniaal en de "gladheids"-regels gelijktijdig.

Stel je voor dat je een huis bouwt waarbij de muren en het bouwplan op exact hetzelfde moment worden getekend.

De Bakstenen: Je begint met eenvoudige, bekende getallen (zoals breuken).
De Lijm: Je voegt een speciale regel toe die zegt: "Als twee punten dicht genoeg bij elkaar liggen, zijn ze eigenlijk hetzelfde punt."
De Magie: Omdat de regel voor "dichtbij" in de definitie van het huis zelf is ingebouwd, hoef je later geen van die magische keuzes meer te maken. Het huis is compleet op het moment dat je de laatste baksteen legt.

De Uitdaging: De Computervertaler
De auteur, Jackson Brough, nam dit theoretische ontwerp en probeerde het te vertalen naar een taal die een computer kan begrijpen en verifiëren: Cubical Agda.

Stel je voor dat je probeert een complexe dansroutine uit te leggen aan een robot die alleen strikte, letterlijke instructies begrijpt.

Het Probleem: Eerdere pogingen om dit ontwerp te vertalen mislukten omdat de computertaal niet de juiste "bewegingen" had (specifiek kon het niet omgaan met de gelijktijdige definitie van de liniaal en de regels voor dichtbij). De vertalers moesten zeggen: "Neem aan dat deze beweging bestaat", wat in de wiskunde bedriegen is.
De Oplossing: Cubical Agda is een nieuwere, slimmere robot die deze complexe bewegingen natief begrijpt. Het stelt de auteur in staat het ontwerp exact te schrijven zoals het was ontworpen, zonder te bedriegen.

Wat Er Gebeurde Tijdens de Vertaling?
Het proefschrift gaat niet alleen over het typen van code; het gaat over wat er gebeurde toen de auteur probeerde de computer de wiskunde te laten begrijpen. De strenge aard van de computer dwong de auteur om verborgen gaten in de oorspronkelijke uitleg te vinden:

De "Alternatieve" Kaart: Het oorspronkelijke boek beschreef hoe je kunt controleren of twee punten dicht bij elkaar liggen. Maar toen de auteur probeerde de code te schrijven, realiseerde hij zich dat de methode in het boek als een "eenrichtingsstraat" werkte. Je kon bewijzen dat punten dicht bij elkaar lagen, maar je kon niet eenvoudig terugwerken om te zien waarom. De auteur moest een tweede, "berekenende" kaart bouwen (een alternatieve relatie genoemd) die fungeert als een achteruitversnelling, waardoor de computer het antwoord daadwerkelijk kan berekenen.
Het Ontbrekende Ingrediënt: Het boek beschreef een regel voor het bouwen van functies (zoals vermenigvuldiging) alsof de computer het oorspronkelijke lijstje met benaderingen kon "onthouden". De eerste codeversie van de auteur vergat dit geheugen. De computer verwierp het. De auteur moest de regel herschrijven om het geheugen expliciet mee te nemen, en besefte dat de oorspronkelijke tekst te vaag was voor een machine.
De Meervariabele Puzzel: Het boek suggereerde dat regels voor enkele getallen eenvoudig kunnen worden toegepast op paren of drietallen getallen. De computer was niet overtuigd. De auteur moest een nieuw, specifiek lemma bewijzen dat laat zien dat als een regel werkt voor één variabele, het ook werkt voor twee, mits je ze één voor één controleert.

Het Resultaat
Het eindproduct is een enorme, open-source bibliotheek met code (meer dan 13.000 regels) die bewijst dat de HoTT-boek reële getallen perfect werken.

Het bewijst dat deze getallen een compleet, geordend lichaam vormen (je kunt ze optellen, aftrekken, vermenigvuldigen, delen en vergelijken).
Het bewijst dat de liniaal "Archimedisch" is (wat betekent dat ongeacht hoe klein een gat je hebt, je altijd een breuk kunt vinden die erin past).
Het allerbelangrijkste: het doet dit alles zonder te bedriegen. De computer controleerde elke enkele stap, en de code draait zonder "magische aannames".

Samenvattend
Dit proefschrift is het verhaal van het nemen van een mooi, hoog-niveau wiskundig idee en het dwingen om te overleven in de strenge, letterlijke wereld van computerverificatie. Door dit te doen, bouwde de auteur niet alleen een digitale liniaal; hij polijste het ontwerp zelf, onthulde verbonden details en maakte de theorie sterker en nauwkeuriger dan voorheen. De code is nu beschikbaar voor iedereen om te gebruiken als een solide fundament voor toekomstige wiskundige ontdekkingen.

1. Probleemstelling

Constructieve wiskunde streeft naar het leveren van computationele interpretaties voor wiskundige bewijzen, maar de constructie van de reële getallen ( $\mathbb{R}$ ) heeft historisch gezien aanzienlijke compromissen vereist:

Klassieke Cauchy-constructie: Vereist het Axioma van Aftelbare Keuze om vertegenwoordigers te selecteren uit equivalentieklassen van Cauchy-rijen om Cauchy-volledigheid te bewijzen. Dit is niet-constructief.
Bishop's Setoid-constructie: Vermijdt keuze door te werken met Cauchy-rijen uitgerust met een expliciete equivalentierelatie (setoids). Dit introduceert echter aanhoudende administratieve overhead, waarbij voor elke operatie en elk stelling expliciete congruentiebewijzen vereist zijn, wat algebraïsche structuren ingewikkeld maakt.
Dedekind-snedes: In voorspelbare type-theorie vereisen Dedekind-snedes het bijhouden van universum-niveaus (de reële getallen leven één niveau boven hun snedes), wat ontwikkelingen omslachtig maakt.

Het HoTT-boek (Homotopy Type Theory) stelt een oplossing voor: het definiëren van reële getallen als een Higher Inductive-Inductive Type (HIIT). Deze constructie vermijdt keuze, elimineert setoid-overhead door $\epsilon$ -dichtbijzijnde reële getallen te identificeren via padconstructoren, en vermijdt het bijhouden van universum-niveaus. Eerdere formalisaties (bijvoorbeeld door Gilbert in Rocq) waren echter onvolledig omdat de bewijshulpmiddelen geen native ondersteuning hadden voor HIITs, waardoor de auteur gedwongen was de padconstructoren en hun berekeningsregels te postuleren in plaats van ze af te leiden.

2. Methodologie

Het proefschrift presenteert een volledige, machine-gecontroleerde formalisatie van de HoTT-boek reële getallen met behulp van Cubical Agda, een bewijshulpmiddel gebaseerd op Cubical Type Theory.

Native Ondersteuning: Cubical Agda ondersteunt native Higher Inductive Types (HITs) en Inductief-Inductieve definities. Dit stelt de auteur in staat om de reële getallen en de dichtbijzijnde-relatie simultaan te definiëren zonder postulaten, zodat padconstructoren native berekeningsregels hebben.
Formalisatieomvang: Het werk formaliseert meer dan 13.000 regels code, die de volgende onderwerpen bestrijken:
1. De HIIT-definitie van $\mathbb{R}$ en de dichtbijzijnde-relatie ( $\sim_\epsilon$ ).
2. Inductie- en recursieprincipes.
3. Eigenschappen van de dichtbijzijnde-relatie (reflexiviteit, symmetrie, driehoeksongelijkheid, afgerondheid).
4. Uitbreidingsprincipes voor Lipschitz- en niet-expanderende afbeeldingen.
5. De constructie van algebraïsche operaties (optelling, negatie, min/max, vermenigvuldiging, reciproke).
6. Orde-theorie (strikt/niet-strikt ongelijkheden, apartheid).
7. Het bewijs dat $\mathbb{R}$ een Archimedisch geordend lichaam vormt.
Tooling: De auteur gebruikte Claude Code (Anthropic's AI-agent) om te helpen bij het navigeren door de grote Cubical Agda-standaardbibliotheek en om informele bewijsschetsen om te zetten in formele Agda-termen, wat de ontwikkeling van complexe bewijzen, zoals de constructie van de reciproke, aanzienlijk versnelde.

3. Belangrijkste Bijdragen

A. De Eerste Volledige Formalisatie van HoTT Reële Getallen

Dit is de eerste formalisatie van de HoTT-boek reële getallen die geen gebruik maakt van postulaten. Eerdere pogingen moesten de existentie van padconstructoren aannemen; dit werk leidt ze direct af uit de Cubical Agda type-theorie, zodat alle berekeningsregels definitorisch gelden.

B. Oplossing van Formalisatiegaten

Het formalisatieproces onthulde subtiele problemen in de informele presentatie van het HoTT-boek die wiskundige verfijning vereisten:

Alternatieve Dichtbijzijnde-relatie: De inductieve definitie van dichtbijzijnde ( $\sim$ ) biedt voldoende voorwaarden maar niet noodzakelijke voorwaarden voor het extraheren van getuigen. De formalisatie construeert strikt een hulprelatie ( $\approx$ ) die berekent op constructoren en bewijst dat $\sim \iff \approx$ , wat casusanalyse op dichtbijzijnde-hypothese mogelijk maakt.
Verbeterd Recursieprincipe: De notatie voor het recursieprincipe in de informele tekst nam stilzwijgend toegang aan tot de domeinbenadering ( $x_\epsilon$ ) binnen de inductieve hypothese. De formalisatie vereiste een expliciete herformulering van het recursieprincipe om zowel de benadering als de toewijzing van het codomein mee te dragen, een detail dat in eerste naïeve transcripties was gemist.
Meervoudige Continuïteit: Het HoTT-boek impliceert dat aparte continuïteit voldoende is voor het uitbreiden van identiteiten naar meerdere variabelen. De formalisatie bewees dit expliciet (Lemma 2.3.4), en toonde aan dat aparte continuïteit voldoende is om binaire en ternaire identiteiten van $\mathbb{Q}$ naar $\mathbb{R}$ uit te breiden.

C. Constructie van Vermenigvuldiging en Reciproke

Vermenigvuldiging en reciproke zijn niet globaal Lipschitz, dus ze kunnen niet worden gedefinieerd via eenvoudige uitbreidingsprincipes. Het proefschrift adopteert Gilbert's lokaal-naar-globaal strategie:

Definieer operaties op beperkte domeinen waar Lipschitz-grenzen bestaan (bijvoorbeeld het vaststellen van een grens voor één factor).
Bewijs dat deze lokale definities overeenkomen op overlappingen.
Gebruik Kraus's Stelling (afbeeldingen van propositionele truncaties naar sets) om de afhankelijkheid van de specifieke grens te elimineren, wat een globale definitie oplevert.
Deze aanpak werd geïmplementeerd met behulp van het SetElim-module van de Cubical Agda-standaardbibliotheek.

D. Computationele Efficiëntie

In tegenstelling tot de klassieke quotiëntconstructie in Lean (waarbij $2+2=4$ voor reële getallen niet definitorisch waar is), staat de HoTT-constructie in Cubical Agda toe dat rekenen op rationele invoer definitorisch berekent. Bijvoorbeeld, rational(2) + rational(2) = rational(4) reduceert direct tot refl (reflexiviteit) in de typechecker.

4. Resultaten

Archimedisch Geordend Lichaam: De formalisatie bewijst succesvol dat het geconstrueerde type $\mathbb{R}$ voldoet aan alle axioma's van een Archimedisch geordend lichaam, inclusief het bestaan van inverse elementen voor elementen die apart zijn van nul.
Beschikbaarheid Code: De volledige codebase (ongeveer 13.500 regels) is open source en type-checkt zonder gaten of postulaten met de nieuwste Cubical Agda-standaardbibliotheek.
AI-ondersteunde Ontwikkeling: Het proefschrift demonstreert de effectiviteit van het gebruik van op LLM gebaseerde coderingsagenten voor formele wiskunde, specifiek voor het navigeren door grote bibliotheken en het vertalen van hoog-niveau bewijsstrategieën naar laag-niveau afhankelijke type-termen.

5. Betekenis

Fundamenteel voor Constructieve Analyse: Dit werk biedt een robuuste, machine-gecontroleerde basis voor constructieve analyse binnen het programma van Univalente Fundamenten. Het verwijdert de "administratieve" last van setoids en de "keuze"-last van klassieke quotiënten.
Evolutie van Bewijshulpmiddelen: Het valideert Cubical Agda als een superieure omgeving voor HIIT-gebaseerde wiskunde in vergelijking met systemen zoals Rocq (Coq) die geen native HIT-ondersteuning hebben.
Toekomstig Werk: De formalisatie bereidt het toneel voor voor het uitbreiden van constructieve analyse naar complexere structuren (bijvoorbeeld Riemann-integratie, differentiaalvergelijkingen) en het generaliseren van concepten zoals locators (structuren die berekening op reële getallen toestaan) naar bredere metrische ruimten.
Methodologisch Inzicht: Het proefschrift benadrukt dat formalisatie niet louter een verificatie-oefening is, maar een wiskundige activiteit die impliciete aannames kan blootleggen en stellingen kan verfijnen op manieren die informele lectuur alleen niet kan.

Kortom, Jackson Brough's proefschrift overbrugt de kloof tussen de theoretische elegantie van de reële getallen uit het HoTT-boek en praktische, uitvoerbare wiskunde, en biedt een geverifieerde, computationeel efficiënte en postulaat-vrije basis voor reële analyse in type-theorie.