🔢 mathematics

Nested Sequents for Horn-Characterizable Quantified Modal Logics with Equality via Reachability Rules

Deze paper introduceert een nieuw, snijvrij systeem van geneste sequenten met bereikbaarheidsregels en grammatica-gebaseerde parameters dat voor het eerst een geluid en compleet bewijsstelsel biedt voor een brede klasse van gekwantificeerde modale logica's met gelijkheid, die semantisch worden gedefinieerd via modellen met zowel in- als buitendomeinen.

Oorspronkelijke auteurs: Tim S. Lyon, Eugenio Orlandelli

Gepubliceerd 2026-04-21

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tim S. Lyon, Eugenio Orlandelli

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 logica een enorme bibliotheek is, vol met boeken die vertellen hoe de wereld werkt. Sommige boeken beschrijven een vaste wereld waar alles altijd hetzelfde blijft (zoals wiskunde). Andere boeken beschrijven een veel dynamischere wereld, waar dingen kunnen veranderen, waar mensen kunnen reizen naar andere tijden of plaatsen, en waar sommige dingen misschien bestaan in de ene wereld maar niet in de andere. Dit noemen we modale logica.

Wanneer we ook nog eens gaan praten over "iemand" of "iets" (zoals "alle mensen" of "er bestaat een getal"), komen we in de kwantificerende modale logica. Dit is als het lezen van die boeken, maar dan met een extra complexe laag: we moeten niet alleen weten waar iets gebeurt, maar ook wie er in die specifieke wereld bestaat.

De auteurs van dit paper, Tim Lyon en Eugenio Orlandelli, hebben een nieuw en slimme manier bedacht om deze complexe boeken te analyseren en te controleren of ze logisch kloppen. Ze noemen hun methode "Nested Sequents" (Genesteelde Zinnen), maar laten we het een Lego-toren van logica noemen.

Hier is een simpele uitleg van wat ze hebben gedaan, met behulp van analogieën:

1. De Probleem: De "Vaste" Wereld

Stel je voor dat je een spelletje speelt waarbij je regels moet volgen. In de oude methoden om deze logica's te controleren, waren de regels vaak te stijf. Het was alsof je probeerde een spel te spelen waarbij je regels had die alleen werkten als iedereen in elke wereld precies dezelfde spullen had.
In de echte wereld (en in veel logica's) is dat niet zo. In de ene wereld (bijvoorbeeld "morgen") kunnen er meer mensen zijn dan vandaag (een groeiend domein), of juist minder (krimpend domein). De oude methoden faalden hier vaak op, of ze dwongen je om te doen alsof de wereld statisch was, wat niet eerlijk is.

2. De Oplossing: De Lego-toren met "Handelskaarten"

De auteurs bouwen een nieuw systeem op basis van Nested Sequents.

De Toren: Stel je een Lego-toren voor. De onderste laag is onze huidige wereld. De lagen daarboven zijn mogelijke toekomstige werelden.
De Handtekeningen (Signatures): Dit is het slimme deel. Bij elke laag van de toren hangen ze een lijstje met "namen" of "objecten" (zoals een paspoort). Dit noemen ze een signature.
- Als je een nieuwe wereld (een nieuwe Lego-laag) bouwt, kun je kijken naar het lijstje van de wereld eronder.
- Als de regel is "werelden kunnen groeien", dan mag je nieuwe namen toevoegen aan het lijstje van de nieuwe wereld.
- Als de regel is "werelden krimpen", dan mag je alleen namen houden die ook in de vorige wereld stonden.
- Dit zorgt ervoor dat het systeem precies weet wie er in welke wereld mag bestaan.

3. De Magische "Reisregels" (Reachability Rules)

Dit is het meest innovatieve stukje van het paper. Stel je voor dat je in die Lego-toren een boodschap wilt sturen van de bovenste laag naar de onderste, of andersom.

In de oude systemen was het moeilijk om te zeggen: "Stuur deze boodschap alleen door als je een reeks van 3 stappen naar rechts hebt gedaan."
De auteurs gebruiken Reisregels die werken met een soort taal of code (een grammatica).
Ze zeggen: "Je mag een regel toepassen als je een pad kunt vinden dat lijkt op de code R-R-R (drie stappen vooruit) of R-terug-R."
Het is alsof je een GPS hebt die precies weet welke routes (paden) tussen de werelden geldig zijn. Als de GPS zegt "Ja, deze route bestaat volgens de regels van deze wereld", dan mag je de logica-regel toepassen.

4. Waarom is dit geweldig?

Geen "Goochelen" meer: Vroeger moest je voor elke soort wereld (groot, klein, statisch) een heel nieuw, complex systeem bouwen. Met dit nieuwe systeem heb je één basis-toren en één set GPS-regels. Je verandert alleen de instellingen van de GPS (de grammatica), en plotseling werkt het systeem voor een heel ander type wereld.
Zonder "Knippen": In de logica-wereld is het heel moeilijk om te bewijzen dat je geen "cheats" (zoals het knippen en plakken van bewijzen, wat ze cut noemen) gebruikt. De auteurs bewijzen dat hun toren altijd eerlijk en logisch is, zonder trucs.
De "Barcan" Valstrik: Ze ontdekten iets interessants: hun standaard-regel voor "voor iedereen" (het universele kwantificator) werkt zo goed, dat hij automatisch zorgt dat de "wereld van mogelijke objecten" constant blijft. Dit is een diep inzicht: hun systeem is zo natuurlijk gebouwd dat het bijna onmogelijk is om een wereld te maken waar de "potentiële" mensen veranderen, tenzij je de regels specifiek aanpast.

Samenvatting

Kortom, Lyon en Orlandelli hebben een universele bouwset bedacht voor logische systemen die gaan over mensen, dingen en mogelijke werelden.

Ze gebruiken Lego-torens om de wereldstructuur te bouwen.
Ze gebruiken lijstjes met namen om te bepalen wie er bestaat.
Ze gebruiken GPS-achtige regels om te bepalen hoe je van de ene wereld naar de andere mag reizen.

Dit maakt het voor computers en wiskundigen veel makkelijker om te controleren of complexe redeneringen kloppen, zonder dat ze voor elke nieuwe situatie een heel nieuw systeem hoeven uit te vinden. Het is alsof ze een multitool hebben uitgevonden voor de logica, in plaats van een hele gereedschapskist met één tool per klus.

Probleemstelling

De auteurs richten zich op de uitdaging om analytische bewijssystemen (zonder cut) te ontwikkelen voor een brede klasse van kwantificerende modale logieken (QMLs) die gelijkheid bevatten. Hoewel sequentkalkulen voor propositional modale logieken goed bestudeerd zijn, blijft de literatuur voor kwantificerende systemen beperkt.

De specifieke problemen die worden aangepakt zijn:

Complexiteit van domeinen: QMLs worden vaak gedefinieerd via relationele modellen met zowel een innerlijke domein (bestaande objecten) als een buitenste domein (mogelijke objecten). Het modelleren van verschillende domeincondities (zoals toenemend, afnemend, constant, leeg of variërend) is lastig met standaard inferentieregels.
Beperkingen van bestaande systemen:
- Gekoppelde sequenten (Labeled sequents): Hoewel modulair, introduceren ze vaak redundante syntactische structuren en hebben ze geen directe formule-interpretatie, wat de bewijsgrootte onnodig vergroot.
- Standaard regels voor kwantoren: Het toevoegen van standaard regels voor de universele kwantor aan een geneste sequentstelsel leidt onbedoeld tot de bewijsbaarheid van de Barcan-formule (BF) en de converse Barcan-formule (CBF). Dit forceert het systeem om alleen QMLs met constante domeinen te modelleren, waardoor logieken met variërende domeinen niet correct kunnen worden gevangen.
Gebrek aan uniformiteit: Bestaande benaderingen vereisen vaak specifieke, ad-hoc structurele regels voor elke specifieke frame-conditie (zoals transitiviteit of symmetrie), wat de modulariteit van het bewijssysteem ondermijnt.

Methodologie

De auteurs introduceren een nieuw type geneste sequentstelsels (nested sequent systems) die gebruikmaken van twee kernconcepten om de bovenstaande problemen op te lossen:

Signatures (Handtekeningen):
- Geneste sequenten worden uitgebreid met signatures, gedefinieerd als multisets van termen.
- Deze signatures coderen lokaal een bestaanspredikaat ( $E$ ) en beperken hoe kwantoren worden geïntroduceerd. Dit stelt het systeem in staat om onderscheid te maken tussen objecten die in een specifiek wereld-domein bestaan en die welke niet, waardoor logieken met toenemende, afnemende of variërende domeinen kunnen worden gemodelleerd.
Reachability Rules (Bereikbaarheidsregels):
- Dit is de meest innovatieve component. De auteurs gebruiken inferentieregels die worden geparametriseerd door formele grammata (specifiek semi-Thue systemen of $\Sigma$ -systemen).
- Deze regels opereren door formules of termen te propageren of te consumeren langs specifieke paden binnen de boomstructuur van een geneste sequent.
- De paden worden gecodeerd als strings gegenereerd door de parameteriserende grammatica. Afhankelijk van de gekozen grammatica (bijv. $S_4$ voor gerichte bereikbaarheid of $S_5$ voor ongerichte bereikbaarheid) en de toegepaste productieregels, kunnen verschillende frame-condities (zoals serialiteit, transitiviteit, symmetrie, Euclidische eigenschappen) en domeincondities (toenemend/afnemend) uniform worden gevangen.
Semantisch Model:
- De logieken worden gedefinieerd op basis van normale modellen (volgens Corsi) met een constant buitenste domein en variërende innerlijke domeinen. De auteurs tonen aan dat hun systeem natuurlijk leidt tot constante buitenste domeinen als gevolg van de structuur van de universele kwantorregels.

Belangrijkste Bijdragen

Eerste Sound en Complete Systemen: Dit is het eerste werk dat sound en complete, cut-vrije geneste sequentstelsels biedt voor QMLs die semantisch worden gekarakteriseerd door modellen met zowel innerlijke als buitenste domeinen.
Uniforme Behandeling via Reachability Rules: In plaats van aparte regels voor elke frame-conditie, gebruiken de auteurs reachability rules die werken met een parameteriserende grammatica. Dit maakt het systeem modulair: door de grammatica te wijzigen, verandert het bewijssysteem om een andere logica te dekken zonder de basisregels te hoeven herschrijven.
Integratie van de Extended Barcan Rule (EBR): De auteurs observeren dat de standaard regel voor de universele kwantor in hun systeem de Extended Barcan Rule (EBR) omvat. Dit betekent dat hun systemen per definitie QMLs met constante buitenste domeinen modelleren. Ze tonen aan dat dit een inherente eigenschap is van de geneste sequent-formulering voor deze klasse van logieken.
De "Shift"-regel: Een nieuwe structurele regel, de shift-rule ($sft(C)$), wordt geïntroduceerd. Deze regel is essentieel voor het bewijs van cut-eliminatie en vat alle generaliseerde padcondities samen in één uniforme structuur.
Vereenvoudiging: Het systeem maakt gebruik van éénzijdige geneste sequenten in negatieve normale vorm, wat de notatie vereenvoudigt ten opzichte van eerdere werken.

Resultaten en Bewijstheoretische Eigenschappen

De auteurs bewijzen een reeks fundamentele bewijstheoretische eigenschappen voor hun systemen $NQ^{\circ}_{=.K}(C)$ :

Soundness en Completeness: Het systeem is sound en compleet ten opzichte van de gedefinieerde semantiek. Voor compleetheid wordt een methode ontwikkeld om tegenmodellen te extraheren uit gefaalde bewijspogingen (via een Kripke-achtige constructie).
Invertibiliteit: Alle regels in het systeem zijn hoogtebehoudend inverteerbaar (height-preserving invertible). Dit betekent dat als de conclusie bewijsbaar is, de premissen ook bewijsbaar zijn zonder de bewijshoogte te vergroten. Dit is cruciaal voor de constructie van tegenmodellen.
Admissibiliteit van Structurele Regels: Verschillende structurele regels worden bewezen als hoogtebehoudend admissibel (hp-admissible), waaronder:
- Substitutie ( $s(t/x)$ )
- Verzwakking (Weakening) en Contractie (Contraction)
- De nieuwe shift-rule ($sft(C)$), die essentieel is voor het uniform behandelen van padcondities.
Cut-eliminatie: Er wordt een niet-triviale syntactische cut-eliminatie stelling bewezen. Het bewijs is uniek omdat het uniform is voor de hele klasse van QMLs; er zijn geen ad-hoc strategieën nodig voor specifieke logieken. De cut-eliminatie leunt zwaar op de admissibiliteit van de shift-rule.
Eigenschappen van Gelijkheid: Er worden regels voor symmetrie, transitiviteit en vervanging van gelijkheid bewezen als admissibel.

Betekenis en Toekomstperspectief

De betekenis van dit werk ligt in het overbruggen van de kloof tussen de elegantie en computational efficiency van geneste sequenten en de complexiteit van kwantificerende modale logieken met gelijkheid.

Efficiëntie: Door het vermijden van redundante structuren (zoals bij gelabelde sequenten) en het gebruik van compacte bewijzen, biedt dit systeem een efficiëntere basis voor geautomatiseerd redeneren.
Modulariteit: De gebruikte grammatica-methode voor reachability regels biedt een schaalbare manier om nieuwe logieken toe te voegen zonder het bewijssysteem fundamenteel te veranderen.
Beperking en Richting: De auteurs erkennen dat hun huidige systeem beperkt is tot logieken met constante buitenste domeinen vanwege de EBR. Toekomstig werk richt zich op het ontwikkelen van alternatieve regels voor de universele kwantor om ook logieken met niet-constante buitenste domeinen te kunnen modelleren, evenals het uitbreiden naar niet-rigide termen en counterpart-theoretische semantiek.

Kortom, dit artikel levert een fundamentele bijdrage aan de bewijstheorie van niet-klassieke logieken door een krachtig, uniform en analytisch raamwerk te bieden voor een breed scala aan kwantificerende modale systemen.