Semantik kategorikal untuk logika non-monoton?

8

Apakah ada semantik kategoris untuk logika non-monotonik?

Tampaknya jawaban sederhana untuk ini adalah "Tidak" karena gagasan jelas tentang komposisi gagal untuk model logika non-monotonik apa pun. Tetapi apakah ada model yang benar-benar berfungsi dengan gagasan komposisi yang didefinisikan dengan tepat?

ct.category-theory semantics denotational-semantics David Boshton
sumber

3

Apakah Anda bertanya apakah seseorang telah melakukannya, atau apakah itu bisa dilakukan? Tentunya itu bisa dilakukan, tetapi saya tidak tahu apakah itu sudah dilakukan. (Anda seharusnya tidak memodelkan hubungan konsekuensi sebagai hubungan sub-objek, tetapi meneruskan ke fibrasi yang lebih menarik.)

Andrej Bauer

1

Saya bertanya apakah itu bisa dilakukan. Apakah Anda memiliki referensi pada contoh fibrasi?

David Boshton

4

Logika non-monotonik adalah bidang yang luas - apakah Anda memiliki logika tertentu? Ngomong-ngomong, dengan asumsi asumsi :)

Anda tertarik pada logika apa pun di mana prinsip monoton gagal, dan
Anda ingin semantik kategoris dalam arti teori bukti kategorikal (daripada, katakanlah, semantik hyperdoctrine), maka

satu jawaban adalah bahwa Anda dapat memberikan semantik kategoris yang masuk akal untuk logika apa pun yang kalkulus berurutannya dengan eliminasi potong diketahui. Pada dasarnya, tipenya adalah objek, bentuk normal dari kalkulus berurutan adalah morfisme, dan cut-elimination memberi tahu Anda bagaimana menerapkan komposisi. Ini memberi Anda kategori awal dalam kategori model apa pun yang akhirnya Anda gunakan untuk membuktikan kesehatan dan kelengkapan.

Resep ini tidak tergantung pada monotonitas, sehingga dapat bekerja dengan baik bahkan untuk logika non-monotonik. Sebagai contoh, salah satu keberhasilan yang lebih penting dalam logika kategorikal adalah perlakuannya terhadap logika linier . Ini adalah logika di mana, secara intuitif, proposisi merujuk pada sumber daya , sehingga implikasi linear dapat dibaca sebagai " dapat dikonsumsi untuk menghasilkan ". Hubungan konsekuensi dari logika linier adalah non-monotonik (karena fakta bahwa dapat dikonsumsi untuk menghasilkan tidak berarti bahwa dan keduanya dapat dikonsumsi untuk menghasilkan $A \multimap B$ $A$ $B$ $A$ $B$ $A$ $X$ $B$ ). Namun, ia memiliki teori pembuktian yang sangat baik, dan model kategorikalnya terkait erat dengan teori kategori monoid.

Neel Krishnaswami
sumber

Meskipun, memikirkannya, saya tidak tahu harus mulai dari mana secara efektif. Apa itu kategori awal?

David Boshton

1

Ketika Anda membuktikan kesehatan dan kelengkapan, Anda mempertimbangkan koleksi model, dan kemudian menunjukkan bahwa kalkulus membuktikan dengan tepat persyaratan yang dapat dibuktikan dalam setiap model. Biasanya, Anda juga ingin mengatur koleksi model Anda ke dalam kategori juga, dengan morfisme antara model menjadi beberapa gagasan yang sesuai tentang homomorfisme model. Kemudian menunjukkan kesehatan dan kelengkapan pada dasarnya berarti menunjukkan istilah model kalkulus adalah objek awal dalam kategori model.

Neel Krishnaswami

4

[Permintaan maaf saya untuk menulis ini sebagai jawaban, meskipun pada dasarnya itu hanya komentar dari jawaban sebelumnya. Tapi saya tidak diperbolehkan memposting komentar di sana, karena saya tidak punya cukup "reputasi"]

Jawaban sebelumnya tidak benar. Logika linier (juga sistem substrukturalnya: MLL, MALL, MELL, ALL, apa pun yang Anda inginkan ...) sangat monoton .

Jawaban Neel membingungkan "relevansi" dan "non-monotonisitas".

Relevansi dapat dilihat sebagai non-monotonisitas dari konektor inferensi sistem . Logika linier relevan, dalam bahwa provability dari tidak berarti provability dari . Relevansi adalah semacam batin non-monotonisitas dari logika. $\;\vdash A \multimap B$ $\vdash X\otimes A \multimap B$

Di sisi lain, apa yang orang sebut logika non-monoton adalah sistem dimana provability sendiri dari sistem ini tidak monoton: menambahkan elemen baru ke set formula mengubah set formula dapat dibuktikan. Ini adalah bentuk meta non-monotonisitas, karena menyangkut provabilitas dan bukan penghubung kesimpulan. Logika linier adalah monoton: Anda dapat menambahkan apa pun yang Anda inginkan ke set rumus, dan setiap aksioma atau aturan inferensi baru ke sistem, tetapi jika Anda memiliki bukti dari sekuens sebelumnya, Anda akan masih memilikinya sekarang, karena Anda belum mengubah aturan inferensi lain kalkulus sekuens. $\;\Gamma \vdash M: A$

Sejauh yang saya tahu, logika non-monotonik (nyata) sulit untuk diletakkan dalam bentuk kalkulus berurutan yang menikmati pemotongan-potong, atau jenis sistem bukti lainnya dengan gagasan yang sama untuk mengakhiri pengurangan-bukti. Inilah sebabnya mengapa pendekatan semantik kategoris tradisi hampir tidak akan berhasil bagi mereka.

Domenico Ruoppolo
sumber

Semantik kategorikal untuk logika non-monoton?

Jawaban: