Bagian mana dari teori tipe homotopy yang tidak mungkin dalam Agda atau Coq?

16

Ketika kita melihat buku, Homotopy Type Theory - kita melihat topik-topik berikut:

Homotopy type theory 
2.1 Types are higher groupoids
2.2 Functions are functors
2.3 Type families are fibrations
2.4 Homotopies and equivalences
2.5 The higher groupoid structure of type formers
2.6 Cartesian product types
2.7 S-types
2.8 The unit type
2.9 P-types and the function extensionality axiom
2.10 Universes and the univalence axiom
2.11 Identity type
2.12 Coproducts
2.13 Natural numbers
2.14 Example: equality of structures
2.15 Universal properties

Sekarang kita tahu bahwa tidak semua teori tipe homotopy mungkin adalah Agda dan Coq .

Pertanyaan saya adalah: Bagian mana dari teori tipe homotopy yang tidak mungkin dalam Agda atau Coq?

Hawkeye
sumber
4
Bukan pertanyaan yang dirumuskan dengan sangat baik. Apa hubungan antara daftar topik dan pertanyaan?
Dave Clarke
@Dave Clarke, Daftar topik terlihat seperti konteks pikiran si penanya sehingga si penjawab tahu apa titik awal si penanya dan dapat menyesuaikan jawabannya. Pelajar lain juga dapat menghargai jawaban dalam konteks yang sama dan memahami bahwa jawabannya mungkin berguna bagi mereka jika penjawabnya bijaksana dan cerdik mengenai sifat manusia. Semoga itu juga membantu dalam percakapan lain di masa depan.
codeshot

Jawaban:

21

Jika Anda melihat Catatan pada Bab 8, Anda akan melihat apa yang sudah telah diformalkan, dan saya pikir itu banyak. Ada perpustakaan Coq HoTT dan perpustakaan Agda HoTT-Agda yang meresmikan potongan besar dari Teori Tipe Homotopy.

Untuk menyelesaikannya dalam Coq, kami membutuhkan versi khusus Coq yang ditambal hanya untuk keperluan HoTT. Namun, Coq bergerak ke arah yang mendukung teori tipe homotopy, jadi tak lama kita mungkin bisa melakukannya dengan Coq standar.

Di Agda kita harus mengaktifkan --without-Kopsi, jika tidak Agda berpikir semua tipe adalah 0-tipe. Ada beberapa keraguan yang tersisa tentang apakah --without-Kbenar-benar menghilangkan asumsi bahwa semuanya adalah 0-set, atau mungkin orang dapat memperkenalkannya kembali ke Agda dengan penggunaan pola yang cocok.

Aspek formalisasi Coq dan Agda berikut tidak memuaskan:

  1. Aksioma Univalence dinyatakan sebagai hipotesis. Akan lebih baik jika dibangun ke dalam sistem. Secara khusus kami ingin Coq dan Agda memahami aturan perhitungan tentang aksioma Univalence.

  2. Demikian juga, kita harus menggunakan peretasan untuk mendapatkan tipe induktif lebih tinggi yang bisa diterapkan. Sekali lagi, akan lebih baik untuk memiliki dukungan langsung.

Masalah dengan kekurangan di atas adalah bahwa tidak ada yang tahu bagaimana cara memperbaikinya bahkan secara teori. Ini adalah area penelitian aktif.

Selain itu, saya pikir itu adil untuk mengatakan bahwa Hott dapat akan banyak dilakukan di Coq dan Agda, hanya saja tidak dengan cara yang optimal.

Andrej Bauer
sumber
1
Terima kasih, adakah tulisan yang bagus tentang mengapa univalence dan tipe induktif yang lebih tinggi tidak cocok dengan teori tipe seperti Agda dan Coq?
Martin Berger
1
@ MartinBerger ini mungkin bisa menjadi pertanyaan terpisah (dengan beberapa definisi untuk pembaca biasa, dll).
Artem Kaznatcheev
4
Masalah dengan univalensi dan HIT bukanlah bahwa mereka "tidak menyukai teori jenis seperti Agda dan Coq" tetapi bahwa "kita tidak tahu bagaimana melakukannya dengan benar dalam teori jenis apa pun ".
Andrej Bauer
1
@AndrejBauer Univalensi dan tipe induktif yang lebih tinggi diformalkan dalam penulisan HoTT yang merupakan teori tipe (semi formal). Apa bahan yang hilang yang mencegah formalisasi yang tepat dalam Agda / Coq? Terkait, jika Anda bersedia untuk menyerahkan Curry-Howard, apakah ada kesulitan untuk menulis univalence dan tipe induktif yang lebih tinggi dalam prover gaya LCF, seperti Isabelle, menggunakan misalnya LF sebagai bahasa meta untuk memformalkan aturan bukti?
Martin Berger
4
Untuk apa aturan perhitungan ua, konstanta yang menyaksikan aksioma Univalence? Apa aturan perhitungan untuk HIT? Kami punya beberapa ide, tapi tidak ada yang kedap air.
Andrej Bauer
12

Sejauh yang saya mengerti, di Agda adalah mungkin untuk mewakili semua itu (yaitu semua Bab 2 - ada perpustakaan di github yang tidak; AFAIK, hal yang sama berlaku untuk Coq). Hanya ketika Anda sampai ke bab-bab selanjutnya hal-hal menjadi tidak pasti. Ada dua item yang jelas:

  1. Lingkaran. Ini diwakili (dalam Agda) menggunakan postulat , dan tidak sebagus hal-hal lain.
  2. -groupoids. Tetapi ini adalah masalah terbuka tentang bagaimana mewakili banyak hukum koherensi yang tak terbatas.

Ada barang-barang lain juga, tetapi saya belum sempat membaca bagian dari formalisasi Agda ... Tetapi pada umumnya, sebagian besar HoTT dapat diformalkan dengan baik dalam Agda dan Coq.

Lebih penting lagi, kedua tim pengembang secara aktif bekerja mengadaptasi sistem mereka sehingga lebih banyak HoTT dapat ditangani, setidaknya setiap kali ada teori yang jelas tentang bagaimana menerapkan fitur yang dibutuhkan. Itu ternyata menjadi bagian yang menantang.

Jacques Carette
sumber