Apakah MLTT efektif pCiC tanpa Prop?

11

Adalah jenis teori Martin-LOF pada dasarnya Kalkulus predikatif dari Constructions induktif tanpa impredicative ?Prop

Jika mereka terkait erat tetapi dengan lebih banyak perbedaan dari sekedar , apa perbedaan?Prop

type-theory calculus-of-constructions pengguna
sumber
Dalam buku saya, MLTT adalah teori tipe dependen intuisi (lama dan mapan), sementara saya mengasosiasikan Kalkulus Konstruksi dengan asisten bukti Coq. Tapi saya mungkin salah.
Thomas Klimpel
1
MLTT menggunakan tipe identitas untuk menangani kesetaraan. Apa persamaan dalam fragmen predikatif CiC?
Martin Berger
2
@MartinBerger: CiC juga memiliki tipe identitas!
cody
1
Ini seperti bertanya apakah Inggris adalah UE tanpa 27 negara anggota lainnya :-)
Andrej Bauer
3
@AndrejBauer Jika saya cukup cerdas saya akan membuat lelucon singkat, tapi sayangnya saya tidak. :-P
pengguna

Jawaban:

17

Jawaban singkatnya adalah ya, MLTT dapat disamakan dengan CIC tanpa impredikatif Prop.

Masalah teknis utama adalah bahwa ada puluhan varian ketika seseorang berbicara tentang Teori Tipe Martin-Löf dan, mungkin lebih mengejutkan, ketika seseorang berbicara tentang CIC. Misalnya, dengan mengambil versi CIC yang didefinisikan dalam tesis Benjamin Werner, bahkan tidak masuk akal untuk dihapus Prop, karena seseorang tidak memiliki salah satu Setatau semesta Type.

Variasi utama yang dapat dipertimbangkan dalam salah satu dari teori ini adalah:

  1. Universes : berapa banyak, dan bagaimana mereka didefinisikan (Palmgren, On Universes dalam Type Type Theory , membahas banyak variasi yang tidak setara), dan apakah polimorfisme alam semesta diterima atau tidak .

  2. Jenis / keluarga induktif mana : Agda mengakui jenis Induktif-Rekursif, tetapi ada banyak variasi biasa tergantung pada seberapa "besar" jenis-jenis pada konstruktor dan eliminator diizinkan, menangani parameter vs indeks, dll.

  3. Suntik konstruktor tipe . Ini mengarah ke sistem yang tidak konsisten dengan EM di Agda. Tentu saja Epigram memiliki "Teori Jenis Observasional" yang lebih ekstrim, tetapi ini dapat dianggap sesuatu yang berbeda sama sekali.

  4. Aksioma K : ini tersedia secara gratis dengan versi tertentu dari pencocokan pola dependen.

  5. Γ⊢t:IdType A BΓ⊢A = B

  6. Kehadiran jenis coinductive dan prinsip eliminasi terkait.

Semua variasi di atas (kecuali OTT) telah dipertimbangkan dalam literatur dan dikaitkan dengan nama "Martin-Löf Type Theory" atau "Calculus of Inductive Constructions", terutama karena hubungannya dengan sistem Agda dan Coq.

Jadi jawaban panjangnya adalah tidak ada konsensus tentang apa definisi yang tepat dari kedua sistem ini.

cody
sumber