Dalam buku Hott, apakah sebagian besar tipe pembentuk berlebihan? Dan jika demikian, mengapa?

Dalam bab 1 dan Lampiran A dari buku Hott , beberapa keluarga tipe primitif disajikan (tipe semesta, tipe fungsi dependen, tipe pasangan dependen, tipe Coproduct, Tipe Kosong, tipe Unit, tipe nomor alami, dan tipe identitas) untuk membentuk fondasi untuk Teori Tipe Homotopy.

Namun tampaknya diberikan jenis jagat raya, dan tipe fungsi dependen Anda dapat membangun semua tipe "primitif" lainnya. Sebagai contoh, tipe Empty dapat didefinisikan sebagai

ΠT:U.T

Saya berasumsi tipe-tipe lain juga dapat dibangun mirip dengan bagaimana mereka berada dalam CC murni , (yaitu hanya mengambil tipe dari bagian induktif dari definisi).

Banyak dari tipe-tipe ini secara eksplisit dibuat berlebihan oleh tipe Inductive / W yang diperkenalkan pada bab 5 dan 6. Tetapi tipe Inductive / W tampaknya menjadi bagian opsional dari teori ini karena ada pertanyaan terbuka tentang bagaimana mereka berinteraksi dengan HoTT (di Setidaknya pada saat buku itu keluar).

Jadi saya sangat bingung mengapa tipe tambahan ini disajikan sebagai primitif. Intuisi saya adalah bahwa teori dasar harus seminimal mungkin, dan mendefinisikan ulang tipe Kosong yang berlebihan sebagai primitif ke dalam teori itu tampak sangat sewenang-wenang.

Apakah pilihan ini dibuat

untuk beberapa alasan metatheoretik yang tidak saya sadari?
untuk alasan historis, untuk membuat teori jenis terlihat seperti teori tipe masa lalu (yang tidak selalu berusaha menjadi dasar)?
untuk "kegunaan" antarmuka komputer?
untuk beberapa keuntungan dalam pencarian bukti yang tidak saya sadari?

Mirip dengan: Spesifikasi minimal teori tipe Martin-Löf , /cs/82810/reducing-products-in-hott-to-church-scott-encodings/82891#82891

type-theory dependent-type homotopy-type-theory pengguna833970
sumber

Mereka berlebihan, tetapi tidak dengan cara yang Anda sarankan. Anda harus bertanya pada diri sendiri apa tujuan melayani "minimalitas yayasan"? Dan apakah kita peduli dengan tujuannya?

Andrej Bauer

Saya berasumsi pekerjaan teknis minimal dengan konvensi, di mana segala sesuatunya tidak perlu minimal jika jelas nyaman atau secara eksplisit dicatat sebaliknya. Buku ini bahkan menganut hal ini di tempat lain, seperti ketika mendefinisikan jenis pemotongan (ditentukan oleh aturan, tetapi secara eksplisit tidak minimal). Misalnya, jika saya melihat nats yang didefinisikan dalam 0,1,10, penerus dan operasi daya, saya akan bingung, tetapi setidaknya saya bisa melihat mengapa itu nyaman secara nasional. Hott adalah bidang studi yang jauh lebih kompleks dan saya ingin tahu apakah saya kehilangan sesuatu yang jelas.

user833970

Saya akan sangat tertarik mendengar tentang bagaimana mereka bisa berbahaya. Haruskah saya membuat pertanyaan baru tentang itu?

user833970

@AndrejBauer Saya ingin tahu mengapa mereka juga berbahaya. Alasan saya untuk percaya bahwa bahasa dasar harus minimal adalah alasan di balik pisau cukur Occam, itu adalah kompleksitas tambahan yang tidak dapat dibenarkan. Kenapa berhenti di situ? Mengapa tidak menambahkan juga daftar, string, pasangan, tiga kali lipat, vektor? Itu tampaknya pilihan yang sewenang-wenang, apa yang membenarkan mereka? Sunting: Saya baru saja memperhatikan pertanyaan ini memiliki jawaban; tetapi saya akan meninggalkan komentar ini di sini hanya untuk mencatat mengapa saya juga tertarik pada hal itu.

MaiaVictor

Saya akan menulis posting blog.

Andrej Bauer

Jawaban:

Izinkan saya menjelaskan mengapa pengodean yang disarankan untuk tipe kosong tidak berfungsi. Kita perlu secara eksplisit tentang tingkat alam semesta dan tidak menyapu mereka di bawah karpet.

Ketika orang mengatakan "tipe kosong", mereka mungkin berarti satu dari dua hal:

Sebuah tunggal jenis yang kosong terhadap semua jenis. Tipe seperti itu memiliki aturan eliminasi: untuk setiap dan tipe keluarga $E$ $n$ , ada peta . $A : E \to U_n$ $e_{n,A} : E \to A$
Sebuah keluarga jenis , satu untuk setiap tingkat alam semesta , sehingga adalah "jenis kosong ". Seperti jenis harus memuaskan , jelas, dan juga: untuk setiap jenis keluarga $E_k$ $k$ $E_k$ $U_k$ $E_k : U_k$ $A : E_{k} \to U_k$ , ada peta . $e_{k,A} : E_{k} \to A$

Tanpa ketentuan apa pun, ketika orang mengatakan "tipe kosong" mereka mengharapkan makna pertama di atas.

Bagaimana kita bisa mendapatkan ? Percobaan pertama bisa berupa $E$ tapi ini justru semacam menyapu di bawah karpet yang menciptakan kebingungan. Kita harus menuliskan level alam semesta eksplisit. Jika kita menulis sesuatu seperti

E = Π (T : U) . T

$E = \Pi (T : U) \,.\, T$

maka kita mendapatkan urutan tipe

, satu untuk setiap level

. Kita mungkin berharap bahwa urutan ini adalah jenis kosong dalam arti di atas, tetapi tidak, karena

E_{k} = Π (T : U_{k}) . T

$E_k = \Pi (T : U_k) \,.\, T$

E_{0}, E_{1}, E_{2}, \dots

$E_0, E_1, E_2, \ldots$

k

$k$

E_{k}

$E_k$ adalah di

tetapi seharusnya di

U_{k + 1}

$U_{k+1}$

U_{k}

$U_k$

Percobaan lain adalah tetapi sekarang Anda harus menjelaskan apa yang seharusnya " ". Anda mungkin tergoda untuk mengatakan bahwa ada suatu tipe

E = Π n . Π (T : U_{n}) . T

$E = \Pi n \,.\,\Pi (T : U_{n}) \,.\, T$

Π n

$\Pi n$

tingkat semesta, dan karenanya

L

$L$

E = Π (n : L) . Π (T : U_{n}) . T

$E = \Pi (n : L) \,.\,\Pi (T : U_{n}) \,.\, T$ Anda sekarang telah jatuh ke dalam perangkap, karena saya akan bertanya: di alam semesta mana

hidup? Dan di alam semesta mana

hidup? Ini tidak akan berhasil.

E

$E$

L

$L$

Ada solusi, yang dikenal sebagai alam semesta impredikatif . Ini adalah alam semesta ajaib yang memiliki sifat yang, mengingat , tipe tinggal di (dan tidak satu tingkat lebih tinggi dari ). Maka setidaknya lagi dalam , dan akan memiliki eliminator yang diharapkan. Tapi kami masih belum selesai, karena sekarang kami harus khawatir tentang persamaan untuk eliminator, seperti yang ditunjukkan oleh Neel. $U$ $B : U \to U$ $\Pi (X : U) B(X)$ $U$ $U$ $\Pi (X : U) X$ $U$

Alam semesta yang tidak bermoral dapat diatur. Namun, sebuah teorema Thierry Coquand yang terkenal (jika saya tidak salah), menunjukkan bahwa memiliki dua alam semesta yang impredikatif, yang satu mengandung di alam semesta yang lain, mengarah pada kontradiksi.

Moral dari cerita ini adalah: hanya aksioma tipe kosong secara langsung dan berhenti menyandikan sesuatu.

Andrej Bauer
sumber

Itu adalah alasan yang meyakinkan untuk membuat aksioma tipe kosong, tapi saya masih ingin tahu tentang alasan untuk melakukan aksioma semua hal yang lebih berat.

MaiaVictor

@MaiaVictor: berbeda dengan apa?

Andrej Bauer

Maaf? Maksud saya, Anda secara meyakinkan membenarkan mengapa itu adalah ide yang baik untuk membuat aksioma tipe kosong pada khususnya. Tetapi OP juga bertanya tentang hal-hal lain: "tipe alam semesta, tipe fungsi dependen, tipe pasangan dependen, tipe Coproduct, Tipe Kosong, tipe Unit, tipe nomor alami, dan tipe identitas" (yang saya asumsikan juga primitif pada sistem yang diusulkan pada Buku HoTT). (Saya jelas tidak meminta Anda untuk membenarkan semua itu, hanya mewujudkan minat saya.)

MaiaVictor

1 = \prod_{X : U} (X \to X)

$\mathbb{1} = \prod_{X : U} (X \to X)$

@IngoBlechschmidt penasaran ingin mengetahui masalah seperti apa! Terlihat bagus untuk saya ...

MaiaVictor

Anda mengajukan beberapa pertanyaan yang serupa tetapi berbeda.

Mengapa buku HoTT tidak menggunakan pengkodean Gereja untuk tipe data?

Pengkodean gereja tidak berfungsi dalam teori tipe Martin-Löf, karena dua alasan.

$n$ $k < n$

Kedua, bahkan jika Anda mendefinisikan tipe data seperti angka alami dengan pengkodean Gereja, untuk melakukan pembuktian dengan tipe-tipe ini, Anda memerlukan prinsip - prinsip induksi untuk membuktikan hal-hal tentang mereka. Untuk mendapatkan prinsip-prinsip induksi untuk pengkodean Gereja, Anda perlu menggunakan argumen berdasarkan parametrikitas Reynolds, dan pertanyaan tentang bagaimana menginternalisasi prinsip-prinsip parametrik ke dalam teori tipe masih belum sepenuhnya diselesaikan. (Keadaan saat ini adalah makalah Nuyts, Vezzosi, dan Devriese ICFP 2017 Parametrik Kuantitatif untuk Teori Jenis Ketergantungan - perhatikan bahwa ini baik setelah buku HoTT ditulis!)
Selanjutnya, Anda bertanya mengapa fondasinya tidak minimal. Ini sebenarnya adalah salah satu fitur sosiologis khas yayasan tipe-teoretik - tipe teori menganggap memiliki seperangkat aturan kecil sebagai kenyamanan teknis, tanpa signifikansi mendasar banyak. Ini jauh, jauh lebih penting untuk memiliki hak seperangkat aturan, daripada terkecil seperangkat aturan.

Kami mengembangkan teori tipe yang akan digunakan oleh matematikawan dan programmer, dan itu sangat, sangat penting bahwa bukti yang dilakukan dalam teori tipe adalah yang menurut matematikawan dan programmer dilakukan dengan cara yang benar. Ini karena argumen matematikawan biasanya menganggap memiliki gaya yang baik biasanya terstruktur menggunakan prinsip-prinsip aljabar dan geometri kunci dari domain studi. Jika Anda harus menggunakan penyandian yang rumit maka banyak struktur yang hilang atau dikaburkan.

Inilah sebabnya mengapa presentasi tipe-teoretis dari logika klasik proposisional selalu memberikan semua penghubung logis, meskipun secara formal setara dengan logika hanya dengan NAND. Tentu, semua penghubung boolean dapat dikodekan dengan NAND, tetapi pengkodean itu mengaburkan struktur logika.

Neel Krishnaswami
sumber

Terima kasih atas jawaban ini! Saya harus membaca makalah itu (dan kertas Anda) dan mungkin lebih masuk akal. Tapi, saya pikir hierarki alam semesta dirancang agar terlihat seperti Anda dapat melakukan hal-hal predikatif: misalnya (λA: U.λa: Aa) (ΠA: UA → A) akan di-desugar ke (λA: Un + 1.λa: Aa) (ΠA: Un.A → A). Saya pikir itu adalah pilihan editorial yang aneh untuk tidak menjelaskan ini, setiap buku logika yang saya tahu menunjukkan beberapa pengkodean yang lebih minimal seperti CNF, DNF, NAND dan sebagainya. Dan siapa pun yang terbiasa menetapkan teori mengharapkan pengkodean Nats yang "alami", untuk menunjukkan teorinya. Tapi itu mungkin saja bias klasik saya.

user833970

yang seharusnya "impredikatif" dalam komentar terakhir saya

user833970

\prod (T : U_{n}) . T

$\prod (T : U_n) . T$

U_{n}

$U_n$

U_{n + 1}

$U_{n+1}$

U_{n}

$U_n$

Mungkin saya salah paham tentang hierarki alam semesta. Saya berpikir bahwa kita tidak pernah peduli di mana jenis Semesta tertentu berada, hanya nomor alam semesta yang dapat ditetapkan ketika kita ingin memverifikasi suatu bukti. Jadi secara teknis ΠT: UT adalah keluarga jenis yang diindeks di atas alam semesta. Sama seperti identitas polimorfik adalah keluarga jenis diindeks di atas alam semesta. Tapi bukankah kita memiliki masalah yang sama dengan identitas polimorfik? Saya akan sangat menghargai jika Anda dapat memperluas 2 kalimat terakhir, saya rasa saya tidak mengerti.

user833970

Ketika Anda mengatakan bahwa itu tidak memiliki sifat eliminasi yang tepat maksud Anda bahwa begitu alam semesta diperbaiki ada jenis di alam semesta yang lebih tinggi yang tidak dapat secara langsung disintesis dengan istilah termT: Un.T?

user833970