Mengurangi produk di HoTT ke pengkodean gereja / scott

Jadi saya saat ini akan membaca buku HoTT dengan beberapa orang. Saya membuat klaim bahwa sebagian besar tipe induktif yang akan kita lihat dapat direduksi menjadi tipe yang hanya mengandung tipe fungsi dependen dan alam semesta dengan mengambil tipe recuror sebagai inspirasi untuk tipe yang setara. Saya mulai membuat sketsa bagaimana saya pikir ini akan berhasil dan setelah beberapa kali tersandung saya sampai pada apa yang saya pikir merupakan jawaban.

\cdot \times \cdot \equiv \prod_{A, B, C : U} (A \to B \to C) \to C

$\cdot \times \cdot \equiv \prod_{A, B, C : \mathcal{U}} (A \to B \to C) \to C$

(\cdot, \cdot) \equiv λ a : A . λ b : B . λ C : U . λ g : A \to B \to C . g (a) (b)

$(\cdot, \cdot) \equiv \lambda a : A. \lambda b : B. \lambda C : \mathcal{U}. \lambda g : A \to B \to C. g(a)(b)$

i n d_{A \times B} \equiv λ C . λ g . λ p . g (p r_{1} (p)) (p r_{2} (p))

$ind_{A \times B} \equiv \lambda C. \lambda g. \lambda p. g(pr_1(p))(pr_2(p))$

Ini memberikan persamaan definisi yang benar (mendefinisikan persamaan untuk dan dihilangkan) tetapi ini berarti bahwa akan memiliki tipe yang salah. $pr_1$ $pr_2$ $ind_{A \times B}$

{ind}_{A \times B} : \prod_{C : A \times B \to U} (\prod_{a : A} \prod_{b : B} C ((a, b))) \to \prod_{p : A \times B} C ((p r_{1} (p), p r_{2} (p)))

$\text{ind}_{A \times B} : \prod_{C : A \times B \to \mathcal{U}} (\prod_{a:A} \prod_{b:B} C((a, b))) \to \prod_{p : A \times B} C((pr_1(p), pr_2(p)))$

Dan sepertinya tidak ada perbaikan sederhana untuk ini. Saya juga memikirkan definisi berikut.

i n d_{A \times B} \equiv λ C . λ g . λ p . p (C (p)) (g)

$ind_{A \times B} \equiv \lambda C. \lambda g. \lambda p. p(C(p))(g)$

Tapi ini tidak cukup periksa.

$uniq_{A \times B}$ $C((pr_1(p), pr_2(p)))$ $C(p)$ $uniq_{A \times B}$ $uniq_{A \times B}$

Jadi sepertinya kita bisa mendefinisikan recursor di sini tetapi bukan induktor. Kita dapat mendefinisikan sesuatu yang cukup mirip dengan induktor tetapi tidak cukup membuatnya. Rekursi memungkinkan kita melakukan logika dengan menggunakan tipe ini sebagai makna dari konjungsi logis tetapi tidak memungkinkan kita membuktikan hal-hal tentang produk yang tampaknya kurang.

Bisakah kita membuat pengurangan yang saya klaim bisa dibuat? Yaitu, dapatkah kita mendefinisikan suatu tipe hanya menggunakan tipe fungsi dependen dan alam semesta yang memiliki fungsi pairing dan induktor dengan persamaan dan tipe mendefinisikan yang sama dengan produk? Kecurigaan saya yang semakin besar bahwa saya membuat klaim palsu. Sepertinya kita bisa sangat dekat tapi tidak cukup berhasil. Jika kita tidak dapat mendefinisikannya, argumen macam apa yang menjelaskan mengapa kita tidak bisa? Apakah produk yang disajikan dalam buku HoTT meningkatkan kekuatan sistem?

type-theory type-checking dependent-types homotopy-type-theory Jake
sumber

Sejauh yang saya mengerti, pengkodean Gereja yang biasa memberi kita jenis yang mengakui penghapusan non-dependen (recursor), tetapi tidak ada eliminasi dependen (induktor). Pertanyaan Anda bisa terkait dengan yang ini . Saya tidak yakin apakah HoTT mengubah sesuatu terkait hal ini.

chi

Ini sepertinya membantu. Seperti yang saya pahami, pertanyaan saya akan dijawab untuk jenis kalkulus prediktif konstruksi (Coq minus (co) induktif). Saya telah mencari makalah yang membahas model-model ini (model CoC yang bukan model CiC) tetapi tidak dapat menemukannya. Apakah Anda kebetulan punya sumber?

Jake

Sayangnya saya tidak punya referensi untuk dibagikan. Saya juga tertarik untuk memiliki sumber untuk mengutip fakta cerita rakyat ini.

chi

Saya juga terus mencari referensi cerita rakyat untuk fakta ini, tetapi sepertinya saya tidak dapat menemukan penjelasan.

Jake

Pertanyaan yang bagus, tetapi apakah itu tidak cocok dengan lebih baik di cstheory.stackexchange.com

Martin Berger

Jawaban:

Referensi standar yang sering saya berikan adalah Induksi tidak dapat diturunkan dalam teori tipe dependen urutan kedua oleh Herman Geuvers, yang mengatakan bahwa tidak ada tipe

N : T y p e

$N : \mathrm{Type}$

Z : N S : N \to N

$Z:N\qquad S:N\rightarrow N$

seperti yang

i n d : Π P : N \to T y p e . P Z \to (Π m : N . P m \to P (S m)) \to Π n : N . P n

$\mathrm{ind}:\Pi P:N\rightarrow \mathrm{Type}.P\ Z\rightarrow (\Pi m:N.P\ m\rightarrow P\ (S\ m))\rightarrow \Pi n:N. P\ n$

bisa dibuktikan. Ini menunjukkan bahwa memang, pengkodean seperti itu tidak dapat berfungsi untuk pasangan seperti yang Anda gambarkan.

Sistem ini terbukti adalah bagian dari Kalkulus Konstruksi, yang berisi jenis produk yang kuat dan alam semesta. Saya menduga hasil ini dapat diperluas ke sistem yang Anda minati, tergantung pada apa yang Anda miliki.

Sayangnya, saya tidak tahu jawaban lengkap untuk pertanyaan Anda. Saya menduga bahwa menambahkan prinsip-prinsip parametrik tertentu "secara internal" adalah persis apa yang diperlukan untuk membuat pengkodean ini bekerja dengan prinsip induksi penuh. Neel Krishnaswami, yang pengetahuannya adalah superset ketat saya sendiri, menulis makalah di sepanjang baris ini dengan Derek Dreyer:

Menginternalisasi Parametrisitas Relasional dalam Kalkulus Konstruksi Ekstensional

Yang juga menarik adalah makalah berikut oleh Bernardy, Jansson dan Patterson (Bernardy telah memikirkan secara mendalam tentang topik-topik ini):

Parametrik dan Jenis Ketergantungan

Jelas parametrisitas memiliki hubungan yang kuat dengan HoTT secara umum, tetapi saya tidak tahu apa detailnya. Saya pikir Steve Awodey telah mempertimbangkan pertanyaan-pertanyaan ini, karena trik penyandian berguna dalam konteks di mana kita tidak benar-benar tahu seperti apa bentuk eliminatornya.

cody
sumber

Agar ide Anda berfungsi, Anda memerlukan sesuatu yang ekstra, seperti yang ditunjukkan dalam jawaban @ cody. Sam Speight bekerja di bawah pengawasan Steve Awodey untuk melihat apa yang dapat dicapai di HoTT menggunakan semesta impredikatif , lihat Penyandian Impredikatif Jenis Induktif dalam posting blog HoTT .

Andrej Bauer
sumber