Logika Dokazivosti

Sadržaj:

Logika Dokazivosti
Logika Dokazivosti
Anonim

Ulazna navigacija

  • Sadržaj unosa
  • Bibliografija
  • Akademske alate
  • Prijatelji PDF pregled
  • Podaci o autoru i citiranju
  • Povratak na vrh

Logika dokazivosti

Prvo objavljeno u srijedu 2. travnja 2003.; suštinska revizija Wed Apr 5, 2017

Logika dokazivosti modalna je logika koja se koristi da bi se istražilo što aritmetičke teorije mogu izraziti ograničenim jezikom o predikatima njihove provedivosti. Logika je inspirirana razvojem meta-matematike, poput Gödelovih teorema o nepotpunosti iz 1931. i Löbova teorema iz 1953. Kao modalna logika, logika dokazivanja proučavala se od ranih sedamdesetih godina i imala je važne primjene u osnovama matematike.

S filozofskog stajališta, logika dokazivosti je zanimljiva jer koncept dokazivosti u fiksnoj teoriji aritmetike ima jedinstveno i neproblematično značenje, osim koncepata poput nužnosti i znanja proučavanih u modalnoj i epiztemičkoj logici. Nadalje, logika dokazivosti pruža alate za proučavanje pojma samoreferencije.

  • 1. Povijest logike dokazivosti
  • 2. Aksiomni sustav logike prijedloga provabilnosti

    • 2.1 Aksiomi i pravila
    • 2.2 Teorem fiksne točke
  • 3. Moguća semantika svjetova i topološka semantika

    • 3.1 Karakterizacija i modalna zvučnost
    • 3.2 Modalna cjelovitost
    • 3.3 Neuspjeh jake cjelovitosti
    • 3.4 Topološka semantika logike dokazivosti
  • 4. Logika dokazivosti i peano aritmetika

    • 4.1 Aritmetička zvučnost
    • 4.2 Aritmetička cjelovitost
  • 5. Opseg logike dokazivosti

    • 5.1 Granice
    • 5.2 Logika tumačenja
    • 5.3 Propozicioni kvantifikatori
    • 5.4 Japaridzeova bimodalna i polimodalna logika dokazivosti
    • 5.5 Predvidi logiku dokazivosti
    • 5.6 Ostale generalizacije
  • 6. Filozofski značaj
  • Bibliografija
  • Akademske alate
  • Ostali internetski resursi

    • Radovi i prezentacije
    • Ostala web mjesta
  • Povezani unosi

1. Povijest logike dokazivosti

Dva pravca istraživanja dovela su do rađanja logike dokazivosti. Prvi potječe iz rada K. Gödela (1933.), gdje uvodi prijevode iz intuicijske propozicijske logike u modalnu logiku (točnije, u sustav koji se danas naziva S4), te ukratko spominje da se provabilnost može promatrati kao modalni operator, Još ranije CI Lewis započeo je moderno proučavanje modalne logike uvodeći strogu implikaciju kao neku vrstu dedujibilnosti, pri čemu je on možda mislio na dedujibilnost u formalnom sustavu poput Principia Mathematica, ali to nije jasno iz njegovih zapisa.

Drugi pravac polazi od istraživanja meta-matematike: što matematičke teorije mogu reći o sebi kodiranjem zanimljivih svojstava? Godine 1952., L. Henkin je postavio varljivo jednostavno pitanje nadahnuto Gödelovim teoremima nepotpunosti. Da bi se formuliralo Henkinovo pitanje, potrebna je još neka podloga. Kao podsjetnik, Gödelov prvi teorem o nepotpunosti kaže da je za dovoljno snažnu formalnu teoriju poput aritmetike peano svaka rečenica koja tvrdi vlastitu neizrecivost u stvari nedokaziva. S druge strane, izvana "formalne teorije" može se vidjeti da je takva rečenica istinita u standardnom modelu, ukazujući na važnu razliku između istine i dokazivosti.

Formalnije, neka (ulcorner A / urcorner) označava Gödel broj aritmetičke formule (A), što je rezultat dodjeljivanja numeričkog koda (A). Neka je ((Prov) formalizirani predikat provabilnosti za Peano Aritmetiku, koji je oblika (postoji p \, / Dokaz (p, x)). Ovdje je (Dokaz) formalizirani dokazni predikat peano-aritmetike, a (Dokaz (p, x)) stoji za „Gödelov broj (p) kodira točan dokaz iz aksioma Peano-aritmetike formula s Gödelovim brojem (x)”. (Za precizniju formulaciju pogledajte Smoryński (1985), Davis (1958).) Pretpostavimo da Peano Aritmetika dokazuje (A / leftrightarrow / neg) (Prov (ulcorner A / urcorner)), tada po Gödelinom rezultatu, (A) nije dokazano u aritmetikama peano, i stoga je istina, jer u stvari samoreferencijalna rečenica (A) kaže „nisam dokazana“.

Henkin je s druge strane želio znati može li se nešto reći o rečenicama koje potvrđuju vlastitu dokazivost: pretpostavljajući da Peano Aritmetika dokazuje (B / leftrightarrow / Prov (ulcorner B / urcorner)), što to znači o (B)? Tri godine kasnije M. Löb je prihvatio izazov i na iznenađujući način odgovorio na Henkinovo pitanje. Iako su sve rečenice koje se mogu dokazati u aritmetikama peano doista istinite u vezi s prirodnim brojevima, Löb je pokazao da se formalizirana verzija te činjenice, ((Prov (ulcorner B / urcorner) rightarrow B), može dokazati samo u Peano Arithmetic-u u trivijalnom slučaju da Peano Aritmetika već dokazuje (B). Ovaj rezultat, koji se sada naziva Löbovim teoremom, odmah odgovara na Henkinovo pitanje. (Za dokaz Löbove teoreme vidi odjeljak 4.) Löb je također pokazao formaliziranu verziju svog teorema,naime to dokazuje aritmetika Peanoa

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

U istom je radu Löb formulirao tri uvjeta na predikatu proverljivosti Peano aritmetike, koji tvore korisnu izmjenu složenih uvjeta koje su Hilbert i Bernays uveli 1939. godine kao dokaz Gödelove druge teoreme nepotpunosti. U nastavku, izvedljivost (A) iz peano aritmetike označava se s (PA / vdash A):

  1. Ako je (PA / vdash A), tada (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).)

Ovi Löbovi uvjeti, kako ih danas nazivaju, izgledaju kao modalni logički pregled, gdje modalitet (Box) označava proverljivost u PA. Ironično je da je prvi put da je formalizirana verzija Löbove teoreme navedena kao modalni princip

) Kutija (Kutija A / rightarrow A) rightarrow / Kutija A)

bio je u radu Smileyja 1963. o logičkoj osnovi etike koja uopće nije razmatrala aritmetiku. Međutim, relevantnije istrage ozbiljno su započele tek gotovo dvadeset godina nakon objavljivanja Löbovog rada. U ranim 1970-ima došlo je do brzog razvoja logike propozicijskog provabiliteta, gdje je nekoliko istraživača u različitim zemljama neovisno dokazalo najvažnije rezultate, o kojima se raspravljalo u odjeljcima 2, 3 i 4. Pokazalo se da je logika provazibilnosti dokazala upravo ono što mnoge formalne aritmetičke teorije mogu reći prijedloškim sredstvima o vlastitom predikatu provjerljivosti. U novije vrijeme, istraživači su istraživali granice ovog pristupa i predložili nekoliko zanimljivih ekspresivnijih proširenja logike provjerljivosti (vidi Odjeljak 5).

2. Aksiomni sustav logike prijedloga provabilnosti

Logički jezik logike provazibilnosti propozicije sadrži, osim prijedloga atoma i uobičajenih operatora koji služe istini, kao i kontradiktorni simbol (bot), modalni operator (Kutija) s namjeravanim značenjem "može se pronaći u (T), "gdje je (T) dovoljno jaka formalna teorija, recimo peano aritmetika (vidjeti odjeljak 4). (Diamond A) je skraćenica za (neg \, / Box / neg \, A). Dakle, jezik je isti kao i kod modalnih sustava poput K i S4 prikazanih u modalitetu logike unosa.

2.1 Aksiomi i pravila

Logika propozicijske provabilnosti često se naziva GL, nakon Gödela i Löba. (Alternativna imena pronađena u literaturi za ekvivalentne sustave su L, G, KW, K4W i PrL). Logička GL rezultat je dodavanja sljedećeg aksioma osnovnoj modalnoj logici K:

) oznaka {GL} Kutija (Kutija A / rightarrow A) rightarrow / Kartica A.)

Podsjećanja radi, jer GL proširuje K, sadrži sve formule koje imaju oblik prijedložne tautologije. Iz istog razloga, GL sadrži i

) tag {Aksiom distribucije} Kutija (A / rightarrow B) rightarrow (Okvir A / rightarrow / Kutija B).)

Nadalje, zatvoreno je pod pravilom Modus Ponens, koje omogućuje dobivanje (B) iz (A / rightarrow B) i (A), te pravilom generalizacije, koje kaže da ako (A) je teorema GL, tada je to i (Okvir A).

Pojam (GL / vdash A) označava proverljivost modalne formule (A) u logici prijedloga provabilnosti. Nije teško vidjeti da je modalni aksiom (Box A / rightarrow / Box / Box A) (poznat kao Aksiom 4 modalne logike) doista dostupan u GL. Da bismo to dokazali, upotrebljavamo supstituciju (A / klin / Kutija A) za (A) u aksiomu (GL). Zatim, vidjevši da antecedent rezultirajuće implikacije slijedi iz (okvir A), primjenjujemo se Aksiom distribucije i Pravilo generalizacije, kao i neka logika prijedloga. Ako nije izričito drugačije navedeno, u nastavku „logika dokazivosti“stoji za sistemski GL logike prijedloga proverljivosti.

Što se tiče teorije dokaza logike dokazivosti, Valentini (1983) je dokazao da standardna formulacija sekvencijalnog kalkulusa GL podliježe eliminaciji reza, što znači, grubo formulirano, da svaka formula koja se može dokazati iz GL-a u sekvencijskom računu također ima dokaz GL-sekvencije „bez zaobilaznice”(vidjeti unos razvoj teorije dokaza za precizno objašnjenje uklanjanja reza). Posljednjih godina obnavlja se zanimanje za teoriju dokaza o GL-u, vidi, na primjer, Goré i Ramanayake (2008). Eliminacija reza dovodi do poželjnog svojstva subformula za GL, jer su sve formule koje se pojavljuju u dokazu bez reza podformule sljedećih formula.

Pogledajte nedavna dokazno-teorijska ispitivanja logike dokazivosti koja se temelje na različitim sekvencijalnim proračunima bez reza (Negri 2005, 2014; Poggiolesi 2009). Negri prikazuje dva ekvivalentna obilježena sekvencijalna kalkulacija za GL i sintaktički dokaz uklanjanja reza. Čak i ako se svojstvo potformule ne drži za ove kalkulacije zbog označavanja, mogu se utvrditi uobičajene posljedice svojstva podformule: Označeni formalizam omogućava izravan dokaz potpunosti, koji se može koristiti za utvrđivanje mogućnosti iskoristivosti i konačnog modela svojstvo, što znači da svaka formula koja se ne može dokazati ima konačni kontra-model.

Intrigantni novi dokazno-teorijski razvoj je Shamkanovo širenje sustava dokaza u slijedu koji omogućuju kružne dokaze (Shamkanov 2014). Razmotrimo redoslijed sustava za K4, modalni sustav koji proizlazi iz GL zamjenom aksioma GL slabijim aksiomom (Box A / rightarrow / Box / Box A) (aksiom 4). No, pretpostavimo da su dopuštene otvorene hipoteze, pod uvjetom da se isti slijed dogodi strogo ispod te hipoteze u stablu dokaza. Tehnički formulirano može se pronaći kružna izvedba iz običnog izvedenog stabla povezivanjem svakog njegovog neakiomatskog lišća s identičnim unutarnjim čvorom. Shamkanov (2014) je dokazao da je rezultirajući sustav dosljedan i da, osim toga, svaki slijed ima GL-izvedenje ako i samo ako ima kružnu izvedbu K4. Kružni dokazi također pružaju metodu za teoretski dokaz da Lyndon-ova teorija za interpolaciju vrijedi za GL. Standardna interpolacija za GL već je ranije dokazana različitim metodama (Boolos 1979; Smoryński 1978; Rautenberg 1983). (Za više informacija o Lyndon-ovoj interpolacijskoj teoremi za logiku prvog reda, vidi također i teoriju unosa modela prvog reda).

2.2 Teorem fiksne točke

Glavni „modalni“rezultat logike dokazivosti je teorema o fiksnoj točki, koju su D. de Jongh i G. Sambin neovisno dokazali 1975. (Sambin 1976). Iako je formulirana i dokazana strogo modalnim metodama, teorema o fiksnoj točki i dalje ima veliko aritmetičko značenje. U osnovi kaže da samo referenca u sljedećem smislu zapravo i nije potrebna. Pretpostavimo da su sva pojavljivanja propozicione varijable (p) u datoj formuli (A (p)) unutar djelovanja operatora proverljivosti, na primjer (A (p) = / neg / Box p), ili (A (p) = / Kutija (p / rightarrow q)). Zatim postoji formula (B) u kojoj se (p) ne pojavljuje, tako da se sve prijedloge varijable koje se javljaju u (B) već pojavljuju u (A (p)), i takva da

) GL / vdash B / lijeva svjetla A (B).)

Ova se formula (B) naziva fiksna točka (A (p)). Štoviše, nepokretna je točka jedinstvena, ili točnije, ako postoji druga formula (C) takva da (GL / vdash C / leftrightarrow A (C)), tada moramo imati (GL / vdash B / lijeva svjetla C). Većina dokaza u literaturi daje algoritam pomoću kojeg se može izračunati fiksna točka (vidjeti Smoryński 1985, Boolos 1993, Sambin i Valentini 1982, Lindström 2006). Posebno kratak i jasan dokaz, kao i vrlo učinkovit algoritam za računanje fiksnih točaka, mogu se naći u Reidhaar-Olson (1990).

Na primjer, pretpostavimo da je (A (p) = / neg \, / Okvir p). Tada je fiksna točka proizvedena takvim algoritmom (neg \, / Box / bot), i zaista se može dokazati da

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

Ako se ovo čita aritmetički, pravac slijeva udesno samo je formalizirana verzija Gödelove druge teoreme o nepotpunosti: ako dovoljno jaka formalna teorija (T) poput Peano aritmetike ne dokaže proturječnost, onda nije dokazana u (T) da (T) ne dokazuje kontradikciju. Prema tome, dovoljno jake konzistentne aritmetičke teorije ne mogu dokazati vlastitu dosljednost. Okrenut ćemo se proučavanju odnosa logike provabilnosti i aritmetike točnije u odjeljku 4, ali u tu svrhu prvo treba pružiti još jedan „modalni“aspekt GL: semantika.

3. Moguća semantika svjetova i topološka semantika

Logika dokazivosti ima prikladne semantike mogućih svjetova, baš kao i mnoge druge modalne logike. Podsjećanja radi, mogući model svjetova (ili Kripkeov model) je trostruki (M = / langle W, R, V / rangle), gdje je (W) ne-prazan skup mogućih svjetova, (R) je binarni odnos pristupačnosti na (W), a (V) je vrijednost koja dodjeljuje vrijednost istinitosti svakoj predloženoj varijabli za svaki svijet u (W). Par (F = / langle W, R / rangle) naziva se okvirom ovog modela. Pojam istine formule (A) u modelu (M) u svijetu (W), notacija (M, w / modeli A) definiran je induktivno. Ponovimo samo najzanimljiviju klauzulu, onu za operatora provjerljivosti (Box):

[M, w / modeli / Okvir A / tekst {iff za svaki} w ', / tekst {ako} wRw', / tekst {tada} M, w '\ modeli A.)

Pogledajte modalitet logike za unos za više informacija o mogućoj semantike svjetova uopće.

3.1 Karakterizacija i modalna zvučnost

Modalna logika K vrijedi u svim Kripkeovim modelima. Njegova ekstenzija GL, međutim, nije: klasu mogućih svjetskih modela moramo ograničiti na prikladniji. Recimo da formula (A) vrijedi u okviru (F), notacija (F / modeli A), iff (A) vrijedi u svim svjetovima u Kripkeovim modelima (M) na temelju (F). Ispada da novi aksiom (GL) logike dokazivosti odgovara uvjetima na okvirima, kako slijedi:

Za sve okvire (F = / langle W, R / rangle, F / modeli / Box (Box p / rightarrow p) rightarrow / Box p) iff (R) je tranzitivan i obrnuto utemeljen.

Ovdje je tranzitivnost poznato svojstvo koje je za sve svjetove (w_1), (w_2), (w_3) u (W), ako (w_1 Rw_2) i (w_2 Rw_3), zatim (w_1 Rw_3). Odnos je obrnuto utemeljen ako nema beskonačnih nizova u usponu, to su nizovi oblika (w_1 Rw_2 Rw_3 R / ldots). Imajte na umu da su obrnuto utemeljeni okviri također nerefleksivni, jer ako (wRw), to stvara beskonačni uzlazni niz (wRwRwR / ldots).

Gornji rezultat korespondencije odmah pokazuje da je GL modalno zvučan s obzirom na klasu mogućih svjetskih modela na tranzitivno obrnuto utemeljenim okvirima jer na takvim modelima vrijede svi aksiomi i pravila GL-a. Pitanje je i da li potpunost također drži: na primjer, formula (Box A / rightarrow / Box / Box A), koja vrijedi za sve prijelazne okvire, doista je dokazana u GL, kao što je spomenuto u odjeljku 1. Ali je li svaka formula koja vrijedi za sve tranzitivne obrnuto utemeljene okvire dokazana i u GL?

3.2 Modalna cjelovitost

Nesvjestan aritmetičkog značenja GL-a, K. Segerberg je 1971. dokazao da je GL doista cjelovit s obzirom na tranzitivne obrnuto utemeljene okvire; D. de Jongh i S. Kripke neovisno su dokazali i ovaj rezultat. Segerberg je pokazao da je GL cjelovit čak i s obzirom na ograničenu klasu konačnih tranzitivnih irefleksivnih stabala, što se kasnije pokazalo vrlo korisnim za Solovayev dokaz teoreme o aritmetičkoj potpunosti (vidi Odjeljak 4).

Teoremi o modalnoj zvučnosti i cjelovitosti odmah potiču postupak odlučivanja za provjeru da li bilo koja modalna formula (A) da li (A) slijedi iz GL ili ne, pretraživanjem najprije po dubini kroz nerefleksivna tranzitivna stabla ograničene dubine. Promatrajući postupak malo preciznije, može se pokazati da je GL razlučiv u razredu složenosti računanja PSPACE, poput poznatih modalnih logika K, T i S4. To znači da postoji Turingov stroj koji, s danom formulom (A) kao ulazom, odgovara li (A) slijedi iz GL ili ne; veličina memorije koja Turingovom stroju treba za njegovo izračunavanje samo je polinom u duljini (A). Može se pokazati da je problem odlučivanja za GL (opet, poput problema s odlukama za K, T i S4) PSPACE-cjelovit,u smislu da svi ostali problemi u PSPACE-u nisu ništa teže od odlučivanja da li je današnja formula teorema GL. (Pogledajte Goré i Kelly (2007) za opis automatizirane potvrde teorema za GL.)

Da bi se dobila dodatna perspektiva složenosti, klasa P funkcija koja se može izračunati u duljini unosa vremenskog polinoma uključena je u PSPACE, što je zauzvrat uključeno u klasu EXPTIME funkcija koje se mogu izračunati u eksponencijalnom vremenu (vidi ulazna računarnost i složenost). Ostaje poznati otvoreni problem jesu li ove dvije uključenosti stroge, premda mnogi teoretičari složenosti vjeruju da jesu. Neke druge poznate modalne logike, poput epistemičke logike sa općim znanjem, mogu se odrediti u EXPTIME, pa mogu biti složenije od GL, ovisno o otvorenim problemima.

3.3 Neuspjeh jake cjelovitosti

Mnoge poznate modalne logike (S) nisu samo kompletne u odnosu na odgovarajuću klasu okvira, već su čak i snažno cjelovite. Da bismo objasnili snažnu cjelovitost, potreban nam je pojam izvedljivosti iz skupa pretpostavki. Formula (A) proizlazi iz skupa pretpostavki (Gamma) u modalnoj logici (S), napisana kao (Gamma / vdash A), ako je (A) u (Gamma) ili (A) slijedi iz formula u (Gamma) i aksioma (S) primjenom Modus Ponensa i pravila generalizacije. Ovdje se Pravilo generalizacije može primijeniti samo na derivacije bez pretpostavki (vidjeti Hakli i Negri 2010).

Sada je modalna logika (S) snažno potpuna ako je za sve (konačne ili beskonačne) skupove (Gamma) i sve formule (A):

Ako je, na odgovarajućim (S) okvirima, (A) istinito u svim svjetovima u kojima su sve formule (Gamma) istinite, onda je (Gamma / vdash A) u logici (S).

Ovaj uvjet vrijedi za sustave poput K, M, K4, S4 i S5. Ako je ograničen na konačne skupove (Gamma), gornji uvjet odgovara potpunosti.

Međutim, snažna potpunost ne važi za logikom dokazivosti jer semantička kompaktnost ne uspijeva. Semantička kompaktnost je svojstvo koje za svaki beskonačni skup formula (Gamma) formula, Ako svaki konačni podskup (Delta) iz (Gamma) ima model na odgovarajućem (S) - okviru, onda (Gamma) također ima model na odgovarajućem (S) -frame.

Kao kontrazagled, uzmite beskonačni skup formula

) 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 })

Tada se za svaki konačni podskup (Delta) (Gamma) može konstruirati model na tranzitivnom, obrnuto utemeljenom okviru i svijetu u modelu u kojem su sve formule (Delta) pravi. Dakle, modalnom zvučnošću GL ne dokazuje (bot) iz (Delta) za nijedno ograničenje (Delta / subseteq / Gamma), a fortiori GL ne dokazuje (bot) iz (Gamma), kao što je bilo koji GL-dokaz konačan. S druge strane, lako je vidjeti da ne postoji model na tranzitivnom, obrnuto utemeljenom okviru u kojem u bilo kojem svijetu postoje sve formule (Gamma). Dakle, (bot) semantički slijedi iz (Gamma), ali se od nje ne može dokazati u GL, što je u suprotnosti s uvjetom jake cjelovitosti.

3.4 Topološka semantika logike dokazivosti

Kao alternativa mogućoj semantičnosti svjetova, mnoge modalne logike mogu se dati topološkoj semantika. Jasno je da se prijedlozi mogu protumačiti kao podskupovi topološkog prostora. Lako je također vidjeti da propozicijska vezivnost (klina) odgovara teoretskom skupu (cap), dok (vee) odgovara (cup), (neg) odgovara kompletu teoretskog komplementa, a (rightarrow) odgovara (subseteq). Modalna logika koja sadrži aksiom refleksije (Okvir A / rightarrow A) također uživa posebno prirodno tumačenje modalnih operatora. Za ove logike (Diamond) odgovara operatoru zatvaranja u topološkom prostoru, dok (Box) odgovara unutrašnjosti. Da biste vidjeli zašto su ta tumačenja primjerena,primijetite da aksiom refleksije odgovara činjenici da je svaki skup uključen u njegovo zatvaranje, a svaki skup uključuje njegovu unutrašnjost.

Međutim, logika dokazivosti ne dokazuje odraz, jer bi instancija (Box / bot / rightarrow / bot) refleksije dovela do kontradikcije s aksiomom (GL).

Logika dokazivanja stoga treba drugačiji pristup. Na temelju prijedloga J. McKinsey i A. Tarski (1944), L. Esakia (1981, 2003) istraživao je interpretaciju (Diamond) kao izvedenog operatora skupa (d), koji preslikava skup (B) na skupu svojih graničnih točaka (d (B)). Da bismo objasnili posljedice ove interpretacije (Diamond), potrebne su nam još dvije definicije, naime koncepti gusto u sebi i raspršeni. Podskup (B) topološkog prostora naziva se gusto samo po sebi ako (B / subseteq d (B)). Topološki prostor naziva se raspršen ako nema ne-prazan podskup koji je sam po sebi gust. Ordinali u svojoj intervalnoj topologiji čine primjere rasutih prostora. Esakia (1981) se pokazao važnom podudarnošću: pokazao je da topološki prostor zadovoljava aksiom GL ako i samo ako je prostor razbacan. Ta je korespondencija ubrzo dovela do rezultata, koji su Abashidze (1985.) i Blass (1990.) neovisno utvrdili da je logika dokazivanja potpuna u odnosu na bilo koji redni (ge / omega ^ / omega).

Posljednjih godina topološka semantika logike dokazivosti doživjela je pravi preporod, posebno u proučavanju Japaridzeove bimodalne logike provabilnosti GLB, proširenje GL (Japaridze 1986). Pokazalo se da je logika GLB modularno nepotpuna s obzirom na moguću svjetsku semantiku, u smislu da ne odgovara nijednoj klasi okvira. Ovo svojstvo stavlja bimodalni GLB u oštar kontrast s unimodalnim GL, što odgovara klasi konačnih tranzitivnih irefleksivnih stabala, kao što je gore spomenuto. Beklemishev i sur. (2009) pokazao je da je GLB, međutim, cjelovit s obzirom na njegovu topološku semantiku (vidi također Beklemishev 2009, Icard 2011). Intrigantni odjek Esakijine korespondencije između GL i raspršenih topoloških prostora može se naći čak i u nedavnim topološkim studijama prostorne i epiztemičke logike (vidjeti Aiello i sur.2007). (Pogledajte odjeljak 5.4 za daljnju raspravu o GLB-u).

4. Logika dokazivosti i peano aritmetika

Iz vremena formuliranja GL-a, istraživači su se pitali je li to primjereno formalnim teorijama poput Peano-aritmetike (PA): dokazuje li GL sve o pojmu proverljivosti koji se može izraziti prijedloškim modalnim jezikom i može se dokazati u Peano-aritmetici ili treba li u GL dodati više principa? Da bismo ovo poimanje adekvatnosti učinili preciznijim, definiramo da je realizacija (koja se ponekad naziva prijevod ili interpretacija) funkcija f koja svakom predloženom atomu modalne logike dodjeljuje aritmetičku rečenicu, pri čemu je

  • (F (bot) = / bot;)
  • (f) poštuje logičke konektive, na primjer, (f (B / rightarrow C) = (f (B) rightarrow f (C));) i
  • (Kutija) prevodi se kao predikat provabilnosti (Prov), pa je (f (Okvir B) = / Prov (ulcorner f (B) urcorner).)

4.1 Aritmetička zvučnost

Već ranih sedamdesetih godina prošlog stoljeća GL je bio aritmetički zvučan u odnosu na PA, formalno:

) text {If} GL / vdash A, / text {tada za sve realizacije} f, / PA / vdash f (A).)

Da bismo dobili neki okus meta-matematike, nacrtajmo dokaz zvučnosti.

Dokazna skica aritmetičke zvučnosti. PA doista dokazuje ostvarenja propozicijskih tautologija, a proverljivost aksioma distribucije GL prevodi na

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

za sve formule A i B, što je samo Löbov drugi uvjet izvedljivosti (vidi Odjeljak 1). Nadalje, PA se pridržava Modus Ponensa, kao i prijevod Pravilnika o generalizaciji:

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

što je upravo Löbov prvi uvjet izvedljivosti. Konačno, prijevod glavnog aksioma (GL) doista je dokaziv u PA:

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

To je upravo formalizirana verzija Löbovog teorema spomenutog u 1. odjeljku.

Donosimo skicu dokaza samog Löbovog teorema iz njegovih uvjeta izvedljivosti (dokaz formalizirane verzije je sličan). Dokaz se temelji na Gödelovoj lemi za dijagonalizaciju, koja kaže da za bilo koju aritmetičku formulu (C (x)) postoji aritmetička formula (B) takva da

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

Riječima, formula (B) kaže: "Imam svojstvo (C)."

Dokaz Löbove teoreme:. Pretpostavimo da je (PA / vdash / Prov (ulcorner A / urcorner) rightarrow A); trebamo pokazati da (PA / vdash A). Dijagonalizacijskom lemom postoji formula (B) takva

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

Iz ovoga slijedi prvi i drugi uvjet izvedljivosti Löb plus nešto prijedložno obrazloženje

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

Dakle, opet Löbovim drugim uvjetom,) PA / vdash / Prov (ulcorner B / urcorner) rightarrow (Prov (ulcorner / Prov (ulcorner B / urcorner) urcorner) rightarrow / Prov (ulcorner A / urcorner)).)

S druge strane, treći uvjet daje Löb

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

Tako

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

Zajedno s pretpostavkom da (PA / vdash / Prov (ulcorner A / urcorner) rightarrow A), to daje

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

Konačno, jednadžba proizvedena iz dijagonalizacijske leme podrazumijeva da (PA / vdash B), dakle (PA / vdash / Prov (ulcorner B / urcorner)), dakle

) PA / vdash A,)

po želji.

Imajte na umu da supstituiranje (bot) za (A) u Löbovoj teoremi izvodi da (PA / vdash / neg \, / Prov (ulcorner / bot / urcorner)) podrazumijeva (PA / vdash / bot), što je samo suprotnost Gödelovoj drugoj teoremi nepotpunosti.

4.2 Aritmetička cjelovitost

Vrhunski rezultat logike dokazivosti je teorem o aritmetičkoj cjelovitosti R. Solovaya iz 1976. godine, koji pokazuje da je GL doista adekvatan za aritmetiku peanoa:

) GL / vdash A / tekst {ako i samo ako za sve realizacije} f, / PA / vdash f (A).)

Ovaj teorem u osnovi kaže da modalna logika GL bilježi sve ono što Peano Aritmetika može istinski u modalnom smislu reći o vlastitom predikatu provedivosti. Smjer s lijeva na desno, aritmetička zvučnost GL, raspravlja se gore. Solovay je namjeravao suprotstaviti drugi, mnogo teži smjer. Njegov se dokaz temelji na zamršenim autoreferencijalnim tehnikama i ovdje se može dati samo mali pogled.

Teorem o modalnoj cjelovitosti po Segerbergu bio je važan prvi korak u Solovajevom dokazu aritmetičke cjelovitosti GL u odnosu na Peano Aritmetiku. Pretpostavimo da GL ne dokazuje modalnu formulu (A). Zatim, modalnom cjelovitošću, postoji krajnje tranzitivno irefleksivno stablo takvo da je (A) lažno u korijenu tog stabla. Sada je Solovay smislio genijalan način da na jeziku peano aritmetike simulira tako konačno stablo. Tako je pronašao realizaciju (f) od modalnih formula do aritmetičkih rečenica, tako da aritmetika Peano ne dokazuje (f (A)).

Solovayev teorem o cjelovitosti pruža alternativni način konstruiranja mnogih aritmetičkih rečenica koje se ne mogu dokazati u aritmetikama Peano. Na primjer, lako je napraviti mogući model svjetova da se pokaže da se GL ne dokazuje (Box p / vee / Box / neg \, p), pa po Solovayevom teoremu postoji aritmetička rečenica (f (p)) takav da Peano Aritmetika ne dokazuje (Prov (ulcorner f (p) urcorner) vee / Prov (ulcorner / neg \, f (p) urcorner)). Konkretno, to implicira da ni pena aritmetika nije dokazana ni (f (p)), ni (neg \, f (p)); za pretpostavimo suprotno da je (PA / vdash f (p)), tada Löbovim prvim uvjetom i logikom prijedloga, (PA / vdash / Prov (ulcorner f (p) urcorner) vee / Prov (ulcorner / neg \, f (p) urcorner)), što dovodi do kontradikcije i slično ako se pretpostavlja da (PA / vdash / neg \, f (p)).

Solovayev teorem je toliko značajan jer pokazuje da se zanimljiv fragment neodređene formalne teorije poput aritmetike Peano - naime ona koju aritmetika može izraziti u propoziciji o vlastitom predikatu proverljivosti - može proučiti pomoću modalističke logike, GL, s perspektivna semantika svjetova.

5. Opseg logike dokazivosti

U ovom su dijelu razmatrani neki nedavni trendovi u istraživanju logike dokazivosti. Jedan važan dio odnosi se na ograničenja opsega GL, gdje je glavno pitanje, za koje su formalne teorije, osim peano aritmetike, GL odgovarajuća logika prijedloga proverljivosti? Zatim ćemo raspravljati o nekim generalizacijama logike prijedloga proverljivosti u izrazitijim modalnim jezicima.

5.1 Granice

Posljednjih godina logičari su istraživali mnoge druge aritmetičke sustave koji su slabiji od peano aritmetike. Često su ovi logičari crpili svoju inspiraciju iz problema s računanjem, na primjer, izučavanjem funkcija koje se mogu izračunati u polinomnom vremenu. Oni su dali djelomični odgovor na pitanje: "Za koje teorije aritmetike se još uvijek drži Solovayeva teorema o aritmetičkoj potpunosti (s obzirom na odgovarajuće dokaze proverljivosti)?" Za raspravu o ovom pitanju potrebna su dva koncepta. (Delta_0) - formule su aritmetičke formule u kojima su svi kvantifikatori ograničeni izrazom, na primjer

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

gdje je (bs) operator sljednika ("(+ 1)"). Aritmetička teorija (I / Delta_0) (gdje sam oznaka za "indukcija") slična je Peano Aritmetika, samo što dopušta manje indukcije: indukcijska shema

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

je ograničeno na (Delta_0) - formule (A).

Kao što su De Jongh i drugi (1991.) istakli, aritmetička cjelovitost sigurno vrijedi za teorije (T) koje zadovoljavaju sljedeća dva uvjeta:

  1. (T) dokazuje indukciju za (Delta_0) - formule, a (T) dokazuje EXP, formula izražavajući da za sve (x), njegova snaga (2 ^ x) postoji. U standardnijim zapisima: (T) se proteže (I / Delta_0) + EXP;
  2. (T) ne dokazuje nijednu lažnu rečenicu oblika (postoji x \, A (x)), s formulom (A (x)) a (Delta_0).

Za takve teorije, aritmetička zvučnost i cjelovitost GL držanja, pod uvjetom da (Box) prevodi u (Prov_T), predikat prirodne provedivosti s obzirom na dovoljno jednostavnu aksiomatizaciju (T). Dakle, za modalne rečenice (A):

) GL / vdash A / tekst {ako i samo ako za sve realizacije} f, T / vdash f (A).)

Još nije jasno da li uvjet 1 daje donju granicu opsega logike dokazivosti. Na primjer, još uvijek je otvoreno pitanje je li GL logika proverljivosti (I / Delta_0 + / Omega_1), teorija koja je nešto slabija od (I / Delta_0) + EXP u tom (Omega_1) je aksiom koji tvrdi da za sve (x) postoji njegova moć (x ^ { log (x)}). Logika proverljivosti GL je aritmetički zvučna u odnosu na (I / Delta_0 + / Omega_1), ali osim nekih djelomičnih rezultata Berarduccija i Verbruggea (1993), pružajući aritmetičke realizacije u skladu s (I / Delta_0 + / Omega_1) za ograničeno klase rečenica u skladu s GL, pitanje ostaje otvoreno. Njegov odgovor može ovisiti o otvorenim problemima u teoriji složenosti računanja.

Gornji rezultat De Jongh i sur. pokazuje snažnu karakteristiku logike dokazivosti: za mnoge različite aritmetičke teorije GL bilježi upravo ono što te teorije kažu o predikatima njihove provabilnosti. To je istovremeno i slabost. Primjerice, logika dokazivanja prijedloga ne ukazuje na razlike između onih teorija koje se mogu krajnje aksiomatizirati i onih koje nisu.

5.2 Logika tumačenja

Da bi mogli govoriti modalnim jezikom o važnim razlikama između teorija, istraživači su proširili logiku provjerljivosti na mnogo različitih načina. Spomenimo nekoliko. Jedno proširenje je dodavanje binarnog modaliteta (interpretira), pri čemu je za datu aritmetičku teoriju (T) modalna rečenica (A / interpretira B) označena kao (T + B) tumači se u (T + A)”(Švejdar, 1983). De Jongh i Veltman (1990) istraživali su modalnu semantiku za nekoliko logika interpretabilnosti, dok su De Jongh i Visser (1991) dokazali eksplicitna svojstva fiksne točke za najvažnija. Visser je okarakterizirao logiku interpretacije najčešćih konačno aksiomatiziranih teorija, a Berarducci i Shavrukov neovisno okarakterizirali su onu za PA koja nije krajnje aksiomatizirana. Čini se da zaista,logika interpretacije konačno aksiomatizacijskih teorija različita je od logike interpretacije Peano Aritmetike (vidjeti Montagna 1987; Visser 1990, 1998; Berarducci 1990, Shavrukov 1988; Joosten i Visser 2000).

5.3 Propozicioni kvantifikatori

Drugi način za širenje okvira logike propozicijske provjerljivosti je dodavanje propozicijskih kvantifikata, kako bi se moglo izraziti načela poput Goldfarbovih:

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

rekavši da za bilo koje dvije rečenice postoji treća rečenica koja je dokazana ako i samo ako je bilo koja od prve dvije rečenice dokaziva. Ovo je načelo dokazljivo u peano aritmetici (vidi npr. Artemov i Beklemishev 1993). Skup rečenica GL s propozicijskim kvantifikatima koji je aritmetički valjan ispada da nije moguće odrediti (Shavrukov 1997).

5.4 Japaridzeova bimodalna i polimodalna logika dokazivosti

Japaridzeova (1988) bimodalna logika GLB ima dva (Box) operatora provabilnosti, označena sa ([0]) i ([1]), s njihovim dualnim (Diamond) operaterima sličnim (langle 0 / rangle) i (langle 1 / rangle). U Japaridzeovoj interpretaciji čovjek se može smatrati ([0]) stojećim standardnim predikatom provabilnosti u Peano aritmetici. S druge strane, ([1]) odgovara snažnijem predikatu provabilnosti, naime (omega) - provabilnost.

Definirajmo koncepte koji su potrebni za razumijevanje ove namjeravane interpretacije GLB-a. Aritmetička teorija (T) definirana je kao (omega) - dosljedna ako i samo ako je za sve formule A sa slobodnom varijablom (x), (T / vdash / neg \, A (I_n)) za sve (n) podrazumijeva da (T / not / vdash / postoji x \, A (x)); ovdje je (I_n) broj (n), tj. izraz (bs / bs / ldots / bs 0) s (n) pojavama operatora nasljednika (bs). Peano aritmetika (PA) najpoznatiji je primjer (omega) konzistentne teorije (vidi također Gödelove teoreme nepotpunosti). Neka je PA (^ +) aritmetička teorija čiji su aksiomi PA zajedno sa svim rečenicama (forall x \, / neg \, A (x)) takva da za svaki (n), PA (vdash / neg \, A (I_n)). Sad (omega) - provabilnost je jednostavno dokazivost u PA (^ +),pa je dvostruko od (omega) - dosljednosti.

Japaridzeova logika bimodalne provabilnosti GLB može se aksiomatizirati aksiomima i pravilima GL (vidi Odjeljak 2), formuliranim odvojeno za [0] i [1]. Pored toga, GLB ima dva mješovita aksioma, i to:) tag {Monotonicity} [0] A / rightarrow [1] A)) tag {(Pi ^ 0_1) - potpunost} langle 0 / rangle A / rightarrow [1] langle 0 / rangle A) Japaridzeova logika je odlučna i ima razumnu Kripkeovu semantiku, a aritmetički je zvučna i cjelovita s obzirom na aritmetiku Peano (Japaridze 1988, Boolos 1993).

Polimodalni analog Japaridzeovog GLB-a, nazvan GLP, posljednjih je godina dobio veliku pažnju. GLP ima beskonačno mnogo (Box) operatora provabilnosti, koji su označeni kutijama ([n]) za svaki prirodni broj (n), s njihovim dualnim (Diamond) operaterima sličnim (langle n / rangle). Opet se može smatrati da je ([0]) stajanje za standardni predikat preivabilnosti u Peano aritmetici, (langle 1 / rangle) za (omega) - provabilnost, itd. GLP je aksiomatiziran polazeći od aksioma i pravila GL (vidi Odjeljak 2), formuliranih odvojeno za svaki ([n]). Pored toga, GLP ima tri mješovite sheme aksioma, naime kako je to formulirao Beklemishev (2010): [m] A / rightarrow [n] A, / mbox {for} m / leq n)) langle k / rangle A / rightarrow [n] langle k / rangle A, / mbox {for} k / lt n) [m] A / rightarrow [n] [m] A, / mbox {for} m / leq n)

GLP je nedavno obdaren Kripkeovom semantikom u odnosu na koji je cjelovit, a također se pokazalo da je aritmetički cjelovito u odnosu na peano aritmetiku (vidjeti Beklemishev 2010a, 2011a). Kao i za GL, problem s odlučivanjem za GLP je potpun PSPACE (Shapirovsky 2008), dok je njegov zatvoreni fragment polinomno vrijeme odlučivo (Pakhomov 2014).

Posljednjih godina dokazano je niz rezultata o polimodalnom logičkom GLP-u snažnih predikata dokazivosti. Evo sljedećih korisnih tema:

  • zatvoreni fragment GLP-a (vidjeti Ignatiev 1993; Beklemishev, Joosten i Vervoort 2005);
  • GLP i dokazno-teoretski ordinari (Beklemishev 2004);
  • Interpolacijske teoreme za GLP (vidjeti Beklemishev 2010b, Shamkanov 2011);
  • Odnos između topološke semantike i teorije skupova, među ostalim posebno velikim kardinalnim aksiomima i stacionarnim odrazom (vidi Beklemishev 2011b; Beklemishev i Gabelaia 2013, 2014; Fernández-Duque 2014).

5.5 Predvidi logiku dokazivosti

Konačno, može se proučiti logika dokazivosti. Jezik je jezika predikata, bez funkcijskih simbola, zajedno s operatorom (Box). Ovdje situacija postaje puno složenija nego u slučaju prijedloga logike dokazivosti. Za početak, kvantificirana verzija GL nema svojstvo fiksne točke, nije potpuna u odnosu na bilo koju klasu Kripke okvira i nije aritmetički potpuna s obzirom na Peit Aritmetiku (Montagna, 1984). Tada se postavlja pitanje: Postoji li adekvatna logika aksiomatizirane predikacije predikata koja točno pokazuje valjana načela dokazivosti? Nažalost, odgovor je glasno ne:Vardanyan (1986) je dokazao na temelju Artemovih ideja (1985a) da skup rečenica logike dokazivosti predikata koje su sve realizacije u PA nisu čak i rekurzivno brojljive, ali (Pi ^ 0_2) - potpune, pa nema razumne aksiomatizacije. Visser i De Jonge (2006) pokazali su da ne postoji bijeg od Vardanyanove teoreme dokazivanjem generalizacije: Za širok raspon aritmetičkih teorija (T) skup rečenica predikatne logike proverljivosti svih čije su spoznaje dokazane u (T) ispada da je (Pi ^ 0_2) - isto tako dovršeno. Za širok spektar aritmetičkih teorija (T) skup rečenica logike dokazivosti predikata za koje je sve moguće ostvarenje u (T) ispada da je (Pi ^ 0_2) takođe kompletan. Za širok spektar aritmetičkih teorija (T) skup rečenica logike dokazivosti predikata za koje je sve moguće ostvarenje u (T) ispada da je (Pi ^ 0_2) takođe kompletan.

5.6 Ostale generalizacije

Ostavljeni u gornjoj diskusiji su mnoga druga važna područja istraživanja logike dokazivosti i njegovih proširenja. Zainteresirani čitatelj ukazuje se na sljedeća područja:

  • logika proverljivosti intuicionističke aritmetike (vidjeti Troelstra 1973; Visser 1982, 1999; Iemhoff 2000, 2001, 2003; Visser 2002, 2008);
  • klasifikacija logike dokazivosti (vidjeti Visser 1980, Artemov 1985b, Beklemishev 1989, Beklemishev i sur. 1999);
  • Rosser narudžbe i dokaz ubrzavanja (vidjeti Guaspari i Solovay 1979, Švejdar 1983, Montagna 1992);
  • nekoliko vrsta bimodalne logike provabilnosti s operaterima provabilnosti za različite teorije (vidjeti Carlson 1986; Smoryński 1985; Beklemishev 1994, 1996);
  • logika provabilnosti za standardnu provabilnost u kombinaciji s neobičnim prekatima provabilnosti izvana nabrajajući PA, poput Fefermanovih i Parikhovih prekazivnosti i spori predikatski predikat (vidi Montagna 1978; Visser 1989; Shavrukov 1994; Lindström 1994, 2006; Henk i Pakhomov 2016 (Ostali internetski resursi));
  • logika eksplicitnih dokaza (vidi Artemov 1994, 2001; Artemov i Montagna 1994; Artemov i Iemhoff 2007);
  • primjene logike dokazivosti u teoriji dokaza (vidi Beklemishev 1999, 2004, 2005, 2006);
  • logika pozitivne provabilnosti i proračun refleksije (vidjeti Beklemishev 2012, 2014; Dashkov 2012);
  • generalizacije logike polmodalne provabilnosti GLP, naime logike provabilnosti s beskonačno mnogim modalitetima (vidjeti Beklemishev i sur. 2014; Fernández-Duque i Joosten 2013a, 2013b, 2013b, 2013 (2013, drugi izvori), 2014);
  • odnosi izme logicu logike dokazivosti i kalkulacije (vidi van Benthem 2006, Visser 2005, Alberucci i Facchini 2009); i
  • algebre provabilnosti, koje se nazivaju i dijagonalizabilne algebre ili Magari algebre (vidjeti Magari 1975a, 1975b; Montagna 1979, 1980a, 1980b; Shavrukov 1993a, 1993b, 1997; Zambella 1994; za nedavne rezultate njihovih elementarnih teorija, vidi Pakhomov 2012, 2014 (Ostali Internet Resursi), 2015 (Ostali internetski resursi)).

Za čitatelja koji bi želio doprinijeti području logike dokazivosti i njegovim generalizacijama Beklemishev i Visser (2006) predložili su napomenuti popis intrigantnih otvorenih problema.

6. Filozofski značaj

Iako je logika dokazivosti prijedloga modalna logika s svojevrsnim operatorom "nužnosti", ona podnosi Quineovu (1976) kontroverznu kritiku modalnih pojmova kao nerazumljivu, već zbog njezine jasne i nedvosmislene aritmetičke interpretacije. Na primjer, za razliku od mnogih drugih modalnih logika, formule s ugniježđenim modalitetima poput (Box / Diamond p / rightarrow / Box / bot) nisu problematične, niti postoje sporovi oko toga koja bi trebala biti tautologija. Zapravo, logika dokazivosti utjelovljuje sve desiderate koje je Quine (1953.) postavio za sintaktičke tretmane modaliteta.

Quineove glavne strelice bile su usmjerene prema logikama predikata predikata, posebno konstrukciji rečenica koje sadrže modalne operatore pod opsegom kvantifikatora ("kvantificiranje u"). Međutim, u logici dokazivosti predikata, tamo gdje se kvantifikatori kreću u odnosu na prirodne brojeve, i de diktto i de modalitet imaju izravne interpretacije, suprotno od ostalih modalnih logika (vidjeti napomenu o razlikovanju de dicto / de re). Na primjer, formule poput

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

nisu nimalo problematični. Ako je broj (n) dodijeljen (x), tada je (okvir \, / postoji y \, (y = x)) istinit u vezi s ovim zadatkom ako je rečenica (postoji y \, (y = I_n)) je dokazivo u peano aritmetici; ovdje je (I_n) broj (n), tj. izraz (bs / bs / ldots / bs 0) s (n) pojavama operatora nasljednika (bs). Ova rečenica vrijedi za sve (n) u standardnom modelu prirodnih brojeva, a (forall x \, / Box \, / postoji y \, (y = x)) je čak izvodljivo u aritmetikama peano-a, Usput, Barcan Formula

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

nije istinito za cijele brojeve, a kamoli dokazivo (na primjer, uzmimo za (A (x)) formula "(x) ne kodira dokaz (bot)"). Njegova suprotnost

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

s druge strane, u peano aritmetici je dokazljivo za bilo koju formulu (A).

Logika dokazivosti ima vrlo različite principe od ostalih modalnih logika, čak i onih s naizgled sličnom svrhom. Na primjer, dok logika dokazivosti bilježi provabilnost u formalnim teorijama aritmetike, epiztemska logika nastoji opisati znanje, što bi se moglo smatrati vrstom neformalne dokazivosti. U mnogim inačicama epistemičke logike jedan od najvažnijih principa je aksiom istine (5):

) mbox {S5} vdash / Kutija A / rightarrow A, (tekst {ako netko zna} A, / tekst {tada} A / tekst {je istina}).)

Analogni princip očito ne važi za GL: na kraju krajeva,) tekst {if} GL / vdash / Okvir A / rightarrow A, / tekst {tada} GL / vdash A.)

Stoga se čini pogrešno usporediti snagu oba pojma ili ih kombinirati u jednom modalnom sustavu. Možda je formalna dokazivost doista u nekom smislu jači pojam od neformalne dokazivosti, ali definitivno to nije aritmetička istina ili valjanost niti je drugi smjer. Rasprave o posljedicama Gödelovih teorema o nepotpunosti ponekad uključuju i zbunjenost oko pojma provedivosti, što potiče tvrdnje da bi ljudi mogli pobijediti formalne sustave u teoremima "poznavanja" (vidi Davis (1990, 1993) za dobru raspravu takvih tvrdnji).

Sve u svemu, formalna dokazivost precizno je definiran pojam, mnogo više od istine i znanja. Dakle, samo referenca u okviru dokazivosti ne vodi semantičkim paradoksima poput Lažljivca. Umjesto toga, to je dovelo do nekih najvažnijih rezultata o matematici, poput Gödelovih teorema nepotpunosti.

Bibliografija

Opće reference o logici dokazivosti

  • Artemov, SN, 2006, „Modalna logika u matematici“, u P. Blackburn, et al. (ur.), Priručnik modalne logike, Amsterdam: Elsevier, str. 927–970.
  • Artemov, SN i LD Beklemishev, 2004, "Logic Provability", u Handbook of Philosophical Logic, Second Edition, D. Gabbay i F. Guenthner, ur., Svezak 13, Dordrecht: Kluwer, str. 229–403.
  • Boolos, G., 1979, The Unprovability of Consistentity: Esej in Modal Logic, Cambridge: Cambridge University Press.
  • –––, 1993, Logic of Provability, New York i Cambridge: Cambridge University Press.
  • de Jongh, DHJ i G. Japaridze, 1998., "Logika dokazivosti", u Priručniku teorije dokaza, Buss, SR (ur.), Amsterdam: North-Holland, str. 475-546.
  • Lindström, P., 1996., „Loga provabilnosti - kratak uvod“, Teorija, 52 (1–2): 19–61.
  • Segerberg, K., 1971, Esej u klasičnoj modalnoj logici, Uppsala: Filosofiska Föreningen och Filosofiska Institutionen vid Uppsala Universityitet.
  • Švejdar, V., 2000, „O logici provabilnosti“, Nordijski časopis za filozofiju, 4: 95–116.
  • Smoryński, C., 1985, Samoreferencija i modalna logika, New York: Springer-Verlag.
  • Verbrugge, R. 1996, „Provability“u Enciklopediji filozofije (dodatak), DM Borchert (ur.), New York: Simon i Schuster MacMillan, str. 476–478.
  • Visser, A., 1998., „Logic Provability”, u Routledge Encyclopedia of Philosophy, W. Craig (ur.), London: Routledge, str. 793–797.

Povijest

  • van Benthem, JFAK, 1978., „Četiri paradoksa“, časopis za filozofsku logiku, 7 (1): 49–72.
  • Boolos, G. i G. Sambin, 1991, „Provability: Emerging of Mathematical Modality“, Studia Logica, 50 (1): 1–23.
  • Gödel, K., 1933, „Eine Interpretation des intuitionistischen Aussagenkalküls“, Ergebnisse eines Mathematischen Colloquiums, 4: 39–40; prijevod "Interpretacija intuicionističkog prijedloga proračuna", u K. Gödel, Zbornik radova, S. Feferman i sur. (ur.), Oxford i New York: Oxford University Press, svezak 1, 1986., str. 300–302.
  • –––, 1931, „Über Formal Unentscheidbare Sätze der Principia Mathematica i Verwandter Systeme I“, Monatshefte für Mathematik und Physik, 38: 173–198.
  • Halbach, V. i A. Visser, 2014, “Henkin rečenica”, u M. Mazanu, I. Sainu i E. Alonsu (ur.), Život i djelo Leona Henkina: Eseji o njegovim doprinosima, Dordrecht: Springer International Publishing, str. 249–263.
  • Henkin, L., 1952, "Problem koji se tiče provabilnosti", časopis za simboličku logiku, 17: 160.
  • –––., 1954, „Pregled G. Kreisela: O problemu Leona Henkina“, časopis za simboličku logiku, 19 (3): 219-220.
  • Hilbert, D. i P. Bernays, 1939, Grundlagen der Mathematik, svezak 2, Berlin / Heidelberg / New York: Springer-Verlag.
  • Kreisel, G., 1953, „O problemu Leona Henkina“, Indagationes Mathematicae, 15: 405–406.
  • Lewis, CI, 1912, "Implikacije i algebra logike", Um, 21: 522–531.
  • Löb, MH, 1955, „Rješavanje problema Leona Henkina“, časopis za simboličku logiku, 20: 115–118.
  • Macintyre, AJ i H. Simmons, 1973, „Gödelova tehnika dijagonalizacije i srodna svojstva teorija“, Colloquium Mathematicum, 28: 165–180.
  • Magari, R., 1975a, „Dijagonalizabilne algebre“, Bollettino della Unione Mathematica Italiana, 12: 117–125.
  • –––, 1975b, „Teorija zastupljenosti i dualnosti za dijagonalizabilne algebre“, Studia Logica, 34 (4): 305–313.
  • Smiley, TJ, 1963., "Logičke osnove etike", Acta Philosophica Fennica, 16: 237–246.
  • Smoryński, C., 1991, „Razvoj samo-reference: Löb-ov teorem“, u T. Drucker (ur.), Perspektive povijesti matematičke logike, Basel: Birkhäuser, str. 110–133.

Eliminacija reza zbog logike dokazivosti

  • Goré, R. i R. Ramanayake, 2008, "Valentini-jevo uklanjanje za rješavanje logike provabilnosti", u časopisu Advances in Modal Logic, svezak 7, C. Areces i R. Goldblatt (ur.), London: College Publications, str. 67 -86.
  • Negri, S., 2005, "Proof Analysis in Modal Logic", časopis za filozofsku logiku, 50: 507–544.
  • Negri, S., 2014, „Dokazi i kontra-modeli u neklasičnoj logici“, Logica Universalis, 8 (1): 25–60.
  • Poggiolesi, F., 2009, „Čisto sintaktički i bezbrojni sekvencijalni račun za modalnu logiku proverljivosti“, Pregled simboličke logike, 2 (4): 593–611.
  • Rautenberg, W., 1983., „Modal Tableau Calculi and Interpolation“, časopis za filozofsku logiku, 12 (4): 403–423.
  • Sambin, G. i S. Valentini, 1982, „Modalna logika provabilnosti. Sekvencijalni pristup, “Journal of Philosophical Logic, 11 (3): 311–342.
  • Shamkanov, DS, 2011, "Interpolacijska svojstva logike proverljivosti GL i GLP", Zbornik radova Matematičkog instituta Steklov, 274 (1): 303–316.
  • –––, 2014, „Kružni dokazi za Gödel-Löb-ovu logiku provabilnosti“, Matematičke bilješke, 96 (4): 575–585.
  • Smoryński, C., 1978, „Beth-ova teorema i samoreferencijalne rečenice“, Studije iz logike i temelji matematike, 96: 253–261.
  • Valentini, S., 1983, „Modalna logika dokazivosti: uklanjanje“, časopis Filozofska logika, 12: 471–476.

Teorem fiksne točke

  • de Jongh, DHJ, i F. Montagna, 1988., „Dokazive fiksne točke“, Matematička logika Quarterly, 34 (3): 229-250.
  • Lindström, P., 2006, „Bilješka o nekim građevinama nepokretnih točaka u logici proverljivosti“, časopis za filozofsku logiku, 35 (3): 225-230.
  • Reidhaar-Olson, L., 1990, „Novi dokaz teoreme fiksne točke logike proverljivosti“, časopis Notre Dame za formalnu logiku, 31 (1): 37–43.
  • Sambin, G., 1976, „Efektivna teorema s fiksnom tačkom u intuicijskim dijagonalizacijskim algebrama (algebrizacija teorija koje izražavaju teoriju, IX)“, Studia Logica 35: 345–361.
  • Sambin, G. i S. Valentini, 1982, „Modalna logika provabilnosti. Sekvencijalni pristup, “Journal of Philosophical Logic, 11 (3): 311–342.

Moguća semantika svjetova i topološka semantika

  • Abashidze, M., 1985, „Ordinalna cjelovitost modalnog sustava Gödel-Löb“(na ruskom) u Intensional Logics and Logical Structure Theory, Tbilisi: Metsniereba, str. 49–73.
  • Aiello, M., I. Pratt-Hartmann i J. van Benthem (ur.), 2007., Priručnik prostorne logike, Berlin: Springer-Verlag.
  • Beklemishev, LD 2009, “Ordinal Completeness of Bimodal Provability Logic GLB”, In International Tbilisi Symposium on Logic, Language and Computation, Berlin: Springer-Verlag, str. 1–15.
  • Beklemishev, LD, G. Bezhanishvili i T. Icard, 2009, "O topološkim modelima GLP-a", u R. Schindler (ur.), Načini teorije dokazivanja (Ontos Mathematical Logic: Svezak 2), Frankfurt: Ontos Verlag, s. 133–153.
  • Blass, A., 1990, „Infinitary Combinatorics and Modal Logic“, časopis za simboličku logiku, 55 (2): 761–778.
  • Esakia, L., 1981., "Dijagonalne konstrukcije, Löbova formula i kantorijska raspršena područja" (na ruskom), u Studije iz logike i semantike, Z. Mikeladze (ur.), Tbilisi: Metsniereba, str. 128–143.
  • –––, 2003, „Intuitionistička logika i modalitet putem topologije“, Anali čiste i primijenjene logike, 127: 155–170.
  • Goré, R., 2009, „Strojna provjera dokaza dokaza: Primjena logike na logiku“, u ICLA '09: Zbornik radova 3. indijske konferencije o logici i njezinim primjenama, Berlin: Springer-Verlag, str. 23–35.
  • Goré, R. i J. Kelly, 2007, „Automatizirano traženje dokaza u logici provabilnosti Gödel-Löb“, British Logic Colloquium 2007, dostupno na
  • Hakli, R. i S. Negri, 2012, „Ispada li teorema dedukcije za modalnu logiku?“, Synthese 187 (3): 849–867.
  • Icard, TF III, 2011, „Topološka studija zatvorenog fragmenta GLP-a“, časopis za logiku i računarstvo, 21 (4): 683–696; prvi put objavljen online 2009, doi: 10.1093 / logcom / exp043
  • Japaridze, GK, 1986, Modalna logička sredstva za ispitivanje dokazivosti, teza iz filozofije (na ruskom), Moskva.
  • McKinsey, JCC i A. Tarski, 1944., "Algebra topologije", Anali matematike, 45: 141–191.

Provabilnost i peano aritmetika

  • Davis, M., 1958., Computability and Neoljivost, New York, McGraw-Hill; ponovno tiskan dodatnim prilogom, New York, Dover Publications 1983.
  • Feferman, S., 1960, „Aritmetizacija metamatematike u općem okruženju“, Fundamenta Mathematicae, 49 (1): 35–92.
  • Hájek, P. i P. Pudlák, 1993, Metamathetika Aritmetike prvog reda, Berlin: Springer-Verlag.
  • Solovay, RM, 1976, „Provability Interpretations of Modal Logic“, Izraelski časopis za matematiku, 25: 287–304.

Opseg logike dokazivosti: granice

  • Berarducci, A. i R. Verbrugge, 1993, “O logici vjerojatnosti granične aritmetike”, Anali čiste i primijenjene logike, 61: 75–93.
  • Buss, SR, 1986, Granica aritmetike, Napulj: Bibliopolis.
  • de Jongh, DHJ, M. Jumelet i F. Montagna, 1991., "Dokaz Solovajevog teorema", Studia Logica, 50 (1): 51–70.

Logika tumačenja

  • Berarducci, A., 1990, "Logika interpretacije peano aritmetike", časopis za simboličku logiku, 55: 1059–1089.
  • de Jongh, DHJ, i F. Veltman, 1990, "Lokacije provabilnosti za relativnu interpretabilnost", u PP Petkov (ur.), Matematička logika: Zbornik radova Ljetne škole Heyting 1988. u Varni, Bugarska, Boston: Plenum Press, str. 31-42.
  • de Jongh, DHJ, i A. Visser, 1991., "Izričite fiksne točke u logici interpretabilnosti", Studia Logica, 50 (1): 39–49.
  • Joosten, JJ i Visser, A., 2000, "Logika tumačenja svih razumnih aritmetičkih teorija", Erkenntnis, 53 (1-2): 3–26.
  • Montagna, F., 1987, „Provability in Finte Subtheories of PA“, Journal of Symbolic Logic, 52 (2): 494–511.
  • Shavrukov, V. Y., 1988, „Logika relativne interpretabilnosti preko peano aritmetike“, Tehničko izvješće br. 5, Moskva: Steklov Matematički institut (na ruskom).
  • Švejdar, V., 1983, „Modalna analiza općih Roser rečenica“, časopis za simboličku logiku, 48: 986–999.
  • Visser, A., 1990, "Logika tumačenja", u PP Petkov (ur.), Matematička logika: Zbornik radova Ljetne škole Heyting 1988. u Varni, Bugarska, Boston: Plenum Press, str. 175–209.
  • –––, 1998., „Pregled logike interpretabilnosti“, u M. Kracht i sur. (ur.), Napretci modalne logike (svezak 1), Stanford: CSLI Publikacije, str. 307–359.

Propozicijski kvantifikatori

  • Artemov, SN i LD Beklemišjev, 1993, "O propozicioni kvantifikatori u logici proverljivosti", časopis Notre Dame za formalnu logiku, 34: 401–419.
  • Shavrukov, V. Y., 1997, “Neodrešivost u dijagonalizacijskim algebrama”, časopis za simboličku logiku, 62: 79–116.

Japaridzeova bimodalna i polimodalna logika dokazivosti

  • Beklemishev, LD, 2004, „Algebre provabilnosti i prodo-teoretski ordinari, I“, Anali čiste i primijenjene logike, 128: 103–123.
  • –––, 2010a, „Kripke semantika logike provabilnosti GLP“, Anali čiste i primijenjene logike, 161 (6): 756–774.
  • –––, 2010b, „O Cragovoj interpolaciji i svojstvima fiksne točke GLP“, u S. Feferman i sur. (ur.), Dokazi, kategorije i računi (Tributes, 13), London: College Publications, str. 49–60.
  • –––, 2011a, „Pojednostavljeni dokaz teoreme aritmetičke cjelovitosti logike provabilnosti GLP“, Zbornik radova Matematički institut Steklov, 274 (1): 25–33.
  • –––, 2011b, „Ordinalna cjelovitost Bimodal Provability Logic GLB“, u N. Bezhanishvili i sur. (ur.), logika, jezik i računanje, 8. međunarodni simpozij u Tbilisiju TbiLLC 2009 (Bilješke predavanja iz informatike: svezak 6618), Heidelberg: Springer, str. 1–15.
  • Beklemishev, LD i D. Gabelaia, 2013, „Topološka cjelovitost logike provabilnosti GLP“, Anali čiste i primijenjene logike, 164 (12): 1201–1223.
  • –––, 2014., „Topološka tumačenja logike provabilnosti“, u G. Bezhanishvili (ur.), Leo Esakia o dualnosti u modalnoj i intuicionističkoj logici (izvanredni prilozi logici: svezak 4), Heidelberg: Springer, str. 257– 290.
  • Beklemishev, LD, J. Joosten i M. Vervoort, 2005, „Finitary Treatment of Closed Fragment of Japaridze Logic Provability“, Journal of Logic and Computation, 15 (4): 447–463.
  • Fernández-Duque, D. i JJ Joosten, 2014., "Parovi za transfinitnu japaridze algebru", Logički časopis IGPL-a, 22 (6): 933–963.
  • Ignatiev, KN, 1993, “O snažnim predikabilnostima i povezanim modalnim logikama”, časopis Symbolic Logic, 58: 249-290.
  • Japaridze, G., 1988, „Logika polimodalne provabilnosti“, Intenzivna logika i logička struktura teorija: Materijal s Četvrtog sovjetsko-finskog simpozija o logici, Telavi, str. 16–48.
  • Pakhomov, FN, 2014, “O složenosti zatvorenog fragmenta Japaridzeove logike dokazivosti”, Arhiva za matematičku logiku, 53 (7-8): 949–967.

Predikat logike dokazivosti

  • Artemov, SN, 1985a, „Nonaritmetičnost istine predikatne logike proverljivosti“, Doklady Akademii Nauk SSSR, 284: 270–271 (na ruskom); Prijevod s engleskog na sovjetsku matematiku Doklady, 32: 403–405.
  • McGee, V. i G. Boolos, 1987., „Stupanj skupa rečenica logike dokazivanja predikata koje su istinite u svakom tumačenju“, časopis Symbolic Logic, 52: 165–171.
  • Vardanyan, VA, 1986, „Aritmetička složenost predikatne logike dokazivosti i njihovih fragmenata“, Doklady Akademii Nauk SSSR, 288: 11–14 (na ruskom); Prijevod s engleskog na sovjetsku matematiku Doklady, 33: 569–572.
  • Visser, A. i M. de Jonge, 2006, "Nema bijega iz Vardanyanovog teorema", Arhiva matematičke logike, 45 (5): 539–554.

Ostale generalizacije

  • Alberucci, L. i A. Facchini, 2009, „O modalnoj-kalkuli i Gödel-Löb-ovoj logici“, Studia Logica, 91: 145–169.
  • Artemov, SN, 1985b, „O modalnoj logici koja Axiomatizira provabilnost“, Izvestiya Akadademii Nauk SSSR, Seriya Matematicheskaya, 49 (6): 1123–1154 (na ruskom); Engleski prijevod s Matematike SSSR-a - Izvestiya, 27 (3): 402–429.
  • –––, 1994, „Logija dokaza“, Anali čiste i primijenjene logike, 67 (2): 29–59.
  • –––, 2001, „Eksplicitna provabilnost i konstruktivna semantika“, Bilten simboličke logike, 7: 1–36.
  • Artemov, SN i R. Iemhoff, 2007, "Osnovna intuicijska logika dokaza", časopis za simboličku logiku, 72 (2): 439–451.
  • Artemov, SN i F. Montagna, 1994, „O teorijama prvog reda s operatorom provedivosti“, časopis za simboličku logiku, 59 (4): 1139–1153.
  • Beklemishev, LD, 1989, "O klasifikaciji logike propozicijske provabilnosti", Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya., 53 (5): 915–943 (na ruskom); Engleski prijevod s matematike SSSR-Izvestiya, 35 (1990) 247-275.
  • –––, 1994, „O bimodalnoj logici dokazivosti“, Anali čiste i primijenjene logike, 68: 115–160.
  • –––, 1996, „Bimodalna logika za proširenje aritmetičkih teorija“, časopis za simboličku logiku, 61: 91–124.
  • –––, 1999, „Indukcija bez parametara i dobrojno ukupne funkcije koje se mogu izračunati”, Teorijska informatika, 224: 13–33.
  • –––, 2005, „Načela refleksije i algebre provabilnosti u formalnoj aritmetici“, Uspekhi Matematicheskikh Nauk, 60 (2): 3–78. (na ruskom); Prijevod s engleskog na: Russian Mathematical Surveys, 60 (2) (2005): 197–268.
  • –––, 2006., „Načelo crva“, u bilješkama predavanja iz logike 27. Logički kolokvij '02, Z. Chatzidakis, P. Koepke i W. Pohlers (ur.), Natick (MA): AK Peters, pp. 75–95.
  • –––, 2012, „Kalibracija logike provabilnosti: od modalne logike do kalkulacije refleksije“, u T. Bolander, T. Braüner, S. Ghilardi i L. Moss (ur.), Napredovanje u modalnoj logici (svezak 9), London: College Publications, str. 89–94.
  • –––, 2014, „Logika pozitivne provabilnosti za načela jednoobraznog odrazavanja“, Anali čiste i primijenjene logike, 165 (1): 82–105.
  • Beklemishev, LD, D. Fernández-Duque i JJ Joosten, 2014, „O logici dokazivosti s linearno uređenim modalitetima“, Studia Logica, 102 (3): 541–566.
  • Beklemishev, LD, M. Pentus i N. Vereshchagin, 1999, Provability, Complexity, Gramatika, Prijevodi američkog matematičkog društva (Series 2, Volume 192).
  • Beklemishev, LD i A. Visser, 2006, "Problemi u logici izvedivosti", u DM Gabbay, SS Goncharov i M. Zakharyasv (ur.), Matematički problemi iz primijenjene logike I: Logika za XXI stoljeće (Međunarodna matematička serija, Svezak 4), New York: Springer, str. 77–136.
  • van Benthem, J., 2006, „Korektivnosti modalnog okvira i fiksne točke“, Studia Logica, 83 (1-3): 133–155.
  • Carlson, T., 1986, „Modalna logika s nekoliko tumačenja operatora i proverljivosti“, Izraelski časopis za matematiku, 54 (1): 14–24.
  • Dashkov, EV, 2012, „O pozitivnom fragmentu polimodalne logike provabilnosti GLP“, Matematičke bilješke, 91 (3): 318–333.
  • Fernández-Duque, D., 2014, „The Polytopologies of Transfinite Provability Logic“, Arhiva za matematičku logiku, 53 (3-4): 385–431.
  • Fernández-Duque, D. i JJ Joosten, 2013a, „Hiperacije, Veblenovi progresi i transfinitetno ponavljanje običnih funkcija“, Anali čiste i primijenjene logike 164 (7-8): 785–801, [dostupan online].
  • Fernández-Duque, D. i JJ Joosten, 2013b, „Modeli logike beskonačne dokazivosti“, časopis za simboličku logiku, 78 (2): 543–561, [dostupan online].
  • Guaspari, D. i RM Solovay, 1979, "Rosser Sentences", Anali matematičke logike, 16: 81–99.
  • Iemhoff, R., 2000, „Modalna analiza nekih principa logike provabilnosti heitske aritmetike“, u Napretcima modalne logike (svezak 2), M. Zakharyashev i sur. (ur.), Stanford: CSLI Publications, str. 319–354.
  • –––, 2001, „O dopuštenim pravilima intuicionističke logike propozicija“, časopis za simboličku logiku, 66: 281–294.
  • –––, 2003, „Logika konzervativnosti: analogija logike interpretacije za konstruktivne teorije“, Kvartalna matematička logika, 49 (3): 1–21.
  • Lindström, P., 1994, „Modalna logika probirljivosti Pariha“, Filosofiska Meddelanden, Gröna Serien, Gothenburg: Göteborgs Universitetet.
  • Lindström, P., 2006, „O parikh provability: vježba u modalnoj logici“, u H. Lagerlund, S. Lindström, i R. Sliwinski (ur.), Pitanja o modalitetu: Dvadeset i pet eseja u čast Kristera Segerberga, Uppsala: Uppsala filozofske studije (svezak 53), str. 53–287.
  • Montagna, F., 1978, „O algebrizaciji Fefermanovog predikata“, Studia Logica, 37 (3): 221-236.
  • –––, 1979, „O dijagonalizirajućoj algebri peano-aritmetike“, Bollettino della Unione Matematica Italiana, B (5), 16: 795–812.
  • –––, 1980a, „Interpretacije teorije dijagonalizabilnih algebri prvog reda u peano aritmetici“, Studia Logica, 39: 347–354.
  • –––, 1980b, „Neodrešivost teorije prvog reda dijagonalizabilnih algebri“, Studia Logica, 39: 355–359.
  • –––, 1984., „Predikatna modalna logika dokazivosti“, Časopis za formalnu logiku Notre Dame, 25 (2): 179–189.
  • –––, 1992, „Polinomno i supereksponencijalno kraći dokazi u fragmentima aritmetike“, časopis za simboličku logiku, 57: 844–863.
  • Pakhomov, FN, 2012, „Neodrešivost elementarne teorije polumaratona GLP-riječi“, Sbornik: Matematika, 203 (8): 1211.
  • Shapirovsky, I., 2008, „PSPACE-decidability Japaridze's Polymodal Logic,“Napretci u modalnoj logici, 7: 289–304.
  • Shavrukov, V. Y., 1993a, „Bilješka o dijagonalizacijskim algebrama PA i ZF“, Anali čiste i primijenjene logike, 61: 161–173.
  • –––, 1993b, „Subalgebre dijagonalizabilnih algebri teorija koje sadrže aritmetiku“, Dissertationes Mathematicae, 323.
  • –––, 1994, „Pametno dijete peano-a“, časopis Notre Dame za formalnu logiku, 35 (2): 161–185.
  • Troelstra, AS, 1973, Metamathematičko istraživanje intuicijske aritmetike i analize, Berlin: Springer-Verlag.
  • Visser, A., 1980, Aspekti dijagonalizacije i proverljivosti, dr. Sc. Teza, Utrecht: Sveučilište u Utrechtu.
  • –––, 1982, „O načelu potpunosti: Studija dokazivosti u Heytingovoj aritmetici i ekstenzijama“, Anali matematičke logike, 22 (3): 263–295.
  • –––, 1989., „Peano's Smart Children: Logability Progrability Logical Study of Systems with ugrađena dosljednost“, Notre Dame Journal of Formal Logic, 30 (2): 161–196.
  • –––, 1999, „Pravila i aritmetika“, Časopis za formalnu logiku Notre Dame, 40 (1): 116–140.
  • –––, 2002, „Zamjene rečenica (Sigma_1): Istraživanja između intuicijske logike propozicija i intuicionističke aritmetike“, Anali čiste i primijenjene logike, 114: 227–271.
  • –––, 2005, „Löbova logika zadovoljava µ-račun“, u A. Middeldorp, V. van Oostrom, F. van Raamsdonk i R. de Vrijer (ur.), Procesi, termini i ciklusi: Koraci na putu do beskonačnosti, Berlin: Springer, str. 14–25.
  • –––, 2008, „Zatvoreni fragmenti logike dokazivosti konstruktivnih teorija“, časopis za simboličku logiku, 73: 1081–1096.
  • Zambella, D., 1994, „Shavrukov teorem o subalgebri dijagonalizabilnih algebri za teorije koje sadrže (I / Delta_0 + / exp),“Notre Dame Journal of Formal Logic, 35: 147–157.

Filozofski značaj

  • Davis, M., 1990, "Je li algoritam matematičkog uvida?", Komentar Rogera Penrosea, Carski novi smisao, nauke o ponašanju i mozgu, 13: 659–660.
  • –––, 1993., „Koliko je suptilan Gödelov teorem?“(Komentar Rogera Penrosea, Carski novi um), bihevioralne i misli o mozgu, 16: 611–612.
  • Egré, P., 2005, „Paradoks poznavanja u svjetlu probirljivosti interpretacija modalne logike“, časopis za logiku, jezik i informacije, 14 (1): 13–48.
  • Kaplan, D. i R. Montague, 1960., „Paradoks je zaživio“, časopis Notre Dame za formalnu logiku, 1 (3): 79–90.
  • Montague, R., 1963, „Sintaktički tretmani modaliteta, s rezultatima principa refleksije i konačnom aksiomatizibilnošću“, Acta Philosophica Fennica, 16: 153–67.
  • Quine, WV, 1966, "Neophodna istina", u Quine, WV, Načini paradoksa i drugi eseji, New York: Random House, str. 48–56.
  • –––, 1953., „Tri stupnja modalne uključenosti“, u Zborniku sa 11. međunarodnog filozofskog kongresa, Amsterdam: North-Holland, str. 65-81; reprinted in WV Quine, The Ways of Paradox and Other Essays, New York: Random House, 1966, str. 156–174.

Akademske alate

sep man ikona
sep man ikona
Kako navesti ovaj unos.
sep man ikona
sep man ikona
Pregledajte PDF verziju ovog unosa na Društvu prijatelja SEP-a.
inpho ikona
inpho ikona
Pogledajte ovu temu unosa na projektu Internet Filozofska ontologija (InPhO).
ikona papira phil
ikona papira phil
Poboljšana bibliografija za ovaj unos na PhilPapersu, s vezama na njegovu bazu podataka.

Ostali internetski resursi

Radovi i prezentacije

  • Fernández-Duque, D. i JJ Joosten, 2013., "Interpretacija logike ograničene dokazivosti Omega-pravila", internetski rukopis na arxiv.org.
  • Henk, P. i Pakhomov, F., 2016, „Spora i uobičajena dokazivost za aritmetiku peanoa“, rukopis na arxiv.org.
  • Pakhomov, F., 2014, „O elementarnim teorijama GLP-algebri“, rukopis na arxiv.org.
  • Pakhomov, F., 2015, „O osnovnim teorijama sustava običnih zapisa koji se temelje na principima refleksije“, rukopis na arxiv.org.
  • Visser, Albert, O formalnoj provabilnosti nasuprot ljudskoj provabilnosti (na nizozemskom), internetskim rukopisom, Sveučilište u Utrechtu.
  • Verbrugge, Rineke, Prezentacije o logici dokazivosti, dijapozitivi, University of Groningen

Ostala web mjesta

  • Otvoreni problemi u logici provabilnosti, koji održava Lev Beklemishev
  • Lista mailova Osnove matematike, Sveučilište New York

Preporučeno: