Apa peran predicativity dalam definisi induktif dalam teori tipe?

Kita sering ingin mendefinisikan objek $A \in U$ menurut beberapa aturan inferensi. Aturan-aturan menunjukkan suatu pembangkit fungsi yang, ketika itu monoton, menghasilkan titik setidaknya tetap . Kami mengambil menjadi "definisi induktif" dari . Selain itu, monotonitas memungkinkan kita untuk bernalar dengan "prinsip induksi" untuk menentukan kapan suatu set berisi (yaitu ketika sebuah properti secara universal berpegang pada ).$F$$\mu F$$A := \mu F$$A$$F$$A$$A$

Dalam Coq ini terkait dengan penulisan dari dengan istilah pengantar eksplisit. Sementara definisi ini menunjukkan fungsi tertentu , fungsi itu tidak selalu monoton. Karena itu Coq menggunakan beberapa pemeriksaan sintaksis untuk menjamin "pembentukan yang baik" dari definisi tersebut. Untuk beberapa perkiraan, ia menolak kejadian di posisi negatif dalam jenis istilah pengantar.$\mathtt{Inductive}$$A$$F$$A$

(Jika pemahaman saya sampai pada titik ini cacat, mohon koreksi saya!)

Pertama, beberapa pertanyaan dalam konteks Coq:

1) Apakah pemeriksaan sintaksis dalam Coq hanya berfungsi untuk memastikan bahwa definisi adalah predikatif ? (Jika demikian, apakah impredicativity adalah satu-satunya cara definisi tidak didefinisikan dengan baik?) Atau apakah ia memeriksa monotonitas? (Sejalan dengan itu, apakah non-monotonisitas apa yang mungkin membunuhnya?)$A$

2) Apakah seperti kejadian negatif $A$ selalu berarti bahwa $A$ definisi 's adalah impredicative / non-monoton? Atau apakah Coq tidak dapat memverifikasi bahwa itu didefinisikan dengan baik dalam kasus itu?

Dan yang lebih umum:

3) Apa hubungan antara predicativity dari definisi induktif dan monotonicity dari fungsi yang menghasilkan definisi itu? Apakah mereka dua sisi dari koin yang sama? Apakah mereka tidak berhubungan? Secara informal, mana yang lebih penting?

Tidak, dalam hal ini, predicativity dan monotonicity tidak berhubungan erat.

Pemeriksaan positif dalam Coq / Adga berfungsi untuk memastikan bahwa Anda mengambil titik yang paling tidak tetap dari hal monoton, secara kasar.

Berikut ini cara memikirkan jenis induktif dalam hal kisi dan operator monoton. Ingatlah bahwa teorema Knaster-Tarski mengatakan bahwa pada kisi lengkap , setiap operator monoton f : L → L memiliki titik tetap paling sedikit μ ( f ) . Selanjutnya, kita dapat memikirkan tipe-tipe dalam teori tipe sebagai membentuk kisi di bawah provabilitas. Artinya, ketik S di bawah T jika kebenaran S mensyaratkan bahwa dari T . Sekarang, apa yang ingin kita lakukan adalah mengambil operator monoton F pada tipe, dan menggunakan Knaster-Tarski untuk mengeluarkan interpretasi dari titik paling tidak tetap dari operator ini$L$$f : L \to L$$\mu(f)$$S$$T$$S$$T$$F$ . $\mu(F)$

Namun, tipe dalam teori tipe bukan hanya kisi: mereka membentuk kategori. Artinya, diberikan dua jenis dan T , ada potensi banyak cara untuk S berada di bawah T , dengan salah satu cara untuk setiap bukti e : S → T . Jadi operator tipe F juga harus melakukan sesuatu yang masuk akal pada bukti-bukti ini. Generalisasi monotonisitas yang tepat adalah functoriality . Artinya, kami ingin F memiliki operator pada jenis, dan juga memiliki tindakan pada bukti, sehingga jika e : S → T , maka F $S$$T$$S$$T$$e : S \to T$$F$$F$$e : S \to T$ .$F(e) : F(S) \to F(T)$

Sekarang, fungsi disimpan oleh jumlah dan produk (mis., Jika dan G adalah endofunctor pada tipe, maka F + G dan F × G (bertindak secara pointwise) juga merupakan functors pada tipe (dengan asumsi kami memiliki jumlah dan produk dalam aljabar kami dari Namun, itu tidak diawetkan oleh ruang fungsi, karena bifunctor eksponensial F → G bertentangan dalam argumen kirinya. Jadi ketika Anda menulis definisi tipe induktif, Anda mendefinisikan functor untuk mengambil titik tetap paling sedikit. Untuk memastikan itu benar-benar functor, Anda perlu mengesampingkan kemunculan parameter rekursif di sisi kiri ruang fungsi --- maka dari itu periksa positif.$F$$G$$F+G$$F\times G$$F \to G$

Impredikatif (dalam arti Sistem F) umumnya dihindari, karena itu adalah prinsip yang memaksa Anda untuk memilih antara logika klasik dan model set-theoretik. Anda tidak bisa menafsirkan tipe sebagai set dalam teori himpunan klasik jika Anda memiliki pengindeksan gaya-F. (Lihat Reynolds yang terkenal "Polimorfisme Bukan Set-Theoretik".)

Secara kategorikal, impredicativity gaya-F mengatakan bahwa kategori jenis dan istilah membentuk kategori lengkap kecil (yaitu, homs dan objek sama-sama set, dan batas semua diagram kecil ada). Klasik ini memaksa kategori untuk menjadi poset. Banyak konstruktivis yang konstruktif karena mereka ingin teorema mereka bertahan dalam lebih banyak sistem daripada sekadar logika klasik, dan karenanya mereka tidak ingin membuktikan apa pun yang secara klasik salah. Karenanya mereka curiga terhadap polimorfisme impredikatif.

Namun, polimorfisme memungkinkan Anda mengatakan banyak kondisi yang secara klasik "besar" secara internal terhadap teori tipe Anda - dan kepositifan adalah salah satunya! Operator tipe adalah functorial, jika Anda dapat menghasilkan istilah polimorfik:$F$

Lihat bagaimana ini sesuai dengan fungsi? IMO, ini akan menjadi pilihan yang sangat bagus untuk dimiliki dalam Coq, karena ini akan membuat Anda melakukan pemrograman generik jauh lebih mudah. Sifat sintaksis dari pemeriksaan positif adalah hambatan besar untuk pemrograman generik, dan saya akan senang untuk berdagang kemungkinan aksioma klasik untuk program fungsional yang lebih fleksibel.

EDIT: Pertanyaan yang Anda tanyakan tentang perbedaan antara Prop dan Set muncul dari kenyataan bahwa pengembang Coq ingin mengizinkan Anda berpikir tentang teorema Coq dalam istilah teori set-naif jika Anda mau, tanpa memaksa Anda untuk melakukannya. Secara teknis, mereka membagi Prop dan Set, dan kemudian melarang set bergantung pada konten komputasi dari Prop.

Jadi Anda bisa menafsirkan Prop sebagai nilai kebenaran dalam ZFC, yang merupakan boolean benar dan salah. Di dunia ini, semua bukti proposisi adalah sama, dan jadi jelas Anda tidak boleh menggunakan bukti proposisi. Jadi larangan set tergantung pada konten komputasi bukti Prop benar-benar masuk akal. Lebih jauh, kisi boolean 2-elemen jelas merupakan kisi yang lengkap, sehingga harus mendukung pengindeksan yang tidak tepat, karena pertemuan nilai-set yang ditentukan secara sewenang-wenang ada. Pembatasan predicativity pada Sets muncul dari fakta (yang disebutkan di atas) bahwa pengindeksan gaya-F menurun dalam model set-teoritik klasik.

Coq memiliki model lain (itu logika konstruktif!) Tetapi intinya adalah bahwa dari rak itu tidak akan pernah membuktikan apa pun bahwa seorang ahli matematika klasik akan bingung.

Ada hubungan yang sangat mendalam antara definisi induktif dan impredicativity, tetapi pemahaman saya adalah bahwa dalam konteks apa yang Anda bicarakan (im) predicativity tidak terlalu relevan dan tes ini murni untuk menjamin monotonitas, sehingga teori titik tetap dapat menjadi diterapkan, yaitu, bahwa prinsip induksi didefinisikan dengan baik. (Saya bersedia untuk diperbaiki pada titik ini.)

Hubungan antara impredicativitas dan definisi induktif dieksplorasi dalam pembicaraan oleh Coquand ini. Ini kembali ke beberapa hasil dari 50-an oleh G. Takeuti bahwa definisi impredikatif dapat direduksi menjadi definisi induktif. Buku

• Teori Bukti Subsistem Impredikatif Analisis - Monograf dan Buku Teks dalam Ilmu Fisika 2 oleh W. Buchholz, K. Schutte

memberikan analisis yang baik tentang topik tersebut, jika Anda bisa mendapatkannya. Slide ini memberikan gambaran umum.

Hanya untuk melengkapi penjelasan yang sangat bagus dari Neil, impredicativity memiliki arti "lunak": definisi set atau koleksi dengan menggunakan referensi untuk diri mereka sendiri. Dalam pengertian itu:

Inductive Lam : Set :=
| Var : Nat -> Lam
| App : Lam -> Lam -> Lam
| Abs : (Lam -> Lam) -> Lam

adalah definisi impredikatif, karena mendefinisikan jenis induktif, Lam menggunakan ruang fungsi (Lam -> Lam) yang mengacu pada koleksi itu sendiri. Dalam situasi ini, impredicativity berbahaya : adalah mungkin untuk menggunakan teorema Cantor untuk membuktikan False. Sebenarnya ini adalah merek impredicativity yang sama yang mengabaikan Teori Set naif sebagai landasan yang konsisten untuk matematika. Karena itu dilarang dalam Coq. Lain bentuk impredicativity yang diperbolehkan, karena Anda menyadari:

Definition Unit : Prop := forall X:Prop, X -> X

Definisi Unit sebagai proposisi mengacu pada pengumpulan semua Proposisi yang menjadi anggotanya. Namun, untuk alasan yang agak tidak jelas bagi saya, impredicativitas ini tidak berbahaya karena hadir di ZFC (dalam bentuk pemahaman yang tidak terikat ) yang tidak diketahui tidak konsisten.

Kesimpulannya, kejadian negatif dari tipe induktif dalam definisi adalah suatu bentuk impredicativitas, tetapi bukan yang biasa disebut ketika berbicara tentang CoC sebagai kerangka impredikatif .