Polymodální logika Japaridzes - Japaridzes polymodal logic - Wikipedia
Polymodální logika (GLP) společnosti Japaridze, je systém logika prokazatelnosti s nekonečně mnoha prokazatelnostmi modality. Tento systém hrál důležitou roli v některých aplikacích algebry prokazatelnosti v teorie důkazů, a byl rozsáhle studován od konce 80. let. Je pojmenován po Giorgi Japaridze.
Jazyk a axiomatizace
Jazyk GLP rozšiřuje jazyk jazyka klasického výroková logika zahrnutím nekonečné řady [0], [1], [2], ... operátorů „nezbytnosti“. Jejich duální operátory „možnosti“ <0>, <1>, <2>, ... jsou definovány <n>p = ¬[n]¬p.
Axiomy GLP jsou všechny klasické tautologie a všechny vzorce jedné z následujících forem:
- [n](p → q) → ([n]p → [n]q)
- [n]([n]p → p) → [n]p
- [n]p → [n+1]p
- <n>p → [n+1]<n>p
A pravidla odvození jsou:
- Z p a p → q uzavřít q
- Z p uzavřít [0]p
Sémantika prokazatelnosti
Zvažte „dostatečně silný“ teorie prvního řádu T jako Peano aritmetika PA. Definujte řadu T0,T1,T2, ... z následujících teorií:
- T0 je T
- Tn+1 je příponou Tn prostřednictvím dalších axiomů ∀xF(X) pro každý vzorec F(X) takové, že Tn dokazuje všechny vzorce F(0), F(1), F(2),...
Pro každého n, ať Prn(X) být přirozenou aritmetizací predikátu “X je Gödelovo číslo trestu prokazatelného v Tn.
A realizace je funkce *, která odesílá každý nelogický atom A jazyka GLP na větu A* jazyka T. Rozšiřuje se na všechny vzorce jazyka GLP stanovením, že * dojíždí s logickými spojkami, a to ([n]F) * je Prn(‘F* “), Kde„F* “Znamená (číslici) Gödelova čísla F*.
An věta o aritmetické úplnosti[1] pro GLP uvádí, že vzorec F je v GLP prokazatelný pouze tehdy, pokud je pro každou interpretaci * věta F* je prokazatelné v T.
Výše uvedené chápání série T0,T1,T2, ... teorií není jediným přirozeným porozuměním, které poskytuje spolehlivost a úplnost GLP. Například každá teorie Tn lze chápat jako T rozšířeno o všechny pravdivé ∏n věty jako další axiomy. George Boolos ukázal[2] že GLP zůstává solidní a kompletní s analýzou (aritmetikou druhého řádu) v roli základní teorie T.
Další sémantika
GLP byl zobrazen[1] být neúplné s ohledem na jakoukoli třídu rámů Kripke.
Přirozená topologická sémantika GLP interpretuje modality jako derivační operátory a polytopologický prostor. Takové prostory se nazývají GLP-prostory, kdykoli splňují všechny axiomy GLP. GLP je kompletní s ohledem na třídu všech GLP prostorů.[3]
Výpočetní složitost
Problém být teorémem GLP je PSPACE - kompletní. Stejný problém je tedy omezen pouze na vzorce GLP bez proměnných.[4]
Dějiny
GLP, pod názvem GP, představila společnost Giorgi Japaridze ve své disertační práci „Modální logické prostředky vyšetřování poskytovatelnosti“ (Moskevská státní univerzita, 1986) a publikován o dva roky později[1] spolu s (a) větou úplnosti pro GLP s ohledem na její interpretaci prokazatelnosti (Beklemishev následně přišel s jednodušším důkazem stejné věty[5]) a (b) důkaz, že rámce Kripke pro GLP neexistují. Beklemishev také provedl rozsáhlejší studii modelů Kripke pro GLP.[6] Topologické modely pro GLP studovali Beklemishev, Bezhanishvili, Icard a Gabelaia.[3][7]Rozhodnutelnost GLP v polynomiálním prostoru prokázal I. Shapirovsky,[8] a tvrdost PSPACE jeho variabilního fragmentu prokázal F. Pakhomov.[4] Mezi nejpozoruhodnější aplikace GLP patří jeho použití v proof-teoretické analýze Peano aritmetika, vypracování kanonického způsobu obnovy pořadová notace až do ɛ0 z odpovídající algebry a konstrukce jednoduchých kombinačních nezávislých příkazů (Beklemishev [9]).
Rozsáhlý průzkum GLP v kontextu logiky prokazatelnosti obecně poskytl George Boolos ve své knize „Logika prokazatelnosti“.[10]
Literatura
- L. Beklemishev, „Algebry prokazatelnosti a ordinály ordinace důkazu, já“. Annals of Pure and Applied Logic 128 (2004), str. 103–123.
- L. Beklemishev, J. Joosten a M. Vervoort, „Konečné zacházení s uzavřeným fragmentem prokazatelnosti logiky Japaridze“. Journal of Logic and Computation 15 (2005), č. 4, str. 447–463.
- L. Beklemishev, "Kripkeho sémantika pro prokazatelnou logiku GLP". Annals of Pure and Applied Logic 161, 756–774 (2010).
- L. Beklemishev, G. Bezhanishvili a T. Icar, „O topologických modelech GLP“. Ways of proof theory, Ontos Mathematical Logic, 2, eds. R. Schindler, Ontos Verlag, Frankfurt, 2010, s. 133–153.
- L. Beklemishev, „O Craigově interpolaci a vlastnostech GLP s pevným bodem“. Důkazy, kategorie a výpočty. S. Feferman a kol., Eds., College Publications 2010. str. 49–60.
- L. Beklemishev, "Obyčejná úplnost bimodální logiky prokazatelnosti GLB". Přednášky z informatiky 6618 (2011), s. 1–15.
- L. Beklemishev, "Zjednodušený důkaz věty o aritmetické úplnosti pro logiku prokazatelnosti GLP". Sborník Steklovova matematického ústavu 274 (2011), s. 25–33.
- L. Beklemishev a D. Gabelaia, "Topologická úplnost logiky prokazatelnosti GLP". Annals of Pure and Applied Logic 164 (2013), str. 1201–1223.
- G. Boolos, „Analytická úplnost Japaridzeových polymodálních logik“. Annals of Pure and Applied Logic 61 (1993), str. 95–111.
- G. Boolos, „Logika poskytovatelnosti“. Cambridge University Press, 1993.
- E.V. Dashkov, „O pozitivním fragmentu logiky polymodální prokazatelnosti GLP“. Matematické poznámky 2012; 91: 318–333.
- D. Fernandez-Duque a J. Joosten, "Dobře rozkazy v transfinitní Japaridze algebře". Logic Journal of the IGPL 22 (2014), str. 933–963.
- G. Japaridze, „Polymodální logika prokazatelnosti“. Intenzionální logika a logická struktura teorií. Metsniereba, Tbilisi, 1988, s. 16–48 (rusky).
- F. Pakhomov, "O složitosti uzavřeného fragmentu prokazatelnosti logiky Japaridze". Archiv pro Mathematical Logic 53 (2014), str. 949–967.
- DS Shamkanov, „Interpolační vlastnosti pro prokazatelnou logiku GL a GLP“. Sborník Steklovova matematického ústavu 274 (2011), s. 303–316.
- I. Shapirovsky, „PSPACE-rozhodnutelnost Japaridzeovy polymodální logiky“. Advances in Modal Logic 7 (2008), s. 289–304.
Reference
- ^ A b C G. Japaridze, „Polymodální logika prokazatelnosti“. Intenzionální logika a logická struktura teorií. Metsniereba, Tbilisi, 1988, s. 16–48 (rusky).
- ^ G. Boolos, „Analytická úplnost Japaridzeových polymodálních logik“. Annals of Pure and Applied Logic 61 (1993), str. 95–111.
- ^ A b L. Beklemishev a D. Gabelaia, "Topologická úplnost logiky prokazatelnosti GLP". Annals of Pure and Applied Logic 164 (2013), str. 1201–1223.
- ^ A b F. Pakhomov, "O složitosti uzavřeného fragmentu prokazatelnosti logiky Japaridze". Archiv pro Mathematical Logic 53 (2014), str. 949–967.
- ^ L. Beklemishev, „Zjednodušený důkaz věty o aritmetické úplnosti pro logiku prokazatelnosti GLP“. Sborník Steklovova matematického ústavu 274 (2011), s. 25–33.
- ^ L. Beklemishev, "Kripkeho sémantika pro prokazatelnou logiku GLP". Annals of Pure and Applied Logic 161, 756–774 (2010).
- ^ L. Beklemishev, G. Bezhanishvili a T. Icard, „O topologických modelech GLP“. Ways of proof theory, Ontos Mathematical Logic, 2, eds. R. Schindler, Ontos Verlag, Frankfurt, 2010, s. 133–153.
- ^ I. Shapirovsky, „PSPACE-rozhodnutelnost Japaridzeovy polymodální logiky“. Advances in Modal Logic 7 (2008), s. 289-304.
- ^ L. Beklemishev, „Algebry prokazatelnosti a ordinální ordinály důkazu, já“. Annals of Pure and Applied Logic 128 (2004), str. 103–123.
- ^ G. Boolos, „Logika poskytovatelnosti“. Cambridge University Press, 1993.