Allmän ram - General frame

I logik är allmänna ramar (eller helt enkelt ramar ) Kripke-ramar med en extra struktur, som används för att modellera modal och mellanliggande logik. Den allmänna ramsemantiken kombinerar de viktigaste dygderna med Kripkes semantik och algebraisk semantik : den delar den transparenta geometriska insikten om den förra och den robusta fullständigheten hos den senare.

Definition

En allmän modal ram är en trippel , där är en Kripke-ram (dvs. R är en binär relation på uppsättningen F ), och V är en uppsättning underuppsättningar av F som stängs under följande: ${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$${\ displaystyle \ langle F, R \ rangle}$

• de booleska operationerna i (binär) korsning , union och komplement ,
• operationen , definierad av . ${\ displaystyle \ Box}$${\ displaystyle \ Box A = \ {x \ i F; \, \ forall y \ i F \, (x \, R \, y \ till y \ i A) \}}$

De är alltså ett speciellt fall av uppsättningsfält med ytterligare struktur . Syftet med V är att begränsa de tillåtna värderingarna i ramen: en modell baserad på Kripke-ramen är tillåten i den allmänna ramen F , om ${\ displaystyle \ langle F, R, \ Vdash \ rangle}$${\ displaystyle \ langle F, R \ rangle}$

${\ displaystyle \ {x \ i F; \, x \ Vdash p \} \ i V}$ för varje förslagsvariabel s .

Stängningsförhållandena på V säkerställer sedan att det tillhör V för varje formel A (inte bara en variabel). ${\ displaystyle \ {x \ i F; \, x \ Vdash A \}}$

En formel A är giltig i F , om för alla tillåtna värderingar , och alla poäng . En normal modal logik L är giltigt i ramen F , om alla axiom (eller ekvivalent, alla satser ) av L gäller i F . I det här fallet kallar vi F för en L - ram . ${\ displaystyle x \ Vdash A}$${\ displaystyle \ Vdash}$${\ displaystyle x \ i F}$

En Kripke ram kan identifieras med en allmän ram i vilken alla värderingarna är tillåtlig: dvs , där betecknar effekt uppsättning av F . ${\ displaystyle \ langle F, R \ rangle}$${\ displaystyle \ langle F, R, {\ mathcal {P}} (F) \ rangle}$${\ displaystyle {\ mathcal {P}} (F)}$

Typer av ramar

I allmänhet är generella ramar knappast mer än ett snyggt namn för Kripke- modeller ; i synnerhet går korrespondensen mellan modala axiomer till egenskaper på tillgänglighetsrelationen förlorad. Detta kan åtgärdas genom att införa ytterligare villkor för uppsättningen tillåtna värderingar.

En ram kallas ${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$

• differentierad , om det antyder , ${\ displaystyle \ forall A \ i V \, (x \ i A \ Leftrightarrow y \ i A)}$${\ displaystyle x = y}$
• tätt , om det antyder , ${\ displaystyle \ forall A \ in V \, (x \ in \ Box A \ Rightarrow y \ in A)}$${\ displaystyle x \, R \, y}$
• kompakt , om varje delmängd av V med den ändliga korsningsegenskapen har en icke-tom korsning,
• atom , om V innehåller alla singletoner,
• raffinerad , om den är differentierad och tät,
• beskrivande , om den är förfinad och kompakt.

Kripke-ramar är raffinerade och atomära. Oändliga Kripke-ramar är dock aldrig kompakta. Varje ändlig differentierad eller atomär ram är en Kripke-ram.

Beskrivande ramar är den viktigaste klassen av ramar på grund av dualitetsteorin (se nedan). Raffinerade ramar är användbara som en vanlig generalisering av beskrivande ramar och Kripke-ramar.

Funktioner och morfismer på ramar

Varje Kripke-modell inducerar den allmänna ramen , där V definieras som ${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$ ${\ displaystyle \ langle F, R, V \ rangle}$

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

De grundläggande sanningsbevarande funktionerna för genererade underramar, p-morfiska bilder och oskiljaktiga förbund med Kripke-ramar har analoger på allmänna ramar. En ram är en genererad delram av en ram , om Kripke-ramen är en genererad delram av Kripke-ramen (dvs. är en delmängd av stängd uppåt under , och ), och ${\ 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 \ times G}$

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

En p-morfism (eller avgränsad morfism ) är en funktion från F till G som är en p-morfism av Kripke-ramarna och , och uppfyller den ytterligare begränsningen ${\ displaystyle f \ colon \ mathbf {F} \ to \ mathbf {G}}$${\ displaystyle \ langle F, R \ rangle}$${\ displaystyle \ langle G, S \ rangle}$

${\ displaystyle f ^ {- 1} [A] \ i V}$ för alla . ${\ displaystyle A \ in W}$

Den ojämna sammansättningen av en indexerad uppsättning ramar , är ramen , där F är den ojämna föreningen av , R är föreningen av , och ${\ 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 förfining av en ram är en raffinerad ram definieras enligt följande. Vi betraktar ekvivalensrelationen${\ 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),}$

och låt vara en uppsättning ekvivalensklasser av . Sedan 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.}$

Fullständighet

Till skillnad från Kripke-ramar är varje normal modalogik L komplett med avseende på en klass av allmänna ramar. Detta är en konsekvens av det faktum att L är komplett med avseende på en klass av Kripke-modeller : eftersom L är stängd under substitution är den allmänna ramen som induceras av en L- ram. Dessutom är varje logik L komplett med avseende på en enda beskrivande ram. Faktum är att L är komplett med avseende på dess kanoniska modell, och den allmänna ramen som induceras av den kanoniska modellen (kallad den kanoniska ramen för L ) är beskrivande. ${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$

Dualitet Jónsson – Tarski

Rieger – Nishimura-stegen: en 1-universell intuitionistisk Kripke-ram.

Dess dubbla Heyting-algebra, Rieger – Nishimura-gitteret. Det är gratis Heyting-algebra över 1 generator.

Allmänna ramar har nära koppling till modala algebraer . Låta vara en allmän ram. Uppsättningen V är stängd under booleska operationer, därför är det en delalgebra till den effektuppsatta booleska algebra . Det har också en ytterligare unary operation . Den kombinerade strukturen är en modal algebra, som kallas den dubbla algebra av F , och betecknas 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 motsatt riktning är det möjligt att konstruera den dubbla ramen till vilken modal algebra som helst . Den Boolean algebra har en stenmagasin , vars underliggande set F är mängden av alla ultrafilter av A . Uppsättningen V av tillåtna värderingar i består av de öppna delmängderna av F , och tillgänglighetsrelationen R definieras av ${\ 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)}$

för alla ultrafilter x och y .

En ram och dess dubbla validerar samma formler, därav är den allmänna ramsemantiken och algebraisk semantiken i en mening ekvivalent. Den dubbla dubbla av vilken modal algebra som helst är isomorf för sig själv. Detta är inte sant i allmänhet för dubbla dualer av ramar, eftersom dubbla för varje algebra är beskrivande. I själva verket är en ram beskrivande om och bara om den är isomorf till sin dubbla dubbla . ${\ displaystyle (\ mathbf {A} _ {+}) ^ {+}}$${\ displaystyle \ mathbf {A}}$${\ displaystyle \ mathbf {F}}$${\ displaystyle (\ mathbf {F} ^ {+}) _ {+}}$

Det är också möjligt att definiera dualer av p-morfismer å ena sidan och modala algebra homomorfismer å andra sidan. På detta sätt operatörerna och bli ett par kontravari funktorer mellan kategorin allmänna ramar och kategorin modala algebras. Dessa funktioner ger en dualitet (kallad Jónsson – Tarski-dualitet efter Bjarni Jónsson och Alfred Tarski ) mellan kategorierna av beskrivande ramar och modala algebraer. Detta är ett speciellt fall av en mer allmän dualitet mellan komplexa algebraer och fält av uppsättningar på relationsstrukturer . ${\ displaystyle (\ cdot) ^ {+}}$${\ displaystyle (\ cdot) _ {+}}$

Intuitionistiska ramar

Ramsemantiken för intuitionistisk och mellanliggande logik kan utvecklas parallellt med semantiken för modalogik. En intuitionistisk allmän ram är en trippel , där är en delordning på F , och V är en uppsättning av övre delmängder ( kottar ) av F som innehåller den tomma uppsättningen och är stängd under ${\ displaystyle \ langle F, \ leq, V \ rangle}$${\ displaystyle \ leq}$

• korsning och union,
• operationen . ${\ displaystyle A \ to B = \ Box (-A \ cup B)}$

Giltighet och andra koncept introduceras sedan på samma sätt som modala ramar, med några få ändringar som är nödvändiga för att tillgodose de svagare stängningsegenskaperna för uppsättningen tillåtna värderingar. I synnerhet kallas en intuitionistisk ram ${\ displaystyle \ mathbf {F} = \ langle F, \ leq, V \ rangle}$

• tätt , om det antyder , ${\ displaystyle \ forall A \ i V \, (x \ i A \ Leftrightarrow y \ i A)}$${\ displaystyle x \ leq y}$
• kompakt , om varje delmängd med den ändliga korsningsegenskapen har en icke-tom korsning. ${\ displaystyle V \ cup \ {FA; \, A \ in V \}}$

Täta intuitionistiska ramar differentieras automatiskt och därmed förfinas.

Den dubbla av en intuitionistisk ram är Heyting-algebra . Det dubbla av en Heyting-algebra är den intuitionistiska ramen , där F är uppsättningen av alla primära filter av A , ordningen är inkludering och V består av alla delmängder av F av 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 \},}$

var . Som i modalfallet, och är ett par kontravariantfunktioner, vilket gör kategorin Heyting-algebraer ekvivalent med kategorin beskrivande intuitionistiska ramar. ${\ displaystyle a \ i A}$${\ displaystyle (\ cdot) ^ {+}}$${\ displaystyle (\ cdot) _ {+}}$

Det är möjligt att konstruera intuitionistiska allmänna ramar från transitiva reflexiva modala ramar och vice versa, se modal följeslagare .

Referenser

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