💻 computer science

A Proof-Theoretic Approach to the Semantics of Classical Linear Logic

Dit artikel introduceert een bewijstheoretische benadering voor de semantiek van het multiplicatief-additieve fragment van klassieke lineaire logica door het bestaande basis-extensie-semantiekframework uit te breiden naar het klassieke geval.

Oorspronkelijke auteurs: Victor Barroso-Nascimento, Ekaterina Piotrovskaya, Elaine Pimentel

Gepubliceerd 2026-03-03

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Victor Barroso-Nascimento, Ekaterina Piotrovskaya, Elaine Pimentel

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

De Kern: Van "Waarheid" naar "Bewijs"

Stel je voor dat logica een spel is. In de traditionele manier van kijken (de model-theoretische aanpak), kijken we naar een spiegel. We vragen: "Is deze zin waar in deze spiegelwereld?" Als de spiegel de zin weerspiegelt als 'waar', dan is hij waar. Het gaat hier om statische waarheid.

De auteurs van dit paper (Barroso-Nascimento, Piotrovskaya en Pimentel) willen echter niet naar een spiegel kijken. Ze willen naar de bouwer kijken. In hun wereld (de proof-theoretische aanpak) is iets alleen "waar" als je kunt laten zien hoe je het bouwt. Het gaat niet om of het waar is, maar om hoe je het kunt aantonen.

Het Nieuwe Spel: Linear Logic als een Rekenmachine

Om dit te doen, gebruiken ze een speciaal soort logica genaamd Linear Logic.

Normale logica is als een oneindige voorraad melk: je kunt er een kopje van inschenken, en er is nog steeds genoeg voor een tweede kopje. Je kunt het kopiëren en weggooien zonder gevolgen.
Linear Logic is als een rekenmachine met munten. Als je een munt (een formule) gebruikt om iets te kopen, is die munt op. Je kunt hem niet kopiëren en je kunt hem niet zomaar weggooien. Alles is een hulpbron.

De uitdaging van dit paper is: Hoe maken we een "bouwer" voor de klassieke versie van dit spel? Klassieke logica staat bekend om trucjes zoals "Bewijs dat iets onmogelijk is, en dan is het tegenovergestelde waar" (reductio ad absurdum). In een wereld van schaarse hulpbronnen is dat lastig te verklaren.

De Oplossing: De "Basis-uitbreiding" (Base-Extension Semantics)

De auteurs introduceren een methode genaamd Base-Extension Semantics (BeS). Laten we dit uitleggen met een metafoor:

Stel je voor dat je een recept (een bewijs) wilt maken.

De Basis (B): Dit is je basiskeuken met alleen de allerfundamentele ingrediënten (atomen) en de basisregels hoe je die kunt combineren.
Ondersteuning: Een formule wordt "ondersteund" als je kunt laten zien dat, als je de ingrediënten uit je basis gebruikt, je uiteindelijk een specifiek resultaat kunt bereiken.

Het grote geheim van dit paper:
In de klassieke logica gebruiken we vaak de "niet"-operator (negatie) en de "onmogelijkheid" (⊥, oftewel een foutmelding).
De auteurs zeggen: "Laten we de definitie van 'waarheid' iets strakker maken."

In de intuïtionistische logica (de constructieve versie) zeg je: "Ik kan een bewijs maken voor $A$ als ik een bewijs kan maken voor $A$ ."
In hun nieuwe klassieke versie zeggen ze: "Ik kan een bewijs maken voor $A$ als ik kan aantonen dat het niet mogelijk is om een foutmelding (⊥) te krijgen als ik $A$ gebruik."

Het is alsof je zegt: "Ik heb geen bewijs nodig dat iets bestaat. Ik heb alleen nodig dat ik kan aantonen dat het niet kan leiden tot een crash van het systeem."

De Creatieve Analogie: De "Crash-Test"

Stel je voor dat je een nieuwe auto (een logische formule) test.

Intuïtionistische test: Je bouwt de auto en rijdt ermee. Als hij rijdt, is hij goed.
Deze paper's klassieke test: Je gooit de auto tegen een muur (de basisregels). Als de auto niet crasht (geen foutmelding ⊥ geeft), dan is hij "waar" of "geldig".

De auteurs tonen aan dat je de regels voor de klassieke logica kunt krijgen door de regels voor de intuïtionistische logica heel simpel aan te passen:

In plaats van te vragen: "Kun je een willekeurig doel bereiken?"
Vraag je: "Kun je vermijden dat het systeem crasht?"

Dit is een enorme doorbraak. Het betekent dat klassieke logica (die vaak als "minder constructief" wordt gezien) eigenlijk gewoon een beperkte versie is van constructieve logica. Het is alsof je zegt: "Een klassiek bewijs is een constructief bewijs dat minder informatie nodig heeft om te slagen, omdat het alleen hoeft te voorkomen dat het systeem crasht."

Waarom is dit belangrijk?

Het lost een oud probleem op: Het is al lang moeilijk om te verklaren hoe "klassieke" logica (met zijn trucjes) werkt in een wereld van schaarse hulpbronnen (Linear Logic). Dit paper lost dat op door te zeggen: "Gebruik de crash-test."
Het verbindt twee werelden: Het laat zien dat het verschil tussen "klassiek" en "constructief" niet zozeer een kwalitatief verschil is (heel anders), maar een kwantitatief verschil (hoeveel informatie je nodig hebt).
Het werkt voor Linear Logic: Ze hebben dit succesvol toegepast op de "Multiplicative-Additive" versie van Linear Logic (MALL), wat een complex stukje wiskunde is. Ze bewijzen dat hun regels kloppen (soundness) en dat je alles wat waar is, ook kunt bouwen (completeness).

Samenvatting in één zin

Dit paper zegt: "Om de betekenis van klassieke logica te begrijpen in een wereld waar alles een kostbare hulpbron is, hoef je niet te kijken naar wat je kunt bouwen, maar alleen naar wat je kunt voorkomen dat het systeem laat crashen; en dat is eigenlijk gewoon een strakke, beperkte vorm van bouwen."

Het is een elegante manier om te zeggen dat zelfs de meest "onconstructieve" logica nog steeds een stevige, bouwtechnische basis heeft, mits je de regels net iets anders uitlegt.

Titel: Een Bewijstheoretische Benadering voor de Semantiek van Klassieke Lineaire Logica

1. Het Probleem

De traditionele semantiek voor logica wordt vaak model-theoretisch benaderd, waarbij de betekenis van formules wordt bepaald door hun waarheidswaarde in een model (bijv. Kripke-structuren). Hoewel dit werkt voor klassieke logica, is het minder geschikt voor het begrijpen van de constructieve aard van bewijzen, vooral in niet-klassieke systemen zoals Lineaire Logica (LL).

Er zijn twee bestaande manieren om de semantiek van Lineaire Logica te presenteren:

Context-gebaseerd: Het koppelen van formules aan de verzameling van alle contexten die nodig zijn om ze te bewijzen (bijv. fase-semantiek).
Bewijs-gebaseerd: Het toekennen van betekenis direct aan bewijzen (bijv. coherentieruimtes).

De uitdaging ligt in het ontwikkelen van een bewijstheoretische semantiek (Proof-Theoretic Semantics - PtS) voor de klassieke versie van Lineaire Logica, specifiek het multiplicatief-additieve fragment (MALL). Bestaande PtS-benaderingen, zoals Base-extension Semantics (BeS), zijn succesvol voor intuïtionistische logica, maar het toepassen ervan op klassieke systemen is problematisch vanwege:

De definitie van valsheid ( $\bot$ ): In klassieke logica is valsheid niet simpelweg "nooit waar", maar vereist het een omgang met non-constructieve principes (zoals reductio ad absurdum).
De substructurale aard van LL: Formules zijn hulpbronnen die niet zomaar gekopieerd of verwijderd kunnen worden (geen contractie of verzwakking), wat de standaard BeS-regels compliceert.
De klassieke validiteit: Hoe definieer je klassieke geldigheid puur op basis van bewijzen zonder terug te vallen op bivalente waarheid?

2. Methodologie

De auteurs passen Base-extension Semantics (BeS) toe op MALL. In BeS wordt de betekenis van een formule gedefinieerd door de relatie van "ondersteuning" (support, genoteerd als $\Vdash$ ) ten opzichte van een basis ( $B$ ). Een basis is een verzameling afleidingsregels voor atomaire formules.

De kern van hun methode bestaat uit drie stappen:

Herdefinitie van Atomaire Ondersteuning: In plaats van atomaire ondersteuning direct te reduceren tot afleidbaarheid ( $\vdash_B p$ ), gebruiken de auteurs een "eliminatie-approach". Een atoom $p$ wordt ondersteund als alles wat uit $p$ kan worden afgeleid, ook kan worden afgeleid uit wat $p$ ondersteunt.
Invoering van $\bot$ als Atoom: Om de klassieke aard te vangen, behandelen ze de logische constante $\bot$ (valsheid) als een vast atoom dat door de regels van de basis kan worden gemanipuleerd.
Uniforme Restrictie: De cruciale innovatie is het toepassen van een uniforme restrictie op de intuïtionistische bewijsvoorwaarden. In plaats van te eisen dat een willekeurig atomaire propositie $p$ $p$ wordt afgeleid, eist men consistent de constructie van een bewijs voor $\bot$ .
- Voorbeeld: Voor de multiplicatieve conjunctie ( $\otimes$ ) geldt in de nieuwe semantiek: $\Vdash \phi \otimes \psi$ dan en slechts dan als, voor elke uitbreiding van de basis, als $\phi$ en $\psi$ samen $\bot$ ondersteunen, dan ondersteunt de context ook $\bot$ .

Dit creëert een semantiek waarbij klassieke geldigheid wordt verkregen door een kleine, uniforme beperking op de intuïtionistische bewijsvoorwaarden toe te passen.

3. Belangrijkste Bijdragen

Eerste BeS voor Klassieke Substructurale Systemen: Dit artikel presenteert de eerste Base-extension Semantics voor het klassieke multiplicatief-additieve fragment van Lineaire Logica (MALL).
Unificatie van Klassiek en Constructief: De auteurs tonen aan dat klassieke bewijsvoorwaarden kunnen worden verkregen door een minimale restrictie toe te passen op intuïtionistische voorwaarden. Dit suggereert dat klassieke bewijzen constructieve inhoud hebben, maar minder informatie vereisen dan hun intuïtionistische tegenhangers.
Behandeling van $\bot$ : Ze bieden een elegante oplossing voor het probleem van valsheid in substructurale logica door $\bot$ te behandelen als een "vast atoom" dat deelneemt aan de basisregels, in plaats van het als een semantisch "nooit waar" te definiëren.
Analyse van Connectieven: Ze tonen aan dat de klassieke voorwaarden voor de par-connectief ( $\parr$ ) en de additieve conjunctie ( $\&$ ) direct uit hun standaardregels kunnen worden gelezen, terwijl andere connectieven een restrictie nodig hebben. Dit ondersteunt het idee dat $\parr$ een fundamenteel klassieke connectief is.

4. Resultaten

De auteurs bewijzen de geluidheid (soundness) en volledigheid (completeness) van hun voorgestelde semantiek ten opzichte van een natuurlijk deductiesysteem voor MALL.

Geluidheid (Theorema 4.2): Als een formule $\phi$ afleidbaar is in MALL ( $\Gamma \vdash_{MALL} \phi$ ), dan is deze geldig volgens de BeS-semantiek ( $\Gamma \Vdash \phi$ ).
Volledigheid (Theorema 5.4): Als een formule geldig is volgens de BeS-semantiek ( $\Gamma \Vdash \phi$ $Γ ⊩ ϕ$ ), dan bestaat er een MALL-bewijs voor deze afleiding.
- Voor het bewijs van volledigheid construeren de auteurs een simulatie-basis ( $U$ ). Deze basis bevat regels die de afleidingsregels van MALL nabootsen, maar waarbij alle formules zijn vervangen door unieke atomaire symbolen ( $p_\psi$ ).
- Een opmerkelijk gevolg (Corollary 5.5) is dat elke klassieke afleiding kan worden omgezet in een afleiding waarbij de eliminatieregels voor $\otimes$ , $\oplus$ , $0$ en $\parr$ alleen worden toegepast als de minor-premissen de vorm $\bot$ hebben. Dit is een puur semantisch bewijs van een bewijstheoretisch eigenschap.

5. Significatie en Conclusie

De studie heeft belangrijke implicaties voor de filosofie van logica en de theoretische informatica:

Kwaliteit vs. Kwantiteit van Constructiviteit: De resultaten suggereren dat het onderscheid tussen klassieke en constructieve bewijzen niet kwalitatief (wel/niet constructief) is, maar kwantitatief. Klassieke bewijzen vereisen minder informatie om tot stand te komen dan intuïtionistische bewijzen, maar behouden toch een zekere mate van constructiviteit. Dit verklaart waarom algoritmen kunnen worden geëxtraheerd uit klassieke bewijzen, zelfs met reductio ad absurdum.
Semantische Unificatie: Het werk toont aan dat het mogelijk is om semantische resultaten (zoals geluidheid) te bewijzen via syntactische middelen en omgekeerd, wat de kracht van PtS benadrukt.
Toekomstperspectief: Hoewel het artikel zich beperkt tot MALL, suggereren de auteurs dat hun methode uitbreidbaar is naar de volledige Lineaire Logica (inclusief exponentiële modaliteiten $!$ en $?$ ). Ze stellen semantische clausules voor deze modaliteiten op basis van hun huidige bevindingen, wat een rijke richting voor toekomstig onderzoek biedt.

Kortom, dit artikel levert een fundamentele bijdrage aan het begrijpen van klassieke logica door de lens van bewijstheorie, en positioneert Lineaire Logica als een brug tussen constructieve en klassieke redenering.