Logik Ketersediaan

Isi kandungan:

Logik Ketersediaan
Logik Ketersediaan

Video: Logik Ketersediaan

Video: Logik Ketersediaan
Video: АВТОМАТИЗАЦИЯ В LOGIC PRO X 2024, Mac
Anonim

Navigasi Masuk

  • Kandungan Penyertaan
  • Bibliografi
  • Alat Akademik
  • Pratonton PDF Rakan
  • Maklumat Pengarang dan Petikan
  • Kembali ke atas

Logik Ketersediaan

Pertama kali diterbitkan pada 2 Apr 2003; semakan substantif Rabu 5 Apr 2017

Logika ketersediaan adalah logik modal yang digunakan untuk menyelidiki teori aritmetik apa yang dapat dinyatakan dalam bahasa yang terhad mengenai predikat kebolehpercayaan mereka. Logiknya telah diilhamkan oleh perkembangan dalam meta-matematik seperti teorema ketidaklengkapan Gödel tahun 1931 dan teorema Löb tahun 1953. Sebagai logik modal, logik kebolehpercayaan telah dikaji sejak awal tahun tujuh puluhan, dan mempunyai aplikasi penting dalam asas matematik.

Dari sudut pandang falsafah, logik kebolehpercayaan menarik kerana konsep kebolehpercayaan dalam teori aritmetik tetap mempunyai makna yang unik dan tidak bermasalah, selain daripada konsep seperti keperluan dan pengetahuan yang dikaji dalam logik modal dan epistemik. Selanjutnya, logik kebolehpercayaan menyediakan alat untuk mengkaji konsep rujukan diri.

  • 1. Sejarah logik kebolehpercayaan
  • 2. Sistem aksioma logik kebolehpercayaan cadangan

    • 2.1 Aksioma dan peraturan
    • 2.2 Teorema titik tetap
  • 3. Semantik dunia yang mungkin dan semantik topologi

    • 3.1 Pencirian dan kekukuhan modal
    • 3.2 Kelengkapan modal
    • 3.3 Kegagalan kelengkapan yang kuat
    • 3.4 Semantik topologi untuk logik kebolehpercayaan
  • 4. Logik ketersediaan dan Aritmetik Peano

    • 4.1 Kekukuhan aritmetik
    • 4.2 Kelengkapan aritmetik
  • 5. Skop logik kebolehpercayaan

    • 5.1 Sempadan
    • 5.2 Logik kebolehtafsiran
    • 5.3 Pengukur cadangan
    • 5.4 Logik kebolehpercayaan bimodal dan polimodal Japaridze
    • 5.5 Predikat logik kebolehpercayaan
    • 5.6 Pengitlakan lain
  • 6. Kepentingan falsafah
  • Bibliografi
  • Alat Akademik
  • Sumber Internet Lain

    • Kertas kerja dan Pembentangan
    • Laman web lain
  • Penyertaan Berkaitan

1. Sejarah logik kebolehpercayaan

Dua helai penyelidikan telah menyebabkan lahirnya logik kebolehpercayaan. Yang pertama berasal dari makalah oleh K. Gödel (1933), di mana dia memperkenalkan terjemahan dari logik proposisi intuisi ke logik modal (lebih tepatnya, ke dalam sistem yang sekarang disebut S4), dan secara ringkas menyebutkan bahawa keterbuktian dapat dilihat sebagai pengendali modal. Bahkan sebelumnya, CI Lewis memulakan kajian moden mengenai logik modal dengan memperkenalkan implikasi ketat sebagai semacam deducibility, di mana dia mungkin bermaksud deducibility dalam sistem formal seperti Principia Mathematica, tetapi ini tidak jelas dari tulisannya.

Jalur lain bermula dari penyelidikan dalam meta-matematik: apa yang boleh dikatakan teori matematik mengenai diri mereka dengan mengekod sifat menarik? Pada tahun 1952, L. Henkin mengemukakan pertanyaan sederhana yang terinspirasi oleh teorema ketidaklengkapan Gödel. Untuk merumuskan soalan Henkin, diperlukan beberapa latar belakang lagi. Sebagai peringatan, teorema ketidaklengkapan pertama Gödel menyatakan bahawa, untuk teori formal yang cukup kuat seperti Peano Arithmetic, mana-mana ayat yang menyatakan bahawa tidak dapat dibuktikan sendiri sebenarnya tidak dapat dibuktikan. Sebaliknya, dari "luar" teori formal, seseorang dapat melihat bahawa ayat seperti itu benar dalam model standard, yang menunjukkan perbezaan penting antara kebenaran dan bukti.

Secara lebih formal, mari (ulcorner A / urcorner) menunjukkan nombor Gödel formula aritmetik (A), yang merupakan hasil pemberian kod berangka ke (A). Biarkan (Prov) menjadi predikat kebolehpercayaan formal untuk Peano Arithmetic, yang berupa (ada p \, / Bukti (p, x)). Di sini, (Proof) adalah predikat bukti rasmi dari Peano Arithmetic, dan (Proof (p, x)) bermaksud "Nombor Gödel (p) kod bukti yang betul dari aksioma Peano Arithmetic of formula dengan nombor Gödel (x)”. (Untuk rumusan yang lebih tepat, lihat Smoryński (1985), Davis (1958).) Sekarang, anggap Peith Arithmetic membuktikan (A / leftrightarrow / neg) (Prov (ulcorner A / urcorner)), kemudian oleh hasil Gödel, (A) tidak dapat dibuktikan dalam Peano Arithmetic, dan dengan itu benar, kerana sebenarnya ayat rujukan diri (A) menyatakan "Saya tidak dapat dibuktikan".

Henkin sebaliknya ingin mengetahui sama ada ada yang boleh dikatakan mengenai ayat yang menyatakan kebolehpercayaan mereka sendiri: andaian bahawa Aritmetik Peano membuktikan (B / leftrightarrow / Prov (ulcorner B / urcorner)), apakah maksudnya mengenai (B)? Tiga tahun kemudian, M. Löb menyahut cabaran dan menjawab pertanyaan Henkin dengan cara yang mengejutkan. Walaupun semua ayat yang dapat dibuktikan dalam Peano Arithmetic benar tentang nombor semula jadi, Löb menunjukkan bahawa versi rasmi dari fakta ini, (Prov (ulcorner B / urcorner) rightarrow B), dapat dibuktikan hanya dalam Peano Arithmetic dalam kes remeh yang Peith Arithmetic sudah membuktikan (B) itu sendiri. Hasil ini, sekarang disebut teorema Löb, segera menjawab pertanyaan Henkin. (Untuk bukti teorema Löb, lihat Bahagian 4.) Löb juga menunjukkan versi teoremanya yang diformalkan,iaitu bahawa Aritmetik Peano membuktikan

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

Dalam makalah yang sama, Löb merumuskan tiga syarat pada predikat kebolehpercayaan Peano Arithmetic, yang membentuk pengubahsuaian berguna dari keadaan rumit yang diperkenalkan oleh Hilbert dan Bernays pada tahun 1939 untuk bukti mereka mengenai teorema ketidaklengkapan kedua Gödel. Berikut ini, derivatif (A) dari Peano Arithmetic dilambangkan dengan (PA / vdash A):

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

Keadaan Löb ini, seperti yang disebut sekarang, seolah-olah berseru untuk penyelidikan logik modal, di mana modaliti (Box) bermaksud kebolehpercayaan dalam PA. Ironinya, pertama kalinya versi formal teorema Löb dinyatakan sebagai prinsip modal

(Kotak (Kotak A / kanan panah A) sebelah kanan / Kotak A)

ada dalam makalah oleh Smiley pada tahun 1963 mengenai asas etika logik, yang sama sekali tidak menganggap aritmetik. Bagaimanapun, penyelidikan yang lebih relevan, bermula dengan serius hanya hampir dua puluh tahun setelah penerbitan makalah Löb. Awal tahun 1970-an menyaksikan perkembangan pesat logik kebolehcayaan proposisional, di mana beberapa penyelidik di negara-negara yang berbeza membuktikan hasil yang paling penting, yang dibincangkan dalam Bahagian 2, 3, dan 4. Logik kebolehlaksanaan cadangan ternyata dapat menangkap dengan tepat apa yang banyak teori formal aritmetik dapat katakan dengan kaedah cadangan mengenai predikat kebolehpercayaan mereka sendiri. Baru-baru ini, para penyelidik telah menyelidiki batas-batas pendekatan ini dan telah mencadangkan beberapa logik kebolehpercayaan yang lebih ekspresif yang menarik (lihat Bahagian 5).

2. Sistem aksioma logik kebolehpercayaan cadangan

Bahasa logik logik kebolehkesanan proposisional mengandung, selain atom proposional dan operator fungsional kebenaran yang biasa serta simbol kontradiksi (bot), operator modal (Kotak) dengan maksud yang dimaksudkan dapat dibuktikan dalam (T),”di mana (T) adalah teori formal yang cukup kuat, mari kita katakan Peano Arithmetic (lihat Bahagian 4). (Diamond A) adalah singkatan untuk (neg \, / Box / neg \, A). Oleh itu, bahasanya sama dengan sistem modal seperti K dan S4 yang disajikan dalam logik modal masuk.

2.1 Aksioma dan peraturan

Logik provabiliti cadangan sering disebut GL, selepas Gödel dan Löb. (Nama alternatif yang terdapat dalam literatur untuk sistem yang setara adalah L, G, KW, K4W, dan PrL). Logik GL terhasil daripada menambahkan aksioma berikut ke logik modal asas K:

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

Sebagai peringatan, kerana GL memanjangkan K, ia berisi semua formula yang mempunyai bentuk tautologi cadangan. Atas sebab yang sama, GL mengandungi

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

Selanjutnya, ia ditutup di bawah Modus Ponens Rule, yang memungkinkan untuk memperoleh (B) dari (A / rightarrow B) dan (A), dan Generalization Rule, yang mengatakan bahawa jika (A) adalah teorema GL, maka begitu juga (Kotak A).

Pengertian (GL / vdash A) menunjukkan kebolehkesanan formula modal (A) dalam logik kebolehcadangan proposisional. Tidak sukar untuk melihat bahawa aksioma modal (Box A / rightarrow / Box / Box A) (dikenali sebagai Axiom 4 logik modal) memang dapat dibuktikan dalam GL. Untuk membuktikannya, seseorang menggunakan penggantian (A / wedge / Box A) untuk (A) dalam aksioma (GL). Kemudian, melihat bahawa anteseden dari implikasi yang dihasilkan berasal dari (Kotak A), seseorang menerapkan Aksi Pengagihan dan Peraturan Generalisasi serta beberapa logik cadangan. Kecuali dinyatakan secara eksplisit sebaliknya, dalam sekuel "logik kebolehpercayaan" bermaksud sistem GL logik kebolehpercayaan cadangan.

Mengenai teori bukti logik kebolehpercayaan, Valentini (1983) membuktikan bahawa formulasi kalkulus urutan standard GL mematuhi penghapusan potong, yang bermaksud, dirumuskan secara kasar, bahawa setiap formula yang dapat dibuktikan dari GL dalam kalkulus urutan juga mempunyai bukti urutan GL “tanpa jalan memutar”(lihat entri pengembangan teori bukti untuk penjelasan tepat mengenai penghapusan potongan). Dalam beberapa tahun kebelakangan ini, terdapat minat baru dalam teori bukti GL, lihat misalnya Goré dan Ramanayake (2008). Penghapusan potongan membawa kepada sifat subformula yang diinginkan untuk GL, kerana semua formula yang muncul dalam bukti bebas potong adalah subformula dari formula akhir.

Untuk penyiasatan teori-bukti terkini mengenai logik kebolehpercayaan berdasarkan kalkulus urutan bebas potong yang berbeza lihat (Negri 2005, 2014; Poggiolesi 2009). Negri memberikan dua calculi urutan berlabel yang setara untuk GL dan bukti sintaksis penghapusan potongan. Walaupun sifat subformula penuh tidak berlaku untuk kalkulus ini kerana pelabelan, akibat biasa dari sifat subformula dapat ditentukan: Formalisme berlabel membenarkan bukti kelengkapan langsung, yang dapat digunakan untuk membuktikan kerentanan serta model terhingga harta, yang bermaksud bahawa sebarang formula yang tidak dapat dibuktikan mempunyai model kontra yang terhad.

Perkembangan teoritis bukti-bukti baru yang menarik adalah pengembangan sistem bukti gaya urutan Shamkanov dengan membenarkan bukti bulat (Shamkanov 2014). Pertimbangkan sistem berurutan untuk K4, sistem modal yang dihasilkan dari GL dengan menggantikan aksioma GL dengan aksioma yang lebih lemah (Box A / rightarrow / Box / Box A) (aksioma 4). Walau bagaimanapun, anggap hipotesis terbuka dibenarkan, dengan syarat urutan yang sama berlaku betul-betul di bawah hipotesis di pohon bukti. Diformulasikan secara lebih teknikal, seseorang dapat mencari derivasi bulat dari pohon turunan biasa dengan menghubungkan setiap daun bukan aksiomatiknya dengan simpul dalaman yang sama. Shamkanov (2014) membuktikan bahawa sistem yang dihasilkan adalah konsisten dan lebih-lebih lagi, secara umum, setiap urutan mempunyai turunan GL jika dan hanya jika mempunyai turunan K4 bulat. Pembuktian pekeliling juga menyediakan kaedah untuk menunjukkan bukti-teori bahawa teorema interpolasi Lyndon berlaku untuk GL. Interpolasi standard untuk GL telah terbukti sebelum ini dengan kaedah yang berbeza (Boolos 1979; Smoryński 1978; Rautenberg 1983). (Untuk maklumat lebih lanjut mengenai teorema interpolasi Lyndon untuk logik pesanan pertama, lihat juga teori model pesanan pertama).

2.2 Teorema titik tetap

Hasil "modal" utama mengenai logik kebolehpercayaan adalah teorema titik tetap, yang dibuktikan oleh D. de Jongh dan G. Sambin secara bebas pada tahun 1975 (Sambin 1976). Walaupun dirumuskan dan dibuktikan dengan kaedah modal yang ketat, teorema titik tetap masih mempunyai aritmetik yang sangat penting. Ini pada dasarnya mengatakan bahawa rujukan diri tidak benar-benar diperlukan, dalam pengertian berikut. Anggaplah bahawa semua kejadian pemboleh ubah proposisi (p) dalam formula tertentu (A (p)) berada di bawah skop pengendali kebolehpercayaan, misalnya (A (p) = / neg / Kotak p), atau (A (p) = / Kotak (p / kanan bawah q)). Kemudian ada formula (B) di mana (p) tidak muncul, sehingga semua pemboleh ubah proposisi yang terjadi di (B) sudah muncul di (A (p)), dan seperti itu

(GL / vdash B / kiri kananarrow A (B).)

Rumus ini (B) dipanggil titik tetap (A (p)). Lebih-lebih lagi, titik tetap adalah unik, atau lebih tepat, jika ada formula lain (C) sehingga (GL / vdash C / leftrightarrow A (C)), maka kita mesti mempunyai (GL / vdash B / kiri kanan C). Sebilangan besar bukti dalam literatur memberikan algoritma di mana seseorang dapat mengira titik tetap (lihat Smoryński 1985, Boolos 1993, Sambin dan Valentini 1982, Lindström 2006). Bukti yang sangat pendek dan jelas, serta algoritma yang sangat cekap untuk mengira titik tetap, terdapat dalam Reidhaar-Olson (1990).

Contohnya, anggaplah (A (p) = / neg \, / Kotak p). Maka titik tetap yang dihasilkan oleh algoritma seperti itu adalah (neg \, / Box / bot), dan memang seseorang dapat membuktikan bahawa

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

Sekiranya ini dibaca secara aritmetik, arah dari kiri ke kanan hanyalah versi formal dari teorema ketidaklengkapan kedua Gödel: jika teori formal yang cukup kuat (T) seperti Peano Arithmetic tidak membuktikan percanggahan, maka itu tidak dapat dibuktikan di (T) bahawa (T) tidak membuktikan percanggahan. Oleh itu, teori aritmetik konsisten yang cukup kuat tidak dapat membuktikan konsistensinya sendiri. Kami akan mengkaji hubungan antara logik kebolehpercayaan dan aritmetik dengan lebih tepat dalam Bahagian 4, tetapi untuk itu aspek “modal” lain dari GL perlu disediakan terlebih dahulu: semantik.

3. Semantik dunia yang mungkin dan semantik topologi

Logik ketersediaan mempunyai semantik dunia yang sesuai, seperti banyak logik modal lain. Sebagai peringatan, model dunia yang mungkin (atau model Kripke) adalah triple (M = / langle W, R, V / rangle), di mana (W) adalah sekumpulan dunia yang mungkin kosong, (R) adalah hubungan kebolehaksesan binari pada (W), dan (V) adalah penilaian yang memberikan nilai kebenaran kepada setiap pemboleh ubah cadangan untuk setiap dunia di (W). Pasangan (F = / langle W, R / rangle) dipanggil kerangka model ini. Pengertian kebenaran formula (A) dalam model (M) di dunia (W), notasi (M, w / model A), didefinisikan secara induktif. Mari kita ulangi hanya klausa yang paling menarik, satu untuk pengendali kebolehpercayaan (Box):

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

Lihat logik modal entri untuk maklumat lebih lanjut mengenai semantik dunia mungkin secara umum.

3.1 Pencirian dan kekukuhan modal

Logik modal K berlaku di semua model Kripke. Peluasan GL bagaimanapun, tidak: kita perlu menghadkan kelas model dunia yang mungkin kepada model yang lebih sesuai. Katakan bahawa formula (A) berlaku dalam bingkai (F), notasi (F / model A), iff (A) berlaku di semua dunia dalam model Kripke (M) berdasarkan (F). Ternyata logik kebolehpercayaan aksioma (GL) baru sesuai dengan keadaan pada bingkai, seperti berikut:

Untuk semua bingkai (F = / langle W, R / rangle, F / models / Box (Box p / rightarrow p) rightarrow / Box p) iff (R) bersifat transitif dan bertentangan dengan baik.

Di sini, transitiviti adalah harta yang terkenal yang untuk semua dunia (w_1), (w_2), (w_3) di (W), jika (w_1 Rw_2) dan (w_2 Rw_3), kemudian (w_1 Rw_3). Suatu hubungan terbentuk dengan baik sekiranya tidak ada urutan menaik yang tidak terbatas, iaitu urutan bentuk (w_1 Rw_2 Rw_3 R / ldots). Perhatikan bahawa bingkai yang bertentangan dengan baik juga tidak mencerminkan, kerana jika (wRw), ini menimbulkan urutan menaik yang tidak terbatas (wRwRwR / ldots).

Hasil korespondensi di atas langsung menunjukkan bahawa GL cukup baik untuk model kelas dunia mungkin pada bingkai transitif yang bertentangan dengan baik, kerana semua aksioma dan peraturan GL berlaku pada model tersebut. Persoalannya adalah apakah kelengkapan juga berlaku: misalnya, formula (Box A / rightarrow / Box / Box A), yang berlaku pada semua bingkai transitif, memang dapat dibuktikan dalam GL, seperti yang disebutkan dalam Bahagian 1. Tetapi adakah setiap formula yang berlaku pada semua bingkai transitif yang bertentangan dengan baik juga dapat dibuktikan dalam GL?

3.2 Kelengkapan modal

Tanpa menyedari aritmetik kepentingan GL, K. Segerberg membuktikan pada tahun 1971 bahawa GL sememangnya lengkap berkenaan dengan bingkai transitif yang bertapak dengan baik; D. de Jongh dan S. Kripke secara bebas membuktikan hasil ini juga. Segerberg menunjukkan bahawa GL lengkap walaupun berkenaan dengan kelas pokok tak transitif transitif terhingga yang lebih terhad, sebuah fakta yang kemudiannya sangat berguna untuk bukti Solovay mengenai teorema kelengkapan aritmetik (lihat Bahagian 4).

Teorema modal dan kelengkapan modal segera menimbulkan prosedur keputusan untuk memeriksa formula formula apa pun (A) sama ada (A) mengikuti GL atau tidak, dengan carian pertama yang mendalam melalui pokok transitif yang tidak refleks dengan kedalaman batas. Melihat prosedur dengan lebih tepat, dapat ditunjukkan bahawa GL dapat ditentukan dalam kelas kerumitan komputasi PSPACE, seperti logik modal K, T dan S4 yang terkenal. Ini bermaksud bahawa ada mesin Turing yang, diberi formula (A) sebagai input, menjawab sama ada (A) mengikuti dari GL atau tidak; ukuran memori yang diperlukan oleh mesin Turing untuk pengiraannya hanya polinomial dengan panjang (A). Seseorang dapat menunjukkan bahawa masalah keputusan untuk GL (sekali lagi, seperti masalah keputusan untuk K, T dan S4) selesai PSPACE,dalam arti bahawa semua masalah lain di PSPACE tidak lebih sukar daripada memutuskan sama ada formula yang diberikan adalah teorem GL. (Lihat Goré dan Kelly (2007) untuk perihalan peribahasa teorema automatik untuk GL.)

Untuk memberikan lebih banyak perspektif mengenai kerumitan, fungsi kelas P yang dapat dikira dalam jumlah masa polinomial dalam panjang input, dimasukkan ke dalam PSPACE, yang seterusnya termasuk dalam kelas EKSPTIME fungsi yang dapat dikira dalam waktu eksponensial (lihat pengiraan kemasukan dan kerumitan). Ini tetap menjadi masalah terbuka yang terkenal sama ada kedua-dua penyertaan ini ketat, walaupun banyak teori kerumitan percaya bahawa mereka benar. Beberapa logik modal lain yang terkenal, seperti logik epistemik dengan pengetahuan umum, dapat ditentukan dalam PENGECUALIAN, oleh itu ia mungkin lebih kompleks daripada GL, bergantung pada masalah terbuka.

3.3 Kegagalan kelengkapan yang kuat

Banyak logik modal terkenal (S) tidak hanya lengkap berkenaan dengan bingkai bingkai yang sesuai, tetapi juga lengkap. Untuk menjelaskan kelengkapan yang kuat, kita memerlukan pengertian derivabiliti dari satu set andaian. Rumus (A) boleh diturunkan dari kumpulan andaian (Gamma) dalam logik modal (S), ditulis sebagai (Gamma / vdash A), jika (A) ada di (Gamma) atau (A) mengikuti formula di (Gamma) dan aksioma (S) oleh aplikasi Modus Ponens dan Peraturan Umum. Di sini, Peraturan Generalisasi hanya dapat diterapkan pada derivasi tanpa andaian (lihat Hakli dan Negri 2010).

Kini logik modal (S) sangat lengkap jika untuk semua set (terhingga atau tak terhingga) (Gamma) dan semua formula (A):

Jika, pada bingkai (S) yang sesuai, (A) adalah benar di semua dunia di mana semua formula (Gamma) adalah benar, maka (Gamma / vdash A) dalam logik (S).

Keadaan ini berlaku untuk sistem seperti K, M, K4, S4, dan S5. Sekiranya terhad kepada set terhingga (Gamma), syarat di atas sesuai dengan kelengkapan.

Kelengkapan yang kuat tidak memerlukan logik kebolehpercayaan, kerana kesempitan semantik gagal. Kekompakan semantik adalah sifat bagi setiap rangkaian formula yang tidak terhingga (Gamma), Sekiranya setiap subset terhingga (Delta) dari (Gamma) mempunyai model pada bingkai (S) yang sesuai, maka (Gamma) juga mempunyai model pada (S) yang sesuai -rangka.

Sebagai contoh, ambil formula yang tidak terhingga

(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}), / lots })

Kemudian untuk setiap subset terhingga (Delta) (Gamma), seseorang dapat membina model pada bingkai transitif, bertentangan dengan baik dan dunia dalam model di mana semua formula (Delta) berada benar. Oleh itu, dengan kekuatan modal, GL tidak membuktikan (bot) dari (Delta) untuk apa-apa yang terhingga (Delta / subseteq / Gamma), dan a fortiori GL tidak membuktikan (bot) dari (Gamma), kerana sebarang bukti GL adalah terhad. Sebaliknya, mudah dilihat bahawa tidak ada model pada bingkai transitif, bertentangan dengan baik di mana di mana-mana dunia, semua formula (Gamma) tahan. Oleh itu (bot) mengikuti secara semantik dari (Gamma), tetapi tidak dapat dibuktikan dari itu dalam GL, bertentangan dengan keadaan kelengkapan yang kuat.

3.4 Semantik topologi untuk logik kebolehpercayaan

Sebagai alternatif untuk semantik dunia yang mungkin, banyak logika modal mungkin diberi semantik topologi. Jelas, proposisi dapat ditafsirkan sebagai subset dari ruang topologi. Juga mudah untuk melihat bahawa penghubung proporsional (wedge) sesuai dengan operasi set-teoretik (cap), sementara (vee) sesuai dengan (cup), (neg) sesuai dengan pelengkap set-teoretik, dan (kanan bawah] sesuai dengan (subseteq). Logik modal yang mengandungi aksioma pantulan (Kotak A / rightarrow A) menikmati penafsiran semula jadi pengendali modal juga. Untuk logik ini, (Diamond) sesuai dengan operator penutupan di ruang topologi, sementara (Box) sesuai dengan pedalaman. Untuk melihat mengapa tafsiran ini sesuai,perhatikan bahawa aksioma pantulan sesuai dengan kenyataan bahawa setiap set termasuk dalam penutupnya dan setiap set merangkumi bahagian dalamnya.

Namun, logik kebolehpercayaan tidak membuktikan refleksi, kerana pemantulan (Box / bot / rightarrow / bot) akan menimbulkan percanggahan dengan aksioma (GL).

Oleh itu, logik ketersediaan memerlukan pendekatan yang berbeza. Berdasarkan cadangan J. McKinsey dan A. Tarski (1944), L. Esakia (1981, 2003) menyiasat tafsiran (Diamond) sebagai pengendali set turunan (d), yang memetakan satu set (B) ke set titik hadnya (d (B)). Untuk menjelaskan akibat penafsiran (Diamond) ini, kita memerlukan dua definisi lagi, iaitu konsep yang padat dan tersebar. Subset (B) ruang topologi dipanggil padat dalam dirinya jika (B / subseteq d (B)). Ruang topologi dipanggil tersebar jika tidak mempunyai subset kosong yang padat. Ordo dalam topologi selang mereka membentuk contoh ruang yang tersebar. Esakia (1981) membuktikan korespondensi penting: dia menunjukkan bahawa ruang topologi memenuhi aksioma GL jika dan hanya jika ruang itu tersebar. Surat-menyurat ini segera membawa kepada hasil, yang secara bebas dijumpai oleh Abashidze (1985) dan Blass (1990), bahawa logik kebolehpercayaan lengkap sehubungan dengan ordinal (ge / omega ^ / omega).

Dalam beberapa tahun kebelakangan ini, semantik topologi untuk logik kebolehpercayaan telah melihat kebangkitan semula, terutamanya dalam kajian logik kebolehpercayaan bimodal Japaridze GLB, lanjutan dari GL (Japaridze 1986). Logik GLB ternyata tidak lengkap secara modalnya sehubungan dengan semantik dunia yang mungkin, dalam arti bahawa ia tidak sesuai dengan kelas bingkai mana pun. Ciri ini menempatkan GLB bimodal dalam kontras yang tajam dengan GL unimodal, yang sesuai dengan kelas pokok tak transitif transitif terhingga, seperti yang disebutkan di atas. Beklemishev et al. (2009) menunjukkan bahawa GLB, bagaimanapun, lengkap berkaitan dengan semantik topologi (lihat juga Beklemishev 2009, Icard 2011). Gema yang mengasyikkan mengenai korespondensi Esakia antara GL dan ruang topologi yang tersebar bahkan dapat dijumpai dalam kajian topologi baru-baru ini mengenai logik spasial dan epistemik (lihat Aiello et al.2007). (Lihat Bahagian 5.4 untuk perbincangan lebih lanjut mengenai GLB).

4. Logik ketersediaan dan Aritmetik Peano

Dari saat GL dirumuskan, para penyelidik tertanya-tanya apakah itu memadai untuk teori formal seperti Peano Arithmetic (PA): adakah GL membuktikan segala-galanya mengenai gagasan kebolehpercayaan yang dapat dinyatakan dalam bahasa modal cadangan dan dapat dibuktikan dalam Peano Arithmetic, atau perlukah lebih banyak prinsip ditambahkan pada GL? Untuk menjadikan pengertian kecukupan ini lebih tepat, kami mendefinisikan kesedaran (kadang-kadang disebut terjemahan atau tafsiran) menjadi fungsi yang memberikan kepada setiap atom cadangan logik modal kalimat aritmetik, di mana

  • (f (bot) = / bot;)
  • (f) menghormati penghubung logik, sebagai contoh, (f (B / rightarrow C) = (f (B) rightarrow f (C));) dan
  • (Box) diterjemahkan sebagai predikat kebolehpercayaan (Prov), jadi (f (Kotak B) = / Prov (ulcorner f (B) urcorner).)

4.1 Kekukuhan aritmetik

Sudah jelas pada awal tahun 1970-an bahawa GL sesuai secara aritmetik terhadap PA, secara rasmi:

(text {If} GL / vdash A, / text {kemudian untuk semua kesedaran} f, / PA / vdash f (A).)

Untuk memberi gambaran mengenai meta-matematik, mari kita lakar bukti kukuh.

Lakaran bukti arithmetical soundness. PA sememangnya membuktikan kesedaran mengenai tautologi proposisional, dan kebolehlenturan dari Distribusi Axiom of GL diterjemahkan

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

untuk semua formula A dan B, yang merupakan syarat terbitan kedua Löb (lihat Bahagian 1). Lebih-lebih lagi, PA mematuhi Modus Ponens, dan juga terjemahan Peraturan Umum:

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

yang merupakan syarat terbitan pertama Löb. Akhirnya, terjemahan aksioma utama (GL) memang dapat dibuktikan dalam PA:

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

Ini betul-betul versi rasmi teorema Löb yang disebutkan dalam Bahagian 1.

Marilah kita memberikan sketsa bukti teorema Löb itu sendiri dari keadaan terbitannya (bukti versi formal serupa). Buktinya berdasarkan pada diagonalisasi lemma Gödel, yang mengatakan bahawa untuk formula aritmetik mana pun (C (x)) terdapat formula aritmetik (B) sehingga

(PA / vdash B / kiri kananarrow C (ulcorner B / urcorner).)

Dengan kata lain, formula (B) mengatakan "Saya mempunyai harta (C)."

Bukti Lob yang theorem:. Katakan bahawa (PA / vdash / Prov (ulcorner A / urcorner) rightarrow A); kita perlu menunjukkan bahawa (PA / vdash A). Dengan lemma pepenjuru, terdapat formula (B) sedemikian rupa

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

Dari ini diikuti oleh syarat derivasi pertama dan kedua Löb ditambah dengan beberapa alasan yang bernas bahawa

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

Oleh itu, sekali lagi dengan keadaan kedua Löb, (PA / vdash / Prov (ulcorner B / urcorner) rightarrow (Prov (ulcorner / Prov (ulcorner B / urcorner) urcorner) rightarrow / Prov (ulcorner A / urcorner)).)

Sebaliknya syarat ketiga Löb memberi

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

dengan demikian

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

Bersama dengan anggapan bahawa (PA / vdash / Prov (ulcorner A / urcorner) rightarrow A), ini memberikan

(PA / vdash / Prov (ulcorner B / urcorner) kanan bawah A.)

Akhirnya, persamaan yang dihasilkan oleh diagonalisasi lemma menunjukkan bahawa (PA / vdash B), jadi (PA / vdash / Prov (ulcorner B / urcorner)), dengan demikian

(PA / vdash A,)

seperti yang dikehendaki.

Perhatikan bahawa menggantikan (bot) dengan (A) dalam teorema Löb, kita memperoleh bahawa (PA / vdash / neg \, / Prov (ulcorner / bot / urcorner)) menyiratkan (PA / vdash / bot), yang merupakan kontras dari teorema ketidaklengkapan kedua Gödel.

4.2 Kelengkapan aritmetik

Hasil utama dalam logik kebolehpercayaan adalah teorema kelengkapan aritmetik R. Solovay tahun 1976, menunjukkan bahawa GL sememangnya mencukupi untuk Peano Arithmetic:

(GL / vdash A / text {jika dan hanya jika untuk semua kesedaran} f, / PA / vdash f (A).)

Teorema ini pada asasnya mengatakan bahawa logik modal GL menangkap semua yang dapat dikatakan oleh Peano Arithmetic dengan jujur dalam istilah modal mengenai predikat pembuktiannya sendiri. Arah dari kiri ke kanan, kekemasan aritmetik GL, dibincangkan di atas. Solovay berusaha untuk membuktikan arah yang lain, jauh lebih sukar, dengan cara bertentangan. Bukti beliau berdasarkan teknik rujukan diri yang rumit, dan hanya sekilas kecil yang dapat diberikan di sini.

Teori kelengkapan modal oleh Segerberg adalah langkah pertama yang penting dalam bukti Solovay mengenai kelengkapan aritmetik GL berkenaan dengan Peano Arithmetic. Katakan GL tidak membuktikan formula mod (A). Kemudian, dengan kelengkapan moda, ada pokok tak transitif transitif terhingga sehingga (A) salah pada akar pokok itu. Kini Solovay merancang cara bijak untuk mensimulasikan sebatang pokok terhingga dalam bahasa Peano Arithmetic. Oleh itu, dia menemui kesedaran (f) dari formula modal hingga kalimat aritmetik, sehingga Aritmetik Peano tidak membuktikan (f (A)).

Teorema kelengkapan Solovay menyediakan kaedah alternatif untuk membina banyak ayat aritmetik yang tidak dapat dibuktikan dalam Peano Arithmetic. Sebagai contoh, adalah mudah untuk membuat model dunia yang mungkin untuk menunjukkan bahawa GL tidak membuktikan (Box p / vee / Box / neg \, p), oleh itu oleh teorema Solovay, ada kalimat aritmetik (f (p)) supaya Aritmetik Peano tidak membuktikan (Prov (ulcorner f (p) urcorner) vee / Prov (ulcorner / neg \, f (p) urcorner)). Secara khusus, ini menunjukkan bahawa (f (p)) atau (neg \, f (p)) tidak dapat dibuktikan dalam Peano Arithmetic; kerana anggap sebaliknya bahawa (PA / vdash f (p)), kemudian oleh keadaan pertama dan logik cadangan Löb, (PA / vdash / Prov (ulcorner f (p) urcorner) vee / Prov (ulcorner / neg \, f (p) urcorner)), yang membawa kepada percanggahan, dan juga jika seseorang menganggap bahawa (PA / vdash / neg \, f (p)).

Teorema Solovay begitu penting kerana ia menunjukkan bahawa suatu fragmen menarik dari teori formal yang tidak dapat dipertikaikan seperti Peano Arithmetic-iaitu yang dapat dinyatakan oleh aritmetik secara proporsional mengenai predikat kebolehpercayaannya sendiri-dapat dikaji dengan menggunakan logik modal yang dapat diputuskan, GL, dengan semantik dunia yang berpotensi besar.

5. Skop logik kebolehpercayaan

Dalam bahagian ini, beberapa trend terkini dalam penyelidikan logik kebolehpercayaan dibincangkan. Satu helai penting berkaitan dengan batasan skop GL, di mana persoalan utamanya adalah, untuk teori formal mana, selain Peano Arithmetic, adakah GL merupakan logik kebolehkesanan cadangan yang sesuai? Seterusnya, kita membincangkan beberapa generalisasi logik kebolehkesanan proposisional dalam bahasa modal yang lebih ekspresif.

5.1 Sempadan

Dalam beberapa tahun kebelakangan ini, pakar logik telah menyiasat banyak sistem aritmetik lain yang lebih lemah daripada Aritmetik Peano. Selalunya pakar logik ini mengambil inspirasi dari masalah kebolehkomputeran, misalnya kajian fungsi yang dapat dikira pada masa polinomial. Mereka telah memberikan sebagian jawaban untuk pertanyaan: "Untuk teori aritmetik manakah teorema kelengkapan aritmetik Solovay (berkenaan dengan predikat kebolehcayaan yang sesuai) masih ada?" Untuk membincangkan persoalan ini, diperlukan dua konsep. (Delta_0) - formula adalah formula aritmetik di mana semua pengukur dibatasi oleh istilah, misalnya

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

di mana (bs) adalah operator pengganti ("(+ 1)"). Teori aritmetik (I / Delta_0) (di mana saya bermaksud "induksi"), mirip dengan Aritmetik Peano, kecuali ia membenarkan lebih sedikit aruhan: skema induksi

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

dihadkan kepada (Delta_0) - formula (A).

Seperti yang ditunjukkan oleh De Jongh dan lain-lain (1991), kelengkapan aritmetik pasti berlaku untuk teori (T) yang memenuhi dua syarat berikut:

  1. (T) membuktikan induksi untuk (Delta_0) - formula, dan (T) membuktikan EXP, formula yang menyatakan bahawa untuk semua (x), kekuatannya (2 ^ x) ada. Dalam tatatanda yang lebih standard: (T) memanjang (I / Delta_0) + EXP;
  2. (T) tidak membuktikan ayat palsu dari bentuk (wujud x \, A (x)), dengan formula (A (x)) a (Delta_0) -.

Untuk teori seperti itu, kekemasan aritmetik dan kelengkapan penahan GL, dengan syarat (Box) diterjemahkan ke (Prov_T), predikat kebolehpercayaan semula jadi berkenaan dengan aksiomatisasi yang cukup sederhana dari (T). Oleh itu untuk ayat mod (A):

(GL / vdash A / text {jika dan hanya jika untuk semua kesedaran} f, T / vdash f (A).)

Masih belum jelas sama ada Syarat 1 memberikan had yang lebih rendah pada skop logik kebolehpercayaan. Sebagai contoh, masih menjadi persoalan terbuka sama ada GL adalah logik kebolehpercayaan (I / Delta_0 + / Omega_1), teori yang agak lemah daripada (I / Delta_0) + EXP dalam (Omega_1) adalah aksioma yang menegaskan bahawa untuk semua (x), kuasanya (x ^ { log (x)}) wujud. Logik kebolehpercayaan GL sesuai dengan aritmetik sehubungan dengan (I / Delta_0 + / Omega_1), tetapi kecuali beberapa hasil separa oleh Berarducci dan Verbrugge (1993), memberikan realiti aritmetik selaras dengan (I / Delta_0 + / Omega_1) untuk larangan kelas ayat selaras dengan GL, soalannya tetap terbuka. Jawapannya mungkin bergantung pada masalah terbuka dalam teori kerumitan komputasi.

Hasil di atas oleh De Jongh et al. menunjukkan ciri logik kebolehpercayaan yang kuat: bagi banyak teori aritmetik yang berbeza, GL menangkap dengan tepat apa yang dikatakan oleh teori-teori itu mengenai predikat kebolehpercayaan mereka sendiri. Pada masa yang sama ini adalah kelemahan. Sebagai contoh, logik kebolehkesanan proporsional tidak menunjukkan perbezaan antara teori-teori yang dapat aksiomatizkan dengan yang tidak.

5.2 Logik kebolehtafsiran

Untuk dapat berbicara dalam bahasa modal mengenai perbezaan penting antara teori, penyelidik telah memperluas logik kebolehpercayaan dengan pelbagai cara. Mari kita sebutkan beberapa. Satu peluasan ialah menambahkan modaliti binari (menafsirkan), di mana untuk teori aritmetik tertentu ((T), kalimat modal (A / menafsirkan B) dimaksudkan sebagai singkatan dari (T + B) dapat ditafsirkan dalam (T + A)”(Švejdar, 1983). De Jongh dan Veltman (1990) menyelidiki semantik modal untuk beberapa logika kebolehtafsiran, sementara De Jongh dan Visser (1991) membuktikan sifat titik tetap eksplisit untuk yang paling penting. Visser mencirikan logik kebolehtafsiran teori-teori aksiomatik yang paling biasa, dan Berarducci dan Shavrukov secara bebas menggambarkan teori PA, yang tidak dapat aksiomatik. Nampaknya,logik kebolehtafsiran teori aksiomatizik yang berbeza adalah berbeza dari logik kebolehtafsiran Peano Arithmetic (lihat Montagna 1987; Visser 1990, 1998; Berarducci 1990, Shavrukov 1988; Joosten dan Visser 2000).

5.3 Pengukur cadangan

Cara lain untuk memperluas kerangka logik kebolehcayaan proposisional adalah dengan menambahkan pengukur proposisional, sehingga seseorang dapat menyatakan prinsip seperti Goldfarb:

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

mengatakan bahawa untuk mana-mana dua ayat terdapat ayat ketiga yang dapat dibuktikan jika dan hanya jika salah satu daripada dua ayat pertama dapat dibuktikan. Prinsip ini dapat dibuktikan dalam Peano Arithmetic (lihat misalnya Artemov dan Beklemishev 1993). Kumpulan ayat GL dengan pengukur proposisional yang valid secara aritmetik ternyata tidak dapat ditentukan (Shavrukov 1997).

5.4 Logik kebolehpercayaan bimodal dan polimodal Japaridze

Logik bimodal Japaridze (1988) GLB mempunyai dua (Box) - seperti pengendali kebolehtentuan, dilambangkan dengan ([0]) dan ([1]), dengan operator mereka yang serupa (Diamond) - (langle 0 / rangle) dan (langle 1 / rangle), masing-masing. Dalam tafsiran Japaridze, seseorang dapat menganggap ([0]) sebagai singkatan dari predikat kebolehpercayaan standard dalam Peano Arithmetic. Sebaliknya, ([1]) sesuai dengan predikat kebolehpercayaan yang lebih kuat, iaitu (omega) - provabiliti.

Mari kita tentukan konsep yang diperlukan untuk memahami tafsiran GLB yang dimaksudkan ini. Teori aritmetik (T) didefinisikan sebagai (omega) - konsisten jika dan hanya jika untuk semua formula A dengan pemboleh ubah bebas (x), (T / vdash / neg \, A (I_n)) untuk semua (n) menyiratkan bahawa (T / not / vdash / wujud x \, A (x)); di sini, (I_n) adalah angka (n), iaitu, istilah (bs / bs / ldots / bs 0) dengan (n) kejadian pengendali pengganti (bs). Peano Arithmetic (PA) adalah contoh teori konsisten (omega) yang paling terkenal (lihat juga teorema ketidaklengkapan Gödel). Sekarang mari PA (^ +) menjadi teori aritmetik yang aksiomanya adalah PA bersama semua ayat (forall x \, / neg \, A (x)) sehingga untuk setiap (n), PA (vdash / neg \, A (I_n)). Sekarang (omega) - kebolehpercayaan hanyalah kebolehpercayaan dalam PA (^ +),jadi ia adalah dua dari konsistensi (omega).

Logik kebolehpercayaan bimodal Japaridze GLB dapat diakui oleh aksioma dan peraturan GL (lihat Bahagian 2), dirumuskan secara berasingan untuk [0] dan [1]. Selain itu, GLB mempunyai dua aksioma campuran, iaitu: (tag {Monotonicity} [0] A / rightarrow [1] A) (tag {(Pi ^ 0_1) - kelengkapan} langle 0 / rangle A / rightarrow [1] langle 0 / rangle A) Logik Japaridze dapat diputuskan dan mempunyai semantik Kripke yang wajar, dan aritmetiknya baik dan lengkap sehubungan dengan Peano Arithmetic (Japaridze 1988, Boolos 1993).

Analog polimodal GLB Japaridze, bernama GLP, telah mendapat banyak perhatian dalam beberapa tahun kebelakangan ini. GLP mempunyai banyak (Box) - seperti pengendali kebolehtentuan, dilambangkan dengan kotak ([n]) untuk setiap nombor semula jadi (n), dengan operator " langle n / rangle). Sekali lagi, seseorang boleh menganggap ([0]) sebagai singkatan dari predikat kebolehpercayaan standard dalam Peano Arithmetic, (langle 1 / rangle) untuk (omega) - kebolehlaksanaan, dan lain-lain. GLP telah di aksiomatikan dengan bermula dari aksioma dan peraturan GL (lihat Bahagian 2), dirumuskan secara berasingan untuk setiap ([n]). Sebagai tambahan, GLP mempunyai tiga skema aksioma campuran, yaitu, seperti yang dirumuskan oleh 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 {untuk} m / leq n)

GLP baru-baru ini dikurniakan semantik Kripke yang mana ia lengkap, dan juga telah terbukti lengkap secara aritmetik sehubungan dengan Aritmetik Peano (lihat Beklemishev 2010a, 2011a). Sama seperti GL, masalah keputusan untuk GLP adalah PSPACE-lengkap (Shapirovsky 2008), sementara fragmen tertutupnya adalah masa polinomial yang dapat ditentukan (Pakhomov 2014).

Dalam tahun-tahun kebelakangan ini sejumlah hasil telah dibuktikan mengenai GLP polimodal logik predikat predabiliti kuat. Di sini ikuti beberapa topik yang sangat bermanfaat:

  • serpihan tertutup GLP (lihat Ignatiev 1993; Beklemishev, Joosten dan Vervoort 2005);
  • GLP dan teori bukti-bukti (Beklemishev 2004);
  • Teori interpolasi untuk GLP (lihat Beklemishev 2010b, Shamkanov 2011);
  • Hubungan antara semantik topologi dan teori set, antara lain aksioma kardinal besar dan pantulan pegun (lihat Beklemishev 2011b; Beklemishev dan Gabelaia 2013, 2014; Fernández-Duque 2014).

5.5 Predikat logik kebolehpercayaan

Akhirnya, seseorang tentu saja dapat mempelajari logik kebolehpercayaan predikat. Bahasa adalah logika predikat tanpa simbol fungsi, bersama dengan operator (Box). Di sini, keadaan menjadi jauh lebih rumit daripada logik kebolehcadangan proposisional. Sebagai permulaan, versi GL langsung yang diukur tidak mempunyai sifat titik tetap, tidak lengkap berkenaan dengan kelas bingkai Kripke mana pun, dan tidak lengkap secara aritmetik berkenaan dengan Aritmetik Peano (Montagna, 1984). Persoalannya kemudian timbul: Adakah logik kebolehpercayaan predikat aksiomatik yang baik yang memadai, yang membuktikan prinsip pembuktian yang betul? Jawapannya sayangnya tidak:Vardanyan (1986) telah membuktikan berdasarkan idea-idea oleh Artemov (1985a) bahawa kumpulan ayat logik kebolehpercayaan predikat yang kesemua realisasinya dapat dibuktikan dalam PA bahkan tidak dapat dikira secara berulang tetapi (Pi ^ 0_2) - lengkap, sehingga tidak mempunyai aksiomatisasi yang munasabah. Visser dan De Jonge (2006) menunjukkan bahawa tidak ada jalan keluar dari teorema Vardanyan dengan membuktikan generalisasi: Untuk pelbagai teori aritmetik (T), kumpulan ayat logik kebolehpercayaan predikat yang kesemuanya direalisasikan dapat dibuktikan dalam (T) ternyata (Pi ^ 0_2) - lengkap juga. Untuk pelbagai teori aritmetik (T), kumpulan ayat logik kebolehpercayaan predikat yang kesemuanya dapat dibuktikan dalam (T) ternyata juga (Pi ^ 0_2) - lengkap juga. Untuk pelbagai teori aritmetik (T), kumpulan ayat logik kebolehpercayaan predikat yang kesemuanya dapat dibuktikan dalam (T) ternyata juga (Pi ^ 0_2) - lengkap juga.

5.6 Pengitlakan lain

Tinggal dalam perbincangan di atas adalah banyak lagi bidang penting dalam logik kebolehpercayaan dan peluasannya. Pembaca yang berminat menunjukkan bidang-bidang berikut:

  • logik kebolehpercayaan aritmetik intuisi (lihat Troelstra 1973; Visser 1982, 1999; Iemhoff 2000, 2001, 2003; Visser 2002, 2008);
  • pengkelasan logik kebolehpercayaan (lihat Visser 1980, Artemov 1985b, Beklemishev 1989, Beklemishev et al. 1999);
  • Urutan Rosser dan peningkatan bukti (lihat Guaspari dan Solovay 1979, Švejdar 1983, Montagna 1992);
  • beberapa jenis logik kebolehkesanan bimodal dengan pengendali kebolehpercayaan untuk teori yang berbeza (lihat Carlson 1986; Smoryński 1985; Beklemishev 1994, 1996);
  • logik kebolehpercayaan untuk kebolehpercayaan standard digabungkan dengan predikat kebolehtentuan luar biasa yang menghitung PA secara luaran, seperti predikat prediksi Feferman dan Parikh dan predikat predabiliti perlahan (lihat Montagna 1978; Visser 1989; Shavrukov 1994; Lindström 1994, 2006; Henk dan Pakhomov 2016 (Sumber Internet Lain));
  • logik bukti eksplisit (lihat Artemov 1994, 2001; Artemov dan Montagna 1994; Artemov dan Iemhoff 2007);
  • aplikasi logik kebolehpercayaan dalam teori bukti (lihat Beklemishev 1999, 2004, 2005, 2006);
  • logik kebolehpercayaan positif dan kalkulus refleksi (lihat Beklemishev 2012, 2014; Dashkov 2012);
  • generalisasi logik kebolehpercayaan polimodal GLP, iaitu logik kebolehpercayaan dengan banyak modaliti (lihat Beklemishev et al. 2014; Fernández-Duque dan Joosten 2013a, 2013b, 2013 (Sumber Internet Lain), 2014);
  • hubungan antara logik kebolehpercayaan dan (mu) - kalkulus (lihat van Benthem 2006, Visser 2005, Alberucci dan Facchini 2009); dan
  • algebra kebolehpercayaan, juga disebut algebras boleh diagonalis atau aljabar Magari (lihat Magari 1975a, 1975b; Montagna 1979, 1980a, 1980b; Shavrukov 1993a, 1993b, 1997; Zambella 1994; untuk hasil terkini mengenai teori asas mereka, lihat Pakhomov 2012, 2014 (Internet Lain Sumber), 2015 (Sumber Internet Lain)).

Bagi pembaca yang ingin memberi sumbangan kepada bidang logik kebolehpercayaan dan generalisasinya, Beklemishev dan Visser (2006) telah mengemukakan senarai anotasi masalah terbuka yang menarik.

6. Kepentingan falsafah

Walaupun logik kebolehkesanan proposisional adalah logik modal dengan jenis pengendali "keperluan", ia menahan kritikan kontroversial Quine (1976) terhadap gagasan modal sebagai tidak dapat difahami, kerana penafsiran aritmatiknya yang jelas dan jelas. Contohnya, tidak seperti banyak logik modal lain, formula dengan modaliti bersarang seperti (Box / Diamond p / rightarrow / Box / bot) tidak bermasalah, juga tidak ada pertikaian mengenai mana yang harus menjadi tautologi. Sebenarnya, logik kebolehpercayaan merangkumi semua desiderata yang ditetapkan oleh Quine (1953) untuk rawatan modaliti sintaksis.

Anak panah utama Quine ditunjuk ke arah logika predikat modal, terutama pembinaan kalimat yang berisi operator modal di bawah ruang lingkup pengukur ("quantifying in"). Walau bagaimanapun, dalam logika kebolehpercayaan predikat, di mana pengukur berada di atas nombor semula jadi, kedua-dua moda de dicto dan de re mempunyai tafsiran langsung, bertentangan dengan logik modal lain (lihat catatan mengenai perbezaan deicto / de re). Contohnya, formula seperti

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

sama sekali tidak bermasalah. Sekiranya nombor (n) diberikan kepada (x), maka (Kotak \, / wujud y \, (y = x)) adalah benar berkenaan dengan tugasan ini jika kalimat (ada y \, (y = I_n)) dapat dibuktikan dalam Peano Arithmetic; di sini, (I_n) adalah angka (n), iaitu, istilah (bs / bs / ldots / bs 0) dengan (n) kejadian pengendali pengganti (bs). Kalimat ini berlaku untuk semua (n) dalam model standard nombor semula jadi, dan (forall x \, / Box \, / wujud y \, (y = x)) bahkan dapat dibuktikan dalam Peano Arithmetic.

By the way, Formula Barcan

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

tidak benar untuk bilangan bulat, apalagi dapat dibuktikan (misalnya, ambil untuk (A (x)) formula "(x) tidak membuat kod bukti (bot)"). Sebaliknya

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

sebaliknya, boleh dibuktikan dalam Peano Arithmetic untuk sebarang formula (A).

Logik ketersediaan mempunyai prinsip yang sangat berbeza dari logik modal lain, bahkan yang mempunyai tujuan yang nampaknya serupa. Sebagai contoh, sementara logik kebolehkesanan menangkap kebolehpercayaan dalam teori aritmetik formal, logik epistemik berusaha untuk menggambarkan pengetahuan, yang dapat dilihat sebagai sejenis kebolehpercayaan tidak formal. Dalam banyak versi logik epistemik, salah satu prinsip yang paling penting adalah aksioma kebenaran (5):

(mbox {S5} vdash / Box A / rightarrow A, (text {jika seseorang tahu} A, / text {maka} A / text {adalah benar}).)

Prinsip analog jelas tidak berlaku untuk GL: bagaimanapun, (text {if} GL / vdash / Box A / rightarrow A, / text {then} GL / vdash A.)

Oleh itu, nampaknya sesat untuk membandingkan kekuatan kedua-dua tanggapan atau menggabungkannya dalam satu sistem modal. Mungkin keterbuktian formal memang dalam arti pengertian yang lebih kuat daripada pembuktian tidak formal, tetapi pastinya ini bukan kebenaran atau kesahan aritmetik, dan juga arah lain. Perbincangan mengenai konsekuensi teorema ketidaklengkapan Gödel kadang-kadang melibatkan kekeliruan di sekitar konsep pembuktian, sehingga menimbulkan tuntutan bahawa manusia boleh mengalahkan sistem formal dalam "mengetahui" teorema (lihat Davis (1990, 1993) untuk perbincangan yang baik mengenai tuntutan tersebut).

Secara keseluruhan, kebolehpercayaan formal adalah konsep yang ditentukan dengan tepat, lebih-lebih lagi daripada kebenaran dan pengetahuan. Oleh itu, rujukan diri dalam skop kebolehpercayaan tidak membawa kepada paradoks semantik seperti Pembohong. Sebaliknya, ia membawa kepada beberapa hasil yang paling penting mengenai matematik, seperti teorema ketidaklengkapan Gödel.

Bibliografi

Rujukan umum mengenai logik kebolehpercayaan

  • Artemov, SN, 2006, "Logik Modal dalam Matematik," dalam P. Blackburn, et al. (eds.), Buku Panduan Logik Modal, Amsterdam: Elsevier, hlm. 927–970.
  • Artemov, SN dan LD Beklemishev, 2004, “Provability Logic,” dalam Handbook of Philosophical Logic, Edisi Kedua, D. Gabbay dan F. Guenthner, ed., Volume 13, Dordrecht: Kluwer, hlm. 229–403.
  • Boolos, G., 1979, The Unprovability of Consistency: An Essay in Modal Logic, Cambridge: Cambridge University Press.
  • –––, 1993, Logik Ketersediaan, New York dan Cambridge: Cambridge University Press.
  • de Jongh, DHJ dan G. Japaridze, 1998, “Logik Ketersediaan,” dalam Buku Panduan Teori Bukti, Buss, SR (ed.), Amsterdam: Belanda Utara, hlm. 475-546.
  • Lindström, P., 1996, “Logic Provability-A Short Introduction,” Theoria, 52 (1–2): 19–61.
  • Segerberg, K., 1971, Esei dalam Logik Modal Klasik, Uppsala: Filosofiska Föreningen och Filosofiska Institutionen v Uppsala Universitet.
  • Švejdar, V., 2000, “On Logability Provability,” Nordic Journal of Philosophy, 4: 95–116.
  • Smoryński, C., 1985, Rujukan Diri dan Logik Modal, New York: Springer-Verlag.
  • Verbrugge, R. 1996, “Ketersediaan” dalam The Encyclopedia of Philosophy (Tambahan), DM Borchert (ed.), New York: Simon dan Schuster MacMillan, hlm. 476–478.
  • Visser, A., 1998, “Logic Provability,” dalam Routledge Encyclopedia of Philosophy, W. Craig (ed.), London: Routledge, hlm. 793–797.

Sejarah

  • van Benthem, JFAK, 1978, "Four Paradoxes," Journal of Philosophical Logic, 7 (1): 49-72.
  • Boolos, G. dan G. Sambin, 1991, "Ketersediaan: Kemunculan Modaliti Matematik," Studia Logica, 50 (1): 1–23.
  • Gödel, K., 1933, “Eine Interpretation des intuitionistischen Aussagenkalküls,” Ergebnisse eines Mathematischen Kolloquiums, 4: 39–40; terjemahan "Interpretasi Kalkulus Propuisiistik Intuisi," dalam K. Gödel, Collected Works, S. Feferman et al. (eds.), Oxford dan New York: Oxford University Press, Jilid 1, 1986, hlm. 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., dan A. Visser, 2014, "The Henkin Sentence," dalam M. Mazano, I. Sain, dan E. Alonso (eds.), Kehidupan dan Karya Leon Henkin: Esei mengenai Sumbangannya, Dordrecht: Springer International Publishing, hlm.249–263.
  • Henkin, L., 1952, "Masalah Mengenai Ketersediaan," Jurnal Logik Simbolik, 17: 160.
  • –––., 1954, “Ulasan G. Kreisel: Mengenai Masalah Leon Henkin,” Jurnal Logik Simbolik, 19 (3): 219–220.
  • Hilbert, D. dan P. Bernays, 1939, Grundlagen der Mathematik, jilid 2, Berlin / Heidelberg / New York: Springer-Verlag.
  • Kreisel, G., 1953, “Tentang Masalah Leon Henkin,” Indagationes Mathematicae, 15: 405–406.
  • Lewis, CI, 1912, “Implikasi dan Aljabar Logik,” Pikiran, 21: 522–531.
  • Löb, MH, 1955, “Penyelesaian Masalah Leon Henkin,” Jurnal Logik Simbolik, 20: 115–118.
  • Macintyre, AJ dan H. Simmons, 1973, "Teknik Diagonalisasi Gödel dan Properti Berkaitan Teori," Colloquium Mathematicum, 28: 165-180.
  • Magari, R., 1975a, “The Diagonalizable Algebras,” Bollettino della Unione Mathematica Italiana, 12: 117–125.
  • –––, 1975b, “Representasi dan Teori Dualitas untuk Algebras Diagonalisasi,” Studia Logica, 34 (4): 305–313.
  • Smiley, TJ, 1963, “Dasar Logik Etika,” Acta Philosophica Fennica, 16: 237–246.
  • Smoryński, C., 1991, “Pengembangan Rujukan Diri: Teorema Löb,” dalam T. Drucker (ed.), Perspektif Sejarah Logik Matematik, Basel: Birkhäuser, hlm. 110–133.

Penghapusan potongan untuk logik kebolehpercayaan

  • Goré, R. dan R. Ramanayake, 2008, "Penghapusan Valentini untuk Kebolehlaksanaan Logik Diselesaikan," dalam Advances in Modal Logic Volume 7, C. Areces and R. Goldblatt (eds.), London: College Publications, pp. 67 -86.
  • Negri, S., 2005, “Analisis Bukti dalam Logik Modal,” Jurnal Logik Falsafah, 50: 507–544.
  • Negri, S., 2014, “Bukti dan Model Kontra dalam Logik Tidak Klasik,” Logica Universalis, 8 (1): 25–60.
  • Poggiolesi, F., 2009, “Kalkulus Berurutan Sintaksis dan Bebas Potong Murni untuk Logik Modal Ketersediaan,” Ulasan Logik Simbolik, 2 (4): 593–611.
  • Rautenberg, W., 1983, "Modal Tableau Calculi and Interpolation," Journal of Philosophical Logic, 12 (4): 403–423.
  • Sambin, G., dan S. Valentini, 1982, “Logik Modal Ketersediaan. Pendekatan Berurutan,”Jurnal Logik Falsafah, 11 (3): 311–342.
  • Shamkanov, DS, 2011, "Interpolation Properties for Provability Logics GL and GLP," Prosiding Steklov Institute of Mathematics, 274 (1): 303-316.
  • –––, 2014, “Bukti Pekeliling untuk Logik Kebolehlaksanaan Gödel-Löb,” Nota Matematik, 96 (4): 575–585.
  • Smoryński, C., 1978, "Beth Theorem and Self-referential Sentences," Kajian dalam Logik dan Asas-asas Matematik, 96: 253-261.
  • Valentini, S., 1983, "Logik Modal Ketersediaan: Penghapusan Potong," Jurnal Logik Falsafah, 12: 471-476.

Teorema titik tetap

  • de Jongh, DHJ, dan F. Montagna, 1988, "Titik Tetap yang Dapat Diperolehi," Logik Matematik Suku Tahunan, 34 (3): 229-250.
  • Lindström, P., 2006, “Catatan pada Beberapa Pembinaan Titik Tetap dalam Logik Kebolehlaksanaan,” Jurnal Logik Falsafah, 35 (3): 225–230.
  • Reidhaar-Olson, L., 1990, "Bukti Baru dari Teorema Titik Tetap Logik Ketersediaan," Notre Dame Journal of Formal Logic, 31 (1): 37–43.
  • Sambin, G., 1976, "Teorema Titik Tetap yang Berkesan dalam Algebras Diagonalisasi Intuisiistik (Algebraizasi Teori Yang Menyatakan Teor, IX)," Studia Logica 35: 345-336.
  • Sambin, G., dan S. Valentini, 1982, “Logik Modal Ketersediaan. Pendekatan Berurutan,”Jurnal Logik Falsafah, 11 (3): 311–342.

Semantik dunia dan semantik topologi

  • Abashidze, M., 1985, “Kelengkapan Biasa dari Sistem Modal Gödel-Löb,” (dalam bahasa Rusia) dalam Logik Intensional dan Struktur Logik Teori, Tbilisi: Metsniereba, hlm. 49–73.
  • Aiello, M., I. Pratt-Hartmann dan J. van Benthem (eds.), 2007, Buku Panduan Spatial Logics, Berlin: Springer-Verlag.
  • Beklemishev, LD 2009, “Kelengkapan Biasa Logik Ketersediaan Bimodal GLB,” Dalam Simposium Internasional Tbilisi mengenai Logik, Bahasa, dan Pengiraan, Berlin: Springer-Verlag, hlm. 1–15.
  • Beklemishev, LD, G. Bezhanishvili, dan T. Icard, 2009, "Pada Model Topologi GLP," dalam R. Schindler (ed.), Teori Cara Bukti (Logik Matematik Ontos: Jilid 2), Frankfurt: Ontos Verlag, hlm 133–153.
  • Blass, A., 1990, “Infinitary Combinatorics and Modal Logic,” Journal of Symbolic Logic, 55 (2): 761–778.
  • Esakia, L., 1981, "Diagonal Constructions, Löb's Formula and Cantor's Spattered Spaces," (dalam bahasa Rusia), dalam Studies in Logic and Semantics, Z. Mikeladze (ed.), Tbilisi: Metsniereba, hlm. 128–143.
  • –––, 2003, “Logik Intuisi dan Modalitas Melalui Topologi,” Annals of Mure and Applied Logic, 127: 155–170.
  • Goré, R., 2009, "Teori Bukti Pemeriksaan Mesin: Aplikasi Logik untuk Logik," Dalam ICLA '09: Prosiding Persidangan India ke-3 mengenai Logik dan Aplikasinya, Berlin: Springer-Verlag, hlm. 23–35.
  • Goré, R. dan J. Kelly, 2007, "Pencarian Bukti Automatik dalam Gödel-Löb Provability Logic,", British Logic Colloquium 2007, tersedia di https://www.dcs.bbk.ac.uk/~roman/blc/.
  • Hakli, R. dan S. Negri, 2012, “Adakah Teorema Pemotongan Gagal untuk Logik Modal ?,” Sintesis 187 (3): 849–867.
  • Icard, TF III, 2011, "Kajian Topologi Fragmen Tertutup GLP," Jurnal Logik dan Pengiraan, 21 (4): 683-696; pertama kali diterbitkan dalam talian 2009, doi: 10.1093 / logcom / exp043
  • Japaridze, GK, 1986, The Modal Logical Means of Investigation of Provability, Thesis in Philosophy (dalam bahasa Rusia), Moscow.
  • McKinsey, JCC dan A. Tarski, 1944, "The Algebra of Topology," Annals of Mathematics, 45: 141–191.

Ketersediaan dan Aritmetik Peano

  • Davis, M., 1958, Komputabiliti dan Ketidakselarasan, New York, McGraw-Hill; dicetak semula dengan lampiran tambahan, New York, Dover Publications 1983.
  • Feferman, S., 1960, “Arithmetization of Metamathematics in a General Setting,” Fundamenta Mathematicae, 49 (1): 35–92.
  • Hájek, P. dan P. Pudlák, 1993, Metamathematics of First-Order Arithmetic, Berlin: Springer-Verlag.
  • Solovay, RM, 1976, "Interpretasi Ketersediaan dari Logik Modal," Israel Journal of Mathematics, 25: 287-304.

Skop logik kebolehpercayaan: sempadan

  • Berarducci, A. dan R. Verbrugge, 1993, “Mengenai Logika Ketersediaan Aritmetik Terikat,” Annals of Mure and Applied Logic, 61: 75–93.
  • Buss, SR, 1986, Bounded Arithmetic, Naples: Bibliopolis.
  • de Jongh, DHJ, M. Jumelet dan F. Montagna, 1991, “Pada Bukti Teorema Solovay,” Studia Logica, 50 (1): 51–70.

Logik kebolehtafsiran

  • Berarducci, A., 1990, "The Interpretability Logic of Peano Arithmetic," Journal of Symbolic Logic, 55: 1059-1089.
  • de Jongh, DHJ, dan F. Veltman, 1990, "Logika Ketersediaan untuk Interpretasi Relatif," dalam PP Petkov (ed.), Logik Matematik: Prosiding Sekolah Musim Panas Heyting 1988 di Varna, Bulgaria, Boston: Plenum Press, pp. 31–42.
  • de Jongh, DHJ, dan A. Visser, 1991, “Titik Tetap Eksplisit dalam Logik Interpretabilitas,” Studia Logica, 50 (1): 39–49.
  • Joosten, JJ, dan Visser, A., 2000, "Logik Tafsiran dari Semua Teori Aritmetik yang Beralasan," Erkenntnis, 53 (1-2): 3–26.
  • Montagna, F., 1987, "Kebolehlaksanaan dalam Teori Terhingga PA," Jurnal Logik Simbolik, 52 (2): 494-511.
  • Shavrukov, V. Yu., 1988, "Logik Tafsiran Relatif terhadap Aritmetik Peano," Laporan Teknikal No. 5, Moscow: Institut Matematik Steklov (dalam bahasa Rusia).
  • Švejdar, V., 1983, "Analisis Modal Kalimat Rosser Umum," Jurnal Logik Simbolik, 48: 986-999.
  • Visser, A., 1990, "Interpretability Logic," dalam PP Petkov (ed.), Logik Matematik: Prosiding Sekolah Musim Panas Heyting 1988 di Varna, Bulgaria, Boston: Plenum Press, hlm. 175-209.
  • –––, 1998, “Gambaran Keseluruhan Tafsiran Logik,” dalam M. Kracht et al. (eds.), Kemajuan dalam Logik Modal (Jilid 1), Stanford: CSLI Publications, hlm. 307–359.

Pengukur cadangan

  • Artemov, SN dan LD Beklemishev, 1993, “On Propositional Quantifiers in Provability Logic,” Notre Dame Journal of Formal Logic, 34: 401–419.
  • Shavrukov, V. Yu., 1997, “Ketidaktentuan dalam Algebras Diagonalisasi,” Jurnal Logik Simbol, 62: 79–116.

Logik kebolehpercayaan bimodal dan polimodal Japaridze

  • Beklemishev, LD, 2004, "Algebras Ketersediaan dan Prinsip-Teoretik Bukti, Saya," Annals of Mure and Applied Logic, 128: 103–123.
  • –––, 2010a, “Kripke Semantics for Provability Logic GLP,” Annals of Mure and Applied Logic, 161 (6): 756–774.
  • –––, 2010b, “Mengenai Interpolasi Craig dan Properti Titik Tetap GLP,” dalam S. Feferman et al. (eds.), Bukti, Kategori dan Pengiraan (Tribut, 13), London: College Publications, hlm. 49-60.
  • –––, 2011a, “Bukti Kesederhanaan Teorema Kelengkapan Aritmetik untuk Logika Kebolehlaksanaan GLP,” Prosiding Steklov Institut Matematik, 274 (1): 25–33.
  • –––, 2011b, “Kelengkapan Biasa Logik Ketersediaan Bimodal GLB,” dalam N. Bezhanishvili et al. (eds.), Logik, Bahasa, dan Pengiraan, 8th International Tbilisi Symposium TbiLLC 2009 (Nota Kuliah dalam Sains Komputer: Jilid 6618), Heidelberg: Springer, hlm 1–15.
  • Beklemishev, LD, dan D. Gabelaia, 2013, “Kelengkapan Topologi Logika Kebolehlaksanaan GLP,” Annals of Mure and Applied Logic, 164 (12): 1201–1223.
  • –––, 2014, “Tafsiran Topologi Logik Ketersediaan,” dalam G. Bezhanishvili (ed.), Leo Esakia mengenai Dualitas dalam Logik Modal dan Intuisi (Sumbangan Luar Biasa untuk Logik: Jilid 4), Heidelberg: Springer, hlm. 257– 290.
  • Beklemishev, LD, J. Joosten dan M. Vervoort, 2005, "Rawatan Fineter terhadap Fragmen Tertutup Logika Kebolehpercayaan Japaridze," Jurnal Logik dan Pengiraan, 15 (4): 447-463.
  • Fernández-Duque, D. dan JJ Joosten, 2014, "Pesanan yang baik pada Transfinite Japaridze Algebra," Logic Journal of the IGPL, 22 (6): 933-963.
  • Ignatiev, KN, 1993, “Mengenai Predikat Ketahanan yang Kuat dan Logik Modal yang Berkaitan,” Jurnal Logik Simbolik, 58: 249–290.
  • Japaridze, G., 1988, "The Polymodal Provability Logic," In Intensional Logics and the Logical Structure of Theories: Bahan dari Simposium Soviet-Finland Keempat pada Logik, Telavi, hlm. 16-48.
  • Pakhomov, FN, 2014, “Mengenai Kerumitan Fragmen Tertutup Logika Kebolehlaksanaan Japaridze,” Arkib Logik Matematik, 53 (7-8): 949–967.

Predikat logik kebolehpercayaan

  • Artemov, SN, 1985a, "Nonarithmeticity of Truth Predicate Logics of Provability," Doklady Akademii Nauk SSSR, 284: 270-271 (dalam bahasa Rusia); Terjemahan Bahasa Inggeris dalam Soviet Matematik Doklady, 32: 403–405.
  • McGee, V. dan G. Boolos, 1987, “Tahap Himpunan Kalimat Logik Ketersediaan Predikat yang Benar di bawah Setiap Tafsiran,” Jurnal Logik Simbolik, 52: 165–171.
  • Vardanyan, VA, 1986, "Arithmetic Complexiy of Predicate Logics of Provability and Fragments mereka," Doklady Akademii Nauk SSSR, 288: 11–14 (dalam bahasa Rusia); Terjemahan Bahasa Inggeris dalam Matematik Soviet Doklady, 33: 569–572.
  • Visser, A. dan M. de Jonge, 2006, "Tidak Melarikan diri dari Teorema Vardanyan", Arkib Logik Matematik, 45 (5): 539-554.

Generalisasi lain

  • Alberucci, L., dan A. Facchini, 2009, “Pada logika Modal μ-Kalkulus dan Gödel-Löb,” Studia Logica, 91: 145–169.
  • Artemov, SN, 1985b, “On Modic Logics Axiomatizing Provability,” Izvestiya Akadademii Nauk SSSR, Seriya Matematicheskaya, 49 (6): 1123–1154 (dalam bahasa Rusia); Terjemahan Bahasa Inggeris dalam Matematik Uni Soviet – Izvestiya, 27 (3): 402–429.
  • –––, 1994, “Logic of Proofs,” Annals of Mure and Applied Logic, 67 (2): 29–59.
  • –––, 2001, “Ketersediaan Tersurat dan Semantik Konstruktif,” Buletin Logik Simbolik, 7: 1–36.
  • Artemov, SN dan R. Iemhoff, 2007, "The Intuitionistic Logic of Proofs," Jurnal Simbolik Logik, 72 (2): 439-451.
  • Artemov, SN dan F. Montagna, 1994, “On The First-order Theories with Provability Operator,” Journal of Symbolic Logic, 59 (4): 1139–1153.
  • Beklemishev, LD, 1989, "Mengenai Klasifikasi Logika Kebolehlaksanaan," Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya., 53 (5): 915–943 (dalam bahasa Rusia); Terjemahan Bahasa Inggeris dalam Matematik Uni Soviet – Izvestiya, 35 (1990) 247–275.
  • –––, 1994, “Pada Logik Bimodal Ketersediaan,” Annals of Mure and Applied Logic, 68: 115–160.
  • –––, 1996, “Logik Bimodal untuk Penyambungan Teori Aritmetik,” Jurnal Logik Simbolik, 61: 91–124.
  • –––, 1999, “Induksi Bebas Parameter dan Jumlah Fungsi yang Dapat Dikira,” Sains Komputer Teoritis, 224: 13–33.
  • –––, 2005, “Prinsip Refleksi dan Algebras Ketersediaan dalam Aritmetik Formal,” Uspekhi Matematicheskikh Nauk, 60 (2): 3–78. (dalam bahasa Rusia); Terjemahan Bahasa Inggeris dalam: Survei Matematik Rusia, 60 (2) (2005): 197–268.
  • –––, 2006, “The Worm Principle,” dalam Lecture Notes in Logic 27. Logic Colloquium ’02, Z. Chatzidakis, P. Koepke, dan W. Pohlers (eds.), Natick (MA): AK Peters, pp 75–95.
  • –––, 2012, “Mengkalibrasi Logika Kebolehlaksanaan: Dari Logik Modal ke Kalkulus Refleksi,”, dalam T. Bolander, T. Braüner, S. Ghilardi, dan L. Moss (ed.), Kemajuan dalam Logik Modal (Jilid 9), London: College Publications, hlm. 89–94.
  • –––, 2014, “Logik Ketersediaan Positif untuk Prinsip Refleksi Seragam,” Annals of Murni and Applied Logic, 165 (1): 82–105.
  • Beklemishev, LD, D. Fernández-Duque, dan JJ Joosten, 2014, "Pada Logik Ketersediaan dengan Modalitas Teratur Linear," Studia Logica, 102 (3): 541–566.
  • Beklemishev, LD, M. Pentus dan N. Vereshchagin, 1999, Ketersediaan, Kerumitan, Tatabahasa, Terjemahan Masyarakat Matematik Amerika (Siri 2, Jilid 192).
  • Beklemishev, LD dan A. Visser, 2006, "Masalah dalam Logik Ketersediaan," dalam DM Gabbay, SS Goncharov dan M. Zakharyashev (ed.), Masalah Matematik dari Logik Terapan I: Logik untuk Abad XXI (Siri Matematik Antarabangsa, Jilid 4), New York: Springer, hlm. 77–136.
  • van Benthem, J., 2006, “Coral Coralespondencies and Fixed-point Modal,” Studia Logica, 83 (1-3): 133–155.
  • Carlson, T., 1986, "Logik Modal dengan Beberapa Pengendali dan Tafsiran Ketersediaan," Israel Journal of Mathematics, 54 (1): 14–24.
  • Dashkov, EV, 2012, “Tentang Fragmen Positif Logika Kebolehlaksanaan Polimodal,” Catatan Matematik, 91 (3): 318–333.
  • Fernández-Duque, D., 2014, "The Polytopologies of Transfinite Provability Logic," Archive for Mathematical Logic, 53 (3-4): 385–431.
  • Fernández-Duque, D. dan JJ Joosten, 2013a, "Hyperations, Veblen Progressions, and Transfinite Iteration of Ordinal Functions," Annals of Pure and Applied Logic 164 (7-8): 785-801, [tersedia dalam talian].
  • Fernández-Duque, D. dan JJ Joosten, 2013b, "Model Logic Provability Transfinite," Journal of Symbolic Logic, 78 (2): 543-561, [tersedia dalam talian].
  • Guaspari, D. dan RM Solovay, 1979, “Rosser Sentences,” Annals of Mathematical Logic, 16: 81–99.
  • Iemhoff, R., 2000, "Analisis Modal dari beberapa Prinsip Logik Ketersediaan dari Aritmetik Heyting," dalam Advances in Modal Logic (Volume 2), M. Zakharyashev et al. (eds.), Stanford: CSLI Publications, hlm. 319–354.
  • –––, 2001, “Atas Peraturan yang Diterima dari Logik Proposisi Intuisi,” Jurnal Logik Simbolik, 66: 281–294.
  • –––, 2003, “Logik Preservativiti: Analog Logik Interpretabiliti untuk Teori Konstruktif,” Logik Matematik Suku Tahunan, 49 (3): 1–21.
  • Lindström, P., 1994, "Logik Modal Ketersediaan Parikh," Filosofiska Meddelanden, Gröna Serien, Gothenburg: Göteborgs Universitetet.
  • Lindström, P., 2006, “On Parikh Provability: Exercise in Modal Logic,” dalam H. Lagerlund, S. Lindström, dan R. Sliwinski (eds.), Modality Matters: Twenty-Five Essays in Honor of Krister Segerberg, Uppsala: Kajian Falsafah Uppsala (Jilid 53), hlm. 53–287.
  • Montagna, F., 1978, “Mengenai algebraizasi predikat Feferman,” Studia Logica, 37 (3): 221–236.
  • –––, 1979, “Pada Algebra Diagonalisasi Peano Arithmetic,” Bollettino della Unione Matematica Italiana, B (5), 16: 795–812.
  • –––, 1980a, “Tafsiran Teori Tertib dari Algebras Diagonalisasi dalam Aritmetik Peano,” Studia Logica, 39: 347–354.
  • –––, 1980b, “Ketidakpastian Teori Tertib Algebras Diagonalisasi,” Studia Logica, 39: 355–359.
  • –––, 1984, “Predicate Modal Logic of Provability,” Notre Dame Journal of Formal Logic, 25 (2): 179–189.
  • –––, 1992, “Bukti yang lebih pendek secara polinomial dan Superexponensial dalam Fragmen Aritmetik,” Jurnal Logik Simbolik, 57: 844–863.
  • Pakhomov, FN, 2012, "Ketidakpastian Teori Elemen Semilattice GLP-kata," Sbornik: Matematik, 203 (8): 1211.
  • Shapirovsky, I., 2008, “PSPACE-decidability of Japaridze's Polymodal Logic,” Kemajuan dalam Modal Logic, 7: 289–304.
  • Shavrukov, V. Yu., 1993a, "Catatan pada Algebras Diagonalisasi PA dan ZF," Annals of Mure and Applied Logic, 61: 161–173.
  • –––, 1993b, "Subalgebras of Diagonalizable of Algebras of Theories Yang Mengandungi Aritmetik," Dissertationes Mathematicae, 323.
  • –––, 1994, “Anak pintar dari Peano,” Notre Dame Journal of Formal Logic, 35 (2): 161–185.
  • Troelstra, AS, 1973, Metamathematical Investigation of Intuitionistic Arithmetic and Analysis, Berlin: Springer-Verlag.
  • Visser, A., 1980, Aspek Diagonalisasi dan Ketersediaan, Ph. D. Tesis, Utrecht: Universiti Utrecht.
  • –––, 1982, “Mengenai Prinsip Kesempurnaan: Kajian Ketersediaan dalam Aritmetik dan Sambungan Heyting,” Annals of Mathematical Logic, 22 (3): 263–295.
  • –––, 1989, “Anak Pintar Peano: Suatu Kajian Logik Kebolehkesanan Sistem dengan Konsistensi Built-in,” Notre Dame Journal of Formal Logic, 30 (2): 161–196.
  • –––, 1999, “Peraturan dan Aritmetik,” Notre Dame Journal of Formal Logic, 40 (1): 116–140.
  • –––, 2002, “Penggantian Kalimat (Sigma_1): Penjelajahan antara Logik Proposisi Propuisi dan Aritmetik Intuisi,” Annals of Mure and Applied Logic, 114: 227–271.
  • –––, 2005, "Logik Löb Memenuhi K-Kalkulus," dalam A. Middeldorp, V. van Oostrom, F. van Raamsdonk dan R. de Vrijer (ed.), Proses, Syarat dan Kitaran: Langkah-langkah di Jalan to Infinity, Berlin: Springer, hlm. 14–25.
  • –––, 2008, “Fragmen Tertutup dari Logika Ketersediaan Teori Konstruktif,” Jurnal Logik Simbolik, 73: 1081–1096.
  • Zambella, D., 1994, “Teorema Shavrukov pada Subalgebras Algebras Diagonalisasi untuk Teori yang Mengandungi (I / Delta_0 + / exp),” Notre Dame Journal of Formal Logic, 35: 147–157.

Kepentingan falsafah

  • Davis, M., 1990, "Adakah Algoritma Wawasan Matematik ?," Ulasan mengenai Roger Penrose, The Emperor's New Mind, Behavioural and Brain Sciences, 13: 659-660.
  • –––, 1993, "Bagaimana Halus Teorema Gödel?" (Ulasan mengenai Roger Penrose, Pikiran Baru Kaisar), Ilmu Tingkah Laku dan Otak, 16: 611-612.
  • Egré, P., 2005, “The Knower Paradox in Light of Provability Interpretations of Modal Logics,” Journal of Logic, Language, and Information, 14 (1): 13–48.
  • Kaplan, D. dan R. Montague, 1960, "Sebuah Paradoks Diperolehi," Notre Dame Journal of Formal Logic, 1 (3): 79–90.
  • Montague, R., 1963, “Perlakuan Sintaksis Modalitas, Dengan Corollaries on Reflection Principles and Finite Axiomatizability,” Acta Philosophica Fennica, 16: 153–67.
  • Quine, WV, 1966, "Nuthary Truth," dalam Quine, WV, The Ways of Paradox and Other Essays, New York: Random House, hlm. 48-56.
  • –––, 1953, “Tiga Gred Penglibatan Modal,” dalam Prosiding Kongres Falsafah Antarabangsa ke-11, Amsterdam: Belanda Utara, hlm. 65-81; dicetak semula dalam WV Quine, The Ways of Paradox and Other Essays, New York: Random House, 1966, hlm. 156–174.

Alat Akademik

ikon sep lelaki
ikon sep lelaki
Cara memetik entri ini.
ikon sep lelaki
ikon sep lelaki
Pratonton versi PDF entri ini di Friends of the SEP Society.
ikon inpho
ikon inpho
Cari topik entri ini di Projek Ontologi Falsafah Internet (InPhO).
ikon kertas phil
ikon kertas phil
Bibliografi yang dipertingkatkan untuk entri ini di PhilPapers, dengan pautan ke pangkalan data.

Sumber Internet Lain

Kertas kerja dan Pembentangan

  • Fernández-Duque, D. dan JJ Joosten, 2013, "Pentafsiran Omega-aturan Logik Ketersediaan Transfinit," manuskrip dalam talian di arxiv.org.
  • Henk, P., dan Pakhomov, F., 2016, "Ketersediaan Lambat dan Biasa untuk Aritmetik Peano," manuskrip di arxiv.org.
  • Pakhomov, F., 2014, “On Elementary Theories of GLP-algebras,” manuskrip di arxiv.org.
  • Pakhomov, F., 2015, “On Elementary Theories of Ordinal Notation Systems berdasarkan Reflection Principles,” manuskrip di arxiv.org.
  • Visser, Albert, Mengenai kebolehtentuan formal berbanding kebolehpercayaan manusia (dalam bahasa Belanda), manuskrip dalam talian, University of Utrecht.
  • Verbrugge, Rineke, Slide pembentangan mengenai logik kebolehpercayaan, slaid, University of Groningen

Laman web lain

  • Masalah terbuka dalam Provability Logic, dikendalikan oleh Lev Beklemishev
  • Senarai mel Yayasan Matematik, Universiti New York

Disyorkan: