Dalam benang baru-baru ini di milis Agda, pertanyaan dari hukum muncul, di mana Peter Hancock membuat pemikiran komentar .
Pemahaman saya adalah bahwa undang-undang datang dengan tipe negatif, yaitu. penghubung yang aturan pengantarnya tidak bisa dibalik. Untuk menonaktifkan untuk fungsi, Hank menyarankan menggunakan eliminator yang dibuat khusus, funsplit , alih-alih aturan aplikasi yang biasa. Saya ingin memahami ucapan Hank dalam hal polaritas.
Misalnya, ada dua presentasi -jenis. Ada eliminator split Martin-Löf tradisional , dalam gaya positif:
Dan ada versi negatifnya:
Presentasi terakhir ini membuatnya mudah untuk mendapatkan untuk pasangan, yaitu. ( π 0 p , π 1 p ) = = p untuk setiap pasangan p (di mana == adalah singkatan dari kesetaraan definisi). Dalam hal provabilitas, perbedaan ini tidak masalah: secara intuisi, Anda dapat mengimplementasikan proyeksi dengan terbelah, atau sebaliknya.
Sekarang, -jenis biasanya (dan saya kira tidak kontroversial) dianggap negatif:
Yang memberi kita untuk fungsi: λ x . f x = = f .
Namun, dalam surat itu, Hank ingat eliminator funsplit (Pemrograman dalam teori tipe ML, [http://www.cse.chalmers.se/research/group/logic/book/], hal.56). Ini dijelaskan dalam kerangka logis oleh:
Menariknya, Nordstrom et al. memotivasi definisi ini dengan mengatakan bahwa "bentuk non-kanonik alternatif [ini] didasarkan pada prinsip induksi struktural". Ada aroma positif yang kuat pada pernyataan ini: fungsi akan 'didefinisikan' oleh konstruktornya, .
Namun, saya tidak bisa cukup memberikan presentasi yang memuaskan dari aturan itu dalam deduksi alami (atau, bahkan lebih baik, kalkulus berurutan). Penggunaan (ab) kerangka logis untuk memperkenalkan tampaknya sangat penting di sini.
Jadi, apakah funsplit merupakan presentasi positif -type? Apakah kita juga memiliki sesuatu yang serupa dalam kalkulus urutan (tidak tergantung)? Seperti apa bentuknya?
Seberapa umum / penasaran itu untuk pembuktian teori di lapangan?
sumber
Inilah perspektif yang sedikit berbeda pada jawaban Fredrik. Pada umumnya kasus bahwa pengkodean tipe Gereja yang tidak sesuai akan memenuhi hukum relevan , tetapi tidak akan memenuhi hukum η .β η
Jadi ini berarti kita dapat mendefinisikan pasangan dependen sebagai berikut:
Sekarang, perhatikan bahwa π 1 mudah didefinisikan: π 1 : ∃ x : X .
Namun, proyeksi kedua dapat diwujudkan , dan dalam model parametrik Anda dapat menunjukkan bahwa ia memiliki perilaku yang tepat juga. (Lihat konsep saya baru-baru ini dengan Derek Dreyer tentang parametrik dalam Kalkulus Konstruksi untuk lebih lanjut tentang ini.) Jadi saya pikir bahwa proyeksi mendasar menuntut beberapa sifat ekstensionalitas yang kuat agar masuk akal.π2
Dalam hal kalkulus berurutan, eliminator lemah memiliki aturan yang sedikit mirip:
sumber
Richard Garner telah menulis artikel yang bagus tentang aplikasi vs funsplit, Tentang kekuatan produk dependen dalam teori tipe Martin-Löf (APAL 160 (2009)), yang juga membahas sifat urutan tinggi dari aturan funsplit (dengan mengacu pada Peter Schroeder-Heister's Sebuah ekstensi alami deduksi alami (JSL 49 (1984))).
Richard menunjukkan bahwa di hadapan jenis identitas (dan aturan pembentukan dan pengenalan untukΠ jenis), funsplit dapat ditafsirkan dengan aturan aplikasi di atas + eta proposisional, yaitu dua aturan berikut:
Artinya, jika Anda memiliki funsplit, Anda dapat menentukan aplikasi danη seperti di atas supaya ( Π -Prop- η-Comp ) memegang. Lebih menarik, jika Anda memiliki aplikasi dan aturan eta proposisional, maka Anda dapat mendefinisikan funsplit.
Selain itu, funsplit benar-benar lebih kuat daripada aplikasi: aturan eta proposisional tidak dapat didefinisikan dalam teori dengan hanya aplikasi - maka funsplit tidak dapat ditentukan, karena aturan eta proposisional juga akan berlaku. Secara intuitif, ini karena aturan aplikasi memberi Anda sedikit lebih kendur: tidak seperti funsplit (dan eta), mereka tidak memberi tahu Anda apa fungsinya, hanya saja mereka dapat diterapkan pada argumen. Saya yakin argumen Richard bisa diulangiΣ jenis juga, untuk menunjukkan hasil yang sama untuk s p l i t vs proyeksi.
Perhatikan bahwa jika Anda memiliki aturan eta definisi, Anda tentu akan memilikinya secara proposisi (denganη( m ) : = r e fl (m) ). Jadi, saya pikir pernyataan Anda "[...] yang memberi kamiη untuk fungsi "dan" [...] presentasi terakhir ini membuatnya mudah diperoleh η untuk pasangan "salah. Agda, bagaimanapun, mengimplementasikan η untuk fungsi dan pasangan (jika Σ didefinisikan sebagai catatan), tetapi ini tidak mengikuti hanya dari aplikasi.
sumber