Cut-eliminasi untuk kalkulus dengan nats atau tipe data induktif lainnya?

14

Apakah ada yang mengarahkan saya ke sebuah makalah yang merinci teorema cut-eliminasi untuk logika intuitionistic proposisional, termasuk tipe data induktif seperti bilangan alami (daftar atau pohon juga akan baik-baik saja)? Contoh dari jenis sistem yang saya minati adalah Godel's T, yang memiliki tipe yang diberikan oleh tata bahasa . Saya tidak terlalu tertarik pada bilangan bulat atas bilangan asli atau predikat yang diindeks oleh bilangan alami.SEBUAH:: =N|SEBUAHSEBUAH

Saya tahu bagaimana membuktikan beta-normalisasi untuk versi deduksi alami dari sistem ini menggunakan argumen hubungan logis (atau teknik terkait seperti NbE), tetapi ingin tahu apakah ada referensi standar tentang cara menyesuaikan metode ini ke sekuens kalkuli.

Alasan saya bertanya adalah bahwa saya sedang belajar menambahkan operator titik tetap untuk rekursi yang dijaga ke suatu bahasa. Ide denotasional agak lama - menafsirkan tipe sebagai ruang ultrametrik dan titik tetap melalui teorema Banach - tetapi teknik sintaksis murni yang saya tahu untuk membuktikan cut-elimination tampaknya tidak beradaptasi dengan baik.

Neel Krishnaswami
sumber

Jawaban:

10

Bagaimana dengan pekerjaan Ulrich Berger? Misalnya Normalisasi yang kuat untuk kalkulus lambda yang diterapkan . Bagian "konstanta yang didefinisikan secara rekursif" memberi Anda tipe induktif, lebih atau kurang. Dan jangan tertunda oleh kata "untyped", dia mendapatkan hasil untuk sistem yang diketik juga.

Andrej Bauer
sumber
Ini ide yang sangat menarik! Saya tertarik untuk menambahkan (misalnya) konstanta untuk titik-titik tertentu yang tidak harus kiri-atau-aturan, jadi ini sepertinya tempat yang bagus untuk mencari.
Neel Krishnaswami
10

Anda bisa melihat McDowell dan Miller Cut-Elimination untuk Logika dengan Definisi dan Induksi , yang menunjukkan bagaimana mengadopsi metode Tait ke kalkulus sekuens intuitionistic orde pertama dengan predikat bilangan alami yang ditentukan secara induktif.

Noam Zeilberger
sumber
Terima kasih - saya membaca makalah ini beberapa waktu yang lalu, tetapi lupa tentang itu. Saya akan melihat lagi.
Neel Krishnaswami