Tõenäosusloogika

Sisukord:

Tõenäosusloogika
Tõenäosusloogika
Anonim

Sisenemise navigeerimine

  • Sissesõidu sisu
  • Bibliograafia
  • Akadeemilised tööriistad
  • Sõprade PDF-i eelvaade
  • Teave autori ja tsitaadi kohta
  • Tagasi üles

Tõenäosusloogika

Esmakordselt avaldatud K, 2. aprill 2003; sisuline redaktsioon K 5. aprill 2017

Tõestatavuse loogika on modaaloogika, mida kasutatakse uurimaks, mida aritmeetilised teooriad võivad piiratud keeles väljendada nende tõestatavuse predikaatide kohta. Loogika on inspireeritud sellistest metamatemaatika arengutest nagu Gödeli 1931. aasta mittetäielikkuse teoreemid ja Löbi 1953. aasta teoreem. Modaalloogikana on tõestatavuse loogikat uuritud juba seitsmekümnendate algusest ning sellel on olnud olulisi rakendusi matemaatika alustalades.

Filosoofilisest aspektist on tõestatavuse loogika huvitav, kuna fikseeritud aritmeetika teooria tõenduslikkuse kontseptsioonil on ainulaadne ja probleemideta tähendus, välja arvatud sellised mõisted nagu vajadus ja teadmised, mida on uuritud modaalses ja episteemilises loogikas. Lisaks pakub tõestatavuse loogika vahendeid eneseviitamise mõiste uurimiseks.

  • 1. Tõendatavuse loogika ajalugu
  • 2. Proportsionaalse tõestatavuse loogika aksioomide süsteem

    • 2.1 Aksioomid ja reeglid
    • 2.2 Fikseeritud punkti teoreem
  • 3. Võimalikud maailmade semantika ja topoloogiline semantika

    • 3.1 Iseloomustus ja modaalne usaldusväärsus
    • 3.2 Režiimi terviklikkus
    • 3.3 Tugeva täielikkuse ebaõnnestumine
    • 3.4 Tõendatavuse loogika topoloogiline semantika
  • 4. Tõendatavuse loogika ja Peano aritmeetika

    • 4.1 Aritmeetiline usaldusväärsus
    • 4.2 Aritmeetiline terviklikkus
  • 5. Tõendatavuse loogika ulatus

    • 5.1 Piirid
    • 5.2 tõlgendatavuse loogika
    • 5.3 Esialgsed kvantitaatorid
    • 5.4 Japaridze bimodaalse ja polümodaalse tõestatavuse loogika
    • 5.5 Ennustatavuse loogika
    • 5.6 Muud üldistused
  • 6. Filosoofiline tähtsus
  • Bibliograafia
  • Akadeemilised tööriistad
  • Muud Interneti-ressursid

    • Ettekanded ja ettekanded
    • Muud saidid
  • Seotud kirjed

1. Tõendatavuse loogika ajalugu

Kaks uurimissuunda on viinud tõestatavuse loogika sünnini. Esimene neist tuleneb K. Gödeli (1933) artiklist, kus ta tutvustab intuitsioonilisest ettepanekuloogikast pärit tõlked modaalloogikasse (täpsemalt süsteemi, mida tänapäeval nimetatakse S4), ja mainib lühidalt, et tõestatavust saab vaadelda modaaloperaatorina. Veel varem alustas CI Lewis moodsa loogika tänapäevast uurimist, viies omavastutusena sisse range implikatsiooni, kus ta võis tähendada mahaarvatavust formaalses süsteemis nagu Principia Mathematica, kuid see ei selgu tema kirjutistest.

Teine tegevussuund algab metamatemaatika uurimisega: mida saavad matemaatilised teooriad enda kohta öelda huvitavate omaduste kodeerimise teel? 1952. aastal esitas L. Henkin petlikult lihtsa küsimuse, mis oli inspireeritud Gödeli puudulikkuse teoreemidest. Henkini küsimuse sõnastamiseks on vaja veel mõnda tausta. Meenutuseks, et Gödeli esimene mittetäielikkuse teoreem väidab, et piisavalt tugeva formaalse teooria jaoks nagu Peano Aritmeetik, on iga lause, mis väidab enda tõestamatust, tegelikult tõestamatu. Teisest küljest on formaalse teooria “väljastpoolt” näha, et selline lause vastab standardmudelis tõele, osutades olulisele erinevusele tõe ja tõestatavuse vahel.

Ametlikumalt olgu see, et (ulcorner A / urcorner) tähistaks Gödeli aritmeetilise valemi arvu (A), mis on numbrilise koodi määramise tulemus (A). Olgu (Prov) Peano aritmeetika vormindatud tõestatavuse predikaat, mis on kujul (eksisteerib p \, / Proof (p, x)). Siin on (Proof) Peano aritmeetika vormindatud tõendipreparaat ja (Proof (p, x)) tähistab “Gödeli arv (p) kodeerib õige tõestuse Peano aritmeetika aksioomidest valem Gödeli numbriga (x)”. (Täpsema sõnastuse leiate Smoryński (1985), Davis (1958).) Oletagem nüüd, et Peano Aritmeetika tõestab (A / leftrightarrow / neg) (Prov (Ulcorner A / Urcorner)), siis Gödeli tulemuse järgi ei ole (A) Peano aritmeetikas tõestatav ja seega on see tõsi, sest tegelikult on enesereferentsilauses (A) öeldud: "Ma ei ole tõestatav".

Henkin seevastu soovis teada, kas nende enda tõestatavust kinnitavate lausete kohta võiks midagi öelda: kui eeldada, et Peano Aritmeetika osutub (B / leftrightarrow / Prov (ulcorner B / urcorner)), mida see siis tähendab (B)? Kolm aastat hiljem võttis M. Löb väljakutse vastu ja vastas Henkini küsimusele üllatuslikult. Ehkki kõik Peano Aritmeetikas tõestatavad laused vastavad tõepoolest naturaalarvudele, näitas Löb, et selle fakti vormindatud versioon, (Prov (Ulcorner B / Urcorner) Rightarrow B) on tõestatav ainult Peano Aritmeetikas. triviaalsel juhul, mida Peano Arithmetic juba tõestab (B). See tulemus, mida nüüd nimetatakse Löbi teoreemiks, vastab kohe Henkini küsimusele. (Löbi teoreemi tõestuse leiate lõigust 4.) Löb näitas ka tema teoreemi ametlikku versiooni,nimelt, et Peano aritmeetika tõestab

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

Samas raamatus sõnastas Löb Peano aritmeetika tõestatavuse predikaadil kolm tingimust, mis moodustavad kasuliku modifikatsiooni keerulistest tingimustest, mille Hilbert ja Bernays tutvustasid 1939. aastal Gödeli teise puudulikkuse teooria tõestuseks. Järgnevalt tähistatakse (A) tuletatavust Peano Aritmeetikast tähega (PA / vdash A):

  1. Kui (PA / vdash A), siis (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).)

Need Löbi tingimused, nagu neid tänapäeval nimetatakse, näivad olevat kriitiline modaalse loogilise uurimise järele, kus modaalsus (Box) tähistab PA tõestatavust. Irooniline on see, et esimest korda väideti Löbi teoreemi ametlikku versiooni modaalse põhimõttena

) Kast (kast A / parempoolne nool A) paremnool / kast A)

oli Smiley 1963. aastal eetika loogilise aluse kohta kirjutatud artiklis, mis ei pidanud aritmeetilist üldse. Asjakohasemad uurimised algasid tõsiselt alles kakskümmend aastat pärast Löbi paberi avaldamist. 1970ndate alguses arenes väidetava provalentsusloogika kiire areng, kus mitmed eri riikide teadlased tõestasid iseseisvalt kõige olulisemaid tulemusi, mida käsitleti 2., 3. ja 4. jaos. Propositsionaalne provokatiivsusloogika osutus just selleks, et tabada täpselt seda, mida paljud aritmeetika formaalsed teooriad suudavad öelda omaenda tõestatavuse predikaadi kohta ettepanekuvõimaluste abil. Hiljuti on teadlased uurinud selle lähenemisviisi piire ja pakkunud välja mitu huvitavat, ekspressiivsemat tõestatavuse loogika laiendit (vt punkt 5).

2. Proportsionaalse tõestatavuse loogika aksioomide süsteem

Proportsionaalse tõestatavuse loogika loogiline keel sisaldab lisaks propositsioonilistele aatomitele ja tavalistele tõe funktsionaalsetele operaatoritele ning vastuolulisuse sümbolile (bot) kavandatud tähendusega modaaloperaatorit (Box), mis on tõestatav (T)”, kus (T) on piisavalt tugev formaalne teooria, ütleme Peano aritmeetika (vt 4. jagu). (Teemant A) on lühend lühendist (neg \, / Box / neg \, A). Seega on sama keel nagu modaalsüsteemidel nagu K ja S4, mis on esitatud sisenemismodaali loogikas.

2.1 Aksioomid ja reeglid

Propositsionaalset tõestatavuse loogikat nimetatakse Gödeli ja Löbi järel sageli GL-iks. (Kirjanduses leiduvate alternatiivsete nimetustena samaväärsete süsteemide jaoks on L, G, KW, K4W ja PrL). Loogika GL tuleneb järgmise aksioomi lisamisest põhilisele modaalloogikale K:

) silt {GL} Box (Box A / paremnool A) paremnool / Box A.)

Meeldetuletuseks, et kuna GL laiendab K-d, sisaldab see kõiki valemeid, mis omavad pakkumise tautoloogiat. Samal põhjusel sisaldab GL:

) silt {Distribution Axiom} Box (A / paremnool B) paremnool (Box A / paremnool / Box B).)

Lisaks sellele on see suletud vastavalt Modus Ponensi reeglile, mis võimaldab tuletada (B) (A / parempoolne nool B) ja (A), ning üldistusreeglist, mis ütleb, et kui (A) on GL teoreem, nii on ka (Box A).

Mõiste (GL / vdash A) tähistab modaalvalemi (A) tõestatavust pakutavas tõestatavuse loogikas. Ei ole raske mõista, kas modaalaksioom (Box A / rightarrow / Box / Box A) (tuntud modaalloogika aksioomina 4) on tõepoolest GL-is tõestatav. Selle tõestamiseks kasutatakse aksioomis (GL) asendust (A / kiil / Box A) (A). Siis, nähes, et sellest tuleneva implikatsiooni eelnev järeldus tuleneb (Box A), rakendatakse jaotusaksia ja üldistusreeglit ning ka mõnda juhendiloogikat. Kui ei ole selgesõnaliselt öeldud teisiti, tähistab jaotis „tõestatavuse loogika” eeldusliku loogika süsteemi GL-i.

Tõendatavuse loogika tõestamise teooria osas tõestas Valentini (1983), et standardses järjestuses sisalduvas GL-i koostises järgitakse eliminatsiooni, mis tähendab laias laastus formuleeritult, et ka kõigil järgneval arvutusel GL-st tõestatavatel valemitel on GL-i järjestikused tõendid „ilma ümbersõidud”(lõikamise kõrvaldamise täpsemat selgitust vaata sissekandest tõestusteooria väljatöötamine). Viimastel aastatel on taas ilmnenud huvi GL tõestusteooria vastu, vt näiteks Goré ja Ramanayake (2008). Lõikamine - eemaldamine viib GL-i soovitud alamvormi omaduseni, sest kõik valemid, mis esinevad lõiketa tõendis, on järgnevate valemite alamvormid.

Värsketel lõikamata järjestikustel kalkulatsioonidel põhinevate tõestatavuse loogika hiljutiste tõenditeoreetiliste uuringute kohta vaata (Negri 2005, 2014; Poggiolesi 2009). Negri esitleb kahte ekvivalentset märgistatud järjestikulist kaltsiumi GL-i jaoks ja süntaktilist tõendit lõikuse elimineerimise kohta. Isegi kui täieliku alamvormi omadus nende arvutuste jaoks märgistuse tõttu ei kehti, saab alamvormi omaduse tavalised tagajärjed kindlaks teha: Märgistatud formalism võimaldab otsest täielikkuse tõestamist, mida saab kasutada nii otsustusvõime kui ka lõpliku mudeli kindlakstegemiseks omadus, mis tähendab, et igal valemil, mida ei saa tõestada, on piiratud vastasmudel.

Intrigeeriv uus tõestusteoreetiline areng on Šamkanovi laiendatud järjestikuse stiilis tõestussüsteemid, võimaldades ümmargusi tõestusi (Shamkanov 2014). Mõelge K4 järjestikusele süsteemile, mis tuleneb GL-ist, asendades GL-i aksioomi nõrgema aksioomiga (Box A / parempoolne / Box / Box A) (aksioom 4). Oletame siiski, et lahtised hüpoteesid on lubatud, kui sama jada toimub tõenduspuus hüpoteesist rangelt allpool. Tehniliselt sõnastatuna võib tavalisest tuletuspuust leida ümmarguse tuletise, sidudes selle kõik mitteaksioomaatsed lehed identse sisesõlmega. Shamkanov (2014) tõestas, et saadud süsteem on järjekindel ja lisaks on üldiselt igal jadadel GL-tuletus siis ja ainult siis, kui sellel on ümmargune K4-tuletis. Ümmargused tõendid pakuvad ka meetodit teoreetiliselt tõestada, et Lyndoni interpolatsiooniteoreem kehtib GL kohta. GL standardne interpoleerimine oli juba varem tõestatud erinevate meetoditega (Boolos 1979; Smoryński 1978; Rautenberg 1983). (Lisateavet Lyndoni esimese astme loogika interpolatsiooniteoreemi kohta leiate ka sisestuse esimese astme mudeli teooriast).

2.2 Fikseeritud punkti teoreem

Tõendatavuse loogika peamine „modaalne” tulemus on fikseeritud punkti teoreem, mille D. de Jongh ja G. Sambin tõestasid iseseisvalt 1975. aastal (Sambin 1976). Ehkki see on sõnastatud ja tõestatud rangelt modaalsete meetoditega, on fikseeritud punkti teoreemil siiski suur aritmeetiline tähtsus. Sisuliselt öeldakse, et eneseviitamine pole tegelikult vajalik järgmises tähenduses. Oletame, et kõik pakkumismuutuja (p) esinemised antud valemis (A (p)) kuuluvad tõestatavuse operaatori ulatusse, näiteks (A (p) = / neg / Box p), või (A (p) = / kast (p / parempoolne nool q)). Siis on valem (B), milles (p) ei kuvata, nii et kõik (B) esinevad pakkumismuutujad ilmuvad juba (A (p)) ja selline, et

) GL / vdash B / vasakpoolne nool A (B).)

Seda valemit (B) nimetatakse (A (p)) fikseeritud punktiks. Lisaks on fikseeritud punkt kordumatu või õigemini, kui leidub mõni muu valem (C), näiteks (GL / vdash C / leftrightarrow A (C)), siis peab meil olema (GL / vdash B / vasakpoolne nool C). Enamik kirjanduse tõestusi annab algoritmi, mille abil saab fikseeritud punkti arvutada (vt Smoryński 1985, Boolos 1993, Sambin ja Valentini 1982, Lindström 2006). Eriti lühikese ja selge tõestuse, aga ka väga tõhusa algoritmi püsipunktide arvutamiseks võib leida Reidhaar-Olsonist (1990).

Oletame näiteks, et (A (p) = / neg \, / Box p). Siis on sellise algoritmi toodetud fikseeritud punkt (neg \, / Box / bot) ja tõepoolest saab tõestada, et

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

Kui seda loetakse aritmeetiliselt, on suund vasakult paremale vaid Gödeli teise mittetäielikkuse teoreemi vormindatud versioon: kui piisavalt tugev formaalne teooria (T) nagu Peano aritmeetika ei tõesta vastuolu, siis pole see tõestatav (T), et (T) ei tõenda vastuolu. Seega ei suuda piisavalt tugevad järjekindlad aritmeetilised teooriad enda järjepidevust tõestada. Järgnevalt uurime tõestatavuse loogika ja aritmeetika vahelist seost täpsemalt 4. jaos, kuid selleks tuleb esmalt esitada veel üks GL-i modaalne aspekt: semantika.

3. Võimalikud maailmade semantika ja topoloogiline semantika

Tõendatavuse loogikal on nagu ka paljudel teistel modaalloogikatel sobivaid võimalikke maailmade semantikaid. Võimalik maailmamudel (või Kripke mudel) on kolmekordne (M = / langle W, R, V / rangle), kus (W) on võimalike maailmade mittetühi kogum, (R) on binaarne juurdepääsetavuse seos saidil (W) ja (V) on väärtus, mis määrab tõe väärtuse igale pakkumismuutujale iga maailma jaoks asukohas (W). Paari (F = / langle W, R / rangle) nimetatakse selle mudeli raamiks. Valemi (A) tõe mõiste mudelis (M) maailmas (W), märge (M, w / mudelid A) on määratletud induktiivselt. Kordame ainult kõige huvitavamat lauset, tõendusoperaatorile (Box):

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

Lisateavet maailma võimaliku semantika kohta üldiselt leiate sisenemismodaali loogikast.

3.1 Iseloomustus ja modaalne usaldusväärsus

Modaalloogika K kehtib kõigis Kripke mudelites. Selle laiendus GL ei ole siiski: me peame piirama võimalike maailmamudelite klassi sobivamaga. Ütleme nii, et valem (A) kehtib kaadris (F), märge (F / mudelid A), iff (A) kehtib Kripke mudelite kõigis maailmades (M) põhineb (F). Selgub, et uus tõestatavuse loogika aksioom (GL) vastab raamide tingimusele järgmiselt:

Kõigi kaadrite (F = / langle W, R / rangle, F / models / Box (Box p / rightarrow p) rightarrow / Box p) puhul on iff (R) transitiivne ja vastupidiselt hästi põhjendatud.

Transitiivsus on siin üldtuntud omadus, mis kõigi maailmade (w_1), (w_2), (w_3) jaoks (W), kui (w_1 Rw_2) ja (w_2 Rw_3), siis (w_1 Rw_3). Seos on vastupidiselt põhjendatud, kui puuduvad lõpmata tõusvad jadad, see on järgnev kujul (w_1 Rw_2 Rw_3 R / ldots). Pange tähele, et ka vastupidiselt hästi põhjendatud kaadrid on ka ebareflektiivsed, sest kui (wRw), põhjustab see lõpmatu tõusujada (wRwRwR / ldots).

Ülaltoodud kirjavahetuse tulemus näitab kohe, et GL on transitiivselt vastupidiselt põhjendatud raamidel võimalike maailmamudelite klassi suhtes modaalselt vedel, kuna kõik GL-i aksioomid ja reeglid kehtivad sellistel mudelitel. Küsimus on selles, kas ka täielikkus kehtib: näiteks valem (Box A / rightarrow / Box / Box A), mis kehtib kõigil transitiivsetel kaadritel, on tõepoolest GL-is tõestatav, nagu mainiti 1. jaos. Kuid kas iga valem, mis kehtib kõigis transitiivsetes vastupidiselt hästi põhjendatud kaadrites, on tõestatav ka GL-is?

3.2 Režiimi terviklikkus

Teadmata GL aritmeetilisest olulisusest tõestas K. Segerberg 1971. aastal, et GL on tõepoolest täielik transitiivsete vastupidiselt hästi põhjendatud raamide osas; Seda tulemust tõestasid iseseisvalt ka D. de Jongh ja S. Kripke. Segerberg näitas, et GL on täielik isegi piiratud transitiivsete ebareflektiivsete puude piiratud piires - see oli hiljem väga kasulik Solovay tõenduseks aritmeetilise täielikkuse teoreemi kohta (vt punkt 4).

Modaalse õigsuse ja täielikkuse teoreemid annavad kohe aluse otsustusprotseduuriks, et kontrollida modaalse valemi (A) kas (A) tuleneb GL-st või mitte, uurides sügavuse järgi esmalt ebareflektiivseid, piiratud sügavusega puid. Protseduuri veidi täpsemini vaadates võib näidata, et GL on arvutusliku keerukuse klassis PSPACE otsustatav nagu tuntud modaalloogika K, T ja S4. See tähendab, et on olemas Turingi masin, mis sisendina valemiga (A) vastab kas (A) tuleneb GL-st või mitte; mälu suurus, mida Turingi masin arvutamiseks vajab, on ainult polünoomi pikkuses (A). Võib näidata, et GL-i otsustusprobleem (jällegi nagu K, T ja S4-i otsustusprobleemid) on PSPACE-täielik,selles mõttes, et kõik muud PSPACE probleemid pole raskem kui otsustamine, kas antud valem on GL-i teoreem. (Vt Goré ja Kelly (2007) GL automatiseeritud teoreemianalüüsi kirjeldust.)

Keerukuse perspektiivi lisamiseks lisatakse PSPACE-le funktsioonide klass P, mis on arvutatav sisendpikkuse ajalises polünoomis, (PSPACE), mis omakorda kuulub eksponentsiaalse ajaga arvutatavate funktsioonide klassi EXPTIME (vt kande arvutatavus ja keerukus). See, kas need kaks kandmist on ranged, on endiselt kuulus lahtine probleem, ehkki paljud keerukusteoreetikud usuvad, et sellised on. Mõni muu tuntud modaalloogika, näiteks üldteada episteemiline loogika, on EXPTIME järgi otsustatav, seega võivad need sõltuvalt avatud probleemidest olla keerukamad kui GL.

3.3 Tugeva täielikkuse ebaõnnestumine

Paljud tuntud modaalloogikad (S) ei ole mitte ainult vastava kaadriklassi osas täielikud, vaid isegi tugevalt täielikud. Tugeva täielikkuse selgitamiseks vajame mõistet tuletatavus eelduste kogumist. Valem (A) on tuletatav modaalloogikas (S) oletatavate eelduste hulgast (Gamma), kirjutatud kujul (Gamma / vdash A), kui (A) on (Gamma) või (A) tuleneb (Gamma) valemitest ja (S) aksioomidest Modus Ponensi ja üldistusreeglite rakenduste abil. Siin saab üldistusreeglit kohaldada ainult eeldusteta tuletiste suhtes (vt Hakli ja Negri 2010).

Nüüd on modaalne loogika (S) kindlalt täielik, kui kõigi (lõplike või lõpmatute) komplektide (gamma) ja kõigi valemite (A) korral:

Kui sobivatel (S) kaadritel on (A) tõene kõigis maailmades, kus kõik (Gamma) valemid on tõesed, siis (Gamma / vdash A) loogikas (S).

See tingimus kehtib selliste süsteemide kohta nagu K, M, K4, S4 ja S5. Kui see on piiratud piiratud komplektidega (Gamma), vastab ülaltoodud tingimus täielikkusele.

Tugevus ei vasta tõestatavuse loogikale, kuna semantiline kompaktsus ebaõnnestub. Semantiline kompaktsus on omadus, mis valemi iga lõpmatu komplekti (Gamma) korral

Kui igal (Gamma) lõplikul alamhulgal (Delta) on mudel sobivas ((S)) kaadris, siis on ka ((Gamma)) sobivas (S) -raam.

Tehke vastanäidisena lõpmatu komplekt valemeid

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

Siis saab (Gamma) iga piiratud alamhulga (Delta) jaoks konstrueerida mudeli transitiivsel, vastupidiselt hästi rajatud raami ja mudeli maailmas, kus kõik (Delta) valemid on tõsi. Nii et modaalse usaldusväärsuse järgi ei tõesta GL (bot) (Delta) ühegi lõpliku (Delta / subseteq / Gamma) korral ja veel enam GL ei tõesta (bot) (Gamma), kuna iga GL-tõend on piiratud. Teisest küljest on lihtne mõista, et transitiivsel, vastupidiselt hästi rajatud raamil pole ühtegi mudelit, kus üheski maailmas kehtivad kõik (Gamma) valemid. Seega tuleneb (bot) semantiliselt versioonist (Gamma), kuid ei ole sellest GL-is tõestatav, vastuolus tugeva täielikkuse tingimusega.

3.4 Tõendatavuse loogika topoloogiline semantika

Alternatiivina võimalikule maailmade semantikale võib paljudele modaalloogikatele anda topoloogilise semantika. On selge, et väiteid saab tõlgendada topoloogilise ruumi alamhulkadena. Samuti on lihtne näha, et pakutav ühenduvus (kiil) vastab komplektteoreetilisele operatsioonile (cap), samas kui (vee) vastab (cup), (neg) vastab komplektteoreetilisele komplektile ja (paremnool) vastab (subseteq). Mõtteaksioomi (kast A / parempoolne nool A] sisaldavad modaalloogikad naudivad ka modaaloperaatorite eriti loomulikku tõlgendust. Selle loogika jaoks vastab (Teemant) topoloogilises ruumis sulgemisoperaatorile ja (Kast) sisemusele. Et näha, miks need tõlgendused sobivad,pange tähele, et peegelduse aksioom vastab tõsiasjale, et iga komplekt on oma sulguriga ja iga komplekt sisaldab selle sisemust.

Tõendatavuse loogika ei tõesta aga peegeldust, kuna peegelduse (Box / bot / rightarrow / bot) peegeldumine viiks vastuollu aksioomiga (GL).

Seetõttu vajab usaldusväärsuse loogika teistsugust lähenemist. J. McKinsey ja A. Tarski (1944) ettepaneku põhjal uuris L. Esakia (1981, 2003) (Diamond) tõlgendamist tuletatud komplekti operaatorina (d), mis kaardistab komplekti (B) selle piirpunktide kogumi (d (B)). Sellise (Teemandi) tõlgendamise tagajärgede selgitamiseks on vaja veel kahte määratlust, nimelt tihedalt omaette ja hajutatud mõisteid. Topoloogilise ruumi alamhulka (B) nimetatakse tihedaks omaette, kui (B / subseteq d (B)). Topoloogilist ruumi nimetatakse hajutatuks, kui sellel pole mitte-tühja alamhulka, mis oleks iseenesest tihe. Oma intervallitopoloogias olevad ordinaadid moodustavad hajutatud tühikute näiteid. Esakia (1981) osutus oluliseks kirjavahetuseks: ta näitas, et topoloogiline ruum vastab GL aksioomile ainult siis, kui see on hajutatud. See kirjavahetus viis peagi Abashidze (1985) ja Blassi (1990) iseseisvalt leitud tulemuseni, et tõestatavuse loogika on täielik kõigi tavaliste (ge / omega ^ / omega) suhtes.

Viimastel aastatel on tõestatavuse loogika topoloogiline semantika näinud tõelist taastumist, eriti Japaridze bimodaalse tõestatavuse loogika GLB, GL pikenduse (Japaridze 1986) uurimisel. Loogika GLB osutub oma võimaliku maailmade semantika suhtes modaalselt puudulikuks, selles mõttes, et see ei vasta ühelegi kaadriklassile. See funktsioon asetab bimodaalse GLB teravas kontrastis unimodaalse GL-ga, mis vastab piiritletud transitiivsete ebareflektiivsete puude klassile, nagu eespool mainitud. Beklemishev jt. (2009) näitasid, et GLB on topoloogilise semantika osas siiski täielik (vt ka Beklemishev 2009, Icard 2011). Intrigeerivaid jäljendusi Esakia vastavusest GL ja hajutatud topoloogiliste ruumide vahel võib leida isegi hiljutistest ruumilise ja episteemilise loogika topoloogilistest uuringutest (vt Aiello et al.2007). (Vt jaotist 5.4, et arutada lähemalt GLB-d).

4. Tõendatavuse loogika ja Peano aritmeetika

Alates GL sõnastamisest mõtlesid teadlased, kas see on piisav selliste formaalsete teooriate jaoks nagu Peano Arithmetic (PA): kas GL tõestab kõike tõestatavuse mõiste kohta, mida saab väljendada ettepanekulises modaalkeeles ja mida saab tõestada Peano Aritmeetikas, või kas GL tuleks lisada rohkem põhimõtteid? Selle adekvaatsuse mõiste täpsustamiseks määratleme teostuse (mida mõnikord nimetatakse tõlkimiseks või tõlgendamiseks) funktsioonina f, mis igale modaaloogika aatomiaatomile määrab aritmeetilise lause, kus

  • (f (bot) = / bot;)
  • (f) austab loogilisi ühendusi, näiteks (f (B / parempoolne nool C) = (f (B (parempoolne nool f (C));) ja)
  • (Box) tõlgitakse tõestatavuse predikaadina (Prov), seega (f (Box B) = / Prov (ulcorner f (B) urcorner).)

4.1 Aritmeetiline usaldusväärsus

Juba 1970. aastate alguses oli selge, et GL on PA suhtes aritmeetiliselt kindel, formaalselt:

) tekst {Kui} GL / vdash A, / text {siis kõigi realiseerimiste jaoks} f, / PA / vdash f (A).)

Meta-matemaatika mõningase maitse saamiseks visandame visioonikindluse.

Tõestatud visand aritmeetilisest usaldusväärsusest. PA tõestab väidetavate tautoloogiate realiseerumist ja GL jaotumise aksiomi tõestatavus tähendab

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

kõigi valemite A ja B jaoks, mis on lihtsalt Löbi teine tuletatavuse tingimus (vt punkt 1). Lisaks järgib PA Modus Ponensi ja üldistuse reegli tõlget:

) tekst {Kui} PA / vdash A, / text {siis} PA / vdash / Prov (ulcorner A / urcorner),)

mis on just Löbi esimene tuletatavuse tingimus. Lõpuks on PA-s tõestatud ka põhiaksioomi (GL) tõlge:

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

See on täpselt 1. osas mainitud Löbi teoreemi ametlik versioon.

Esitame visandi Löbi teoreemi enda tõestamise kohta tema tuletatavuse tingimustest (ametliku versiooni tõestamine on sarnane). Selle tõestus põhineb Gödeli diagonaalimise leemal, mis ütleb, et mis tahes aritmeetilise valemi (C (x)) jaoks on olemas selline aritmeetiline valem (B), et

) PA / vdash B / vasakpoolne nool C (ulcorner B / urcorner).)

Sõnades ütleb valem (B): "Mul on vara (C)."

Tõend Löb teoreem:. Oletame, et (PA / vdash / Prov (ulcorner A / urcorner) rightarrow A); peame seda näitama (PA / vdash A). Diagonaalimise lemma järgi on valem (B) selline, et

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

Siit järeldub Löbi esimene ja teine tuletatavuse tingimus, millele lisanduvad mõned väidetavad põhjendused

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

Seega jälle Löbi teise tingimuse järgi,) PA / vdash / Prov (ulcorner B / urcorner) rightarrow (Prov (ulcorner / Prov (ulcorner B / urcorner) urcorner) rightarrow / Prov (ulcorner A / urcorner)).)

Teisest küljest annab Löbi kolmas tingimus

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

seega

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

Koos eeldusega, et (PA / vdash / Prov (ulcorner A / urcorner) rightarrow A), annab see

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

Lõpuks eeldab diagonaalimise lemma loodud võrrand, et (PA / vdash B), seega (PA / vdash / Prov (Ulcorner B / urcorner)), seega

) PA / vdash A,)

nagu ihaldatud.

Pange tähele, et kui asendada Löbi teoreemis (A) (bot), tuletame, et (PA / vdash / neg \, / Prov (ulcorner / bot / urcorner)) tähendab ka (PA / vdash / bot), mis on vaid Gödeli teise puudulikkuse teoreemi vastand.

4.2 Aritmeetiline terviklikkus

Tõendatavuse loogika maamärk on R. Solovay 1976. aasta aritmeetilise täielikkuse teoreem, mis näitab, et GL on Peano aritmeetika jaoks tõepoolest piisav:

) GL / vdash A / text {ainult siis, kui kõigi realiseerimiste korral} f, / PA / vdash f (A).)

See teoreem ütleb sisuliselt seda, et modaalloogika GL hõlmab kõike seda, mida Peano Arithmetic saab tõepoolest modaalses mõttes öelda omaenda tõestatavuse predikaadi kohta. Suund vasakult paremale, GL aritmeetiline heledus on arutatud eespool. Solovay otsustas teise, palju raskema suuna suuna tõestada kontratseptsiooni teel. Tema tõendusmaterjal põhineb keerulistel enesereferentsivõtetel ja siin saab anda vaid väikese pilgu.

Segerbergi mooduli täielikkuse teoreem oli oluline esimene samm Solovay tõendis GL aritmeetilise täielikkuse kohta Peano aritmeetika suhtes. Oletame, et GL ei tõesta modaalset valemit (A). Siis moodustab modaalne terviklikkus lõpliku transitiivse ebafleksiivse puu, mille korral (A) on selle puu juurtes vale. Nüüd töötas Solovay välja leidliku viisi, kuidas simuleerida sellist piiratud puud Peano aritmeetika keeles. Nii leidis ta teostuse (f) modaalsetest valemitest aritmeetika lauseteni, nii et Peano aritmeetika ei tõesta (f (A)).

Solovay täielikkuse teoreem pakub alternatiivse viisi paljude aritmeetiliste lausete konstrueerimiseks, mis pole Peano aritmeetikas tõestatavad. Näiteks on lihtne teha võimalikku maailmamudelit, et näidata, et GL ei tõesta (Box p / vee / Box / neg \, p), seega on Solovay teoreemi järgi aritmeetiline lause (f (p)) nii, et Peano Aritmeetika ei tõesta (Prov (ulcorner f (p) urcorner) vee / Prov (ulcorner / neg \, f (p) urcorner)). Eelkõige tähendab see, et ei (f (p)) ega (neg \, f (p)) pole Peano aritmeetikas tõestatavad; kui oletame vastupidi, et (PA / vdash f (p)), siis Löbi esimese tingimuse ja ettepanekuloogika abil, (PA / vdash / Prov (ulcorner f (p) urcorner) vee / Prov (ulcorner / neg \, f (p) urcorner)), mis põhjustab vastuolu ja samamoodi siis, kui arvatakse, et (PA / vdash / neg \, f (p)).

Solovay teoreem on sedavõrd märkimisväärne, et see näitab, et sellise otsustamatu formaalse teooria nagu Peano aritmeetika huvitavat fragmenti - nimelt seda, mida aritmeetika suudab väljendada algsõnaliselt omaenda tõestatavuse predikaadi kohta - saab uurida otsustava modaalloogika, GL, abil silmatorkava võimaliku maailmade semantika.

5. Tõendatavuse loogika ulatus

Selles jaotises käsitletakse mõnda hiljutist suundumust tõestatavuse loogika uurimisel. Üks oluline suund on seotud GL ulatuse piiridega, kus põhiküsimus on see, milliste formaalsete teooriate, välja arvatud Peano aritmeetika osas on GL asjakohane eeldatav loogika? Järgnevalt arutleme mõned väidetava provalentsusloogika üldistused ekspressiivsemates modaalkeeltes.

5.1 Piirid

Viimastel aastatel on logistikud uurinud paljusid teisi aritmeetika süsteeme, mis on Peano aritmeetikast nõrgemad. Sageli leidsid need loogikud inspiratsiooni arvutatavuse probleemidest, näiteks polünoomi ajal arvutatavate funktsioonide uurimisel. Nad on andnud osalise vastuse küsimusele: "Milliste aritmeetiliste teooriate kohta kehtib endiselt Solovay aritmeetilise täielikkuse teoreem (lähtudes sobivast tõestatavuse predikaadist)?" Selle küsimuse arutamiseks on vaja kahte kontseptsiooni. (Delta_0) - valemid on aritmeetilised valemid, milles kõik kvantifitseerijad on piiratud terminiga, näiteks

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

kus (bs) on operaatori järeltulija (“(+ 1)”). Aritmeetiline teooria (I / Delta_0) (kus ma tähistan induktsiooni) on sarnane Peano aritmeetikaga, välja arvatud see, et see võimaldab vähem induktsiooni: induktsiooniskeem

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

on piiratud (Delta_0) - valemitega (A).

Nagu De Jongh ja teised (1991) märkisid, kehtib aritmeetiline täielikkus teooriate kohta, mis vastavad kahele järgmisele tingimusele:

  1. (T) tõendab (Delta_0) - valemite esilekutsumist ja (T) tõendab EXP, valem väljendab, et kõigi (x) korral on selle võimsus (2 ^ x) olemas. Tavalisema märke korral: (T) laiendab (I / Delta_0) + EXP;
  2. (T) ei tõenda vormingu (eksisteerib x \, A (x)) valelauseid valemiga (A (x)) a (Delta_0).

Selliste teooriate puhul on GL-i hoidmise aritmeetiline õigsus ja täielikkus eeldusel, et (Box) tähendab (Prov_T), loomuliku tõestatavuse predikaat (T) piisavalt lihtsa aksiomatiseerimise osas. Seega modaalsete lausete (A) korral:

) GL / vdash A / text {ainult siis, kui kõigi realiseerimiste korral} f, T / vdash f (A).)

Veel pole selge, kas tingimus 1 annab tõestatavuse loogika ulatuse alumise piiri. Näiteks on endiselt lahtine küsimus, kas GL on (I / Delta_0 + / Omega_1), teooria, mis on mõnevõrra nõrgem kui (I / Delta_0 / + + EXP) tõestatavuse loogika selles (Omega_1). on aksioom, mis kinnitab, et kõigi (x) korral on selle võimsus (x ^ { log (x)}) olemas. Tõendatavuse loogika: GL on aritmeetiliselt õiglane (I / Delta_0 + / Omega_1) suhtes, kuid välja arvatud Berarducci ja Verbrugge (1993) osalised tulemused, pakkudes piiratud aritmeetilisi realisatsioone, mis vastavad (I / Delta_0 + / Omega_1) klassi lausetega kooskõlas GL-ga, jääb küsimus lahtiseks. Selle vastus võib sõltuda arvutusliku keerukuse teooria avatud probleemidest.

Ülaltoodud tulemuse autorid De Jongh jt. näitab tõestatavuse loogika tugevat joont: paljude erinevate aritmeetiliste teooriate jaoks kajastab GL täpselt seda, mida need teooriad räägivad nende enda tõestatavuse predikaadi kohta. Samal ajal on see nõrkus. Näiteks ei osuta väidetav tõestatavuse loogika mingitele erinevustele nende teooriate vahel, mis on lõplikult aksiomeeritavad, ja nende vahel, mis mitte.

5.2 tõlgendatavuse loogika

Teadlaste oluliste erinevuste osas moodi keeles rääkida saavad teadlased laiendanud tõestatavuse loogikat mitmel erineval viisil. Mainigem mõnda. Üks laiend on binaarse modaalsuse lisamine (tõlgendab), kus antud aritmeetilise teooria (T) korral on modaallause (A / tõlgendab B) tähistamiseks sõna (T + B) on tõlgendatav keeles (T + A)”(Švejdar, 1983). De Jongh ja Veltman (1990) uurisid mitmete tõlgendusloogikategooriate modaalset semantikat, De Jongh ja Visser (1991) tõestasid kõige olulisemate jaoks selget fikseeritud punkti omadust. Visser iseloomustas levinumate lõplikult aksiomeeritud teooriate tõlgendatavuse loogikat ning Berarducci ja Šavrukov iseloomustasid sõltumatult PA-i teooriat, mis pole lõplikult aksiomeeritav. Näib, et tõepoolest,lõplikult aksiomeeritavate teooriate tõlgendatavuse loogika erineb Peano Aritmeetika tõlgendatavusloogikast (vt Montagna 1987; Visser 1990, 1998; Berarducci 1990, Shavrukov 1988; Joosten ja Visser 2000).

5.3 Esialgsed kvantitaatorid

Teine võimalus väidetava tõestatavuse loogika raamistiku laiendamiseks on ettepanekul põhinevate kvantifikaatorite lisamine, et saaks väljendada põhimõtteid nagu Goldfarbi põhimõtted:

) forall p \, forall q \, / eksisteerib r \: / Box ((Box p / vee / Box q) vasakpoolne / Box r),)

öeldes, et iga kahe lause kohta on olemas kolmas lause, mis on tõestatav siis ja ainult siis, kui üks kahest esimesest lausest on tõestatav. See põhimõte on tõestatav Peano aritmeetikas (vt nt Artemov ja Beklemishev 1993). GL aritmeetiliselt paika pandud lausekomplekt koos pakutavate kvantifikaatoritega osutub otsustamatuks (Shavrukov 1997).

5.4 Japaridze bimodaalse ja polümodaalse tõestatavuse loogika

Japaridze (1988) bimodaalsel loogikal GLB-l on kaks (Box) - nagu tõestatavuse operaatorit, mida tähistatakse tähtedega ([0] ja (1)), koos kahese (Diamond) - sarnase operaatoriga. (langle 0 / rangle) ja (langle 1 / rangle) vastavalt. Japaridze tõlgenduses võib mõelda ([0]) kui standardse tõestatavuse predikaadi tähistamisele Peano aritmeetikas. Teisest küljest vastab ([1]) tugevamale tõestatavuse predikaadile, nimelt (omega) - provabiliteet.

Määratlegem mõisted, mida on vaja selle GLB kavandatud tõlgenduse mõistmiseks. Aritmeetiline teooria (T) on määratletud kui (omega) - järjepidev siis ja ainult siis, kui kõigi valemi A korral koos vaba muutujaga (x), (T / vdash / neg \, A (I_n)) kõigi jaoks (n) tähendab, et (T / not / vdash / eksisteerib x \, A (x)); siin on (I_n) numbriga (n), st terminiga (bs / bs / ldots / bs 0) koos (n) õigusjärglase operaatori (bs). Peano aritmeetika (PA) on kõige tuntum näide (oomega] - järjepidevast teooriast (vt ka Gödeli mittetäielikkuse teoreemid). Nüüd olgu PA (^ +) aritmeetiline teooria, mille aksioomid on PA aksioomid koos kõigi lausetega (forall x \, / neg \, A (x)) nii, et iga (n) jaoks PA (vdash / neg \, A (I_n)). Nüüd (omega) - tõestatavus on lihtsalt tõestatavus PA-s (^ +),nii et see on kahetine (omega) - järjepidevus.

Japaridze bimodaalse tõestatavuse loogikat GLB saab aksiomatizida GLi aksioomide ja reeglite järgi (vt punkt 2), mis on eraldi formuleeritud punktide [0] ja [1] jaoks. Lisaks on GLB-l kaks segatud aksioomi, nimelt:) tag {Monotonicity} [0] A / rightarrow [1] A)) tag {(Pi ^ 0_1) - terviklikkus} langle 0 / rangle A / rightarrow [1] langle 0 / rangle A) Japaridze loogika on otsustav ja sellel on mõistlik Kripke semantika ning Peano aritmeetika suhtes aritmeetiliselt kindel ja täielik (Japaridze 1988, Boolos 1993).

Japaridze GLB polümodaalne analoog nimega GLP on viimastel aastatel pälvinud palju tähelepanu. GLP-l on lõputult palju (Box) - nagu tõestatavuse operaatoreid, tähistatud lahtritega ([n]) iga naturaalarvu (n) jaoks koos kahekordse (Diamond) - nagu operaatoritega (langle n / rangle). Jällegi võib mõelda ([0]) kui standardse provokatiivsuse predikaadi tähistamisele Peano aritmeetikas, (langle 1 / rangle) (omega) - tõestatavusele, jne. GLP on aksiomaiseeritud, lähtudes GLi aksioomidest ja reeglitest (vt punkt 2), mis on koostatud iga ([n]) jaoks eraldi. Lisaks on GLP-l kolm segatud aksioomiskeemi, nimelt Beklemishevi (2010) sõnastatud kujul: [m] A / paremnool [n] A, / mbox {jaoks} m / leq n)) langle k / rangle A / paremnool [n] langle k / rangle A, / mbox {jaoks} k / lt n) [m] A / paremnool [n] [m] A, / mbox {jaoks} m / leq n)

GLP pälvis hiljuti Kripke semantika, mille osas see on täielik, ja on näidatud, et see on ka Peano aritmeetika suhtes aritmeetiliselt täielik (vt Beklemishev 2010a, 2011a). Nii nagu GL puhul, on ka GLP otsustusprobleem PSPACE-täielik (Shapirovsky 2008), samas kui selle suletud fragment on polünoomi ajaliselt otsustatav (Pakhomov 2014).

Viimastel aastatel on tõestatud mitmeid tulemusi tugeva prevaleeritava predikaadi polümodaalse loogika GLP kohta. Järgige siin mõnda eriti viljakat teemat:

  • GLP suletud fragment (vt Ignatiev 1993; Beklemishev, Joosten ja Vervoort 2005);
  • GLP ja tõenditeoreetilised korraldused (Beklemishev 2004);
  • Interpolatsiooniteoreemid GLP jaoks (vt Beklemishev 2010b, Shamkanov 2011);
  • Topoloogilise semantika ja setteooria seos, muu hulgas eriti suurte kardinaalsete aksioomide ja statsionaarse peegelduse vahel (vt Beklemishev 2011b; Beklemishev ja Gabelaia 2013, 2014; Fernández-Duque 2014).

5.5 Ennustatavuse loogika

Lõpuks saab muidugi uurida ka provokatiivsuse loogikat. Keel on funktsioonisümboliteta predikaatloogika ja operaatori (Box) keeles. Siin muutub olukord palju keerukamaks kui propositsioonilise tõestatavuse loogika puhul. Alustuseks ei ole GL sirgel kvantifitseeritud versioonil fikseeritud punkti omadust, see pole Kripke kaadrite ühegi klassi osas täielik ega ole Peano aritmeetika osas aritmeetiliselt täielik (Montagna, 1984). Seejärel kerkib küsimus: kas leidub mõnd kenasti aksioomiseeritud predikaadi tõestatavuse loogikat, mis oleks piisav ja mis tõestaks täpselt kehtivaid tõestatavuse põhimõtteid? Vastus on kahjuks kõlav eita:Vardanyan (1986) on Artemovi (1985a) ideede põhjal tõestanud, et predikatiivse tõestatavuse loogika lausekomplekt, mille kõik realiseerumised on PA-s tõestatavad, pole isegi rekursiivselt loendatav, vaid (Pi ^ 0_2) - täielik, nii et sellel puudub mõistlik aksiomatization. Visser ja De Jonge (2006) näitasid, et Vardajani teoreemist ei pääse üldistust tõendades: laia aritmeetilise teooria jaoks (T) on predikaatprovatiivsuse loogika lausekomplekt, mille kõik teostused on tõestatavad (T) osutub (Pi ^ 0_2) - ka täielik. Laiuse aritmeetiliste teooriate (T) korral osutub predikaatprovatiivsuse loogika lausekomplektiks, mille kõigi realiseerimised on tõestatavad (T), (Pi ^ 0_2) - ka täielik. Laiuse aritmeetiliste teooriate (T) korral osutub predikaatprovatiivsuse loogika lausekomplektiks, mille kõigi realiseerimised on tõestatavad (T), (Pi ^ 0_2) - ka täielik.

5.6 Muud üldistused

Ülaltoodud arutelust on välja jäetud paljud muud olulised uurimissuunad tõestatavuse loogikas ja selle laiendites. Huvitatud lugejale viidatakse järgmistele valdkondadele:

  • intuitiivse aritmeetika tõestatavuse loogika (vt Troelstra 1973; Visser 1982, 1999; Iemhoff 2000, 2001, 2003; Visser 2002, 2008);
  • tõestatavuse loogika klassifikatsioon (vt Visser 1980, Artemov 1985b, Beklemishev 1989, Beklemishev jt 1999);
  • Rosseri tellimused ja tõestuskiirendus (vt Guaspari ja Solovay 1979, Švejdar 1983, Montagna 1992);
  • mitut tüüpi bimodaalse tõestatavuse loogika koos tõestatavuse operaatoritega erinevate teooriate jaoks (vt Carlson 1986; Smoryński 1985; Beklemishev 1994, 1996);
  • standardse tõestatavuse tõestatavuse loogika koos ebahariliku tõestatavusega pretsedeerib väliselt PA-d loetlevaid, näiteks Fefermani ja Parikhi tõestatavuse predikaadid ja aeglase tõestatavuse predikaadid (vt Montagna 1978; Visser 1989; Shavrukov 1994; Lindström 1994, 2006; Henk ja Pakhomov 2016 (muud Interneti-ressursid)).);
  • otseste tõendite loogika (vt Artemov 1994, 2001; Artemov ja Montagna 1994; Artemov ja Iemhoff 2007);
  • tõestatavuse loogika rakendused tõestusteoorias (vt Beklemishev 1999, 2004, 2005, 2006);
  • positiivse tõestatavuse loogika ja peegelduskalkulatsioon (vt Beklemishev 2012, 2014; Daškov 2012);
  • polümodaalse tõestatavuse loogika GLP üldistused, nimelt piiritletud arvukate modaalsustega tõestatavuse loogika (vt Beklemishev jt 2014; Fernández-Duque ja Joosten 2013a, 2013b, 2013 (muud Interneti-ressursid), 2014);
  • tõestatavuse loogika ja (mu) - calculuse vahelised seosed (vt van Benthem 2006, Visser 2005, Alberucci ja Facchini 2009); ja
  • tõestatavuse algebrad, mida nimetatakse ka diagonoositavaks algebrateks või Magari algebrateks (vt Magari 1975a, 1975b; Montagna 1979, 1980a, 1980b; Shavrukov 1993a, 1993b, 1997; Zambella 1994; nende põhiteooriate viimaste tulemuste kohta vt Pakhomov 2012, 2014 (Muu Internet) Ressursid), 2015 (muud Interneti-ressursid)).

Lugejale, kes sooviks anda oma panuse tõestatavuse loogika valdkonda ja selle üldistusse, on Beklemishev ja Visser (2006) pakkunud välja intrigeerivate avatud probleemide annoteeritud loetelu.

6. Filosoofiline tähtsus

Ehkki väidetav tõestatavuse loogika on modaalne loogika, millel on omamoodi „vajalikkuse” operaator, peab see Quine'i (1976) modaalmõistete vastuolulist kriitikat mõistmatuks juba selle selge ja ühemõttelise aritmeetilise tõlgenduse tõttu. Näiteks, erinevalt paljudest teistest modaalloogikatest, pole pesastatud modaalsusega valemid, nagu (Box / Diamond p / rightarrow / Box / bot), samuti pole vaidlusi selle üle, millised peaksid olema tautoloogiad. Tegelikult kehastab tõestatavuse loogika kõiki soovimõtteid, mille Quine (1953) esitas modaalsuse süntaktiliste käsitluste jaoks.

Quine'i peamised nooled olid suunatud modaalse predikaatloogika poole, eriti lausete konstrueerimisel, mis sisaldavad modaalseid operaatoreid kvantifikaatorite (“kvantifitseerivad”) piires. Predikatiivse tõestatavuse loogikas, kus kvantifikaatorid ulatuvad naturaalarvudest, on aga nii dikto- kui ka de-modaalsusel sirgjoonelised tõlgendused, vastupidiselt muudele modaalloogikatele (vt märkust deicto / de-eristuse kohta). Näiteks valemid nagu

) jätkub x \, / Box \, / eksisteerib y \, (y = x))

pole üldse probleemsed. Kui arv (n) on määratud väärtusele (x), siis on (Box \, / eksisteerib y \, (y = x)) selle ülesande puhul tõene, kui lause (eksisteerib y \, (y = I_n)) on Peano aritmeetikas tõestatav; siin on (I_n) numbriga (n), st terminiga (bs / bs / ldots / bs 0) koos (n) õigusjärglase operaatori (bs). See lause kehtib kõigi looduslike arvude standardmudeli (n) kohta ja (forall x \, / Box \, / eksisteerib y \, (y = x)) on isegi Peano aritmeetikas tõestatav..

Muide, Barcani valem

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

ei kehti täisarvude osas, rääkimata tõestatavast (näiteks võtke (A (x)) valemiga “(x) ei kodeeri (bot) tõestust”). Selle vastupidine

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

ja teisest küljest on see Peano aritmeetikas tõestatav mis tahes valemi (A) jaoks.

Tõendatavuse loogikal on teistest modaalloogikatest väga erinevad põhimõtted, isegi neil, millel on näiliselt sarnane eesmärk. Näiteks kui tõestatavuse loogika haarab tõestatavuse aritmeetika formaalsete teooriate abil, püüab episteemiline loogika teadmisi kirjeldada, mida võiks vaadelda kui teatavat mitteametlikku tõestatavust. Episteemilise loogika paljudes versioonides on üks olulisemaid põhimõtteid tõe aksioom (5):

) mbox {S5} vdash / Box A / paremnool A, (tekst {kui keegi teab} A, / text {siis} A / text {is true}).)

Analoogne põhimõte ei kehti selgelt ka GL kohta:

) tekst {kui} GL / vdash / kast A / paremnool A, / tekst {siis} GL / vdash A.)

Seega tundub ekslik võrrelda mõlema mõiste tugevust või ühendada need ühes modaalses süsteemis. Võib-olla on formaalne tõestatavus tõepoolest mõnes mõttes tugevam mõiste kui mitteametlik tõestatavus, kuid kindlasti pole see aritmeetiline tõde ega paikapidavus, ega ka teine suund. Gödeli mittetäielikkuse teooriate tagajärgede arutelud hõlmavad vahel segadust tõestatavuse mõiste ümber, tekitades väiteid, et inimesed võiksid teooriate „tundmisel” formaalseid süsteeme ületada (selliste väidete hea arutamise kohta vt Davis (1990, 1993)).

Kokkuvõttes on formaalne tõestatavus täpselt määratletud mõiste, seda enam kui tõde ja teadmised. Seega ei vii enesest viitamine tõestatavuse piires sellistele semantilistele paradoksidele nagu Valetaja. Selle asemel on see viinud matemaatika osas kõige olulisemate tulemusteni, näiteks Gödeli puudulikkuse teoreemid.

Bibliograafia

Üldised viited tõestatavuse loogikale

  • Artemov, SN, 2006, “Modaalne loogika matemaatikas”, P. Blackburn jt. (toim), Modal Logic Handbook, Amsterdam: Elsevier, lk 927–970.
  • Artemov, SN ja LD Beklemishev, 2004, “Provability Logic”, filosoofilise loogika käsiraamatus, teine trükk, D. Gabbay ja F. Guenthner, toim., 13. köide, Dordrecht: Kluwer, lk 229–403.
  • Boolos, G., 1979, Järjepidevuse parandamatus: essee modaalses loogikas, Cambridge: Cambridge University Press.
  • –––, 1993, The Logic of Provability, New York ja Cambridge: Cambridge University Press.
  • de Jongh, DHJ ja G. Japaridze, 1998, “Tõestatavuse loogika”, tõestusteooria käsiraamatus, Buss, SR (toim), Amsterdam: Põhja-Holland, lk 475–546.
  • Lindström, P., 1996, “Tõenäosusloogika - lühike sissejuhatus”, Theoria, 52 (1–2): 19–61.
  • Segerberg, K., 1971, Essee klassikalises modaalses loogikas, Uppsala: Filosofiska Föreningen and Filosofiska Institutionen vid Uppsala Universitet.
  • Švejdar, V., 2000, “On Provability 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” filosoofia entsüklopeedias (lisa), DM Borchert (toim.), New York: Simon ja Schuster MacMillan, lk 476–478.
  • Visser, A., 1998, “Provability Logic”, Routledge'i filosoofia entsüklopeedias, W. Craig (toim), London: Routledge, lk 793–797.

Ajalugu

  • van Benthem, JFAK, 1978, “Neli paradoksi”, Journal of Philosophical Logic, 7 (1): 49–72.
  • Boolos, G. ja G. Sambin, 1991, “Tõestatavus: matemaatilise mooduse teke”, Studia Logica, 50 (1): 1–23.
  • Gödel, K., 1933, “Eine Interpretation des intuitionistischen Aussagenkalküls”, Ergebnisse eines Mathematischen Kolloquiums, 4: 39–40; tõlge “Intuitionistliku propositsioonilise arvutuse tõlgendus”, K. Gödel, Kogutud teosed, S. Feferman jt. (toim), Oxford ja New York: Oxford University Press, 1. köide, 1986, lk 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. ja A. Visser, 2014, “Henkini lause”, M. Mazano, I. Sain ja E. Alonso (toim.), Leon Henkini elu ja töö: Esseed tema kaastöödest, Dordrecht: Springer International Publishing, lk 249–263.
  • Henkin, L., 1952, „Tõenäosusega seotud probleem”, Journal of Symbolic Logic, 17: 160.
  • –––, 1954, „Ülevaade G. Kreislist: Leon Henkini probleemist”, Journal of Symbolic Logic, 19 (3): 219–220.
  • Hilbert, D. ja P. Bernays, 1939, Grundlagen der Mathematik, 2. köide, Berliin / Heidelberg / New York: Springer-Verlag.
  • Kreisel, G., 1953, “Leon Henkini probleemist”, Indagationes Mathematicae, 15: 405–406.
  • Lewis, CI, 1912, “Implikatsioon ja loogika algebra”, Mind, 21: 522–531.
  • Löb, MH, 1955, “Leon Henkini probleemi lahendus”, Journal of Symbolic Logic, 20: 115–118.
  • Macintyre, AJ ja H. Simmons, 1973, “Gödeli diagonaalimismeetod ja teooriate sellega seotud omadused”, Colloquium Mathematicum, 28: 165–180.
  • Magari, R., 1975a, “Diagoneeritavad algebrad”, Bollettino della Unione Mathematica Italiana, 12: 117–125.
  • –––, 1975b, „Diagonoositavate algebrate esitus- ja kahesuseteooria“, Studia Logica, 34 (4): 305–313.
  • Smiley, TJ, 1963, “Eetika loogilised alused”, Acta Philosophica Fennica, 16: 237–246.
  • Smoryński, C., 1991, “Eneseviite areng: Löbi teoreem”, T. Druckeris (toim), Matemaatilise loogika ajaloo perspektiivid, Basel: Birkhäuser, lk 110–133.

Kõrvaldamine tõestatavuse loogika jaoks

  • Goré, R. ja R. Ramanayake, 2008, “Valentini kärpe-likvideerimine tõestatavuse loogika lahendamiseks”, Advances in Modal Logic 7. köites, C. Areces ja R. Goldblatt (toim.), London: College Publications, lk 67 -86.
  • Negri, S., 2005, “Proof Analysis in Modal Logic”, Journal of Philosophical Logic, 50: 507–544.
  • Negri, S., 2014, “Tõendid ja vastuargumendid mitteklassikalises loogikas”, Logica Universalis, 8 (1): 25–60.
  • Poggiolesi, F., 2009, “Puhtalt süntaktiline ja lõikamata järjestikune kalkulatsioon tõestatavuse modaalloogika jaoks”, The Symbolic Logic Review, 2 (4): 593–611.
  • Rautenberg, W., 1983, “Modaalne tabelite arvutamine ja interpolatsioon”, Journal of Philosophical Logic, 12 (4): 403–423.
  • Sambin, G. ja S. Valentini, 1982, “Tõenäosuse modaalne loogika. Järjestikune lähenemisviis”, Journal of Philosophical Logic, 11 (3): 311–342.
  • Shamkanov, DS, 2011, “Provability Logics GL ja GLP interpolatsiooni omadused”, Steklovi matemaatikainstituudi toimetised, 274 (1): 303–316.
  • –––, 2014, „Gödel-Löbi tõestatavuse loogika ümmargused tõendid”, Mathematical Notes, 96 (4): 575–585.
  • Smoryński, C., 1978, “Bethi teoreem ja enesereferentsilised laused”, Uuringud loogika ja matemaatika aluste kohta, 96: 253–261.
  • Valentini, S., 1983, “Tõenäosuse modaalne loogika: lõikamine ja kõrvaldamine”, Journal of Philosophical Logic, 12: 471–476.

Fikseeritud punkti teoreem

  • de Jongh, DHJ ja F. Montagna, 1988, “Provable Fixed Points”, Mathematical Logic Quarterly, 34 (3): 229–250.
  • Lindström, P., 2006, “Märkus mõne kindla fikseeritud punktiga konstruktsiooni kohta tõestatavuse loogikas”, Journal of Philosophical Logic, 35 (3): 225–230.
  • Reidhaar-Olson, L., 1990, “Uus tõend tõestatavuse loogika fikseeritud punkti teoreemist”, Notre Dame Journal of Formal Logic, 31 (1): 37–43.
  • Sambin, G., 1976, “Tõhus fikseeritud punkti teoreem intuitsioonilises diagonoositavas algebras (Theoriat väljendavate teooriate algebraliseerimine, IX)”, Studia Logica 35: 345–361.
  • Sambin, G. ja S. Valentini, 1982, “Tõenäosuse modaalne loogika. Järjestikune lähenemisviis”, Journal of Philosophical Logic, 11 (3): 311–342.

Võimalikud maailmade semantika ja topoloogiline semantika

  • Abashidze, M., 1985, “Gödel-Löbi modaalsüsteemi tavapärane terviklikkus” (vene keeles) intensiivses loogikas ja teooriate loogilises ülesehituses, Thbilisi: Metsniereba, lk 49–73.
  • Aiello, M., I. Pratt-Hartmann ja J. van Benthem (toim.), 2007, Ruumiloogika käsiraamat, Berliin: Springer-Verlag.
  • Beklemišev, LD 2009, “Bimodaalse tõestatavuse loogika GLB tavapärane terviklikkus”, rahvusvaheline Thbilisi loogika, keele ja arvutuse sümpoosion, Berliin: Springer-Verlag, lk 1–15.
  • Beklemišev, LD, G. Bezhanishvili ja T. Icard, 2009, “GLP topoloogilistest mudelitest”, R. Schindler (toim), Tõestusteooria viisid (Ontose matemaatiline loogika: 2. köide), Frankfurt: Ontos Verlag, lk 133–153.
  • Blass, A., 1990, “Infinitary Combinatorics and Modal Logic”, Journal of Symbolic Logic, 55 (2): 761–778.
  • Esakia, L., 1981, “Diagonaalsed konstruktsioonid, Löbi valem ja kantori hajutatud ruumid” (vene keeles), loogika ja semantika uuringutes, Z. Mikeladze (toim), Thbilisi: Metsniereba, lk 128–143.
  • –––, 2003, “Intuitionistlik loogika ja modaalsus topoloogia kaudu”, Annals of Pure and Applied Logic, 127: 155–170.
  • Goré, R., 2009, “Masinate kontrollimise tõestusteooria: loogika rakendamine loogikale”, ICLA '09: India 3. loogikakonverentsi ja selle rakenduste konverentsi toimingud, Berliin: Springer-Verlag, lk 23–35.
  • Goré, R. ja J. Kelly, 2007, “Automatiseeritud tõendusotsing Gödel-Löbi tõestatavuse loogikas”, Briti loogika kollokvium 2007, saadaval aadressil https://www.dcs.bbk.ac.uk/~roman/blc/.
  • Hakli, R. ja S. Negri, 2012, “Kas deduktsiooni teoreem nurjub modaalloogika jaoks?”, Synthese 187 (3): 849–867.
  • Icard, TF III, 2011, “GLP suletud fragmendi topoloogiline uuring”, Journal of Logic and Computation, 21 (4): 683–696; esmakordselt avaldatud veebis 2009, doi: 10.1093 / logcom / exp043
  • Japaridze, GK, 1986, Tõenäosuse uurimise modaalsed loogilised vahendid, filosoofia väitekiri (vene keeles), Moskva.
  • McKinsey, JCC ja A. Tarski, 1944, “Topoloogia algebra”, Annals of Mathematics, 45: 141–191.

Tõendatavus ja Peano aritmeetika

  • Davis, M., 1958, Arvutatavus ja lahutatavus, New York, McGraw-Hill; kordustrükk koos täiendava liitega, New York, Dover Publications 1983.
  • Feferman, S., 1960, “Metamatemaatika aritmeerimine üldises seadistuses”, Fundamenta Mathematicae, 49 (1): 35–92.
  • Hájek, P. ja P. Pudlák, 1993, Esimese astme aritmeetika metamaatika, Berliin: Springer-Verlag.
  • Solovay, RM, 1976, “Modaalloogika tõestatavuse tõlgendused”, Israel Journal of Mathematics, 25: 287–304.

Tõendatavuse loogika ulatus: piirid

  • Berarducci, A. ja R. Verbrugge, 1993, “Piiratud aritmeetika tõestatavuse loogikast”, Annals of Pure and Applied Logic, 61: 75–93.
  • Buss, SR, 1986, piiritletud aritmeetika, Napoli: Bibliopolis.
  • de Jongh, DHJ, M. Jumelet ja F. Montagna, 1991, “Solovay teoreemi tõestuse kohta”, Studia Logica, 50 (1): 51–70.

Tõlgendatavuse loogika

  • Berarducci, A., 1990, “Peano aritmeetika tõlgendatavuse loogika”, Journal of Symbolic Logic, 55: 1059–1089.
  • de Jongh, DHJ ja F. Veltman, 1990, “Suhtelise tõlgendatavuse loogika”, PP Petkov (toim), Matemaatiline loogika: Heytingi 1988. aasta suvekooli toimikud Varnas, Bulgaaria, Boston: Plenum Press, lk. 31–42.
  • de Jongh, DHJ ja A. Visser, 1991, “Selgesõnalised püsipunktid tõlgendusloogikas”, Studia Logica, 50 (1): 39–49.
  • Joosten, JJ, ja Visser, A., 2000, “Kõigi mõistlike aritmeetiliste teooriate tõlgendamisloogika”, Erkenntnis, 53 (1-2): 3–26.
  • Montagna, F., 1987, “Tõestatavus PA lõplikes alamteooriates”, Journal of Symbolic Logic, 52 (2): 494–511.
  • Šavrukov, V. Yu, 1988, “Peano aritmeetika suhtelise tõlgendamise loogika”, Tehniline aruanne nr 5, Moskva: Steklovi matemaatikainstituut (vene keeles).
  • Švejdar, V., 1983, “Rosseri üldiste lausete modaalne analüüs”, Journal of Symbolic Logic, 48: 986–999.
  • Visser, A., 1990, “Interpretability Logic”, PP Petkov (toim), Mathematical Logic: Proceedings of Heyting 1988 Summer School Varnas, Bulgaaria, Boston: Plenum Press, lk 175–209.
  • ––– 1998, „Ülevaade tõlgendamisloogikast”, M. Kracht jt. (toim), Advances in Modal Logic (1. köide), Stanford: CSLI Publications, lk 307–359.

Esialgsed kvantitaatorid

  • Artemov, SN ja LD Beklemishev, 1993, “Prolatiivsete kvantifikaatorite kohta tõestatavuse loogikas”, Notre Dame Journal of Formal Logic, 34: 401–419.
  • Šavrukov, V. Yu, 1997, “Otsustamatus diagonaaliseeritavates algebras”, Journal of Symbolic Logic, 62: 79–116.

Japaridze bimodaalse ja polümodaalse tõestatavuse loogika

  • Beklemishev, LD, 2004, “Provability Algebras and Proof-Theoretic Ordinals, I”, Annals of Pure and Applied Logic, 128: 103–123.
  • –––, 2010a, „Kripke Semantics for Provability Logic GLP”, Annals of Pure and Applied Logic, 161 (6): 756–774.
  • –––, 2010b, „Craigi interpolatsiooni ja GLP fikseeritud punkti omaduste kohta”, S. Feferman jt. (toim), tõendid, kategooriad ja arvutused (austusavaldused, 13), London: College Publications, lk 49–60.
  • –––, 2011a, „Tõestatavuse loogika heade laboritavade aritmeetilise täielikkuse teoreemi lihtsustatud tõestus”, Proceedings Steklov Matemaatika Instituut, 274 (1): 25–33.
  • –––, 2011b, „Bimodaalse tõestatavuse loogika GLB tavaline täielikkus”, N. Bezhanishvili jt. (toim.), loogika, keel ja arvutus, 8. rahvusvaheline Tbilisi sümpoosion TbiLLC 2009 (arvutiteaduse loengute märkused: köide 6618), Heidelberg: Springer, lk 1–15.
  • Beklemišev, LD ja D. Gabelaia, 2013, „Provability Logic GLP topoloogiline täielikkus”, Annals of Pure and Applied Logic, 164 (12): 1201–1223.
  • –––, 2014, „Provability Logic topological interpretations”, G. Bezhanishvili (toim), Leo Esakia teemal „Duaalsus modaalses ja intuitiivses loogikas” (Silmapaistvad kaastööd loogikale: 4. köide), Heidelberg: Springer, lk 257– 290.
  • Beklemišev, LD, J. Joosten ja M. Vervoort, 2005, “Japaridze tõestatavuse loogika suletud osa lõplik käsitlus”, Journal of Logic and Computation, 15 (4): 447–463.
  • Fernández-Duque, D. ja JJ Joosten, 2014, „Häid tellimusi Transfinite Japaridze algebras”, IGPL Logic Journal, 22 (6): 933–963.
  • Ignatiev, KN, 1993, “Tugeva tõestatavuse ennustamise ja sellega seotud modaalloogika kohta”, Journal of Symbolic Logic, 58: 249–290.
  • Japaridze, G., 1988, “Polümodaalse tõestatavuse loogika” intensiivses loogikas ja teooriate loogilises ülesehituses: Nõukogude-Soome neljanda loogikasümpoosioni materjal, Telavi, lk 16–48.
  • Pakhomov, FN, 2014, „Japaridze tõestatavuse loogika suletud fragmendi keerukusest“, Matemaatilise loogika arhiiv, 53 (7-8): 949–967.

Ennustatavuse loogika

  • Artemov, SN, 1985a, “Tõe ennustatavuse loogika mittearitmeetilisus”, Doklady Akademii Nauk, SSSR, 284: 270–271 (vene keeles); Ingliskeelne tõlge nõukogude matemaatikas Doklady, 32: 403–405.
  • McGee, V. ja G. Boolos, 1987, “Prognoositava tõestatavuse loogika lausekomplekti aste, mis on tõene iga tõlgenduse korral”, Journal of Symbolic Logic, 52: 165–171.
  • Vardanyan, VA, 1986, “Proviteeritavuse ja nende fragmentide ennustatava loogika aritmeetiline kompleks”, Doklady Akademii Nauk, SSSR, 288: 11–14 (vene keeles); Ingliskeelne tõlge nõukogude matemaatikas Doklady, 33: 569–572.
  • Visser, A. ja M. de Jonge, 2006, “Vardajani teoreemist ei pääse”, Matemaatilise loogika arhiiv, 45 (5): 539–554.

Muud üldistused

  • Alberucci, L. ja A. Facchini, 2009, “Modaalse μ-Calculuse ja Gödel-Löbi loogikast”, Studia Logica, 91: 145–169.
  • Artemov, SN, 1985b, “Tõenäosust aksiomatiliselt modifitseeriva loogika kohta”, Izvestiya Akadademii Nauk, NSVL, Seriya Matematicheskaya, 49 (6): 1123–1154 (vene keeles); Ingliskeelne tõlge NSVL-i matemaatikas - Izvestiya, 27 (3): 402–429.
  • –––, 1994, “Tõestusloogika”, Puhta ja rakendatud loogika ajakirjad, 67 (2): 29–59.
  • –––, 2001, “Selgesõnaline tõestatavus ja konstruktiivne semantika”, Sümboolse loogika bülletään, 7: 1–36.
  • Artemov, SN ja R. Iemhoff, 2007, “Tõendite põhiline intuitsiooniline loogika”, Journal of Symbolic Logic, 72 (2): 439–451.
  • Artemov, SN ja F. Montagna, 1994, “Esmajärjekorra teooriad koos tõestatavuse operaatoriga”, Journal of Symbolic Logic, 59 (4): 1139–1153.
  • Beklemišev, LDD, 1989, "Prolatiivse tõestatavuse loogika klassifitseerimise kohta", Izvestiya Akademii Nauk, NSVL, Seriya Matematicheskaya., 53 (5): 915–943 (vene keeles); Ingliskeelne tõlge NSVL-i matemaatikas - Izvestiya, 35 (1990) 247–275.
  • ––– 1994, „On tõestatavuse bimodaalne loogika”, Annals of Pure and Applied Logic, 68: 115–160.
  • –––, 1996, “Bimodaalne loogika aritmeetiliste teooriate laiendamiseks”, Journal of Symbolic Logic, 61: 91–124.
  • –––, 1999, “Parameetrivaba induktsioon ja selle arvutatavad funktsioonid kokku”, Teoreetiline arvutiteadus, 224: 13–33.
  • –––, 2005, “Peegelduspõhimõtted ja tõestatavuse algebrad formaalses aritmeetikas”, Uspekhi Matematicheskikh Nauk, 60 (2): 3–78. (Vene keeles); Ingliskeelne tõlge: Russian Mathematical Surveys, 60 (2) (2005): 197–268.
  • –––, 2006, „Ussiprintsiip”, logika loengute märkused 27. Logic Colloquium '02, Z. Chatzidakis, P. Koepke ja W. Pohlers (toim), Natick (MA): AK Peters, lk 75–95.
  • ––– 2012, „Provability Logic kalibreerimine: modaalsest loogikast reflektsiooni kalkuleerimiseni”, T. Bolander, T. Braüner, S. Ghilardi ja L. Moss (toim), Modaalloogika edendamine (9. köide)., London: College Publications, lk 89–94.
  • ––– 2014, “Ühtsete peegelduspõhimõtete positiivse tõestatavuse loogika”, Annals of Pure and Applied Logic, 165 (1): 82–105.
  • Beklemišev, LD, D. Fernández-Duque ja JJ Joosten, 2014, „Lineaarselt järjestatud modaalsustega tõestatavuse loogika kohta”, Studia Logica, 102 (3): 541–566.
  • Beklemishev, LD, M. Pentus ja N. Vereshchagin, 1999, Provability, Complexity, Grammars, American Mathematical Society Translations (Series 2, Volume 192).
  • Beklemišev, LD ja A. Visser, 2006, „Probleemid tõestatavuse loogikas”, DM Gabbay, SS Goncharov ja M. Zakharyashev (toim), Matemaatilised probleemid rakenduslikust loogikast I: loogika XXI sajandile (rahvusvaheline matemaatiline seeria), 4. köide), New York: Springer, lk 77–136.
  • van Benthem, J., 2006, “Modaalraami korrelatsioonid ja püsipunktid”, Studia Logica, 83 (1-3): 133–155.
  • Carlson, T., 1986, “Modaalne loogika mitme operaatoriga ja tõestatavuse tõlgendused”, Israel Journal of Mathematics, 54 (1): 14–24.
  • Dashkov, EV, 2012, „Polümodaalse tõestatavuse loogika heade tavade positiivse fragmendi kohta”, Mathematical Notes, 91 (3): 318–333.
  • Fernández-Duque, D., 2014, „Transfinite Provability Logic Polytopologies of Transfinite Provability Logic“, Matemaatilise loogika arhiiv, 53 (3-4): 385–431.
  • Fernández-Duque, D. ja JJ Joosten, 2013a, “Hüperatsioonid, Vebleni progressioonid ja tavaliste funktsioonide transfinite kordamine”, Annals of Pure and Applied Logic 164 (7-8): 785–801, [saadaval veebis].
  • Fernández-Duque, D. ja JJ Joosten, 2013b, “Transfinite Provability Logic Models of Transfinite Provability Logic”, Journal of Symbolic Logic, 78 (2): 543–561, [saadaval veebis].
  • Guaspari, D. ja RM Solovay, 1979, “Rosseri laused”, Annals of Mathematical Logic, 16: 81–99.
  • Iemhoff, R., 2000, “Aritmeetika heytimise tõenäosusloogika mõne põhimõtte modaalne analüüs”, ajakirjas Advances in Modal Logic (2. köide), M. Zakharyashev et al. (toim), Stanford: CSLI Publications, lk 319–354.
  • –––, 2001, „Intuitionistliku propositsioonilise loogika lubatavate reeglite kohta”, Journal of Symbolic Logic, 66: 281–294.
  • –––, 2003, “Säilitusloogika: konstruktiivsete teooriate tõlgendamisloogika analoog”, Matemaatiline loogika kvartal, 49 (3): 1–21.
  • Lindström, P., 1994, “Parikhi tõestatavuse modaalloogika”, Filosofiska Meddelanden, Gröna Serien, Göteborg: Göteborgs Universitetet.
  • Lindström, P., 2006, “Parikhi tõestatavuse kohta: modaalloogika harjutus”, H. Lagerlund, S. Lindström ja R. Sliwinski (toim.), Modaalsuse küsimused: 25 esseed Krister Segerbergi auks. Uppsala: Uppsala filosoofilised uurimused (53. köide), lk 53–287.
  • Montagna, F., 1978, “Fefermani predikaadi algebreerimise kohta”, Studia Logica, 37 (3): 221–236.
  • ––– 1979, „Peano aritmeetika diagonoositavast algebrast”, Bollettino della Unione Matematica Italiana, B (5), 16: 795–812.
  • –––, 1980a, „Diagnoositavate algebrate esimese astme teooria tõlgendused Peano aritmeetikas”, Studia Logica, 39: 347–354.
  • –––, 1980b, “Diagonoositavate algebrate esimese järgu teooria seletatavus”, Studia Logica, 39: 355–359.
  • –––, 1984, „Prognoositavuse eeldatav modaalne loogika“, Notre Dame Journal of Formal Logic, 25 (2): 179–189.
  • ––– 1992, “Polünoomiliselt ja supereksponentselt lühemad tõendid aritmeetika fragmentides”, Journal of Symbolic Logic, 57: 844–863.
  • Pakhomov, FN, 2012, “GLP-sõnade ristteabe elementaarse teooria seletamatus”, Sbornik: Mathematics, 203 (8): 1211.
  • Shapirovsky, I., 2008, “JaSPidze polümodaalse loogika PSPACE-otsustatavus”, Advances in Modal Logic, 7: 289–304.
  • Shavrukov, V. Yu, 1993a, “Märkus PA ja ZF diagonaalitatavate algebrate kohta”, Annals of Pure and Applied Logic, 61: 161–173.
  • –––, 1993b, “Aritmeetikat sisaldavate teooriate diagonoositavate algebrate subalgebrad”, Dissertationes Mathematicae, 323.
  • ––– 1994, “Nutikas Peano laps”, Notre Dame Journal of Formal Logic, 35 (2): 161–185.
  • Troelstra, AS, 1973, intuitsioonilise aritmeetika ja analüüsi metamaatiline uurimine, Berliin: Springer-Verlag.
  • Visser, A., 1980, diagonaalimise ja tõestatavuse aspektid, Ph. D. Lõputöö, Utrecht: Utrechti ülikool.
  • –––, 1982, „Terviklikkuse põhimõttest: Heytingi aritmeetika ja laiendite tõestatavuse uuring”, Annals of Mathematical Logic, 22 (3): 263–295.
  • ––– 1989, „Peano nutikad lapsed: sisseehitatud järjepidevusega süsteemide tõestatavuse loogiline uuring”, Notre Dame Journal of Formal Logic, 30 (2): 161–196.
  • –––, 1999, “Reeglid ja aritmeetika”, Notre Dame Journal of Formal Logic, 40 (1): 116–140.
  • –––, 2002, “(Sigma_1) lausete asendamised: uurimised intuitsioonilise propositsioonilise loogika ja intuitsioonilise aritmeetika vahel”, Annals of Pure and Applied Logic, 114: 227–271.
  • –––, 2005, „Löbi loogika vastab μ-kalkuleerimisele”, A. Middeldorp, V. van Oostrom, F. van Raamsdonk ja R. de Vrijer (toim), protsessid, tingimused ja tsüklid: sammud teel lõpmatusse, Berliin: Springer, lk 14–25.
  • –––, 2008, „Konstruktiivsete teooriate tõestatavuse loogika suletud killud“, Journal of Symbolic Logic, 73: 1081–1096.
  • Zambella, D., 1994, “Shavrukovi teoreem diagonaaliseeritavate algebrate subalgebratest teooriate jaoks, mis sisaldavad (I / Delta_0 + / exp)”, Notre Dame Journal of Formal Logic, 35: 147–157.

Filosoofiline tähtsus

  • Davis, M., 1990, “Kas matemaatiline ülevaade on algoritmiline?”, Kommentaar Roger Penrose'ile, keisri uuele meelele, käitumis- ja ajuteadustele, 13: 659–660.
  • ––– 1993, “Kui peen on Gödeli teoreem?” (Kommentaar Roger Penrose'ile, keisri uuele meelele), käitumis- ja ajuteadused, 16: 611–612.
  • Egré, P., 2005, “Knoweri paradoks modaalse loogika tõlgendatavuse valguses”, “Logic, Language and Information”, 14 (1): 13–48.
  • Kaplan, D. ja R. Montague, 1960, “Paradoks sai tagasi”, Notre Dame Journal of Formal Logic, 1 (3): 79–90.
  • Montague, R., 1963, “Modaalsuse süntaktilised käsitlused peegeldumispõhimõtete ja piiritletud aksiomatilisuse parandustega”, Acta Philosophica Fennica, 16: 153–67.
  • Quine, WV, 1966, “Vajalik tõde”, Quine, WV, “Paradoksi viisid ja muud esseed”, New York: Random House, lk 48–56.
  • ––– 1953, Amsterdami 11. rahvusvahelise filosoofiakongressi toimetus „Kolmeastmeline kaasamine moodulisse”, Põhja-Holland, lk 65–81; kordustrükk ajakirjas WV Quine, „Paradoksi viisid ja muud esseed“, New York: Random House, 1966, lk 156–174.

Akadeemilised tööriistad

sep mehe ikoon
sep mehe ikoon
Kuidas seda sissekannet tsiteerida.
sep mehe ikoon
sep mehe ikoon
Vaadake selle sissekande PDF-versiooni SEP-i sõprade veebisaidil.
info ikoon
info ikoon
Otsige seda sisenemisteema Interneti-filosoofia ontoloogiaprojektilt (InPhO).
phil paberite ikoon
phil paberite ikoon
Selle kande täiustatud bibliograafia PhilPapersis koos linkidega selle andmebaasi.

Muud Interneti-ressursid

Ettekanded ja ettekanded

  • Fernández-Duque, D. ja JJ Joosten, 2013, “Omega-reegli tõlgendamine transfinite tõestatavuse loogikast”, veebikäsikiri arxiv.org.
  • Henk, P. ja Pakhomov, F., 2016, “Peano aritmeetika aeglane ja tavaline tõestatavus”, käsikiri arxiv.org.
  • Pakhomov, F., 2014, “GLP-algebrate elementaarteooriatest”, käsikiri arxiv.org.
  • Pakhomov, F., 2015, “Peegeldumispõhimõtetel põhinevate tavaliste märkimissüsteemide elementaarteooriatest”, käsikiri arxiv.org.
  • Visser, Albert, Ametliku ja inimese tõestatavuse kohta (hollandi keeles), veebikäsikiri, Utrechti ülikool.
  • Verbrugge, Rineke, Esitlusslaidid tõestatavuse loogikast, slaidid, Groningeni ülikool

Muud saidid

  • Tõenäosusloogika lahtised probleemid, haldaja Lev Beklemišev
  • Postitusloend Matemaatika alused, New Yorgi ülikool