Bagaimana cara menunjukkan bahwa suatu tipe dalam sistem dengan tipe dependen tidak dihuni (mis. Rumus tidak dapat dibuktikan)?

Untuk sistem tanpa tipe dependen, seperti sistem tipe Hindley-Milner, tipe tersebut sesuai dengan rumus logika intuitionistic. Di sana kita tahu bahwa modelnya adalah aljabar Heyting, dan khususnya, untuk menyangkal rumus, kita dapat membatasi pada satu aljabar Heyting di mana setiap rumus diwakili oleh subset terbuka dari . $\mathbb{R}$

Misalnya, jika kami ingin menunjukkan bahwa tidak dihuni, kami membuat pemetaan dari rumus untuk membuka himpunan bagian dengan mendefinisikan: Kemudian Ini menunjukkan bahwa rumus asli tidak dapat dibuktikan, karena kami memiliki model yang tidak benar, atau ekuivalen (dengan isomorfisme Curry-Howard) tipe tidak dapat dihuni. $\forall\alpha.\alpha\lor(\alpha\rightarrow\bot)$ $\phi$ $\mathbb{R}$

\begin{aligned} ϕ (α) & = (- \infty, 0) \end{aligned}

$\begin{align} \phi(\alpha) &= (-\infty, 0) \end{align}$

\begin{aligned} ϕ (α \to ⊥) & = int ([0, \infty)) \\ = (0, \infty) \\ ϕ (α \lor (α \to ⊥)) & = (- \infty, 0) \cup (0, \infty) \\ = R ∖ 0 . \end{aligned}

$\begin{align} \phi(\alpha\rightarrow\bot) &= \mbox{int}( [0, \infty) ) \\ & = (0,\infty) \\ \phi(\alpha\lor(\alpha\rightarrow\bot)) &= (-\infty, 0) \cup (0,\infty) \\ &= \mathbb{R} \setminus {0}. \end{align}$

Kemungkinan lain adalah menggunakan frame Kriepke .

Apakah ada metode serupa untuk sistem dengan tipe dependen? Seperti beberapa generalisasi aljabar Heyting atau bingkai Kripke?

Catatan: Saya tidak meminta prosedur keputusan, saya tahu tidak mungkin ada. Saya hanya meminta mekanisme yang memungkinkan untuk menyaksikan tidak dapat dibuktikannya suatu formula - untuk meyakinkan seseorang bahwa itu tidak dapat dibuktikan.

lo.logic dependent-type model-theory calculus-of-constructions Petr Pudlák
sumber

Bahwa formula tidak dapat dibuktikan pada dasarnya dapat dilakukan dengan dua cara. Dengan sedikit keberuntungan kita mungkin dapat menunjukkan dalam teori tipe bahwa formula menyiratkan formula yang sudah diketahui tidak dapat dibuktikan. Cara lain adalah menemukan model yang rumusnya tidak valid, dan ini bisa sangat sulit. Sebagai contoh, butuh waktu yang sangat lama untuk menemukan model groupoid dari teori tipe dependen, yang merupakan yang pertama untuk membatalkan keunikan bukti identitas .

Pertanyaan "apa itu model teori tipe dependen?" memiliki jawaban yang agak rumit. Jika Anda mengabaikan sifat substitusi tertentu, model adalah kategori tertutup kartesian lokal , dan itu mungkin jawaban paling sederhana. Jika Anda menginginkan model "nyata", maka ada beberapa opsi, lihat halaman nLab pada model kategorikal dari teori tipe dependen . Bagaimanapun, jawabannya selalu sedikit rumit karena teori tipe dependen adalah sistem formal yang cukup kompleks.

Jika saya menyarankan hanya satu artikel tentang masalah ini, saya mungkin akan merekomendasikan makalah asli oleh Robert Seely, "Kategori tertutup lokal dan teori jenis" . Jika saya menyarankan yang lain, itu mungkin akan menjadi salah satu yang menjelaskan apa yang perlu dikoreksi dalam makalah Seely, misalnya, Martin Hoffman "Pada Penafsiran Teori Jenis di Kategori Tertutup Cartesian Lokal" .

Kemajuan penting baru-baru ini di bidang ini adalah kesadaran bahwa model-teori homotopy juga merupakan model teori tipe dependen, lihat referensi homotopytypetheory.org . Ini memberikan banyak kemungkinan, tetapi kita sekarang harus belajar teori homotopy untuk mendapatkan model.

Andrej Bauer
sumber

Jawaban ini cukup bagus, meskipun mungkin mengabaikan cara paling sederhana untuk membuktikan bahwa jenis tidak dihuni: induksi pada bentuk normal! Secara khusus, mudah untuk membuktikan bahwa bagian tengah yang dikecualikan tidak dapat dihuni dalam Kalkulus Konstruksi dengan induksi semacam itu. Tentu saja, Anda kemudian perlu menunjukkan bahwa setiap istilah dapat dimasukkan ke dalam bentuk normal dari jenis yang sama, dan itu tidak melibatkan konstruksi model ...

cody

@cody: poin bagus, bentuk normal bisa sangat berguna.

Andrej Bauer

@cody: "maka Anda perlu menunjukkan bahwa setiap istilah dapat dimasukkan ke dalam bentuk normal dengan tipe yang sama": bukankah itu bagian standar dari metatheory untuk sistem tipe "baik" (selama Anda tidak memiliki aksioma), atau logika "baik" (di mana ini adalah penghapusan eliminasi)? Jadi Anda bisa menggunakan kembali bukti yang ada, kan?

Blaisorblade

@ Blaisorblade: tentu saja Anda hanya perlu membuktikan cut-elimination sekali. Poin yang mungkin adalah bahwa menggunakan induksi pada bentuk normal dan bukan konstruksi model adalah cara untuk mengajukan pertanyaan: Anda sudah membuat model untuk menunjukkan bahwa setiap istilah dapat dimasukkan ke dalam bentuk normal. Dalam beberapa hal Anda bekerja di "model bentuk normal", daripada melakukan pekerjaan sintaksis ketat.

cody

Saya mengerti - saya sedang memikirkan "upaya pembuktian", sementara saya kira Anda beralasan tentang bagaimana seluruh pembuktian diterapkan. Tapi Anda membuat saya mempertanyakan lagi perbedaan antara pendekatan sintaksis dan semantik, mengingat konstruksi seperti model istilah. Jadi saya mengajukan pertanyaan terpisah tentang itu: cstheory.stackexchange.com/q/21534/989

Blaisorblade

Bagaimana cara menunjukkan bahwa suatu tipe dalam sistem dengan tipe dependen tidak dihuni (mis. Rumus tidak dapat dibuktikan)?

Jawaban: