Hyperdoctrines dan Monadic Second Order Logic

Pertanyaan ini pada dasarnya adalah pertanyaan yang saya ajukan di Mathoverflow.

Logika Monadic Second Order (MSO) adalah logika second order dengan kuantifikasi atas predikat unary. Yaitu, kuantifikasi atas set. Ada beberapa logika MSO yang mendasar bagi struktur yang dipelajari dalam ilmu komputer.

Pertanyaan 1. Apakah ada semantik kategorikal untuk Logika Orde Kedua Monadik?

Pertanyaan 2. Perawatan logika kategorikal sering berbicara tentang "logika intuitionistic tingkat tinggi." Apakah saya benar untuk berasumsi bahwa mereka mengacu pada fungsi urutan yang lebih tinggi, daripada kuantifikasi atas predikat urutan kedua?

Pertanyaan 3. (Ditambahkan, 08 Nov 2013, setelah jawaban Neel) Pemahaman saya tentang kuantifikasi orde pertama (dalam hal penyajian Pitts yang disebutkan di bawah) adalah bahwa ia didefinisikan sehubungan dengan mundurnya dari morfisme proyeksi . Secara khusus, kuantifikasi universal ditafsirkan sebagai adjoin kanan dan kuantifikasi eksistensial ditafsirkan sebagai adjoin kiri . Adjoints ini harus memenuhi beberapa kondisi, yang kadang-kadang saya lihat disebut sebagai kondisi Beck-Chevalley dan Frobenius-Reciprocity. π π ∗ π $\pi^*$$\pi$$\pi^*$$\pi^*$

Sekarang jika kita ingin mengukur lebih dari predikat, saya berasumsi saya berada dalam kategori tertutup Cartesian, gambarnya hampir sama, kecuali bahwa bawah ini memiliki struktur yang berbeda dari sebelumnya.$X$

$$\exists_{I,X}, \forall_{I,X}: P_C(I\times X) \to P_C(I)$$

Apakah itu benar?

Saya percaya blok mental saya adalah karena saya sebelumnya berurusan dengan hyperdoctrine orde pertama dan tidak perlu kategori ditutup Cartesian dan tidak mempertimbangkannya nanti.

Latar Belakang dan Konteks. Saya telah bekerja dengan presentasi logika kategorikal oleh Andy Pitts dalam bukunya Handbook of Logic dalam artikel Ilmu Komputer , tetapi saya juga akrab dengan pengobatan teori Tripos dalam disertasi doktoralnya, serta catatan Awodey dan Bauer. Saya mulai mempelajari Crole's Categories for Types dan buku karya Lambek dan Scott, tetapi sudah lama saya tidak membaca dua teks terakhir.

Untuk motivasi, saya tertarik pada jenis logika MSO yang muncul dalam teorema di bawah ini. Saya tidak ingin berurusan dengan logika yang secara eksplisit setara dengan salah satunya. Artinya, saya tidak ingin mengkodekan predikat monadik dalam hal fungsi tingkat tinggi dan kemudian berurusan dengan logika lain, tapi saya senang mempelajari semantik yang mencakup pengkodean semacam itu di bawah tenda.

1. (Buechi dan Elgot Theorem) Ketika alam semesta struktur adalah kata-kata hingga di atas alfabet terbatas, sebuah bahasa adalah teratur jika dapat didefinisikan dalam MSO dengan predikat yang ditafsirkan untuk mengekspresikan posisi berturut-turut.
2. (Teorema Buechi) Ketika alam semesta struktur adalah kata di atas alfabet hingga, bahasa adalah teratur persis jika itu dapat didefinisikan dalam MSO dengan predikat ditafsirkan yang sesuai.$\omega$$\omega$
3. (Teorema Thatcher dan Wright) Seperangkat pohon hingga dapat dikenali oleh robot pohon terbatas bottom-up persis jika itu dapat didefinisikan dalam MSO dengan predikat yang ditafsirkan.
4. WS1S adalah teori Orde Satu Monadik Lemah dari Satu Penerus. Rumus mendefinisikan himpunan bilangan asli dan variabel urutan kedua hanya dapat diartikan sebagai himpunan terbatas. WS1S dapat diputuskan oleh automata terbatas dengan menyandikan tupel bilangan asli sebagai kata-kata terbatas.
5. (Teorema Rabin) S2S adalah teori urutan kedua dari Dua Penerus. S2S dapat diputuskan oleh Rabin automata.

1. Saya tidak tahu!

2. Tidak, anggapan Anda tidak benar. Anda dapat mengukur lebih dari fungsi tingkat tinggi dan predikat di IHOL (pada kenyataannya, predikat hanya fungsi menjadi jenis proposisi). Pengaturannya terlihat seperti ini:

   $$\begin{array}{llcl} \mbox{Sort} & \omega & ::= & \omega \to \omega \;\; | \;\; \omega \times \omega \;\; | \;\; 1 \;\;|\;\; \mathrm{prop} \;\;|\;\; \iota\\ \mbox{Term} & t & ::= & x \;\;|\;\; \lambda x.t \;\;|\;\; t\;t' \;\;|\;\; (t,t) \;\; | \;\; \pi_1(t) \;\;|\;\; \pi_2(t) \;\;|\;\; () \\ & & | & p \Rightarrow q \;\;|\;\; \top \;\;|\;\; p \wedge q \;\;|\;\; \bot \;\;|\;\; p \vee q \\ & & | & \forall x:\omega.p \;\;|\;\; \exists x:\omega.p \;\;|\;\; t =_\omega t' \\ & & | & f(\vec{t}) \end{array}$$

$\mathrm{prop}$$\iota$

$P : C^\mathrm{op} \to \mathrm{Poset}$$C$

Untuk sampai ke IHOL, Anda juga menegaskan hal itu

1. $C$
2. $C$$H$$\Gamma \in C$$\mathit{Obj}(P(\Gamma)) \simeq C(\Gamma, H)$$H$$\mathrm{prop}$$\mathrm{prop}$

$P(\Gamma)$$\Gamma$