Modální společník - Modal companion

v logika, a modální společník a superintucionistický (střední) logika L je normální modální logika který interpretuje L určitým kanonickým překladem, popsaným níže. Modální společníci sdílejí různé vlastnosti originálu střední logika, který umožňuje studovat střední logiku pomocí nástrojů vyvinutých pro modální logiku.

Překlad Gödel – McKinsey – Tarski

Nechat A být propoziční intuitivní vzorec. Modální vzorec T(A) je definován indukcí na složitosti A:

${displaystyle T (p) = Box p}$ pro všechny výroková proměnná ${displaystyle p}$,

${displaystyle T (ot) = ot,}$

${displaystyle T (Aland B) = T (A) země T (B),}$

${displaystyle T (Alor B) = T (A) lor T (B),}$

${displaystyle T (A o B) = Box (T (A) o T (B)).}$

Protože negace je v intuitivní logice definována ${displaystyle A o ot}$, také máme

${displaystyle T (např. A) = rámeček např. T (A).}$

T se nazývá Gödelův překlad nebo Gödel –McKinsey –Tarski překlad. Překlad je někdy prezentován mírně odlišnými způsoby: jeden může například vložit ${displaystyle Box}$ před každou podformulí. Všechny tyto varianty jsou prokazatelně ekvivalentní v S4.

Modální společníci

Pro jakoukoli normální modální logiku M který se prodlužuje S4, definujeme jeho si-fragment ρM tak jako

${displaystyle ho M = {Uprostřed Mvdash T (A)}.}$

Si-fragment jakéhokoli normálního rozšíření S4 je superintucionistická logika. Modální logika M je modální společník superintucionistické logiky L -li ${displaystyle L = ho M}$.

Každá superintucionistická logika má modální společníky. The nejmenší modální společník z L je

${displaystyle au L = mathbf {S4} oplus {T (A) mid Lvdash A},}$

kde ${displaystyle oplus}$ označuje normální uzavření. Je možné ukázat, že každá superintucionistická logika má také největší modální společník, který je označen σL. Modální logika M je společníkem L kdyby a jen kdyby ${displaystyle au Lsubseteq Msubseteq sigma L}$.

Například, S4 sama o sobě je nejmenším modálním společníkem intuicionistické logiky (IPC). Největší modální společník IPC je Grzegorczyk logika Grz, axiomatizován axiomem

${displaystyle Box (Box (A o Box A) o A) o A}$

přes K.. Nejmenší modální společník klasické logiky (CPC) je Lewis ' S5, zatímco jeho největší modální společník je logika

${displaystyle mathbf {Triv} = mathbf {K} oplus (Aleftrightarrow Box A).}$

Další příklady:

Blok – Esakia izomorfismus

Sada rozšíření superintucionistické logiky L seřazeno podle inkluzních formulářů a úplná mříž, označené ExtL. Podobně sada normálních rozšíření modální logiky M je úplná příhrada NExtM. Společné operátory ρM, τLa σL lze považovat za mapování mezi mřížkami ExtIPC a dalšíS4:

${displaystyle ho colon mathrm {NExt}, mathbf {S4} o mathrm {Ext}, mathbf {IPC},}$

${displaystyle au, sigma colon mathrm {Ext}, mathbf {IPC} o mathrm {NExt}, mathbf {S4}.}$

Je snadné vidět, že všechny tři jsou monotónní, a ${displaystyle ho circ au = ho circ sigma}$ je funkce identity na ExtIPC. L. Maksimova a V. Rybakov ukázaly, že ρ, τ a σ jsou ve skutečnosti kompletní, spojit-dokončit a splnit-splnit mřížkové homomorfismy, resp. Základním kamenem teorie modálních společníků je Věta Blok – Esakia, nezávisle prokázáno Wim Blok a Leo Esakia. Uvádí

Mapování ρ a σ jsou vzájemná inverzní mříž izomorfismy z ExtIPC a DalšíGrz.

V souladu s tím σ a omezení z ρ do NExtGrz se nazývají Blok – Esakia izomorfismus. Důležitým důsledkem věty Blok – Esakia je jednoduchý syntaktický popis největších modálních společníků: pro každou superintucionistickou logiku L,

${displaystyle sigma L = au Loplus mathbf {Grz}.}$

Sémantický popis

Gödelův překlad má protějšek rámcově teoretický. Nechat ${displaystyle mathbf {F} = jazyk F, R, Vangle}$ být tranzitivní a reflexní modální obecný rám. The předobjednávka R vyvolává vztah ekvivalence

${displaystyle xsim yiff x, R, yland y, R, x}$

na F, který identifikuje body patřící do stejného klastru. Nechat ${displaystyle langle ho F, leq angle = langle F, Rangle / {sim}}$ být indukovaný kvocient částečná objednávka (tj. ρF je sada třídy ekvivalence z ${displaystyle sim}$), a dal

${displaystyle ho V = {A / {sim} mid Ain V, A = Box A}.}$

Pak ${displaystyle ho mathbf {F} = jazyk ho F, leq, ho Vangle}$ je intuitivní obecný rámec, nazývaný kostra z F. Smyslem konstrukce skeletu je to, že zachovává platnost modulo Gödelova překladu: pro jakýkoli intuicionistický vzorec A,

A platí v ρF kdyby a jen kdyby T(A) je platný v F.

Proto si-fragment modální logiky M lze definovat sémanticky: pokud M je kompletní s ohledem na třídu C tranzitivních reflexivních obecných rámců, pak ρM je kompletní s ohledem na třídu ${displaystyle {ho mathbf {F};, mathbf {F} v C}}$.

Největší modální společníci mají také sémantický popis. Pro jakýkoli intuitivní obecný rámec ${displaystyle mathbf {F} = jazyk F, leq, Vangle}$, nechť σPROTI být uzávěrkou PROTI v rámci booleovských operací (binární průsečík a doplněk ). Je možné ukázat, že σPROTI je uzavřen pod ${displaystyle Box}$, tím pádem ${displaystyle sigma mathbf {F} = jazyk F, leq, sigma Vangle}$ je obecný modální rámec. Kostra σF je izomorfní s F. Li L je superintucionistická logika úplná s ohledem na třídu C obecných rámců, pak jeho největší modální společník σL je kompletní s ohledem na ${displaystyle {sigma mathbf {F};, mathbf {F} v C}}$.

Kostra a Kripkeho rám je sám o sobě rámem Kripke. Na druhou stranu, σF nikdy není rámem Kripke, pokud F je rám Kripke nekonečné hloubky.

Věty o zachování

Hodnota modálních společníků a věty Blok – Esakia jako nástroje pro zkoumání střední logiky vychází ze skutečnosti, že některé zajímavé vlastnosti logiky jsou zachovány některými nebo všemi zobrazeními ρ, σ a τ. Například,

• rozhodnutelnost je konzervován ρ, τ a σ,
• vlastnost konečného modelu je konzervován ρ, τ a σ,
• tabulkovitost je konzervován ρ a σ,
• Kripke úplnost je konzervován ρ a τ,
• první objednávka definovatelnost na rámech Kripke je zachována pomocí ρ a τ.

Další vlastnosti

Každá mezilehlá logika L má nekonečný počet modálních společníků a navíc sada ${displaystyle ho ^ {- 1} (L)}$ modálních společníků L obsahuje nekonečný sestupný řetězec. Například, ${displaystyle ho ^ {- 1} (mathbf {CPC})}$ skládá se z S5a logika ${displaystyle L (C_ {n})}$ pro každé kladné celé číslo n, kde ${displaystyle C_ {n}}$ je n-prvkový klastr. Sada modálních společníků libovolného L je buď počitatelný, nebo má mohutnost kontinua. Rybakov ukázal, že mříž ExtL může být vložený v ${displaystyle ho ^ {- 1} (L)}$; logika má zejména kontinuum modálních společníků, pokud má kontinuum rozšíření (platí například pro všechny střední logiky níže KC). Není známo, zda je obrácení také pravdivé.

Lze použít Gödelův překlad pravidla stejně jako vzorce: překlad pravidla

${displaystyle R = {frac {A_ {1}, tečky, A_ {n}} {B}}}$

je pravidlem

${displaystyle T (R) = {frac {T (A_ {1}), tečky, T (A_ {n})} {T (B)}}.}$

Pravidlo R je přípustný logicky L pokud množina vět o L je uzavřen pod R. Je snadné to vidět R je přípustné v superintucionistické logice L kdykoli T(R) je přípustný v modálním společníkovi L. Konverzace není obecně platná, ale platí pro největšího modálního společníka L.

Reference

• Alexander Chagrov a Michael Zakharyaschev, Modální logika, sv. 35 of Oxford Logic Guides, Oxford University Press, 1997.
• Vladimír V. Rybakov, Přípustnost pravidel logického odvození, sv. 136 of Studies in Logic and the Foundations of Mathematics, Elsevier, 1997.