Reaksi Logis untuk Sistem Impredikatif di MetaTheory Predikatif

Hubungan logis untuk bahasa Impredikatif seperti Sistem F tampaknya bergantung secara kritis pada impredicativitas dari logika ambient. Secara khusus, interpretasi untuk tipe forall akan didefinisikan dalam istilah semua hubungan yang diketik. Dalam sistem impredikatif (seperti CiC / Coq) itu baik, tetapi tampaknya tidak mungkin dalam sistem predikatif (seperti Agda).

Bagaimana ini bisa dilakukan? Misalnya, bagaimana Anda membuktikan normalisasi untuk Sistem F di Agda? Apakah Anda harus membangun alam semesta impredikatif Anda sendiri?

Secara umum, apa yang biasanya kita sebut argumen hubungan logis tidak benar-benar terkait dengan impredicativitas: ide utamanya adalah hanya untuk menafsirkan istilah dalam beberapa aljabar abstrak , dan untuk mewakili jenis sebagai hubungan ( n -ary) R ⊆ A n .$\cal A$$n$$R \subseteq \cal A^n$

Ini berfungsi dengan baik untuk semua jenis teori jenis, termasuk teori yang diketik secara dependen, lihat misalnya Shürmann dan Sarnat: Hubungan Struktural Logical di mana logika predikatif (bahwa Twelf) digunakan untuk membuktikan properti tertentu (decidability of equality) untuk kalkulus predikatif. (cukup ketik -kalkulus) menggunakan hubungan logis.$\lambda$

Seperti yang Anda duga, bagaimanapun, tidak mungkin untuk membuktikan normalisasi sistem F di Agda (jika Agda tidak diam-diam lebih kuat dari yang diharapkan, yaitu tentang kekuatan teori tipe Martin-Löf dengan sekelompok alam semesta). Hal ini karena normalisasi sistem F menyiratkan konsistensi urutan 2 aritmatika ( ) yang lebih kuat dari jenis teori ML dengan setiap jumlah (predikatif) alam semesta.$\mathrm{PA}_2$

Sangat membantu untuk mencari tahu di mana buktinya salah di Agda. Ini memang terjadi ketika Anda mencoba mendefinisikan interpretasi hubungan logis dari kuantifikasi impredikatif. Interpretasi dari penghubung non-impredikatif (termasuk kuantifikasi "tergantung") adalah halal dalam teori seperti Agda.