Teknik untuk menunjukkan non-derivasi dalam logika dan sistem bukti formal lainnya

Dalam sistem pembuktian untuk logika proposisional klasik jika seseorang ingin menunjukkan bahwa formula tertentu tidak dapat diturunkan, hanya menunjukkan bahwa dapat diturunkan (walaupun teknik lain tentu saja mungkin). Non-derivabilitas pada dasarnya mengikuti dari kesehatan dan kelengkapan sistem bukti. $\psi$ $\neg\psi$

Sayangnya untuk logika non-klasik dan sistem bukti yang lebih eksotis (seperti aturan yang mendasari semantik operasional) tidak ada teknik langsung semacam itu. Ini bisa jadi karena non-derivabilitas tidak menyiratkan bahwa dapat diturunkan, seperti halnya dengan logika intuitionistic, atau hanya bahwa tidak ada gagasan negasi. $\psi$ $\neg\psi$

Pertanyaan saya diberikan sistem bukti , di mana $(\mathcal{L},\vdash)$ , (dan mungkin semantiknya), teknik apa yang ada untuk menunjukkan non-derivasi? $\vdash\;\subseteq\mathcal{L}^*\times\mathcal{L}$

Sistem bukti kepentingan dapat mencakup semantik operasional bahasa pemrograman, logika Hoare, sistem tipe, logika non-klasik, atau aturan inferensi untuk apa yang Anda miliki.

lo.logic Dave Clarke
sumber

Dave, saya pikir ada salah ketik dalam pertanyaan, untuk menunjukkan bahwa

tidak dapat diturunkan, kami tidak menunjukkan bahwa

dapat diturunkan, kami hanya menunjukkan bahwa itu konsisten, dan ini hanya didasarkan pada konsistensi logika klasik. Jika logikanya adalah logika klasik orde pertama, maka ada kalimat-kalimat yang tidak dapat kita buktikan atau bantah (kecuali kita berbicara tentang teori yang lengkap ). Atau apakah saya salah membaca pertanyaan Anda?

φ

$\varphi$

\neg φ

$\lnot \varphi$

Kaveh

Saya mengubahnya menjadi logika proposisional klasik. Pertanyaannya menanyakan teknik apa pun selain membuktikan negasi, karena banyak sistem formal (koleksi aksioma dan aturan inferensi) tidak memiliki negasi, atau bahkan mungkin tidak terlihat seperti "logika".

Dave Clarke

Terima kasih atas klarifikasi, pikiran saya beralih ke logika tingkat pertama secara default ketika saya membaca logika klasik. :)

Kaveh

Jawaban:

IME, daftar berikut ini paling mudah hingga yang paling sulit (tentu saja, itu juga paling tidak paling kuat):

$\lnot \phi$
Jika Anda memiliki semantik-teori kisi untuk logika Anda, relatif terhadap semua aturan pembuktian Anda yang valid, maka jika makna proposisi bukanlah elemen paling atas dari kisi, maka itu bukan proposisi yang dapat diturunkan.
$\phi$
Kadang-kadang Anda bisa lolos dengan terjemahan ke logika lain, dan menunjukkan bahwa turunan di sini menyiratkan hasil nonderivabilitas yang dikenal di sana.
Jika Anda memiliki deduksi alami atau kalkulus berurutan, periksa untuk melihat apakah ada hasil eliminasi potong yang diketahui, atau jika Anda dapat membuktikannya. Jika ada, maka Anda sering dapat mengeksploitasi properti subformula untuk memberikan argumen induktif sederhana tentang nonderivability. (Mis., Konsistensi melalui cut-eliminasi hanya pernyataan bahwa tidak ada bukti cut-free yang salah, dan jadi jika semua pemotongan dapat dihilangkan maka tidak ada inkonsistensi.)
Jika tidak ada yang berfungsi, maka Anda sering dapat menunjukkan hasil konsistensi / nonderivabilitas melalui argumen hubungan logis. Ini adalah senjata besar, yang bekerja ketika tidak ada yang lain - dalam istilah set-theoretic, itu bermuara pada penggunaan aksioma Penggantian, yang memungkinkan Anda menunjukkan set besar dipesan dengan baik. (Inilah sebabnya Anda dapat menggunakannya untuk membuktikan hal-hal seperti normalisasi Sistem F.)

Neel Krishnaswami
sumber

F

$F$

P A^{2}

$PA^2$

F^{2}

$F^2$

Terima kasih, sekarang saya mengerti apa yang Anda maksud dengan "hal-hal seperti normalisasi Sistem F". :)

Kaveh

@ Kaveh, @Neel: Normalisasi yang kuat dari sistem F bukan teorema PA2, melainkan setara dengan PA dengan konsistensi PA2. Alih-alih, normalisasi yang kuat untuk semua syarat peringkat n (peringkat menjadi ukuran kedalaman maxiumum dari tipe penjelajah nsted) dapat dibuktikan menggunakan ACA- n . Saya suka berbicara tentang membangun model kulit domba secara rahasia ...

Charles Stewart

@ Charles: Saya belajar tentang ide ini dari beberapa makalah Jean Gallier, yang secara mengejutkan kurang dikutip. Agak aneh, pandangan mewah ini membantu saya memahami akun sederhana Mitchell & Scedrov.

Neel Krishnaswami