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

Reference

  1. ^ A b C G. Japaridze, „Polymodální logika prokazatelnosti“. Intenzionální logika a logická struktura teorií. Metsniereba, Tbilisi, 1988, s. 16–48 (rusky).
  2. ^ G. Boolos, „Analytická úplnost Japaridzeových polymodálních logik“. Annals of Pure and Applied Logic 61 (1993), str. 95–111.
  3. ^ A b L. Beklemishev a D. Gabelaia, "Topologická úplnost logiky prokazatelnosti GLP". Annals of Pure and Applied Logic 164 (2013), str. 1201–1223.
  4. ^ A b F. Pakhomov, "O složitosti uzavřeného fragmentu prokazatelnosti logiky Japaridze". Archiv pro Mathematical Logic 53 (2014), str. 949–967.
  5. ^ 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.
  6. ^ L. Beklemishev, "Kripkeho sémantika pro prokazatelnou logiku GLP". Annals of Pure and Applied Logic 161, 756–774 (2010).
  7. ^ 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.
  8. ^ I. Shapirovsky, „PSPACE-rozhodnutelnost Japaridzeovy polymodální logiky“. Advances in Modal Logic 7 (2008), s. 289-304.
  9. ^ L. Beklemishev, „Algebry prokazatelnosti a ordinální ordinály důkazu, já“. Annals of Pure and Applied Logic 128 (2004), str. 103–123.
  10. ^ G. Boolos, „Logika poskytovatelnosti“. Cambridge University Press, 1993.