Yleinen kehys - General frame

On logiikka , yleisesti kehyksiä (tai yksinkertaisesti kehykset ) ovat kripke kehyksiä ylimääräinen rakenne, joita käytetään mallintamaan modaalinen ja väli- logiikka. Yleinen kehyssemantiikka yhdistää Kripke-semantiikan ja algebrallisen semantiikan pää hyveet : se jakaa ensimmäisen läpinäkyvän geometrisen oivalluksen ja jälkimmäisen vankan täydellisyyden.

Määritelmä

Modaalinen yleinen kehys on kolminkertainen , jossa on kripke kehys (eli R on binäärirelaatio on joukko F ), ja V on joukko osajoukkojen F , joka on suljettu seuraavasti: ${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$${\ displaystyle \ langle F, R \ rangle}$

• (binäärisen) leikkauksen , liiton ja täydennyksen Boolen operaatiot ,
• operaation , on määritelty . ${\ displaystyle \ Box}$${\ displaystyle \ Box A = \ {x \ in F; \, \ forall y \ in F \, (x \, R \, y \ to y \ in A) \}}$

Ne ovat siis erityistapaus lisärakenteisten joukkoalueiden kanssa . V: n tarkoituksena on rajoittaa kehyksen sallittuja arviointeja: Kripke-kehykseen perustuva malli on sallittu yleisessä kehyksessä F , jos ${\ displaystyle \ langle F, R, \ Vdash \ rangle}$${\ displaystyle \ langle F, R \ rangle}$

${\ displaystyle \ {x \ in F; \, x \ Vdash p \} \ in V}$ jokaiselle lausemuuttujalle p .

Sitten V: n sulkemisolosuhteet varmistavat, että se kuuluu V : lle jokaiselle kaavalle A (ei vain muuttujalle). ${\ displaystyle \ {x \ in F; \, x \ Vdash A \}}$

Kaava A on voimassa muodossa F , jos kaikki hyväksyttävät arvot ja kaikki pisteet . Normaali modaalilogiikan L on voimassa kehyksessä F , jos kaikki aksioomat (tai vastaavasti, kaikki lauseet ) ja L ovat voimassa F . Tässä tapauksessa kutsumme F L - runko . ${\ displaystyle x \ Vdash A}$${\ displaystyle \ Vdash}$${\ displaystyle x \ in F}$

Kripke kehys , voidaan tunnistaa yleisesti runko, jossa kaikki arvon ovat hyväksyttäviä: eli , jossa tarkoittaa asetetulla teholla ja F . ${\ displaystyle \ langle F, R \ rangle}$${\ displaystyle \ langle F, R, {\ mathcal {P}} (F) \ rangle}$${\ displaystyle {\ mathcal {P}} (F)}$

Kehystyypit

Kaiken kaikkiaan yleiset kehykset ovat tuskin muuta kuin hieno nimi Kripke- malleille ; erityisesti menetettyjen aksiomien ja ominaisuuksien vastaavuus saavutettavuussuhteessa menetetään. Tämä voidaan korjata asettamalla lisäehtoja hyväksyttäville arvostuksille.

Kehystä kutsutaan ${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$

• eriytetty , jos merkitsee , ${\ displaystyle \ forall A \ in V \, (x \ in A \ Leftightarrow y \ in A)}$${\ displaystyle x = y}$
• tiukka , jos se merkitsee , ${\ displaystyle \ forall A \ in V \, (x \ in \ Box A \ Rightarrow y \ in A)}$${\ displaystyle x \, R \, y}$
• kompakti , jos kaikilla V : n osajoukoilla, joilla on rajallinen leikkausominaisuus, on tyhjä leikkauspiste,
• atomi , jos V sisältää kaikki singletonit,
• hienostunut , jos se on eriytetty ja tiukka,
• kuvaava , jos se on hienostunut ja kompakti.

Kripke-kehykset ovat hienostuneita ja atomisia. Äärettömät Kripke-kehykset eivät kuitenkaan ole koskaan kompakteja. Jokainen rajallinen eriytetty tai atomikehys on Kripke-kehys.

Kuvaavat kehykset ovat tärkein kehysluokka kaksinaisuuden teorian takia (katso alla). Tarkennetut kehykset ovat hyödyllisiä kuvailevien ja Kripke-kehysten yleisenä yleistyksenä.

Toiminnot ja morfismit kehyksissä

Jokainen Kripke-malli indusoi yleisen kehyksen , jossa V määritellään ${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$ ${\ displaystyle \ langle F, R, V \ rangle}$

${\ displaystyle V = {\ iso \ {} \ {x \ in F; \, x \ Vdash A \}; \, A {\ hbox {on kaava}} {\ iso \}}.}$

Generoitujen alikehysten, p-morfisten kuvien ja Kripke-kehysten epäyhtenäisten liittojen perustotuuden säilyttämistoiminnoilla on analogeja yleisissä kehyksissä. Kehys on tuotettu alikehyksen kehyksen , jos kripke kehys on tuotettu alikehykselle kripke kehyksen (ts, on osajoukko suljettu ylöspäin alla , ja ), ja ${\ 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 \ korkki G \ kertaa G}$

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

P-morfismi (tai rajoitettu morfismi ) on funktion F ja G , joka on p-morfismi on Kripke kehysten ja , ja täyttää lisäksi rajoite ${\ displaystyle f \ kaksoispiste \ mathbf {F} \ to \ mathbf {G}}$${\ displaystyle \ langle F, R \ rangle}$${\ displaystyle \ langle G, S \ rangle}$

${\ displaystyle f ^ {- 1} [A] \ sisään V}$ jokaiselle . ${\ displaystyle A \ sisään W}$

Disjoint unioni on indeksoitu joukko kehyksiä , on runko , jossa F on disjoint liitto , R on liitto , ja ${\ displaystyle \ mathbf {F} _ {i} = \ langle F_ {i}, R_ {i}, V_ {i} \ rangle}$${\ displaystyle i \ sisään I}$${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$${\ displaystyle \ {F_ {i}; \, i \ sisään I \}}$${\ displaystyle \ {R_ {i}; \, i \ sisään I \}}$

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

Tarkentaminen kehyksen on hienostunut kehys määritellään seuraavasti. Otamme huomioon ekvivalenssisuhteen${\ displaystyle \ mathbf {F} = \ langle F, R, V \ rangle}$${\ displaystyle \ mathbf {G} = \ langle G, S, W \ rangle}$

${\ displaystyle x \ sim y \ iff \ kaikki A \ in V \, (x \ in A \ vasen palkki y \ in A),}$

ja anna olla joukko vastaavuusluokkia . Sitten laitamme ${\ displaystyle G = F / {\ sim}}$${\ displaystyle \ sim}$

${\ displaystyle \ langle x / {\ sim}, y / {\ sim} \ rangle \ in S \ iff \ kaikki A \ V: ssä, (x \ laatikossa A \ Rightarrow y \ A: ssa),}$

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

Täydellisyys

Toisin kuin Kripke-kehykset, jokainen normaali modaalilogiikka L on täydellinen suhteessa yleisten kehysten luokkaan. Tämä on seurausta siitä, että L on täydellinen suhteessa Kripke-mallien luokkaan : kun L on suljettu substituution alla, yleinen kehys, jonka indusoi, on L- kehys . Lisäksi jokainen logiikka L on täydellinen suhteessa yhteen kuvaavaan kehykseen. Todellakin, L on täydellinen suhteessa sen kanoninen malli, ja yleisen kehyksen aiheuttama kanoninen mallin (kutsutaan kanoninen runko on L ) on kuvaileva. ${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$${\ displaystyle \ langle F, R, {\ Vdash} \ rangle}$

Jónsson – Tarski-kaksinaisuus

Rieger – Nishimura-tikkaat: yksi universaali intuitiivinen Kripke-kehys.

Sen kaksois-Heyting-algebra, Rieger – Nishimura-ristikko. Se on ilmainen Heyting-algebra yli yhden generaattorin.

Yleisillä kehyksillä on läheinen yhteys modaalisiin algebroihin . Antaa olla yleinen kehys. Sarja V on suljettu Boolen toimintoja, joten se on subalgebra tehon joukko Boolen algebran . Se kuljettaa myös ylimääräisen unaarista toiminnan . Yhdistetty rakenne on modaalinen algebran, jota kutsutaan kaksi algebran ja F , ja merkitään . ${\ 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} ^ {+}}$

Päinvastaisessa suunnassa on mahdollista rakentaa kaksoiskehys mihin tahansa modaaliseen algebraan . Boolen algebralla on kiviavaruus , jonka taustajoukko F on A: n kaikkien ultrasuodattimien joukko . Joukko V hyväksyttävien arvostukset koostuu clopen osajoukkojen F , ja saavutettavuus suhde R on määritelty ${\ 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 \ sisältää kaikki \ in A \, (\ Box a \ sisään x \ Rightarrow a \ in y)}$

kaikille ultrasuodattimille x ja y .

Kehys ja sen kaksoisvahvistavat samat kaavat, joten yleinen kehyssemantiikka ja algebrallinen semantiikka ovat tavallaan vastaavia. Minkä tahansa modaalisen algebran kaksoisduaali on isomorfinen itselleen. Tämä ei pidä paikkaansa kehysten kaksoisduplien suhteen, koska jokaisen algebran kaksoiskuva on kuvaileva. Itse asiassa kehys on kuvaava vain ja vain, jos se on isomorfinen sen kaksoisduplan suhteen . ${\ displaystyle (\ mathbf {A} _ {+}) ^ {+}}$${\ displaystyle \ mathbf {A}}$${\ displaystyle \ mathbf {F}}$${\ displaystyle (\ mathbf {F} ^ {+}) _ {+}}$

On myös mahdollista määritellä toisaalta p-morfismien duaalit ja toisaalta modaaliset algebran homomorfismit. Näin operaattorit ja tulla pari contravariant functors välillä luokan yleisten kehysten, ja luokka modaalinen algebras. Nämä functors tarjoavat kaksinaisuus (kutsutaan Jónsson-Tarski kaksinaisuus jälkeen Bjarni Jónsson ja Alfred Tarski ) välillä luokat kuvaileva kehyksiä, ja liikennemuotojen algebrat. Tämä on erityistapaus monimutkaisten algebrojen ja relaatiorakenteiden joukkoalueiden välisestä yleisemmästä kaksinaisuudesta . ${\ displaystyle (\ cdot) ^ {+}}$${\ displaystyle (\ cdot) _ {+}}$

Intuitionistiset kehykset

Intuitionistisen ja välilogiikan kehyssemantiikkaa voidaan kehittää rinnakkain modaalisen logiikan semantiikan kanssa. Intuitionistic yleinen kehys on kolminkertainen , jossa on osittainen järjestys on F , ja V on joukko ylemmän osajoukkojen ( kartioiden ) on F , joka sisältää tyhjä joukko, ja on suljettu alle ${\ displaystyle \ langle F, \ leq, V \ rangle}$${\ displaystyle \ leq}$

• risteys ja liitos,
• operaation . ${\ displaystyle A - B = \ Box (laatikko (-A \ cup B)}$

Voimassaolo ja muut käsitteet otetaan sitten käyttöön samalla tavalla kuin liikennemuodot, muutamalla muutoksella, jotka ovat välttämättömiä hyväksyttävien arvioiden joukon heikompien sulkemisominaisuuksien huomioon ottamiseksi. Erityisesti kutsutaan intuitionistista kehystä ${\ displaystyle \ mathbf {F} = \ langle F, \ leq, V \ rangle}$

• tiukka , jos se merkitsee , ${\ displaystyle \ forall A \ in V \, (x \ in A \ Leftightarrow y \ in A)}$${\ displaystyle x \ leq y}$
• kompakti , jos jokaisella rajallisen leikkausomaisuuden osajoukolla on tyhjä leikkauspiste. ${\ displaystyle V \ cup \ {FA; \, A \ in V \}}$

Tiukat intuitionistiset kehykset erotellaan automaattisesti, joten ne tarkentuvat.

Intuitionistisen kehyksen dualismi on Heyting-algebra . Heyting-algebran kaksoistunnus on intuitionistinen kehys , jossa F on A: n kaikkien alkusuodattimien joukko , järjestys on sisällytys ja V koostuu muodon F kaikista osajoukoista ${\ displaystyle \ mathbf {F} = \ langle F, \ leq, V \ rangle}$ ${\ displaystyle \ mathbf {F} ^ {+} = \ langle V, \ cap, \ cup, \ to, \ emptyyset 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 \},}$

missä . Kuten modaalitapauksessa, ja ne ovat pari sopivia funktoreita, jotka tekevät Heyting-algebrojen luokan kaksinkertaiseksi kuvailevien intuitionististen kehysten luokkaan. ${\ displaystyle a \ sisään A}$${\ displaystyle (\ cdot) ^ {+}}$${\ displaystyle (\ cdot) _ {+}}$

On mahdollista rakentaa intuitionistisia yleisiä kehyksiä transitiivisista refleksiivisistä modaalikehyksistä ja päinvastoin, katso modaalinen kumppani .

Viitteet

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