Algemeen frame - General frame

In de logica zijn algemene frames (of gewoon frames ) Kripke-frames met een aanvullende structuur, die worden gebruikt om modale en intermediaire logica's te modelleren . De algemene kadersemantiek combineert de belangrijkste deugden van Kripke-semantiek en algebraïsche semantiek : het deelt het transparante geometrische inzicht van de eerste en de robuuste volledigheid van de laatste.

Definitie

Een modaal algemeen frame is een drievoudig , waarbij een Kripke-frame is (dat wil zeggen, R is een binaire relatie op de verzameling F ), en V is een verzameling subsets van F die is gesloten onder het volgende: ${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$${\ displaystyle \ langle F, R \ rangle}$

• de Booleaanse bewerkingen van (binaire) intersectie , vereniging en complement ,
• de operatie , gedefinieerd door . ${\ displaystyle \ Box}$${\ Displaystyle \ Box A = \ {x \ in F; \, \ forall y \ in F \, (x \, R \, y \ to y \ in A) \}}$

Ze zijn dus een speciaal geval van velden van sets met aanvullende structuur . Het doel van V is om de toegestane waarderingen in het frame te beperken: een model gebaseerd op het Kripke frame is toelaatbaar in het algemene frame F , indien ${\ displaystyle \ langle F, R, \ Vdash \ rangle}$${\ displaystyle \ langle F, R \ rangle}$

${\ displaystyle \ {x \ in F; \, x \ Vdash p \} \ in V}$ voor elke propositionele variabele p .

De sluitingsvoorwaarden op V zorgen er dan voor dat bij V hoort voor elke formule A (niet alleen een variabele). ${\ displaystyle \ {x \ in F; \, x \ Vdash A \}}$

Een formule A is geldig in F , indien voor alle toelaatbare waarderingen , en alle punten . Een normale modale logica L geldt in het frame F , indien alle axioma's (of op equivalente wijze alle stellingen ) van L gelden in F . In dit geval noemen we F een L - frame . ${\ displaystyle x \ Vdash A}$${\ displaystyle \ Vdash}$${\ displaystyle x \ in F}$

Een Kripke gestel kan worden geïdentificeerd met een algemene kader waarin alle waarderingen ontvankelijk: dwz , waarbij staat voor de ingestelde vermogen van F . ${\ displaystyle \ langle F, R \ rangle}$${\ displaystyle \ langle F, R, {\ mathcal {P}} (F) \ rangle}$${\ displaystyle {\ mathcal {P}} (F)}$

Soorten frames

In het algemeen zijn algemene monturen nauwelijks meer dan een mooie naam voor Kripke- modellen ; in het bijzonder gaat de overeenkomst tussen modale axioma's en eigenschappen over de toegankelijkheidsrelatie verloren. Dit kan worden verholpen door aanvullende voorwaarden te stellen aan de set van toelaatbare taxaties.

Een frame wordt genoemd ${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$

• gedifferentieerd , indien impliciet , ${\ Displaystyle \ forall A \ in V \, (x \ in A \ Leftrightarrow y \ in A)}$${\ displaystyle x = y}$
• strak , als impliceert , ${\ Displaystyle \ forall A \ in V \, (x \ in \ Box A \ Rightarrow y \ in A)}$${\ displaystyle x \, R \, y}$
• compact , als elke subset van V met de eigenschap eindige intersectie een niet-lege intersectie heeft,
• atomair , als V alle singletons bevat,
• verfijnd , als het gedifferentieerd en strak is,
• beschrijvend , als het verfijnd en compact is.

Kripke-monturen zijn verfijnd en atomair. Oneindige Kripke-frames zijn echter nooit compact. Elk eindig gedifferentieerd of atomair frame is een Kripke-frame.

Beschrijvende frames zijn de belangrijkste klasse van frames vanwege de dualiteitstheorie (zie hieronder). Verfijnde frames zijn handig als algemene generalisatie van beschrijvende en Kripke-frames.

Operaties en morfismen op frames

Elk Kripke-model induceert het algemene frame , waarbij V wordt gedefinieerd als ${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$ ${\ displaystyle \ langle F, R, V \ rangle}$

${\ displaystyle V = {\ big \ {} \ {x \ in F; \, x \ Vdash A \}; \, A {\ hbox {is een formule}} {\ big \}}.}$

De fundamentele waarheidsbehoudende bewerkingen van gegenereerde subframes, p-morfische afbeeldingen en onsamenhangende verbanden van Kripke-frames hebben analogen op algemene frames. Een frame is een gegenereerd subframe van een frame , als het Kripke-frame een gegenereerd subframe is van het Kripke-frame (dat wil zeggen, een subset is van naar boven gesloten onder , en ), en ${\ displaystyle \ mathbf {G} = \ langle G, S, W \ rangle}$${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$${\ displaystyle \ langle G, S \ rangle}$${\ displaystyle \ langle F, R \ rangle}$${\ displaystyle G}$${\ displaystyle F}$${\ displaystyle R}$${\ displaystyle S = R \ cap G \ maal G}$

${\ displaystyle W = \ {A \ cap G; \, A \ in V \}.}$

Een p-morfisme (of begrensd morfisme ) is een functie van F tot G die een p-morfisme van Kripke frames en , en voldoet aan de extra beperking ${\ displaystyle f \ colon \ mathbf {F} \ to \ mathbf {G}}$${\ displaystyle \ langle F, R \ rangle}$${\ displaystyle \ langle G, S \ rangle}$

${\ displaystyle f ^ {- 1} [A] \ in V}$ voor elk . ${\ displaystyle A \ in W}$

De disjuncte vereniging van een geïndexeerde reeks frames , is het frame , waarbij F de disjuncte vereniging van , R is de vereniging van en ${\ displaystyle \ mathbf {F} _ {i} = \ langle F_ {i}, R_ {i}, V_ {i} \ rangle}$${\ displaystyle i \ in I}$${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$${\ displaystyle \ {F_ {i}; \, i \ in I \}}$${\ displaystyle \ {R_ {i}; \, i \ in I \}}$

${\ Displaystyle V = \ {A \ subseteq F; \, \ forall i \ in I \, (A \ cap F_ {i} \ in V_ {i}) \}.}$

De verfijning van een frame is een verfijnd frame dat als volgt wordt gedefinieerd. We beschouwen de equivalentierelatie${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$${\ displaystyle \ mathbf {G} = \ langle G, S, W \ rangle}$

${\ Displaystyle x \ sim y \ iff \ forall A \ in V \, (x \ in A \ Leftrightarrow y \ in A),}$

en laten we de reeks equivalentieklassen zijn van . Dan zetten we ${\ displaystyle G = F / {\ sim}}$${\ displaystyle \ sim}$

${\ Displaystyle \ langle x / {\ sim}, y / {\ sim} \ rangle \ in S \ iff \ forall A \ in V \, (x \ in \ Box A \ Rightarrow y \ in A),}$

${\ displaystyle A / {\ sim} \ in W \ iff A \ in V.}$

Volledigheid

In tegenstelling tot Kripke-frames is elke normale modale logica L compleet met betrekking tot een klasse van algemene frames. Dit is een gevolg van het feit dat L compleet is met betrekking tot een klasse van Kripke-modellen : aangezien L gesloten is onder substitutie, is het algemene frame dat wordt geïnduceerd door een L- frame . Bovendien is elke logische L compleet met betrekking tot een enkel beschrijvend frame. Inderdaad, L is compleet met betrekking tot zijn canonieke model, en het algemene frame dat wordt geïnduceerd door het canonieke model (het canonieke frame van L genoemd ) is beschrijvend. ${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$

Dualiteit van Jónsson-Tarski

De Rieger – Nishimura ladder: een 1-universeel intuïtionistisch Kripke-frame.

Zijn dubbele Heyting-algebra, het Rieger-Nishimura-rooster. Het is de gratis Heyting-algebra over 1 generator.

Algemene kaders houden nauw verband met modale algebra's . Laat een algemeen kader zijn. De verzameling V is gesloten onder Booleaanse bewerkingen, daarom is het een subalgebra van de machtsverzameling Booleaanse algebra . Het draagt ook een extra unaire operatie . De gecombineerde structuur is een modale algebra, die de dubbele algebra van F wordt genoemd en wordt aangeduid met . ${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$ ${\ displaystyle \ langle {\ mathcal {P}} (F), \ cap, \ cup, - \ rangle}$${\ displaystyle \ Box}$${\ displaystyle \ langle V, \ cap, \ cup, -, \ Box \ rangle}$${\ displaystyle \ mathbf {F} ^ {+}}$

In de tegenovergestelde richting is het mogelijk om het dubbele frame te construeren voor elke modale algebra . De Booleaanse algebra een steen ruimte , waarvan de onderliggende set F is de verzameling van alle ultrafilters van A . De set V van toelaatbare waarderingen in bestaat uit de clopen subsets van F , en de toegankelijkheidsrelatie R wordt gedefinieerd door ${\ displaystyle \ mathbf {A} _ {+} = \ langle F, R, V \ rangle}$${\ displaystyle \ mathbf {A} = \ langle A, \ wedge, \ vee, -, \ Box \ rangle}$${\ displaystyle \ langle A, \ wedge, \ vee, - \ rangle}$${\ displaystyle \ mathbf {A} _ {+}}$

${\ Displaystyle x \, R \, y \ iff \ forall a \ in A \, (\ Box a \ in x \ Rightarrow a \ in y)}$

voor alle ultrafilters x en y .

Een frame en zijn duaal valideren dezelfde formules, vandaar dat de algemene framesemantiek en de algebraïsche semantiek in zekere zin equivalent zijn. De dubbele duaal van elke modale algebra is isomorf met zichzelf. Dit geldt in het algemeen niet voor dubbele duals van frames, aangezien de duale van elke algebra beschrijvend is. In feite is een frame alleen maar beschrijvend als het isomorf is met zijn dubbele duaal . ${\ displaystyle (\ mathbf {A} _ {+}) ^ {+}}$${\ displaystyle \ mathbf {A}}$${\ displaystyle \ mathbf {F}}$${\ displaystyle (\ mathbf {F} ^ {+}) _ {+}}$

Het is ook mogelijk om duals van p-morfismen aan de ene kant en modale algebra-homomorfismen aan de andere kant te definiëren. Op deze manier worden de operators en worden een paar contravariante functoren tussen de categorie van algemene frames en de categorie van modale algebra's. Deze functoren zorgen voor een dualiteit ( Jónsson-Tarski dualiteit genoemd naar Bjarni Jónsson en Alfred Tarski ) tussen de categorieën van beschrijvende frames en modale algebra's. Dit is een speciaal geval van een meer algemene dualiteit tussen complexe algebra's en velden van verzamelingen op relationele structuren . ${\ displaystyle (\ cdot) ^ {+}}$${\ displaystyle (\ cdot) _ {+}}$

Intuïtionistische frames

De framesemantiek voor intuïtionistische en intermediaire logica kan parallel aan de semantiek voor modale logica worden ontwikkeld. Een intuïtionistisch algemeen frame is een drievoudig , waarbij een gedeeltelijke bestelling op F is , en V is een set van bovenste subsets ( kegels ) van F die de lege set bevat en is gesloten onder ${\ displaystyle \ langle F, \ leq, V \ rangle}$${\ displaystyle \ leq}$

• kruising en vereniging,
• de operatie . ${\ displaystyle A \ to B = \ Box (-A \ cup B)}$

Validiteit en andere concepten worden vervolgens op dezelfde manier geïntroduceerd als modale kaders, met enkele wijzigingen die nodig zijn om rekening te houden met de zwakkere sluitingseigenschappen van de reeks toelaatbare waarderingen. In het bijzonder wordt een intuïtionistisch frame genoemd ${\ displaystyle \ mathbf {F} = \ langle F, \ leq, V \ rangle}$

• strak , als impliceert , ${\ Displaystyle \ forall A \ in V \, (x \ in A \ Leftrightarrow y \ in A)}$${\ displaystyle x \ leq y}$
• compact , als elke subset van met de eigenschap eindige intersectie een niet-lege intersectie heeft. ${\ Displaystyle V \ cup \ {FA; \, A \ in V \}}$

Strakke intuïtionistische kaders worden automatisch gedifferentieerd en dus verfijnd.

Het dubbele van een intuïtionistisch frame is de Heyting-algebra . De duale van een Heyting-algebra is het intuïtionistische frame , waarbij F de verzameling van alle primaire filters van A is , de ordening is opname en V bestaat uit alle subsets van F van de vorm ${\ displaystyle \ mathbf {F} = \ langle F, \ leq, V \ rangle}$ ${\ displaystyle \ mathbf {F} ^ {+} = \ langle V, \ cap, \ cup, \ to, \ emptyset \ rangle}$${\ displaystyle \ mathbf {A} = \ langle A, \ wedge, \ vee, \ to, 0 \ rangle}$${\ displaystyle \ mathbf {A} _ {+} = \ langle F, \ leq, V \ rangle}$${\ displaystyle \ leq}$

${\ displaystyle \ {x \ in F; \, a \ in x \},}$

waar . Zoals in het modale geval, en zijn een paar contravariante functoren, die de categorie van Heyting-algebra's tweevoudig equivalent maken aan de categorie van beschrijvende intuïtionistische kaders. ${\ displaystyle a \ in A}$${\ displaystyle (\ cdot) ^ {+}}$${\ displaystyle (\ cdot) _ {+}}$

Het is mogelijk om intuïtionistische algemene frames te construeren uit transitieve reflexieve modale frames en vice versa, zie modale metgezel .

Referenties

• Alexander Chagrov en Michael Zakharyaschev, Modal Logic , vol. 35 van Oxford Logic Guides, Oxford University Press, 1997.
• Patrick Blackburn, Maarten de Rijke en Yde Venema, Modal Logic , vol. 53 van Cambridge Tracts in Theorhetic Computer Science, Cambridge University Press, 2001.