Mengapa hierarki jenis yang tak terbatas?

18

Coq, Agda, dan Idris memiliki hierarki tipe tak terbatas (Tipe 1: Tipe 2: Tipe 3: ...). Tetapi mengapa tidak melakukannya seperti λC, sistem dalam lambda cube yang paling dekat dengan kalkulus konstruksi, yang hanya memiliki dua jenis, dan , dan aturan-aturan ini? $*$ $◽$

\frac{}{\emptyset ⊢ * : ◽}

$\frac {} {∅ ⊢ * : ◽}$

\frac{Γ ⊢ T_{1} : s_{1} Γ, x : T_{1} ⊢ t : T_{2}}{Γ ⊢ (λ x : T_{1}, t) : (Π x : T_{1}, T_{2})}

$\frac {Γ ⊢ T _ 1 : s _ 1 \qquad Γ, \: x : T _ 1 ⊢ t : T _ 2} {Γ ⊢ (λ \: x : T _ 1, \: t) : (Π \: x : T _ 1, \: T _ 2)}$

\frac{Γ ⊢ T_{1} : s_{1} Γ, x : T_{1} ⊢ T_{2} : s_{2}}{Γ ⊢ (Π x : T_{1}, T_{2}) : s_{2}}

$\frac {Γ ⊢ T _ 1 : s _ 1 \qquad Γ, \: x : T _ 1 ⊢ T _ 2 : s _ 2} {Γ ⊢ (Π \: x : T _ 1, \: T _ 2) : s _ 2}$

Ini sepertinya lebih sederhana. Apakah sistem ini memiliki batasan penting?

coq dependent-type calculus-of-constructions Rui Baptista
sumber

19

Sebenarnya, pendekatan CoC lebih ekspresif - itu memungkinkan kuantifikasi impredikatif sewenang-wenang. Misalnya, tipe $\forall a.\; a \to a$ dapat dipakai dengan sendirinya untuk mendapatkan $(\forall a.\; a \to a) \to (\forall a.\; a \to a)$ , yang tidak mungkin dengan hierarki semesta.

Alasan itu tidak banyak digunakan adalah karena kuantifikasi impredikatif tidak sesuai dengan logika klasik. Jika Anda memilikinya, Anda tidak dapat memberikan model teori tipe di mana jenis ditafsirkan sebagai set dengan cara naif --- lihat makalah John Reynolds yang terkenal Polymorphism is Not Set-theoretic .

Karena banyak orang ingin menggunakan teori tipe sebagai cara untuk memeriksa mesin-bukti matematika biasa, mereka umumnya tidak antusias tentang fitur-fitur teoretis yang tidak sesuai dengan fondasi yang biasa. Faktanya, Coq awalnya mendukung impredicativity, tetapi mereka terus meninggalkannya.

Neel Krishnaswami
sumber

9

Saya akan memuji jawaban Neel (luar biasa, seperti biasa) dengan sedikit penjelasan tentang mengapa level digunakan dalam praktik.

Keterbatasan penting pertama CoC adalah bahwa itu sepele! Pengamatan yang mengejutkan adalah bahwa tidak ada tipe yang dapat Anda buktikan bahwa ia memiliki lebih dari satu elemen, apalagi jumlahnya tidak terbatas. Menambahkan hanya 2 alam semesta memberi Anda bilangan alami dengan banyak elemen yang terbukti tak terhingga, dan semua tipe data "sederhana".

Keterbatasan kedua adalah aturan perhitungan: CoC hanya mendukung iterasi , yaitu fungsi recusive tidak memiliki akses ke sub-syarat argumen mereka. Untuk alasan ini, lebih mudah untuk menambahkan tipe induktif sebagai konstruksi primitif, sehingga menimbulkan CIC. Tapi sekarang masalah lain muncul: aturan induksi paling alami (disebut eliminasi dalam konteks ini) tidak konsisten dengan Excluded Middle! Masalah-masalah ini tidak muncul jika Anda membatasi aturan induksi untuk tipe predikatif dengan alam semesta.

Kesimpulannya, tampaknya CoC tidak memiliki ekspresi atau kekokohan kekokohan yang Anda inginkan dalam sistem dasar. Menambahkan alam semesta memecahkan banyak masalah ini.

cody
sumber

Apakah Anda memiliki beberapa referensi untuk batasan pertama? Jika tidak, dapatkah Anda memberi petunjuk tentang bagaimana alam semesta kedua membantu membuktikan ketidaksetaraan (proposisional? Meta?)?

Łukasz Lew

@ ŁukaszLew Sebenarnya ini adalah konsekuensi sederhana dari model "proof irrelevant", yang dapat dengan mudah di-google-kan. Dalam model itu tidak ada tipe yang memiliki lebih dari 1 elemen. Memiliki 2 semesta mencegah model itu ada. Tesis Alexandre Miquel memberikan referensi untuk jenis dengan jumlah elemen tak terbatas dengan 2 alam semesta.

cody

Mengapa hierarki jenis yang tak terbatas?

Jawaban: