Logika Zajišťovatelnosti

2023 Autor: Noah Black | [email protected]. Naposledy změněno: 2023-11-26 16:06

Vstupní navigace

• Obsah příspěvku
• Bibliografie
• Akademické nástroje
• Náhled PDF přátel
• Informace o autorovi a citaci
• Zpět na začátek

Logika zajišťovatelnosti

První publikováno 2. dubna 2003; věcná revize st 5. dubna 2017

Logika dostupnosti je modální logika, která se používá k prozkoumání toho, jaké aritmetické teorie mohou vyjádřit v omezeném jazyce o svých predikátech prokazatelnosti. Logika byla inspirována vývojem v meta-matematice, jako jsou Gödelovy věty o neúplnosti z roku 1931 a Löbova věta z roku 1953. Jako modální logika byla logika prokazatelnosti studována od počátku sedmdesátých let a měla důležité aplikace v základech matematiky.

Z filozofického hlediska je logika prokazatelnosti zajímavá, protože pojem prokazatelnosti v pevné teorii aritmetiky má jedinečný a bezproblémový význam, jiný než pojmy jako nutnost a znalosti studované v modální a epistemické logice. Logika prokazatelnosti dále poskytuje nástroje pro studium pojmu sebepříkaz.

• 1. Historie logiky prokazatelnosti

• 2. Axiomový systém výrokové logiky prokazatelnosti

  • 2.1 Axiomy a pravidla
  • 2.2 Věta o pevném bodě

• 3. Možná světová sémantika a topologická sémantika

  • 3.1 Charakterizace a kvalita zvuku
  • 3.2 Modální úplnost
  • 3.3 Selhání silné úplnosti
  • 3.4 Topologická sémantika pro logiku prokazatelnosti

• 4. Logika zajišťování a Peano aritmetika

  • 4.1 Aritmetická spolehlivost
  • 4.2 Aritmetická úplnost

• 5. Rozsah logiky prokazatelnosti

  • 5.1 Hranice
  • 5.2 Logika interpretovatelnosti
  • 5.3 Propoziční kvantifikátory
  • 5.4 Japaridzeho bimodální a polymodální logika prokazatelnosti
  • 5.5 Predikátová logika prokazatelnosti
  • 5.6 Další zobecnění
• 6. Filozofický význam
• Bibliografie
• Akademické nástroje

• Další internetové zdroje

  • Příspěvky a prezentace
  • Další weby
• Související záznamy

1. Historie logiky prokazatelnosti

Dva oblasti výzkumu vedly k zrození logiky prokazatelnosti. První vychází z práce K. Gödele (1933), kde zavádí překlady z intuicionální výrokové logiky do modální logiky (přesněji do systému dnes nazývaného S4) a stručně uvádí, že providitelnost lze považovat za modálního operátora.. Ještě dříve zahájil CI Lewis moderní studium modální logiky zavedením přísných implikací jako druhu dedukovatelnosti, kde možná znamenal dedukcibilitu ve formálním systému, jako je Principia Mathematica, ale z jeho spisů to není jasné.

Druhá část začíná výzkumem v meta-matematice: co mohou matematické teorie říci o sobě kódováním zajímavých vlastností? V roce 1952 položil L. Henkin klamně jednoduchou otázku inspirovanou Gödelovými věty o neúplnosti. Abychom mohli formulovat Henkinovu otázku, je zapotřebí dalších pozadí. Jako připomenutí Gödelova první věta o neúplnosti uvádí, že pro dostatečně silnou formální teorii, jako je Peano Aritmetika, je jakákoli věta, která prohlašuje za svou vlastní neproveditelnost, ve skutečnosti neproveditelná. Na druhé straně, z „vnější“formální teorie je vidět, že taková věta je ve standardním modelu pravdivá a ukazuje na důležité rozlišení mezi pravdou a prokazatelností.

Více formálně, nechť (ulcorner A / urcorner) označuje Gödelovo číslo aritmetického vzorce (A), což je výsledek přiřazení číselného kódu k (A). Nechť (Prov) je formalizovaný predikát pro Peano Aritmetiku, který má tvar (existuje p \, / Důkaz (p, x)). Zde je (Proof) formalizovaný predikát Peano Arithmetic a (Proof (p, x)) je zkratka pro Gödel číslo (p) kóduje správný důkaz z axiomů Peano Aritmetiky vzorec s Gödelovým číslem (x)”. (Přesnější formulace viz Smoryński (1985), Davis (1958).) Nyní předpokládejme, že Peano Aritmetika dokazuje (A / leftrightarrow / neg) (Prov (ulcorner A / urcorner)), pak na základě výsledku Gödel, (A) není v Peano Aritmetice prokazatelná, a je tedy pravda, protože ve skutečnosti samoreferenční věta (A) uvádí „Nejsem prokazatelná“.

Henkin na druhé straně chtěl vědět, zda se dá říci něco o větách prokazujících jejich vlastní prokazatelnost: za předpokladu, že Peano Aritmetika dokazuje (B / leftrightarrow / Prov (ulcorner B / urcorner)), co to znamená o (B)? O tři roky později se M. Löb ujal výzvy a překvapivě odpověděl na Henkinovu otázku. I když všechny věty prokazatelné v Peano Aritmetice jsou skutečně pravdivé o přirozených číslech, Löb ukázal, že formalizovaná verze této skutečnosti, (Prov (ulcorner B / urcorner) rightarrow B), lze prokázat pouze v Peano aritmetice v triviálním případě, že Peano Aritmetika již dokazuje (B) sám. Tento výsledek, nyní nazývaný Löbova věta, okamžitě odpovídá na Henkinovu otázku. (Důkaz Löbovy věty viz oddíl 4.) Löb také ukázal formalizovanou verzi své věty,konkrétně to dokazuje Peano Aritmetika

) Prov (ulcorner / Prov (ulcorner B / urcorner) rightarrow B / urcorner) rightarrow / Prov (ulcorner B / urcorner).)

Ve stejném článku formuloval Löb tři podmínky pro predikát prokazatelnosti Peano Aritmetiky, které tvoří užitečnou modifikaci komplikovaných podmínek, které Hilbert a Bernays představili v roce 1939 jako důkaz Gödelovy druhé věty o neúplnosti. V následující, derivability (A) od Peano aritmetiky je označován (PA / vdash A):

1. Pokud (PA / vdash A), pak (PA / vdash / Prov (ulcorner A / urcorner));
2. (PA / vdash / Prov (ulcorner A / rightarrow B / urcorner) rightarrow (Prov (ulcorner A / urcorner) rightarrow / Prov (ulcorner B / urcorner));)
3. (PA / vdash / Prov (ulcorner A / urcorner) rightarrow / Prov (ulcorner / Prov (ulcorner A / urcorner) urcorner).)

Zdá se, že tyto Löbovy podmínky, jak se dnes říkají, volají po modálním logickém zkoumání, kde modalita (Box) znamená PA v prokazatelnosti. Je ironií, že poprvé byla formální verze Löbovy věty uvedena jako modální princip

) Box (Box A / rightarrow A) rightarrow / Box A)

byl v novinách Smiley v roce 1963 o logickém základu etiky, který vůbec nepovažoval aritmetiku. Relevantní vyšetřování však začalo vážně až téměř dvacet let po zveřejnění Löbova článku. Na počátku sedmdesátých let došlo k rychlému rozvoji logiky výrokové prozřetelnosti, kdy několik výzkumníků v různých zemích nezávisle prokázalo nejdůležitější výsledky, diskutované v oddílech 2, 3 a 4. Ukázalo se, že logika prozatímní prokazatelnosti přesně zachycuje, kolik formálních teorií aritmetiky může říkat výrokovými prostředky o jejich vlastním predikátu prokazatelnosti. V poslední době vědci zkoumali hranice tohoto přístupu a navrhli několik zajímavějších výraznějších rozšíření logiky prokazatelnosti (viz oddíl 5).

2. Axiomový systém výrokové logiky prokazatelnosti

Logický jazyk výrokové logiky prokazatelnosti obsahuje, kromě výrokových atomů a obvyklých pravdivě funkčních operátorů, stejně jako symbol rozporu (bot), modální operátor (Box) se zamýšleným významem (T), 'kde (T) je dostatečně silná formální teorie, řekněme Peano aritmetiku (viz oddíl 4). (Diamond A) je zkratka pro (neg \, / Box / neg \, A). Jazyk je tedy stejný jako jazyk modálních systémů, jako jsou K a S4 uvedené v logice vstupních modů.

2.1 Axiomy a pravidla

Logika provizorní prokazatelnosti se často nazývá GL, po Gödelovi a Löbovi. (Alternativní názvy nalezené v literatuře pro ekvivalentní systémy jsou L, G, KW, K4W a PrL). Logická GL vyplývá z přidání následující axiomy k základní modální logice K:

) tag {GL} Box (Box A / rightarrow A) rightarrow / Box A.)

Připomínáme, že protože GL rozšiřuje K, obsahuje všechny vzorce, které mají podobu výrokové tautologie. Ze stejného důvodu obsahuje GL

) tag {Distribuce Axiom} Box (A / rightarrow B) rightarrow (Box A / rightarrow / Box B).)

Dále je uzavřeno podle Modus Ponensova pravidla, které umožňuje odvodit (B) z (A / rightarrow B) a (A), a Obecného pravidla, které říká, že pokud (A) je věta o GL, pak je to také (Box A).

Pojem (GL / vdash A) označuje prokazatelnost modálního vzorce (A) v výrokové logice prokazatelnosti. Není těžké vidět, že modální axiom (Box A / rightarrow / Box / Box A) (známý jako Axiom 4 modální logiky) je v GL skutečně prokazatelný. K prokázání toho se používá substituce (A / wedge / Box A) za (A) v axiomu (GL). Poté, když vidíme, že předek výsledné implikace vyplývá z (Box A), aplikujeme distribuční axiom a generalizační pravidlo, stejně jako nějakou výrokovou logiku. Pokud není výslovně uvedeno jinak, znamená v pokračování „logika prokazatelnosti“systém GL s výrokovou logikou prokazatelnosti.

Pokud jde o důkazní teorii prokazatelnosti, Valentini (1983) prokázal, že standardní postupná formulační formulace GL se řídí řeznou eliminací, což znamená, zhruba formulováno, že každý vzorec prokazatelný z GL v sekvenčním počtu také má GL sekvenční důkaz „bez objížďky “(viz vstup teorie vývoje důkazů pro přesné vysvětlení odstranění řezu). V posledních letech byl obnoven zájem o teorii důkazů o GL, viz například Goré a Ramanayake (2008). Eliminace řezu vede k žádoucí vlastnosti podformule pro GL, protože všechny vzorce, které se objevují v důkazu bez ořezu, jsou podformule následných vzorců.

Nedávná důkazní teoretická zkoumání logiky prokazatelnosti založené na různých bezřezaných sekvenčních kalkulech viz (Negri 2005, 2014; Poggiolesi 2009). Negri představuje dva ekvivalentní značené sekvenční kameny pro GL a syntaktický důkaz eliminace řezu. I když úplná vlastnost podformule pro tyto kalkulu neplatí z důvodu označení, lze zjistit obvyklé důsledky vlastnosti podformule: Označený formalismus umožňuje přímý důkaz úplnosti, který lze použít ke stanovení rozhodovatelnosti a konečného modelu. vlastnost, což znamená, že jakýkoli vzorec, který není prokazatelný, má konečný protinávrh.

Zajímavým novým důkazem-teoretickým vývojem je Shamkanovovo rozšíření důkazních systémů se sekvenčním stylem umožněním kruhových důkazů (Shamkanov 2014). Vezměme si sekvenční systém pro K4, modální systém vyplývající z GL nahrazením axiomu GL slabším axiomem (Box A / rightarrow / Box / Box A) (axiom 4). Předpokládejme však, že otevřené hypotézy jsou povoleny za předpokladu, že stejná sekvence se vyskytuje přísně pod touto hypotézou ve stromu důkazu. Technicky formulované lze najít kruhovou derivaci z obyčejného derivačního stromu propojením každého z jeho neosiomatických listů se stejným vnitřním uzlem. Shamkanov (2014) dokázal, že výsledný systém je konzistentní a že navíc každá sekvence má obecně derivaci GL, a to pouze tehdy, má-li kruhový derivát K4. Kruhové důkazy také poskytují metodu, jak teoreticky prokázat, že Lyndonova interpolační věta platí pro GL. Standardní interpolace pro GL byla již dříve prokázána různými metodami (Boolos 1979; Smoryński 1978; Rautenberg 1983). (Pro více informací o Lyndonově interpolační větě pro logiku prvního řádu viz také teorii modelů prvního řádu).

2.2 Věta o pevném bodě

Hlavním „modálním“výsledkem logiky prokazatelnosti je věta s pevným bodem, kterou D. de Jongh a G. Sambin nezávisle prokázali v roce 1975 (Sambin 1976). Přestože je věta s pevným bodem formulována a prokázána přísně modálními metodami, má stále velký aritmetický význam. V zásadě se uvádí, že vlastní reference není ve skutečnosti nezbytná, v následujícím smyslu. Předpokládejme, že všechny výskyty výrokové proměnné (p) v daném vzorci (A (p)) spadají do působnosti operátora provability, například (A (p) = / neg / Box p), nebo (A (p) = / Box (p / rightarrow q)). Potom existuje vzorec (B), ve kterém se neobjeví (p), takže všechny výrokové proměnné, které se vyskytují v (B), se již objevují v (A (p)) a takové, že

) GL / vdash B / leftrightarrow A (B).)

Tento vzorec (B) se nazývá pevný bod (A (p)). Kromě toho je pevný bod jedinečný nebo přesněji, pokud existuje jiný vzorec (C) takový, že (GL / vdash C / leftrightarrow A (C)), pak musíme mít (GL / vdash B / leftrightarrow C). Většina důkazů v literatuře dává algoritmus, pomocí kterého lze vypočítat pevný bod (viz Smoryński 1985, Boolos 1993, Sambin a Valentini 1982, Lindström 2006). Zvláště krátký a jasný důkaz, jakož i velmi účinný algoritmus pro výpočet pevných bodů, lze nalézt v Reidhaar-Olson (1990).

Předpokládejme například, že (A (p) = / neg \, / Box p). Pak pevný bod vytvořený takovým algoritmem je (neg \, / Box / bot), a opravdu lze dokázat, že

) GL / vdash / neg \, / Box / bot / leftrightarrow / neg \, / Box (neg \, / Box / bot).)

Je-li to čteno aritmeticky, je směr zleva doprava pouze formalizovanou verzí Gödelovy druhé věty o neúplnosti: pokud dostatečně silná formální teorie (T), jako je Peano Aritmetika, neprokáže protiklad, pak to nelze prokázat v (T), že (T) neprokazuje rozpor. Dostatečně silné konzistentní aritmetické teorie tedy nemohou prokázat svou vlastní konzistenci. Přesněji se podíváme na vztah mezi logikou prokazatelnosti a aritmetikou v oddílu 4, ale za tímto účelem je třeba nejprve poskytnout další „modální“aspekt GL: sémantiku.

3. Možná světová sémantika a topologická sémantika

Logika Provability má vhodnou možnou světovou sémantiku, stejně jako mnoho jiných modálních logik. Připomínáme, že možný světový model (nebo Kripkeho model) je trojitý (M = / langle W, R, V / rangle), kde (W) je neprázdná sada možných světů, (R) je binární přístupnost vztahující se k (W) a (V) je ocenění, které přiřadí skutečnou hodnotu každé výrokové proměnné pro každý svět v (W). Pár (F = / langle W, R / rangle) se nazývá rám tohoto modelu. Pojem pravdy vzorce (A) v modelu (M) na světě (W), notace (M, w / models A), je definován induktivně. Opakujme pouze nejzajímavější klauzuli, klauzule pro operátora provability (Box):

[M, w / models / Box A / text {iff for every} w ', / text {if} wRw', / text {then} M, w '\ models A.)

Více informací o možné sémantice světů obecně najdete v logice vstupních modů.

3.1 Charakterizace a kvalita zvuku

Modální logika K platí ve všech modelech Kripke. Jeho rozšíření GL však není: musíme omezit třídu možných světových modelů na vhodnější. Řekněme, že vzorec (A) je platný v rámci (F), notace (F / models A), iff (A) platí ve všech světech modelů Kripke (M) na základě (F). Ukazuje se, že nová axioma (GL) logiky prokazatelnosti odpovídá podmínce na rámcích takto:

Pro všechny snímky (F = / langle W, R / rangle, F / models / Box (Box p / rightarrow p) rightarrow / Box p) iff (R) je tranzitivní a naopak opodstatněný.

Přechodnost je zde známá vlastnost, která pro všechny světy (w_1), (w_2), (w_3) v (W), pokud (w_1 Rw_2) a (w_2 Rw_3), poté (w_1 Rw_3). Vztah je naopak opodstatněný, pokud neexistují nekonečné vzestupné sekvence, tj. Sekvence tvaru (w_1 Rw_2 Rw_3 R / ldots). Všimněte si, že naopak dobře založené rámce jsou také irreflexivní, protože pokud (wRw), bude to mít za následek nekonečnou vzestupnou sekvenci (wRwRwR / ldots).

Výše uvedený výsledek korespondence okamžitě ukazuje, že GL je modálně zdravý s ohledem na třídu možných světových modelů na přechodně obrácených dobře založených rámcích, protože všechny axiomy a pravidla GL jsou na takových modelech platná. Otázkou je, zda platí i úplnost: například vzorec (Box A / rightarrow / Box / Box A), který je platný na všech tranzitivních rámcích, je v GL skutečně prokazatelný, jak bylo uvedeno v oddíle 1. Ale Je každý vzorec, který platí pro všechny tranzitivní, opačně založené rámce, prokazatelný také v GL?

3.2 Modální úplnost

K. Segerberg, který si neuvědomil aritmetický význam GL, prokázal v roce 1971, že GL je skutečně kompletní, pokud jde o tranzitivní obráceně dobře založené rámce; D. de Jongh a S. Kripke tento výsledek nezávisle prokázali. Segerberg ukázal, že GL je úplný i s ohledem na omezenější třídu konečných tranzitivních nerreflexivních stromů, což se později ukázalo jako velmi užitečné pro Solovayův důkaz aritmetické věty o úplnosti (viz oddíl 4).

Věty o modální spolehlivosti a úplnosti okamžitě vedou k rozhodovací proceduře, aby se zkontrolovala jakákoli modální formule (A), zda (A) vyplývá z GL nebo ne, hloubkovým průzkumem nejprve nereflexními tranzitivními stromy ohraničené hloubky. Když se podíváme na postup trochu přesněji, lze ukázat, že GL je rozhodující ve třídě výpočetní složitosti PSPACE, stejně jako dobře známá modální logika K, T a S4. To znamená, že existuje Turingův stroj, který vzhledem ke vzorci (A) jako vstup odpovídá, zda (A) vyplývá z GL nebo ne; velikost paměti, kterou Turingův stroj potřebuje pro svůj výpočet, je pouze polynom v délce (A). Jeden může ukázat, že rozhodovací problém pro GL (opět, jako je rozhodovací problém pro K, T a S4), je PSPACE - kompletní,ve smyslu, že všechny ostatní problémy v PSPACE nejsou o nic těžší než rozhodnutí, zda daný vzorec je věta o GL. (Viz Goré a Kelly (2007), kde je popis automatizovaného provizoru věty pro GL.)

Abychom získali ještě větší pohled na složitost, je třída P funkcí vypočítatelných v množství času polynomu v délce vstupu zahrnuta do PSPACE, což je zase zahrnuto do třídy EXPTIME funkcí vypočítatelných v exponenciálním čase (viz počítatelnost a složitost vstupu). Zůstává slavným otevřeným problémem, zda jsou tyto dva inkluze přísné, i když mnozí teoretici složitosti věří, že jsou. Některé další známé modální logiky, jako je epistemická logika se všeobecnými znalostmi, jsou rozhodující v EXPTIME, takže mohou být složitější než GL, v závislosti na otevřených problémech.

3.3 Selhání silné úplnosti

Mnoho známých modálních logik (S) je nejen kompletní s ohledem na příslušnou třídu rámců, ale dokonce i silně kompletní. Abychom vysvětlili silnou úplnost, potřebujeme pojem odvozitelnosti ze souboru předpokladů. Vzorec (A) je odvozitelný ze sady předpokladů (Gamma) v modální logice (S), zapsané jako (Gamma / vdash A), pokud je (A) v (Gamma) nebo (A) vyplývá z vzorců v (Gamma) a axiomů (S) aplikací Modus Ponens a Generalizačního pravidla. Zde lze pravidlo zobecnění použít pouze na derivace bez předpokladů (viz Hakli a Negri 2010).

Nyní je modální logika (S) silně kompletní, pokud pro všechny (konečné nebo nekonečné) sady (Gamma) a všechny vzorce (A):

Pokud je na příslušných (S) - rámcích pravda, (A) ve všech světech, ve kterých platí všechny vzorce (Gamma), pak (Gamma / vdash A) v logice (S).

Tato podmínka platí pro systémy jako K, M, K4, S4 a S5. Pokud je omezeno na omezené množiny (Gamma), výše uvedená podmínka odpovídá úplnosti.

Silná úplnost však neplatí pro logiku prokazatelnosti, protože selhává sémantická kompaktnost. Sémantická kompaktnost je vlastnost, která pro každou nekonečnou množinu vzorců (Gamma)

Pokud má každá konečná podmnožina (Delta) (Gamma) model na příslušném (S) - rámci, / \ / \ / Gamma) má také model na příslušném (S) -rám.

Jako příklad si vezměte nekonečnou sadu vzorců

) Gamma = { Diamond p_0, / Box (p_0 / rightarrow / Diamond p_1), / Box (p_1 / rightarrow / Diamond p_2), / Box (p_2 / rightarrow / Diamond p_3), / ldots, / Box (p_n / rightarrow / Diamond p_ {n + 1}), / ldots })

Pak pro každou konečnou podmnožinu (Delta) z (Gamma) lze konstruovat model na tranzitivním, obráceně dobře založeném rámci a svět v modelu, kde jsou všechny vzorce (Delta) skutečný. Takže pomocí modální spolehlivosti, GL neprokazuje (bot) z (Delta) pro žádný konečný (Delta / subseteq / Gamma), a a fortiori GL neprokazuje (bot) od (Gamma), protože jakýkoli důkaz o GL je konečný. Na druhé straně je snadné vidět, že neexistuje žádný model na tranzitivním, obráceně dobře podloženém rámci, kde v jakémkoli světě platí všechny vzorce (Gamma). Tedy (bot) sémanticky vyplývá z (Gamma), ale není z toho prokazatelné v GL, což je v rozporu s podmínkou silné úplnosti.

3.4 Topologická sémantika pro logiku prokazatelnosti

Jako alternativa k možné sémantice světů může být mnoha modálním logikám udělena topologická sémantika. Je zřejmé, že výroky lze interpretovat jako podmnožiny topologického prostoru. Je také snadné vidět, že výroková spojovací složka (wedge) odpovídá operaci set-theoretic (cap), zatímco (vee) odpovídá (cup), (neg) odpovídá množině teoretických doplňků a (rightarrow) odpovídá (subseteq). Modální logika, která obsahuje reflexní axiom (Box A / rightarrow A), se těší zvláště přirozené interpretaci modálních operátorů. Pro tyto logiky (Diamond) odpovídá operátorovi uzavření v topologickém prostoru, zatímco (Box) odpovídá interiéru. Abychom zjistili, proč jsou tyto interpretace vhodné,Všimněte si, že reflexní axiom odpovídá skutečnosti, že každá sada je zahrnuta ve svém uzávěru a každá sada obsahuje její vnitřek.

Logika prokazatelnosti však neprokazuje odraz, protože okamžité odrazení by vedlo k rozporu s axiomem (GL).

Logika zajišťovatelnosti proto vyžaduje jiný přístup. Na základě doporučení J. McKinseyho a A. Tarského (1944), L. Esakia (1981, 2003) zkoumal interpretaci (Diamond) jako odvozeného souboru operátor (d), který mapuje soubor (B) k souboru jejích mezních bodů (d (B)). Abychom vysvětlili důsledky této interpretace (Diamond), potřebujeme další dvě definice, jmenovitě koncepty husté samy o sobě a rozptýlené. Podmnožina (B) topologického prostoru se nazývá hustá sama o sobě, pokud (B / subseteq d (B)). Topologický prostor se nazývá rozptýlený, pokud nemá neprázdnou podmnožinu, která je sama o sobě hustá. Ordinály v intervalové topologii tvoří příklady rozptýlených prostorů. Esakia (1981) se ukázal jako důležitá korespondence: ukázal, že topologický prostor vyhovuje axiomu GL pouze tehdy, je-li prostor rozptýlen. Tato korespondence brzy vedla k výsledku, nezávisle nalezenému Abashidzem (1985) a Blassem (1990), že logika prokazatelnosti je úplná s ohledem na jakékoli ordinální (ge / omega ^ / omega).

V posledních letech zaznamenala topologická sémantika logiky prokazatelnosti skutečné oživení, zejména ve studii bimodální logiky prokazatelnosti.jpg

4. Logika zajišťování a Peano aritmetika

Od doby, kdy byl GL formulován, vědci uvažovali, zda je to pro formální teorie, jako je Peano Aritmetika (PA), dostatečné: prokazuje GL všechno o konceptu prokazatelnosti, který může být vyjádřen výrokovým modálním jazykem a může být prokázán v Peano aritmetice, nebo měly by být do GL přidány další zásady? Aby byl tento pojem adekvátnosti přesnější, definujeme realizaci (někdy nazývanou překlad nebo interpretace) jako funkci f, která přiřadí každému výrokovému atomu modální logiky větu aritmetiky, kde

• (f (bot) = / bot;)
• (f) respektuje logické spojky, například (f (B / rightarrow C) = (f (B) rightarrow f (C));) a
• (Box) je přeložen jako predikát provibility (Prov), takže (f (Box B) = / Prov (ulcorner f (B) urcorner).)

4.1 Aritmetická spolehlivost

Již na začátku 70. let bylo jasné, že GL je aritmeticky zdravý s ohledem na PA, formálně:

) text {If} GL / vdash A, / text {pak pro všechny realizace} f, / PA / vdash f (A).)

Abychom si trochu pochutnali na meta-matematice, nakreslíme si důkaz důkladnosti.

Důkazní skica aritmetické zvuku. PA skutečně dokazuje realizaci výrokových tautologií a prokazatelnost distribučního axiomu GL, do kterého se překládá

) PA / vdash / Prov (ulcorner A / rightarrow B / urcorner) rightarrow (Prov (ulcorner A / urcorner) rightarrow / Prov (ulcorner B / urcorner)))

pro všechny vzorce A a B, což je pouze Löbova druhá derivovatelnost (viz oddíl 1). Kromě toho se PA řídí Modusem Ponensem a překladem pravidla zobecnění:

) text {If} PA / vdash A, / text {then} PA / vdash / Prov (ulcorner A / urcorner),)

což je právě Löbův první derivovatelný stav. A konečně, překlad hlavního axiomu (GL) je v PA skutečně prokazatelný:

) PA / vdash / Prov (ulcorner / Prov (ulcorner A / urcorner) rightarrow A / urcorner) rightarrow / Prov (ulcorner A / urcorner).)

Toto je přesně formalizovaná verze Löbovy věty zmíněné v oddíle 1.

Podívejme se na náčrt důkazu Löbovy věty samotné z podmínek odvozitelnosti (důkaz formalizované verze je podobný). Důkaz je založen na Gödelově diagonalizačním lemmatu, které říká, že pro každý aritmetický vzorec (C (x)) existuje aritmetický vzorec (B) takový, že

) PA / vdash B / leftrightarrow C (ulcorner B / urcorner).)

Slovy, vzorec (B) říká: "Mám vlastnost (C)."

Doklad o lob věta:. Předpokládejme, že (PA / vdash / Prov (ulcorner A / urcorner) rightarrow A); musíme to ukázat (PA / vdash A). Podle diagonalizačního lemmatu existuje vzorec (B) takový, že

) PA / vdash B / leftrightarrow (Prov (ulcorner B / urcorner) rightarrow A).)

Z toho vyplývá Löbovy první a druhé podmínky odvozitelnosti a některé výrokové zdůvodnění

) PA / vdash / Prov (ulcorner B / urcorner) leftrightarrow / Prov (ulcorner / Prov (ulcorner B / urcorner) rightarrow A / urcorner).)

Takže opět podle Löbovy druhé podmínky

) PA / vdash / Prov (ulcorner B / urcorner) rightarrow (Prov (ulcorner / Prov (ulcorner B / urcorner) urcorner) rightarrow / Prov (ulcorner A / urcorner)).)

Na druhé straně Löbova třetí podmínka dává

) PA / vdash / Prov (ulcorner B / urcorner) rightarrow / Prov (ulcorner / Prov (ulcorner B / urcorner) urcorner),)

tím pádem

) PA / vdash / Prov (ulcorner B / urcorner) rightarrow / Prov (ulcorner A / urcorner).)

Spolu s předpokladem, že (PA / vdash / Prov (ulcorner A / urcorner) rightarrow A), to dává

) PA / vdash / Prov (ulcorner B / urcorner) rightarrow A.)

Konečně rovnice vytvořená diagonalizačním lemmatem znamená, že (PA / vdash B), takže (PA / vdash / Prov (ulcorner B / urcorner)), tedy

) PA / vdash A,)

podle přání.

Všimněte si, že nahrazení (bot) za (A) v Löbově větě, odvodíme, že (PA / vdash / neg \, / Prov (ulcorner / bot / urcorner)) implikuje (PA / vdash / bot), což je jen protiklad Gödelovy druhé věty o neúplnosti.

4.2 Aritmetická úplnost

Důležitým bodem v logice prokazatelnosti je R. Solovayova aritmetická věta o úplnosti z roku 1976, která ukazuje, že GL je pro Peano aritmetiku skutečně dostačující:

) GL / vdash A / text {pouze a pouze pro všechny realizace} f, / PA / vdash f (A).)

Tato věta v podstatě říká, že modální logika GL zachycuje vše, co může Peano Aritmetika pravdivě říci modálně o svém vlastním predikátu prokazatelnosti. Směr shora zleva doprava, aritmetická spolehlivost GL, je diskutován výše. Solovay se rozhodl ukázat další, mnohem obtížnější, směr kontrakcí. Jeho důkaz je založen na složitých sebepropagačních technikách a zde je možné uvést jen malý pohled.

Věta o modální úplnosti podle Segerberga byla důležitým prvním krokem v Solovayově důkazu aritmetické úplnosti GL s ohledem na Peano aritmetiku. Předpokládejme, že GL neprokáže modální vzorec (A). Pak, modální úplností, existuje konečný přechodný irreflexivní strom takový, že (A) je v kořenovém stromu tohoto stromu nepravdivý. Nyní Solovay vymyslel důmyslný způsob, jak simulovat takový konečný strom v jazyce Peano aritmetiky. Tak našel realizaci (f) od modálních vzorců po věty aritmetických, takže Peano aritmetika neprokazuje (f (A)).

Solovayova věta o úplnosti poskytuje alternativní způsob, jak konstruovat mnoho aritmetických vět, které nejsou v Peano Aritmetice dokázatelné. Například je snadné vytvořit možný světový model, který prokáže, že GL neprokazuje (Box p / vee / Box / neg \, p), takže podle Solovayovy věty existuje aritmetická věta (f (p)) takový, že Peano aritmetika neprokazuje (Prov (ulcorner f (p) urcorner) vee / Prov (ulcorner / neg \, f (p) urcorner))). Zejména to znamená, že ani (f (p)) ani (neg \, f (p)) nejsou v Peano Aritmetice prokazatelné; pro naopak, že (PA / vdash f (p)), pak podle Löbovy první podmínky a výrokové logiky, (PA / vdash / Prov (ulcorner f (p) urcorner) vee / Prov (ulcorner / neg \, f (p) urcorner)), což vede k rozporu a podobně, pokud to člověk předpokládá (PA / vdash / neg \, f (p)).

Solovayova věta je tak významná, protože ukazuje, že zajímavý fragment nerozhodnutelné formální teorie, jako je Peano aritmetika - konkrétně to, co aritmetika může vyjádřit výrokovými tvrzeními o svém vlastním predikátu prokazatelnosti - lze studovat pomocí rozhodné modální logiky, GL, s perspektivní možná sémantika světů.

5. Rozsah logiky prokazatelnosti

V této části jsou diskutovány některé nejnovější trendy ve výzkumu logiky prokazatelnosti. Jeden důležitý prvek se týká limitů rozsahu GL, kde hlavní otázkou je, pro které formální teorie, jiné než Peano Aritmetika, je GL vhodná výroková logika prokazatelnosti? Dále diskutujeme některé zobecnění výrokové logiky prokazatelnosti ve výraznějších modálních jazycích.

5.1 Hranice

V posledních letech zkoumali logici mnoho dalších aritmetických systémů, které jsou slabší než Peano aritmetika. Tito logici se často inspirovali otázkami spočívajícími ve výpočtu, například studiem funkcí, které lze vypočítat v polynomu. Částečně odpověděli na otázku: „Pro které teorie aritmetiky stále platí Solovayova aritmetická věta o úplnosti (s ohledem na vhodný predikát prokazatelnosti)?“K projednání této otázky jsou zapotřebí dva koncepty. (Delta_0) - vzorce jsou aritmetické vzorce, ve kterých jsou všechny kvantifikátory ohraničeny termínem, například

) forall y / le / bs / bs 0 \: / forall z / le y \: / forall x / le y + z \: (x + y / le (y + (y + z)))),)

kde (bs) je nástupnický operátor („(+ 1)“). Aritmetická teorie (I / Delta_0) (kde je zkratka pro „indukci“) je podobná Peano Aritmetice, kromě toho, že umožňuje menší indukci: indukční schéma

[A (0) wedge / forall x \, (A (x) rightarrow A (bs x)) rightarrow / forall x \, A (x))

je omezeno na (Delta_0) - vzorce (A).

Jak zdůraznil De Jongh a další (1991), aritmetická úplnost jistě platí pro teorie (T), které splňují následující dvě podmínky:

1. (T) prokazuje indukci pro (Delta_0) - vzorce a (T) dokazuje EXP, vzorec vyjadřující, že pro všechny (x) existuje její síla (2 ^ x). Ve standardnějším zápisu: (T) rozšiřuje (I / Delta_0) + EXP;
2. (T) neprokazuje falešné věty tvaru (existuje x \, A (x)), s (A (x)) a (Delta_0) - vzorcem.

U takových teorií, aritmetická spolehlivost a úplnost držení GL, za předpokladu, že (Box) se překládá na (Prov_T), přirozená predikovatelnost predikuje s ohledem na dostatečně jednoduchou axiomatizaci (T). Tedy pro modální věty (A):

) GL / vdash A / text {pouze a pouze pro všechny realizace} f, T / vdash f (A).)

Zatím není jasné, zda podmínka 1 dává nižší meze rozsahu logiky prokazatelnosti. Například je stále otevřenou otázkou, zda GL je logika proviritelnosti (I / Delta_0 + / Omega_1), teorie, která je poněkud slabší než (I / Delta_0) + EXP v tom (Omega_1) je axiom, který tvrdí, že pro všechny (x) existuje jeho síla (x ^ { log (x)}). Logika zabezpečitelnosti GL je aritmeticky spolehlivá s ohledem na (I / Delta_0 + / Omega_1), ale s výjimkou některých dílčích výsledků, které provedli Berarducci a Verbrugge (1993), aritmetické realizace konzistentní s (I / Delta_0 + / Omega_1) pro omezené třídy vět odpovídající GL, zůstává otázka otevřená. Jeho odpověď může záviset na otevřených problémech v teorii výpočetní složitosti.

Výše uvedený výsledek De Jongh et al. ukazuje silnou vlastnost logiky prokazatelnosti: pro mnoho různých aritmetických teorií GL zachycuje přesně to, co tyto teorie říkají o svých vlastních predikátech prokazatelnosti. Zároveň je to slabost. Například logika výrokové prokazatelnosti neukazuje na žádné rozdíly mezi těmi teoriemi, které jsou konečně axiomatizovatelné, a těmi, které nejsou.

5.2 Logika interpretovatelnosti

Aby vědci dokázali mluvit modálním jazykem o důležitých rozdílech mezi teoriemi, rozšířili logiku prokazatelnosti mnoha různými způsoby. Zmiňme několik. Jedním rozšířením je přidání binární modality (interprets), kde pro danou aritmetickou teorii (T) je modální věta (A / interprets B) označena jako (T + B)) je interpretovatelný v (T + A)”(Švejdar, 1983). De Jongh a Veltman (1990) zkoumali modální sémantiku pro několik logik interpretovatelnosti, zatímco De Jongh a Visser (1991) se ukázali jako explicitní vlastnost s pevným bodem pro ty nejdůležitější. Visser charakterizoval logiku interpretovatelnosti nejběžnějších konečně axiomatizovaných teorií a Berarducci a Shavrukov nezávisle charakterizovali jeden pro PA, což není konečně axiomatizovatelné. Zdá se, že opravdu,logika interpretovatelnosti konečně axiomatizovatelných teorií se liší od logiky interpretovatelnosti Peano Aritmetiky (viz Montagna 1987; Visser 1990, 1998; Berarducci 1990, Shavrukov 1988; Joosten a Visser 2000).

5.3 Propoziční kvantifikátory

Dalším způsobem, jak rozšířit rámec logiky výrokové prokazatelnosti, je přidání výrokových kvantifikátorů, aby bylo možné vyjádřit principy, jako je Goldfarbova:

) forall p \, / forall q \, / existuje r \: / Box ((Box p / vee / Box q) leftrightarrow / Box r),)

říkat, že pro nějaké dvě věty existuje třetí věta, která je prokazatelná, a to pouze tehdy, je-li jedna z prvních dvou vět prokazatelná. Tento princip je prokazatelný v Peano Aritmetice (viz např. Artemov a Beklemishev 1993). Soubor vět GL s výrokovými kvantifikátory, které jsou aritmeticky platné, se ukazuje jako nerozhodnutelný (Shavrukov 1997).

5.4 Japaridzeho bimodální a polymodální logika prokazatelnosti

Japaridzeho (1988) bimodální logika GLB má dva (Box) - operátory podobné provability, označené ([0]) a ([1]), s jejich duálními (Diamond) - operátory podobnými (langle 0 / rangle) a (langle 1 / rangle). V Japaridze interpretaci, jeden může myslet na ([0]) jak kandidovat na standardní predikát dokazatelnosti v Peano aritmetice. Na druhé straně, ([1]) odpovídá silnějšímu predikátu prokazatelnosti, konkrétně (omega) - provabilty.

Definujme pojmy, které jsou potřebné k pochopení této zamýšlené interpretace GLB. Aritmetická teorie (T) je definována jako (omega) - konzistentní pouze tehdy, pokud pro všechny vzorce A s volnou proměnnou (x), (T / vdash / neg \, A (I_n)) pro všechny (n) znamená, že (T / not / vdash / existuje x \, A (x)); zde, (I_n) je číslice (n), tj. termín (bs / bs / ldots / bs 0) s (n) výskyty nástupnického operátora (bs). Peano aritmetika (PA) je nejznámějším příkladem (omega) - konzistentní teorie (viz také Gödelovy věty o neúplnosti). Nyní nechme PA (^ +) aritmetickou teorii, jejíž axiomy jsou axymy PA spolu se všemi větami (forall x \, / neg \, A (x)) tak, že pro každý (n), PA (vdash / neg \, A (I_n)). Nyní (omega) - prokazatelnost je jednoduše prokazatelnost v PA (^ +),takže se jedná o dvojici konzistence (omega).

Logaritimu bimodální prokazatelnosti Japaridze GLB lze axiomatizovat axiomy a pravidly GL (viz oddíl 2), formulované samostatně pro [0] a [1]. Kromě toho má GLB dva smíšené axiomy, jmenovitě:) tag {Monotonicity} [0] A / rightarrow [1] A)) tag {(Pi ^ 0_1) - úplnost} langle 0 / rangle A / rightarrow [1] langle 0 / rangle A) Japaridzeho logika je rozhodující a má rozumnou sémantiku podle Kripkeho a je aritmeticky spolehlivá a úplná s ohledem na Peano aritmetiku (Japaridze 1988, Boolos 1993).

Polymodální analog Japaridzeho GLB, pojmenovaný GLP, získal v posledních letech velkou pozornost. GLP má nekonečně mnoho (Box) - operátorů providibility, označených boxy ([n]) pro každé přirozené číslo (n), s jejich duálními (Diamond) - operátory (langle n / rangle). Znovu, jeden může myslet na ([0]) jako kandidáta na standardní predikát proveditelnosti v Peano Arithmetic, (langle 1 / rangle) pro (omega) - provibility, atd. GLP byl axiomatizován počínaje axiomy a pravidly GL (viz oddíl 2), formulovanými zvlášť pro každý ([n]). Navíc GLP má tři smíšená axiomatická schémata, jmenovitě formulována Beklemishevem (2010): [m] A / rightarrow [n] A, / mbox {for} m / leq n)) langle k / zazvonit A / rightarrow [n] langle k / rangle A, / mbox {for} k / lt n) [m] A / rightarrow [n] [m] A, / mbox {for} m / leq n)

GLP byla nedávno vybavena sémantikou Kripke, ve vztahu k níž je úplná, a bylo také prokázáno, že je aritmeticky úplná s ohledem na Peano aritmetiku (viz Beklemishev 2010a, 2011a). Stejně jako u GL je rozhodovacím problémem pro GLP PSPACE-kompletní (Shapirovsky 2008), zatímco jeho uzavřený fragment je rozhodnutelný pro polynomiální čas (Pakhomov 2014).

V posledních letech bylo prokázáno mnoho výsledků o polymodální logice GLP silných predikátů prokazatelnosti. Zde sledujte některá zvláště plodná témata:

• uzavřený fragment GLP (viz Ignatiev 1993; Beklemishev, Joosten a Vervoort 2005);
• GLP a důkaz-teoretické ordináře (Beklemishev 2004);
• Interpolační věty pro GLP (viz Beklemishev 2010b, Shamkanov 2011);
• Vztah mezi topologickou sémantikou a teorií množin, mimo jiné zejména velké kardinální axiomy a stacionární reflexe (viz Beklemishev 2011b; Beklemishev a Gabelaia 2013, 2014; Fernández-Duque 2014).

5.5 Predikátová logika prokazatelnosti

Nakonec lze samozřejmě studovat predikátovou logiku prokazatelnosti. Jazyk je jazyk predikátové logiky bez funkčních symbolů spolu s operátorem (Box). Zde se situace stává mnohem složitější než v případě výrokové logiky prokazatelnosti. Začneme tím, že přímá kvantifikovaná verze GL nemá vlastnost s pevným bodem, není úplná s ohledem na žádnou třídu Kripke rámců a není aritmeticky úplná s ohledem na Peano Arithmetic (Montagna, 1984). Potom vyvstává otázka: Existuje nějaká pěkně axiomatizovaná predikátová logika prokazatelnosti, která je adekvátní a přesně prokazuje platné zásady prokazatelnosti? Odpověď je bohužel nezvyklé ne:Vardanyan (1986) na základě myšlenek Artemova (1985a) prokázal, že množina vět logiky predikátové prokazatelnosti, jejichž všechny realizace jsou prokazatelné v PA, není ani rekurzivně vyčíslitelná, ale (Pi ^ 0_2) - úplná, nemá tedy rozumnou axiomatizaci. Visser a De Jonge (2006) ukázali, že nedochází k úniku z Vardanjanovy věty prokazováním zobecnění: Pro širokou škálu aritmetických teorií (T) je množina vět predikátové logiky prokazatelnosti, jejichž všechny realizace jsou prokazatelné v (T) se ukázalo být (Pi ^ 0_2) - také kompletní. Pro širokou škálu aritmetických teorií (T) se sada vět predikátové logiky prokazatelnosti, jejichž všechny realizace jsou prokazatelné v (T), je také (Pi ^ 0_2) - také kompletní. Pro širokou škálu aritmetických teorií (T) se sada vět predikátové logiky prokazatelnosti, jejichž všechny realizace jsou prokazatelné v (T), je také (Pi ^ 0_2) - také kompletní.

5.6 Další zobecnění

Ve výše uvedené diskusi není mnoho dalších důležitých prvků výzkumu logiky prokazatelnosti a jejích rozšíření. Zainteresovaný čtenář se zaměřuje na následující oblasti:

• logika prokazatelnosti intuicionistické aritmetiky (viz Troelstra 1973; Visser 1982, 1999; Iemhoff 2000, 2001, 2003; Visser 2002, 2008);
• klasifikace logiky prokazatelnosti (viz Visser 1980, Artemov 1985b, Beklemishev 1989, Beklemishev et al. 1999);
• Rosserovy objednávky a urychlení důkazů (viz Guaspari a Solovay 1979, Švejdar 1983, Montagna 1992);
• několik druhů bimodální logiky prokazatelnosti s operátory prokazatelnosti pro různé teorie (viz Carlson 1986; Smoryński 1985; Beklemishev 1994, 1996);
• logika prokazatelnosti pro standardní prokazatelnost kombinovaná s neobvyklými predikáty predikovatelnosti externě spočívajícími PA, jako jsou Fefermanovy a Parikhovy predikáty predikovatelnosti a pomalé predikáty predikovatelnosti (viz Montagna 1978; Visser 1989; Shavrukov 1994; Lindström 1994, 2006; Henk a Pakhomov 2016 (Jiné internetové zdroje));
• logika explicitních důkazů (viz Artemov 1994, 2001; Artemov a Montagna 1994; Artemov a Iemhoff 2007);
• aplikace logiky prokazatelnosti v teorii důkazů (viz Beklemishev 1999, 2004, 2005, 2006);
• logika pozitivní prokazatelnosti a reflexe počtu (viz Beklemishev 2012, 2014; Dashkov 2012);
• zobecnění polymodální logiky prokazatelnosti GLP, konkrétně logiky prokazatelnosti s transfinitely mnoha způsoby (viz Beklemishev et al. 2014; Fernández-Duque a Joosten 2013a, 2013b, 2013 (Jiné internetové zdroje), 2014);
• vztahy mezi logikou prokazatelnosti a (mu) - výpočtem (viz van Benthem 2006, Visser 2005, Alberucci a Facchini 2009); a
• provergenční algebry, nazývané také diagonalizovatelné algebry nebo magariské algebry (viz Magari 1975a, 1975b; Montagna 1979, 1980a, 1980b; Shavrukov 1993a, 1993b, 1997; Zambella 1994; poslední výsledky jejich základních teorií viz Pakhomov 2012, 2014 (Other Internet) Zdroje), 2015 (Jiné internetové zdroje)).

Beklemishev a Visser (2006) navrhli pro čtenáře, který by chtěl přispět k oblasti prokazatelnosti a její zobecnění, anotovaný seznam zajímavých otevřených problémů.

6. Filozofický význam

I když je výroková logika prokazatelnosti modální logikou s jakýmsi operátorem „nutnosti“, vydrží Quineovu (1976) kontroverzní kritiku modálních pojmů jako nesrozumitelnou, a to již kvůli své jasné a jednoznačné aritmetické interpretaci. Například, na rozdíl od mnoha jiných modálních logik, formule s vnořenými modalitami, jako je (Box / Diamond p / rightarrow / Box / bot), nejsou problematické, ani neexistují žádné spory ohledně toho, které by měly být tautologiemi. Logika prokazatelnosti ve skutečnosti zahrnuje všechna desiderata, která Quine (1953) stanovila pro syntaktická léčení modality.

Quineovy hlavní šipky směřovaly k logice predikátů modů, zejména ke konstrukci vět, které obsahují modální operátory v rámci kvantifikátorů („kvantifikace v“). V predikátové logice prokazatelnosti, kde se však kvantifikátory pohybují nad přirozenými čísly, mají modality de dikto i de re přímočaré interpretace, na rozdíl od případu jiné modální logiky (viz poznámka k rozlišování de dicto / de re). Například vzorce jako

) forall x \, / Box \, / existuje y \, (y = x))

nejsou vůbec problematické. Pokud je číslo (n) přiřazeno k (x), pak (Box \, / existuje y \, (y = x)) platí s ohledem na toto přiřazení, pokud věta (existuje) y \, (y = I_n)) je prokazatelný v Peano Aritmetice; zde, (I_n) je číslice (n), tj. termín (bs / bs / ldots / bs 0) s (n) výskyty nástupnického operátora (bs). Tato věta platí pro všechny (n) ve standardním modelu přirozených čísel a (forall x \, / Box \, / existuje y \, (y = x)) je dokonce možné prokázat v Peano Aritmetice.

Mimochodem, Barcan Formula

) forall x \, / Box \, A (x) rightarrow / Box \, / forall x \, A (x))

není pravdivá pro celá čísla, natož prokazatelná (například vezměte pro (A (x)) vzorec "(x) nekóduje důkaz (bot)")). Je to obrácené

) Box \, / forall x \, A (x) rightarrow / forall x \, / Box \, A (x))

na druhé straně je prokazatelný v Peano Aritmetice pro jakýkoli vzorec (A).

Logika zajišťovatelnosti má velmi odlišné principy od ostatních modálních logik, dokonce i těch, které mají zdánlivě podobný účel. Například zatímco logika prokazatelnosti zachycuje prokazatelnost ve formálních teoriích aritmetiky, epistemická logika se snaží popsat znalosti, které lze považovat za druh neformální prokazatelnosti. V mnoha verzích epistemické logiky je jedním z nejdůležitějších principů axiom pravdy (5):

) mbox {S5} vdash / Box A / rightarrow A, (text {pokud někdo ví} A, / text {pak} A / text {je pravda}).)

Analogický princip jednoznačně neplatí pro GL: konec konců,) text {if} GL / vdash / Box A / rightarrow A, / text {then} GL / vdash A.)

Zdá se tedy zavádějící porovnávat sílu obou pojmů nebo je kombinovat do jednoho modálního systému. Možná je formální prokazatelnost v jistém smyslu silnější představou než neformální prokazatelnost, ale rozhodně to není aritmetická pravda nebo platnost, ani jiný směr. Diskuse o důsledcích Gödelových teorémů neúplnosti někdy zahrnují zmatek kolem pojmu prokazatelnosti, což vede k tvrzením, že lidé by mohli porazit formální systémy v „vědění“teorémů (viz Davis (1990, 1993) pro dobré diskuse o takových tvrzeních).

Celkově vzato, formální prokazatelnost je přesně definovaný koncept, mnohem více než pravda a znalosti. Sebezkazování v rámci prokazatelnosti tedy nevede ke sémantickým paradoxům, jako je lhář. Místo toho to vedlo k některým nejdůležitějším výsledkům matematiky, jako jsou Gödelovy věty o neúplnosti.

Bibliografie

Obecné odkazy na logiku prokazatelnosti

• Artemov, SN, 2006, „Modal Logic in Mathematics,“v P. Blackburn, et al. (eds.), Handbook of Modal Logic, Amsterdam: Elsevier, s. 927–970.
• Artemov, SN a LD Beklemishev, 2004, „Providence Logic“, v Handbook of Philosophical Logic, Druhé vydání, D. Gabbay a F. Guenthner, edice., Svazek 13, Dordrecht: Kluwer, s. 229–403.
• Boolos, G., 1979, Unprovability of Consistency: An Esay in Modal Logic, Cambridge: Cambridge University Press.
• –––, 1993, The Logic of Provability, New York and Cambridge: Cambridge University Press.
• de Jongh, DHJ a G. Japaridze, 1998, „The Logic of Provability“, v Handbook of Proof Theory, Buss, SR (ed.), Amsterdam: North-Holland, str. 475-546.
• Lindström, P., 1996, „Provability Logic-A Short Introduction“, Theoria, 52 (1–2): 19–61.
• Segerberg, K., 1971, Esej in Classical Modal Logic, Uppsala: Filosofiska Föreningen och Filosofiska Institutionen vid Uppsala Universitet.
• Švejdar, V., 2000, „On Provision Logic,“, Nordic Journal of Philosophy, 4: 95–116.
• Smoryński, C., 1985, Self-Reference and Modal Logic, New York: Springer-Verlag.
• Verbrugge, R. 1996, „Provability“v Encyclopedia of Philosophy (Supplement), DM Borchert (ed.), New York: Simon a Schuster MacMillan, str. 476–478.
• Visser, A., 1998, „Provability Logic“, v Routledge Encyclopedia of Philosophy, W. Craig (ed.), London: Routledge, pp. 793–797.

Dějiny

• van Benthem, JFAK, 1978, „Čtyři paradoxy“, Journal of Philosophical Logic, 7 (1): 49–72.
• Boolos, G. a G. Sambin, 1991, „Provability: Vznik matematické modality“, Studia Logica, 50 (1): 1–23.
• Gödel, K., 1933, „Eine Interpretation des intuitionistischen Aussagenkalküls,“Ergebnisse eines Mathematischen Kolloquiums, 4: 39–40; překlad „Interpretace intuitionistického prozatímního počtu“, v K. Gödel, Collected Works, S. Feferman et al. (eds.), Oxford a New York: Oxford University Press, svazek 1, 1986, s. 300–302.
• –––, 1931, „Über Formal Unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme I,“Monatshefte für Mathematik und Physik, 38: 173–198.
• Halbach, V. a A. Visser, 2014, „The Henkin Sentence“, v M. Mazano, I. Sain a E. Alonso (eds.), Život a dílo Leon Henkin: Eseje o jeho příspěvcích, Dordrecht: Springer International Publishing, s. 249–263.
• Henkin, L., 1952, „Problém týkající se zajišťovatelnosti“, Journal of Symbolic Logic, 17: 160.
• –––., 1954, „Recenze G. Kreisela: K problému Leon Henkin's“, Journal of Symbolic Logic, 19 (3): 219–220.
• Hilbert, D. a P. Bernays, 1939, Grundlagen der Mathematik, svazek 2, Berlín / Heidelberg / New York: Springer-Verlag.
• Kreisel, G., 1953, „O problému Leon Henkin's“, Indagationes Mathematicae, 15: 405–406.
• Lewis, CI, 1912, „Implikace a algebra logiky“, Mind, 21: 522–531.
• Löb, MH, 1955, „Řešení problému Leon Henkin,“Journal of Symbolic Logic, 20: 115–118.
• Macintyre, AJ a H. Simmons, 1973, „Gödelova diagonalizační technika a související vlastnosti teorií“, Colloquium Mathematicum, 28: 165–180.
• Magari, R., 1975a, „Diagonalizovatelné algebry“, Bollettino della Unione Mathematica Italiana, 12: 117–125.
• –––, 1975b „Reprezentace a teorie dvojnosti pro diagonalizovatelné algebry“, Studia Logica, 34 (4): 305–313.
• Smiley, TJ, 1963, „Logický základ etiky“, Acta Philosophica Fennica, 16: 237–246.
• Smoryński, C., 1991, „The Self-reference: Löb's theorem“, v T. Drucker (ed.), Perspectives on History of Mathematical Logic, Basel: Birkhäuser, pp. 110–133.

Cut-eliminace pro logiku prokazatelnosti

• Goré, R. a R. Ramanayake, 2008, „Valentiniho Cut-Eliminace pro logiku zajišťovatelnosti vyřešen“, v Advance in Modal Logic Volume 7, C. Areces a R. Goldblatt (eds.), London: College Publications, s. 67 -86.
• Negri, S., 2005, „Proof Analysis in Modal Logic,“Journal of Philosophical Logic, 50: 507–544.
• Negri, S., 2014, „Důkazy a kontramodely v neklasické logice“, Logica Universalis, 8 (1): 25–60.
• Poggiolesi, F., 2009, „Čistě syntaktický a neříznutý sekvenční počet pro modální logiku zajištění“, Recenze Symbolické logiky, 2 (4): 593–611.
• Rautenberg, W., 1983, „Modal Tableau Calculi and Interpolation,“Journal of Philosophical Logic, 12 (4): 403–423.
• Sambin, G., a S. Valentini, 1982, „Modální logika zajišťovatelnosti. Sekvenční přístup, “Journal of Philosophical Logic, 11 (3): 311–342.
• Shamkanov, DS, 2011, „Interpolační vlastnosti pro zajišťovací logiku GL a GLP,“Sborník Steklovova matematického ústavu, 274 (1): 303–316.
• ––– 2014, „Kruhové důkazy pro logiku zabezpečitelnosti Gödel-Löb“, Mathematical Notes, 96 (4): 575–585.
• Smoryński, C., 1978, „Bethova věta a samoreferenční věty“, Studie logiky a základy matematiky, 96: 253–261.
• Valentini, S., 1983, „Modální logika zajišťování: Cut-Elimination“, Journal of Philosophical Logic, 12: 471–476.

Věta s pevným bodem

• de Jongh, DHJ a F. Montagna, 1988, „Proveded Fixed Points“, Mathematical Logic Quarterly, 34 (3): 229-250.
• Lindström, P., 2006, „Poznámka k některým konstrukcím s pevným bodem v logice zajištění“, Journal of Philosophical Logic, 35 (3): 225–230.
• Reidhaar-Olson, L., 1990, „Nový důkaz věty pevné logiky zajišťovací logiky“, Notre Dame Journal of Formal Logic, 31 (1): 37–43.
• Sambin, G., 1976, „Efektivní věta s pevným bodem v intuitivních diagonalizovatelných algebrách (Algebraizace teorií, které vyjadřují teorii, IX),“Studia Logica 35: 345–361.
• Sambin, G., a S. Valentini, 1982, „Modální logika zajišťovatelnosti. Sekvenční přístup, “Journal of Philosophical Logic, 11 (3): 311–342.

Možná světová sémantika a topologická sémantika

• Abashidze, M., 1985, „Ordinální úplnost Gödel-Löbova modálního systému“(v ruštině) v intenční logice a logické struktuře teorií, Tbilisi: Metsniereba, s. 49–73.
• Aiello, M., I. Pratt-Hartmann a J. van Benthem (eds.), 2007, Handbook of Spatial Logics, Berlin: Springer-Verlag.
• Beklemishev, LD 2009, „Řádná úplnost bimodální logiky zajišťování GLB“, v mezinárodním Tbilisi Symposium o logice, jazyce a výpočtu, Berlín: Springer-Verlag, s. 1–15.
• Beklemishev, LD, G. Bezhanishvili a T. Icard, 2009, „O topologických modelech GLP“, v R. Schindler (ed.), Způsoby důkazní teorie (Ontos Mathematical Logic: Volume 2), Frankfurt: Ontos Verlag, str. 133–153.
• Blass, A., 1990, „Infinitary Combinatorics and Modal Logic,“Journal of Symbolic Logic, 55 (2): 761–778.
• Esakia, L., 1981, „Diagonální konstrukce, Löbův vzorec a Cantorovy rozptýlené prostory“(v ruštině), ve studiích logiky a sémantiky, Z. Mikeladze (ed.), Tbilisi: Metsniereba, s. 128–143.
• ––– 2003, „Intuitionistická logika a modalita prostřednictvím topologie“, Annals of Pure and Applied Logic, 127: 155–170.
• Goré, R., 2009, „Strojová kontrola důkazní teorie: Aplikace logiky na logiku“, v ICLA '09: Sborník z 3. indické konference o logice a jejích aplikacích, Berlín: Springer-Verlag, s. 23–35.
• Goré, R. a J. Kelly, 2007, „Automatické vyhledávání důkazů v Gödel-Löb Provability Logic“, British Logic Colloquium 2007, k dispozici na adrese https://www.dcs.bbk.ac.uk/~roman/blc/.
• Hakli, R. a S. Negri, 2012, „Selže dedukční věta pro modální logiku?“, Synthese 187 (3): 849–867.
• Icard, TF III, 2011, „Topologická studie uzavřeného fragmentu GLP“, Journal of Logic and Computation, 21 (4): 683–696; poprvé publikováno online 2009, doi: 10.1093 / logcom / exp043
• Japaridze, GK, 1986, Modální logické prostředky zkoumání zajišťovatelnosti, diplomová práce (v ruštině), Moskva.
• McKinsey, JCC a A. Tarski, 1944, „Algebra topologie“, Annals of Mathematics, 45: 141–191.

Poskytovatelnost a peano aritmetika

• Davis, M., 1958, Computability and Unsolvability, New York, McGraw-Hill; dotisknut dodatkem, New York, Dover Publications 1983.
• Feferman, S., 1960, „Aritmetizace metamatematiky v obecném prostředí“, Fundamenta Mathematicae, 49 (1): 35–92.
• Hájek, P. a P. Pudlák, 1993, Metamathematics of the First Order Aritmetic, Berlin: Springer-Verlag.
• Solovay, RM, 1976, „Interpretace interpretace modální logiky“, Israel Journal of Mathematics, 25: 287–304.

Rozsah logiky prokazatelnosti: hranice

• Berarducci, A. a R. Verbrugge, 1993, „O logice zajišťování ohraničené aritmetiky“, Annals of Pure and Applied Logic, 61: 75–93.
• Buss, SR, 1986, Bounded Aritmetic, Neapol: Bibliopolis.
• de Jongh, DHJ, M. Jumelet a F. Montagna, 1991, „O důkazu Solovayovy věty“, Studia Logica, 50 (1): 51–70.

Logika interpretovatelnosti

• Berarducci, A., 1990, „Interpretovatelná logika peano aritmetiky“, Journal of Symbolic Logic, 55: 1059–1089.
• de Jongh, DHJ a F. Veltman, 1990, „Logika zajišťování relativní interpretovatelnosti“, v PP Petkov (ed.), Matematická logika: Sborník letní školy Heyting 1988 ve Varně, Bulharsko, Boston: Plenum Press, pp. 31–42.
• de Jongh, DHJ a A. Visser, 1991, „Explicitní pevné body v interpretační logice“, Studia Logica, 50 (1): 39–49.
• Joosten, JJ a Visser, A., 2000, „Logika interpretace všech rozumných aritmetických teorií“, Erkenntnis, 53 (1-2): 3–26.
• Montagna, F., 1987, „Provability in Finite Subtheories of PA“, Journal of Symbolic Logic, 52 (2): 494–511.
• Shavrukov, V. Yu., 1988, „Logika relativní interpretovatelnosti nad peano aritmetikou“, Technická zpráva č. 5, Moskva: Matematický ústav Steklov (v ruštině).
• Švejdar, V., 1983, „Modální analýza zobecněných Rosserových vět,“Journal of Symbolic Logic, 48: 986–999.
• Visser, A., 1990, „Interpretability Logic“, v PP Petkov (ed.), Mathematical Logic: Sborník letní školy Heyting 1988 ve Varně, Bulharsko, Boston: Plenum Press, str. 175–209.
• –––, 1998, „Přehled logiky interpretace“, v M. Kracht et al. (eds.), Advances in Modal Logic (Svazek 1), Stanford: CSLI Publications, pp. 307–359.

Propoziční kvantifikátory

• Artemov, SN a LD Beklemishev, 1993, „O Propozičních kvantifikátorech v logice zajišťování“, Notre Dame Journal of Formal Logic, 34: 401–419.
• Shavrukov, V. Yu., 1997, „Undecidability in Diagonalizable Algebras“, Journal of Symbolic Logic, 62: 79–116.

Japaridzeho bimodální a polymodální prokazatelnost

• Beklemishev, LD, 2004, „Algebry a provizorní ordinály, já,“, Annals of Pure and Applied Logic, 128: 103–123.
• –––, 2010a, „Kripkeho sémantika pro zajišťovací logiku GLP,“Annals of Pure and Applied Logic, 161 (6): 756–774.
• –––, 2010b „O Craigově interpolaci a vlastnostech GLP s pevným bodem“, S. Feferman et al. (eds.), Důkazy, kategorie a výpočty (Tributes, 13), London: College Publications, pp. 49–60.
• –––, 2011a, „Zjednodušený důkaz o aritmetické teorii úplnosti pro logiku SLP,“Sborník Steklov Institute of Mathematics, 274 (1): 25–33.
• –––, 2011b, „Obyčejná úplnost logiky GLB v bimodální dostupnosti“, v N. Bezhanishvili et al. (eds.), Logic, Language and Computation, 8. International Tbilisi Symposium TbiLLC 2009 (Poznámky k přednáškám z informatiky: Svazek 6618), Heidelberg: Springer, s. 1–15.
• Beklemishev, LD, a D. Gabelaia, 2013, „Topologická úplnost logiky SLP,“Annals of Pure and Applica Logic, 164 (12): 1201–1223.
• ––– 2014, „Topologické interpretace logiky zabezpečitelnosti“, v G. Bezhanishvili (ed.), Leo Esakia o dualitě v modální a intuitivní logice (vynikající příspěvky k logice: svazek 4), Heidelberg: Springer, s. 257– 290.
• Beklemishev, LD, J. Joosten a M. Vervoort, 2005, „Finální zpracování uzavřeného fragmentu logiky zabezpečitelnosti Japaridze,“Journal of Logic and Computation, 15 (4): 447–463.
• Fernández-Duque, D. a JJ Joosten, 2014, „Dobré objednávky na Transfinite Japaridze Algebra,“Logický deník IGPL, 22 (6): 933–963.
• Ignatiev, KN, 1993, „O predikátech silné dostupnosti a přidružené modální logice“, Journal of Symbolic Logic, 58: 249-290.
• Japaridze, G., 1988, „Polymodální zajišťovací logika“, v intenzivní logice a logické struktuře teorií: materiál ze čtvrtého sovětsko-finského sympozia o logice, Telavi, s. 16–48.
• Pakhomov, FN, 2014, „O složitosti uzavřeného fragmentu logiky zabezpečitelnosti Japaridze,“Archiv pro matematickou logiku, 53 (7-8): 949–967.

Predikátová logika prokazatelnosti

• Artemov, SN, 1985a, „Nonaritmeticita pravdy predikátové logiky zabezpečitelnosti“, Doklady Akademii Nauk SSSR, 284: 270–271 (v ruštině); Anglický překlad v sovětské matematice Doklady, 32: 403–405.
• McGee, V. a G. Boolos, 1987, „Stupeň sady vět predikátové logiky zajišťování, které jsou pravdivé při každé interpretaci“, Journal of Symbolic Logic, 52: 165–171.
• Vardanyan, VA, 1986, „Aritmetické komplexy predikátové logiky zabezpečitelnosti a jejich fragmenty“, Doklady Akademii Nauk SSSR, 288: 11–14 (v ruštině); Anglický překlad v sovětské matematice Doklady, 33: 569–572.
• Visser, A. a M. de Jonge, 2006, „No Escape from Vardanyan's theorem“, Archive of Mathematical Logic, 45 (5): 539–554.

Další zobecnění

• Alberucci, L. a A. Facchini, 2009, „Na logice Modal μ-Calculus a Gödel-Löb,“Studia Logica, 91: 145–169.
• Artemov, SN, 1985b, „On Modal Logics Axiomatizing Provability“, Izvestiya Akadademii Nauk SSSR, Seriya Matematicheskaya, 49 (6): 1123–1154 (v ruštině); Anglický překlad v matematice SSSR – Izvestiya, 27 (3): 402–429.
• –––, 1994, „Logic of Proofs“, Annals of Pure and Applied Logic, 67 (2): 29–59.
• ––– 2001, „Explicitní dostupnost a konstruktivní sémantika“, Bulletin of Symbolic Logic, 7: 1-36.
• Artemov, SN a R. Iemhoff, 2007, „Základní intuitivní logika důkazů“, Journal of Symbolic Logic, 72 (2): 439–451.
• Artemov, SN a F. Montagna, 1994, „O teoriích prvního řádu s operátorem provizornosti“, Journal of Symbolic Logic, 59 (4): 1139–1153.
• Beklemishev, LD, 1989, „O klasifikaci prozatímní logiky zajišťování,“Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya., 53 (5): 915 - 943 (v ruštině); Anglický překlad v matematice SSSR – Izvestiya, 35 (1990) 247–275.
• –––, 1994, „O bimodální logice zajišťovatelnosti“, Annals of Pure and Applied Logic, 68: 115–160.
• –––, 1996, „Bimodální logika pro rozšíření aritmetických teorií“, Journal of Symbolic Logic, 61: 91–124.
• –––, 1999, „Indukce bez parametrů a prokazatelně úplné kompatibilní funkce“, Teoretická informatika, 224: 13–33.
• –––, 2005, „Principy reflexe a algebry reflexe ve formální aritmetice“, Uspekhi Matematicheskikh Nauk, 60 (2): 3–78. (v Rusku); Překlad do angličtiny v: Russian Mathematical Surveys, 60 (2) (2005): 197–268.
• ––– 2006, „Princip červu“, v přednáškách v logice 27. Logické kolokvium '02, Z. Chatzidakis, P. Koepke a W. Pohlers (ed.), Natick (MA): AK Peters, pp 75–95.
• ––– 2012, „Kalibrace logiky dostupnosti: od modální logiky po reflexi reflexe“, v T. Bolander, T. Braüner, S. Ghilardi a L. Moss (ed.), Pokroky v modální logice (svazek 9), London: College Publications, s. 89–94.
• ––– 2014, „Logika pozitivní dostupnosti pro jednotné principy reflexe“, Annals of Pure and Applica Logic, 165 (1): 82–105.
• Beklemishev, LD, D. Fernández-Duque a JJ Joosten, 2014, „O logice zajišťování dostupnosti s lineárně uspořádanými způsoby,“Studia Logica, 102 (3): 541–566.
• Beklemishev, LD, M. Pentus a N. Vereshchagin, 1999, Provability, Complexity, Gramatics, American Mathematical Society Translations (Series 2, Volume 192).
• Beklemishev, LD a A. Visser, 2006, „Problémy v logice zabezpečitelnosti“, v DM Gabbay, SS Goncharov a M. Zakharyashev (ed.), Matematické problémy z aplikované logiky I: Logika pro XXIst století (Mezinárodní matematická řada), Svazek 4), New York: Springer, str. 77–136.
• van Benthem, J., 2006, „Modální rámcové korespondence a pevné body“, Studia Logica, 83 (1-3): 133–155.
• Carlson, T., 1986, „Modální logika s několika operátory a interpretacemi zabezpečitelnosti“, Israel Journal of Mathematics, 54 (1): 14–24.
• Dashkov, EV, 2012, „O pozitivním fragmentu logické SLP s polymemální stabilitou“, Mathematical Notes, 91 (3): 318–333.
• Fernández-Duque, D., 2014, „The Polytopologies of Transfinite Provability Logic“, „Archiv for Mathematical Logic, 53 (3-4): 385–431.
• Fernández-Duque, D. a JJ Joosten, 2013a „Hyperations, Veblen Progressions a Transfinite Iteration of Ordin Functions“, Annals of Pure and Applic Logic 164 (7-8): 785–801, [k dispozici online].
• Fernández-Duque, D. a JJ Joosten, 2013b, „Modely transfinitální zajišťovací logiky“, Journal of Symbolic Logic, 78 (2): 543–561, [k dispozici online].
• Guaspari, D. a RM Solovay, 1979, „Rosserovy věty“, Annals of Mathematical Logic, 16: 81–99.
• Iemhoff, R., 2000, „Modální analýza některých principů logiky zabezpečitelnosti heytování aritmetiky“, v Advances in Modal Logic (svazek 2), M. Zakharyashev et al. (eds.), Stanford: CSLI Publications, pp. 319–354.
• –––, 2001, „O přípustných pravidlech intuitivní prozatímní logiky“, Journal of Symbolic Logic, 66: 281–294.
• –––, 2003, „Logika konzervativnosti: Analogová logika interpretovatelnosti pro konstruktivní teorie,“čtvrtletní matematická logika, 49 (3): 1–21.
• Lindström, P., 1994, „Modální logika Parikh Provability“, Filosofiska Meddelanden, Gröna Serien, Gothenburg: Göteborgs Universitetet.
• Lindström, P., 2006, „On Parikh Provability: Cvičení v modální logice“, v H. Lagerlund, S. Lindström a R. Sliwinski (eds.), Modality Matters: Dvacet pět esejí na počest Kristera Segerberga, Uppsala: Uppsala Philosophical Studies (svazek 53), s. 53–287.
• Montagna, F., 1978, „O algebraizaci Fefermanova predikátu“, Studia Logica, 37 (3): 221–236.
• –––, 1979, „O diagonalizovatelné algebře peano aritmetiky“, Bollettino della Unione Matematica Italiana, B (5), 16: 795–812.
• –––, 1980a, „Interpretace teorie 1. řádu diagonalizovatelných algebras v alometice peano“, Studia Logica, 39: 347–354.
• –––, 1980b „Nerozhodnutelnost teorie diagonalizovatelných algebras prvního řádu“, Studia Logica, 39: 355–359.
• –––, 1984, „Predikátová modální logika zabezpečitelnosti“, Notre Dame Journal of Formal Logic, 25 (2): 179–189.
• –––, 1992, „Polynomiálně a superexponenciálně kratší důkazy ve fragmentech aritmetiky“, Journal of Symbolic Logic, 57: 844–863.
• Pakhomov, FN, 2012, „Nerozhodnutelnost elementární teorie polořadovky GLP-slov“, Sbornik: Mathematics, 203 (8): 1211.
• Shapirovsky, I., 2008, „PSPACE-rozhodnutelnost Japaridze's Polymodal Logic“, Advances in Modal Logic, 7: 289–304.
• Shavrukov, V. Yu., 1993a, „Poznámka k diagonalizovatelným algebrám PA a ZF,“Annals of Pure and Applied Logic, 61: 161–173.
• –––, 1993b, „Subalgebry diagonalizovatelných algebras teorií obsahujících aritmetiku“, Dissertationes Mathematicae, 323.
• –––, 1994, „Chytré dítě Peano's“, Notre Dame Journal of Formal Logic, 35 (2): 161–185.
• Troelstra, AS, 1973, Metamathematical Investigation of Intuitionistic Aritmetic and Analysis, Berlin: Springer-Verlag.
• Visser, A., 1980, Aspects of Diagonalization and Provability, Ph. D. Diplomová práce, Utrecht: Univerzita v Utrechtu.
• –––, 1982, „O principu úplnosti: Studie proveditelnosti v aritmetice a rozšířeních Heyting,“Annals of Mathematical Logic, 22 (3): 263–295.
• –––, 1989, „Inteligentní děti Peana: Logická studie zajišťování systémů se zabudovanou konzistencí“, Notre Dame Journal of Formal Logic, 30 (2): 161–196.
• –––, 1999, „Pravidla a aritmetika“, Notre Dame Journal of Formal Logic, 40 (1): 116–140.
• –––, 2002, „Substituce (Sigma_1) vět: Výzkumy mezi intuicionální prozatímní logikou a intuitivní aritmetikou,“Annals of Pure and Applied Logic, 114: 227–271.
• –––, 2005, „Löbova logika setká μ-kalkul“, v A. Middeldorp, V. van Oostrom, F. van Raamsdonk a R. de Vrijer (ed.), Procesy, termíny a cykly: Kroky na silnici k Infinity, Berlin: Springer, str. 14–25.
• –––, 2008, „Uzavřené fragmenty logiky zajišťování konstruktivních teorií“, Journal of Symbolic Logic, 73: 1081–1096.
• Zambella, D., 1994, „Shavrukovova věta o subalgebrách diagonalizovatelných algebras pro teorie obsahující (I / Delta_0 + / exp),“Notre Dame Journal of Formal Logic, 35: 147–157.

Filozofický význam

• Davis, M., 1990, „Je algoritmus matematického vhledu algoritmický?“, Komentář k Rogerovi Penroseovi, císařově nové mysli, behaviorálním a mozkovým vědám, 13: 659–660.
• –––, 1993, „Jak jemný je Gödelův teorém?“(Komentář k Roger Penrose, Císařova nová mysl), behaviorální a mozkové vědy, 16: 611–612.
• Egré, P., 2005, „Knower Paradox ve světle interpretací interpretace modální logiky,“Journal of Logic, Language and Information, 14 (1): 13–48.
• Kaplan, D. a R. Montague, 1960, „Paradox Reained“, Notre Dame Journal of Formal Logic, 1 (3): 79–90.
• Montague, R., 1963, „Syntaktická léčba modality, s důsledky na principech reflexe a konečné axiomatizovatelnosti“, Acta Philosophica Fennica, 16: 153–67.
• Quine, WV, 1966, „Nezbytná pravda“, v Quine, WV, Způsoby paradoxu a dalších esejí, New York: Random House, s. 48–56.
• –––, 1953, „Tři stupně modální angažovanosti“, v sborníku 11. mezinárodního kongresu filozofie, Amsterdam: North-Holland, s. 65-81; dotisknuto v WV Quine, The Ways of Paradox and Other Essays, New York: Random House, 1966, s. 156–174.

Akademické nástroje

	Jak citovat tento záznam.
	Náhled na PDF verzi tohoto příspěvku v Friends of the SEP Society.
	Vyhledejte toto vstupní téma v projektu Internet Philosophy Ontology Project (InPhO).
	Vylepšená bibliografie tohoto záznamu ve PhilPapers s odkazy na jeho databázi.

Další internetové zdroje

Příspěvky a prezentace

• Fernández-Duque, D. a JJ Joosten, 2013, „Omega-pravidlo Interpretace logiky transfinitů,“online rukopis na arxiv.org.
• Henk, P., a Pakhomov, F., 2016, „Pomalá a běžná zajišťovatelnost pro peano aritmetiku“, rukopis na arxiv.org.
• Pakhomov, F., 2014, „O elementárních teoriích GLP-algebras“, rukopis na arxiv.org.
• Pakhomov, F., 2015, „O základních teoriích ordinálních notačních systémů založených na principech reflexe“, rukopis na arxiv.org.
• Visser, Albert, O formální prokazatelnosti versus lidská prokazatelnost (v holandštině), online rukopis, Univerzita v Utrechtu.
• Verbrugge, Rineke, Prezentační snímky o logice prokazatelnosti, snímky, University of Groningen

Další weby

• Otevřené problémy v logice zajišťovatelnosti, spravuje Lev Beklemishev
• Mailing list Základy matematiky, New York University