Generel ramme - General frame

I logik er generelle rammer (eller simpelthen rammer ) Kripke-rammer med en ekstra struktur, der bruges til at modellere modal og mellemliggende logik. Den generelle rammesemantik kombinerer de vigtigste dyder ved Kripke-semantik og algebraisk semantik : den deler den gennemsigtige geometriske indsigt i førstnævnte og robust fuldstændighed af sidstnævnte.

Definition

En generel modal ramme er en tredobbelt , hvor er en Kripke-ramme (dvs. R er en binær relation på sættet F ), og V er et sæt undergrupper af F, der er lukket under følgende: ${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$${\ displaystyle \ langle F, R \ rangle}$

• de boolske operationer i (binært) kryds , union og komplement ,
• operationen , defineret af . ${\ displaystyle \ Box}$${\ displaystyle \ Box A = \ {x \ i F; \, \ forall y \ i F \, (x \, R \, y \ til y \ i A) \}}$

De er således et specielt tilfælde af felter af sæt med yderligere struktur . Formålet med V er at begrænse de tilladte værdiansættelser i rammen: en model baseret på Kripke-rammen er tilladt i den generelle ramme F , hvis ${\ displaystyle \ langle F, R, \ Vdash \ rangle}$${\ displaystyle \ langle F, R \ rangle}$

${\ displaystyle \ {x \ i F; \, x \ Vdash p \} \ i V}$ for hver propositionsvariabel s .

Lukningsbetingelserne på V sikrer derefter, at det tilhører V for hver formel A (ikke kun en variabel). ${\ displaystyle \ {x \ i F; \, x \ Vdash A \}}$

En formel A er gyldig i F , hvis for alle tilladte værdiansættelser og alle punkter . En normal modallogik L er gyldig i rammen F , hvis alle aksiomer (eller ækvivalent, alle teoremer ) af L er gyldige i F . I dette tilfælde kalder vi F for en L - ramme . ${\ displaystyle x \ Vdash A}$${\ displaystyle \ Vdash}$${\ displaystyle x \ i F}$

En Kripke ramme kan identificeres med en generel ramme, i hvilken alle vurderingerne kan behandles: dvs. , hvor betegner indstillede effekt af F . ${\ displaystyle \ langle F, R \ rangle}$${\ displaystyle \ langle F, R, {\ mathcal {P}} (F) \ rangle}$${\ displaystyle {\ mathcal {P}} (F)}$

Typer af rammer

Generelt er generelle rammer næppe mere end et fancy navn for Kripke- modeller ; især mistes korrespondancen mellem modale aksiomer og egenskaber på tilgængelighedsrelationen. Dette kan afhjælpes ved at indføre yderligere betingelser for sættet af tilladte værdiansættelser.

En ramme kaldes ${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$

• differentieret , hvis det antyder , ${\ displaystyle \ forall A \ i V \, (x \ i A \ Leftrightarrow y \ i A)}$${\ displaystyle x = y}$
• stramt , hvis det antyder , ${\ displaystyle \ forall A \ i V \, (x \ in \ Box A \ Rightarrow y \ i A)}$${\ displaystyle x \, R \, y}$
• kompakt , hvis hver delmængde af V med den endelige skæringsegenskab har et ikke-tomt kryds,
• atom , hvis V indeholder alle singletoner,
• raffineret , hvis det er differentieret og stramt,
• beskrivende , hvis den er raffineret og kompakt.

Kripke-rammer er raffinerede og atomare. Uendelige Kripke-rammer er dog aldrig kompakte. Hver endelig differentieret eller atomær ramme er en Kripke-ramme.

Beskrivende rammer er den vigtigste klasse af rammer på grund af dualitetsteorien (se nedenfor). Raffinerede rammer er nyttige som en almindelig generalisering af beskrivende og Kripke-rammer.

Funktioner og morfismer på rammer

Hver Kripke-model inducerer den generelle ramme , hvor V er defineret som ${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$ ${\ displaystyle \ langle F, R, V \ rangle}$

${\ displaystyle V = {\ big \ {} \ {x \ i F; \, x \ Vdash A \}; \, A {\ hbox {er en formel}} {\ big \}}.}$

De grundlæggende sandhedsbevarende operationer af genererede underrammer, p-morfiske billeder og uensartede fagforeninger af Kripke-rammer har analoger til generelle rammer. En ramme er en genereret underramme af en ramme , hvis Kripke-rammen er en genereret underramme af Kripke-rammen (dvs. er en delmængde af lukket opad under , og ), og ${\ 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 \ gange G}$

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

En p-morphism (eller afgrænset morphism ) er en funktion fra F til G , der er et p-morphism af Kripke rammer og , og opfylder yderligere begrænsning ${\ displaystyle f \ colon \ mathbf {F} \ to \ mathbf {G}}$${\ displaystyle \ langle F, R \ rangle}$${\ displaystyle \ langle G, S \ rangle}$

${\ displaystyle f ^ {- 1} [A] \ i V}$ for hver . ${\ displaystyle A \ in W}$

Den usammenhængende forening af et indekseret sæt rammer , er rammen , hvor F er den usammenhængende forening af , R er foreningen af , og ${\ displaystyle \ mathbf {F} _ {i} = \ langle F_ {i}, R_ {i}, V_ {i} \ rangle}$${\ displaystyle i \ i I}$${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$${\ displaystyle \ {F_ {i}; \, i \ i I \}}$${\ displaystyle \ {R_ {i}; \, i \ i I \}}$

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

Den forfining af en ramme er en raffineret ramme defineret som følger. Vi overvejer ækvivalensforholdet${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$${\ displaystyle \ mathbf {G} = \ langle G, S, W \ rangle}$

${\ displaystyle x \ sim y \ iff \ forall A \ i V \, (x \ i A \ Leftrightarrow y \ i A),}$

og lad være sættet af ækvivalensklasser af . Så sætter vi ${\ 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} \ i W \ iff A \ i V.}$

Fuldstændighed

I modsætning til Kripke-rammer er enhver normal modalogik L komplet med hensyn til en klasse af generelle rammer. Dette er en konsekvens af det faktum, at L er komplet med hensyn til en klasse af Kripke-modeller : da L er lukket under substitution, er den generelle ramme induceret af en L- ramme . Desuden er hver logik L komplet med hensyn til en enkelt beskrivende ramme. Faktisk er L komplet med hensyn til sin kanoniske model, og den generelle ramme induceret af den kanoniske model (kaldet den kanoniske ramme af L ) er beskrivende. ${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$

Jónsson – Tarski dualitet

Rieger – Nishimura stigen: en 1-universal intuitionistisk Kripke ramme.

Dens dobbelte Heyting-algebra, gitteret Rieger – Nishimura. Det er den gratis Heyting-algebra over 1 generator.

Generelle rammer har tæt forbindelse til modale algebraer . Lad være en generel ramme. Sættet V er lukket under boolske operationer, derfor er det en subalgebra af det boolske algebra . Det udfører også en ekstra unarisk operation . Den kombinerede struktur er en modal algebra, der kaldes den dobbelte algebra for F , og betegnes med . ${\ 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} ^ {+}}$

I den modsatte retning er det muligt at konstruere den dobbelte ramme til enhver modal algebra . Den boolsk algebra har en sten plads , hvis underliggende sæt F er mængden af alle ultrafiltrene af A . Sættet V af tilladte værdiansættelser består af de åbne delmængder af F , og tilgængelighedsrelationen R er defineret af ${\ 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 \ i A \, (\ Box a \ i x \ Rightarrow a \ in y)}$

for alle ultrafilter x og y .

En ramme og dens dobbelte validering af de samme formler, derfor er den generelle rammesemantik og algebraisk semantik på en måde ækvivalent. Den dobbelte dobbelte af enhver modal algebra er isomorf for sig selv. Dette gælder generelt ikke for dobbeltdualer af rammer, da dobbelt for hver algebra er beskrivende. Faktisk er en ramme beskrivende, hvis og kun hvis den er isomorf til sin dobbelte dobbelte . ${\ displaystyle (\ mathbf {A} _ {+}) ^ {+}}$${\ displaystyle \ mathbf {A}}$${\ displaystyle \ mathbf {F}}$${\ displaystyle (\ mathbf {F} ^ {+}) _ {+}}$

Det er også muligt at definere dualer af p-morfismer på den ene side og modal algebra homomorfismer på den anden side. På denne måde operatørerne og bliver et par kontravariant funktioner mellem kategorien af generelle rammer og kategorien af ​​modale algebraer. Disse funktioner giver en dualitet (kaldet Jónsson-Tarski-dualitet efter Bjarni Jónsson og Alfred Tarski ) mellem kategorierne af beskrivende rammer og modale algebraer. Dette er et specielt tilfælde af en mere generel dualitet mellem komplekse algebraer og sæt af felter på relationelle strukturer . ${\ displaystyle (\ cdot) ^ {+}}$${\ displaystyle (\ cdot) _ {+}}$

Intuitionistiske rammer

Rammesemantikken til intuitionistisk og mellemlogik kan udvikles parallelt med semantikken til modalogik. En intuitionistisk generel ramme er en tredobbelt , hvor der er en delvis rækkefølge på F , og V er et sæt af øvre delmængder ( kegler ) af F, der indeholder det tomme sæt, og er lukket under ${\ displaystyle \ langle F, \ leq, V \ rangle}$${\ displaystyle \ leq}$

• kryds og union,
• operationen . ${\ displaystyle A \ til B = \ Box (-A \ cup B)}$

Gyldighed og andre koncepter introduceres derefter på samme måde som modale rammer, med nogle få ændringer nødvendige for at imødekomme de svagere lukkeegenskaber for sættet af tilladte værdiansættelser. Især kaldes en intuitionistisk ramme ${\ displaystyle \ mathbf {F} = \ langle F, \ leq, V \ rangle}$

• stramt , hvis det antyder , ${\ displaystyle \ forall A \ i V \, (x \ i A \ Leftrightarrow y \ i A)}$${\ displaystyle x \ leq y}$
• kompakt , hvis hver delmængde af med den endelige skæringsegenskab har et ikke-tomt kryds. ${\ displaystyle V \ cup \ {FA; \, A \ in V \}}$

Stramme intuitionistiske rammer differentieres automatisk og dermed raffineres.

Det dobbelte af en intuitionistisk ramme er Heyting-algebraen . Det dobbelte af en Heyting-algebra er den intuitionistiske ramme , hvor F er sættet med alle primære filtre af A , rækkefølgen er inkludering , og V består af alle delmængder af F af formen ${\ 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 \ i F; \, a \ i x \},}$

hvor . Som i det modale tilfælde, og er et par kontravariant funktioner, der gør kategorien af ​​Heyting algebraer svarende til kategorien af ​​beskrivende intuitionistiske rammer. ${\ displaystyle a \ i A}$${\ displaystyle (\ cdot) ^ {+}}$${\ displaystyle (\ cdot) _ {+}}$

Det er muligt at konstruere intuitionistiske generelle rammer fra transitive refleksive modale rammer og omvendt, se modal ledsager .

Referencer

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