Apakah path induction konstruktif?

17

Saya membaca buku HoTT dan mengalami kesulitan dengan induksi jalur.

Ketika saya melihat jenis di bagian 1.12.1 : saya tidak punya masalah memahami apa artinya (saya baru saja menulis jenis dari memori, untuk memeriksa itu).

{ind}_{=_{SEBUAH}} : \prod_{C : \prod_{x, y : SEBUAH} (x =_{SEBUAH} y) \to U} ((\prod_{x : SEBUAH} C (x, x, {refl}_{x})) \to \prod_{x, y : SEBUAH} \prod_{hal : x =_{SEBUAH} y} C (x, y, hal)),

$\text{ind}_{=_A}:\prod_{C:\prod\limits_{x,y:A}(x=_Ay)\to \mathcal{U}} \left( \left(\prod_{x:A}C(x,x,\text{refl}_x)\right) \to \prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p) \right),$

Apa yang saya punya masalah adalah pernyataan selanjutnya: kesan pertama saya adalah bahwa ekspresi terakhir ini tidak mendefinisikan fungsi yang dihasilkan tetapi hanya menyatakannya properti .

dengan kesetaraan {ind}_{=_{SEBUAH}} (C, c, x, x, {refl}_{x}) : \equiv c (x)

$\text{with the equality}\quad \text{ind}_{=_A}(C,c,x,x,\text{refl}_x):\equiv c(x)$

f : \prod_{x, y : SEBUAH} \prod_{hal : x =_{SEBUAH} y} C (x, y, hal),

$f:\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p),$

Itu berbeda dengan contoh sebelumnya dari prinsip-prinsip induksi $\text{ind}_{A\times B}$ , $\text{ind}_{A+B}$ atau $\text{ind}_\mathbb{N}$ - ada yang mendefinisikan persamaan untuk unsur-unsur - kita benar-benar tahu bagaimana membangun fungsi yang dihasilkan, diberikan tempat. Yang sesuai dengan "konstruktif" teori tipe yang diiklankan di seluruh bab ini.

Kembali ke $\text{ind}_{=_A}$ , saya curiga dengan fakta bahwa (sepertinya) itu tidak didefinisikan. Menyatakan bahwa elemen $f$ hanya ada sepertinya tidak selaras dengan sisa bab ini. Dan memang, bagian 1.12.1 tampaknya menekankan bahwa kesan saya salah dan kita sebenarnya telah mendefinisikannya

... yang fungsi $f:\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p),$ didefinisikan oleh
jalur induksi dari $c:\prod_{x:A}C(x,x,\text{refl}_x)$ , yang juga
memenuhi $f(x,x,\text{refl}_x):\equiv c(x)$ ...

Itu membuat saya benar-benar bingung, tetapi saya merasa bahwa poin ini sangat penting untuk semua perkembangan selanjutnya. Jadi mana dari dua bacaan untuk harus saya ikuti? Atau, mungkin, saya kehilangan beberapa kehalusan penting dan jawabannya adalah "tidak"? $\text{ind}_{=_A}$

induction dependent-types homotopy-type-theory Kostya
sumber

Ngomong-ngomong, ini sebenarnya bukan pertanyaan khusus HoTT, tetapi pertanyaan "jenis ketergantungan" yang lebih umum.

cody

12

Adalah ilusi bahwa aturan perhitungan "mendefinisikan" atau "membangun" objek yang mereka bicarakan. Anda benar mengamati bahwa persamaan untuk tidak "mendefinisikan" itu, tetapi gagal untuk mengamati bahwa hal yang sama juga berlaku dalam kasus lain. Mari kita perhatikan prinsip induksi untuk unit tipe , yang tampaknya sangat "ditentukan". Menurut Bagian 1.5 dari buku Hott kita memiliki $\mathrm{ind}_{=_A}$ $1$ dengan persamaan Apakah ini "menentukan" atau "membangun" dalam arti bahwa ia meninggalkan diragukan lagi seperti apa "tidak"? Misalnya, atur dan , dan pertimbangkan apa yang bisa kami katakan tentang

{i n d}_{1} : \prod_{C : 1 \to T y p e} C (⋆) \to \prod_{x : 1} P (x)

$\mathrm{ind}_1 : \prod_{C : 1 \to \mathtt{Type}} C(\star) \to \prod_{x : 1} P(x)$

{i n d}_{1} (C, c, ⋆) = c .

$\mathrm{ind}_1 (C, c, \star) = c.$

{i n d}_{1}

$\mathrm{ind}_1$

{i n d}_{1}

$\mathrm{ind}_1$

C (x) = N

$C(x) = \mathbb{N}$

a = 42

$a = 42$

untuk ekspresi yang diberikan

tipe

. Pikiran pertama Anda mungkin bahwa kita dapat mengurangi ini menjadi

karena "

adalah satu-satunya elemen

". Tetapi untuk menjadi cukup tepat, persamaan untuk

hanya berlaku jika kita menunjukkan

, yang tidak mungkin bila

adalah variabel, misalnya. Kita dapat mencoba untuk menggoyangkan keluar dari ini dan mengatakan bahwa kita hanya tertarik perhitungan dengan istilah tertutup, sehingga

harus ditutup.

{i n d}_{1} (C, 42, e)

$\mathrm{ind}_1(C, 42, e)$

e

$e$

1

$1$

42

$42$

⋆

$\star$

1

$1$

{i n d}_{1}

$\mathrm{ind}_1$

e \equiv ⋆

$e \equiv \star$

e

$e$

e

$e$

Apakah tidak terjadi bahwa setiap jangka tertutup tipe adalah judgmentally sama dengan ? Itu sebenarnya tergantung pada detail yang tidak jelas dan bukti normalisasi yang rumit. Dalam kasus Hott jawabannya adalah "tidak" karena bisa berisi contoh dari Univalence Aksioma, dan tidak jelas apa yang lakukan untuk hal itu (ini yang masalah terbuka di Hott). $e$ $1$ $\star$ $e$

Kita dapat menghindari masalah dengan univalance dengan mempertimbangkan versi teori tipe yang memang memiliki sifat yang baik sehingga setiap istilah tertutup tipe secara hukum sama dengan . Dalam hal bahwa itu adalah adil untuk mengatakan bahwa kita tidak tahu bagaimana menghitung dengan , namun: $1$ $\star$ $\mathrm{ind}_1$

Hal yang sama akan berlaku untuk jenis identitas, karena setiap jangka tertutup jenis identitas akan judgmentally sama untuk beberapa , dan kemudian persamaan untuk akan memberitahu kita bagaimana untuk menghitung. $\mathrm{refl}(a)$ $\mathrm{ind}_{=_A}$
Hanya karena kita tahu bagaimana cara menghitung dengan istilah tertutup dari suatu jenis, itu tidak berarti kita benar-benar telah mendefinisikan apa pun karena ada lebih banyak jenis daripada istilah tertutupnya , seperti yang saya coba jelaskan sekali.

Sebagai contoh, ketik teori Martin-LOF (tanpa jenis identitas) dapat diartikan domain-teoritis sedemikian rupa yang berisi dua elemen dan , di mana berkorespondensi untuk dan untuk non-terminasi. Sayangnya, karena tidak ada cara untuk menuliskan ekspresi non-terminating dalam teori tipe, tidak dapat disebutkan namanya. Akibatnya, persamaan untuk tidak tidak memberitahu kita bagaimana untuk menghitung pada (dua pilihan yang jelas menjadi "bersemangat" dan "malas"). $1$ $\bot$ $\top$ $\top$ $\star$ $\bot$ $\bot$ $\mathrm{ind}_1$ $\bot$

Dalam istilah rekayasa perangkat lunak, saya akan mengatakan kami memiliki kebingungan antara spesifikasi dan implementasi . Aksioma HoTT untuk tipe identitas adalah spesifikasi . Persamaan tidak memberi tahu kita cara menghitung, atau bagaimana membangun , melainkan Namun itu $\mathrm{ind}_{=_C}(C,c,x,x,\mathrm{refl}(x)) \equiv c(x)$ $\mathrm{ind}_{=_C}$ adalah "diimplementasikan", kami mengharuskan itu memenuhi persamaan. Ini adalah pertanyaan terpisah apakah dapat diperoleh secara konstruktif. $\mathrm{ind}_{=_C}$ $\mathrm{ind}_{=_C}$

Terakhir, saya sedikit lelah dengan bagaimana Anda menggunakan kata "konstruktif". Sepertinya Anda berpikir bahwa "konstruktif" sama dengan "terdefinisi". Di bawah interpretasi itu, Oracle Henti adalah konstruktif, karena perilakunya ditentukan oleh persyaratan yang kami tetapkan padanya (yaitu bahwa output 1 atau 0 menurut apakah mesin yang diberikan berhenti). Prefek mungkin untuk menggambarkan objek yang hanya ada dalam pengaturan non-konstruktif. Sebaliknya, sangat mungkin untuk berbicara secara konstruktif tentang properti dan hal-hal lain yang sebenarnya tidak dapat dihitung. Inilah satu: hubungan didefinisikan oleh $H \subseteq \mathbb{N} \times \{0,1\}$ konstruktif, yaitu, tidak ada yang salah dengan definisi ini dari sudut pandang konstruktif. Kebetulan yang konstruktif satu tidak dapat menunjukkan bahwa adalah relasi total, dan peta karakteristik tidak faktor tidak melalui

H (n, d) ⟺ (d = 1 \Rightarrow n mesin berhenti) \land (d = 0 \Rightarrow n -di mesin menyimpang)

$H(n,d) \iff (d = 1 \Rightarrow \text{$n$-th machine halts}) \land (d = 0 \Rightarrow \text{$n$-th machine diverges})$

H

$H$

χ_{H} : N \times {0, 1} \to P r o p

$\chi_H : \mathbb{N} \times \{0,1\} \to \mathsf{Prop}$

b o o l

$\mathtt{bool}$ , jadi kita tidak bisa "menghitung" nilainya.

Tambahan: Judul pertanyaan Anda adalah "Apakah induksi jalur konstruktif?" Setelah membersihkan perbedaan antara "konstruktif" dan "terdefinisi", kita dapat menjawab pertanyaan itu. Ya, induksi jalur diketahui konstruktif dalam kasus-kasus tertentu:

Jika kita membatasi untuk mengetik teori tanpa Univalence sehingga kita dapat menunjukkan normalisasi yang kuat, maka jalur induksi dan yang lainnya konstruktif karena ada algoritma yang melakukan prosedur normalisasi.
Ada model realisasi dari teori tipe, yang menjelaskan bagaimana setiap istilah tertutup dalam teori tipe sesuai dengan mesin Turing. Namun, model ini memuaskan Streicher's Axiom K, yang mengesampingkan Univalence.
Ada terjemahan dari teori tipe (lagi tanpa Univalence) ke teori himpunan konstruktif CZF. Sekali lagi, ini memvalidasi aksioma Streicher K.
Ada model groupoid di dalam model realisasi yang memungkinkan kita untuk menafsirkan teori tipe tanpa Streicher's K. Ini adalah karya pendahuluan oleh Steve Awodey dan saya sendiri.

Kita benar-benar perlu memilah status konstruktif dari Univalence.

Andrej Bauer
sumber

Saya yakin jawaban ini sekarang (sebagian) sudah ketinggalan zaman

WorldSEnder

Memang, dalam waktu yang berarti teori tipe kubik memberikan jawaban postive: ada model konstruktif dari teori tipe Univalent.

Andrej Bauer

7

Saya bukan orang HoTT, tapi saya akan memasukkan dua sen saya.

Misalkan kita ingin membuat fungsi Bagaimana kita melakukan ini? Nah, misalkan kita diberi dan bukti kesetaraannya . Karena saya tidak tahu apa-apa tentang tipe sewenang-wenang , saya tidak tahu apa-apa tentang `struktur '

f_{SEBUAH} : \prod_{x, y : SEBUAH} \prod_{hal : x =_{SEBUAH} y} C (x, y, hal)

$f_A : \prod_{x,y : A}\prod_{p : x =_A y} C(x,y,p)$

x, y : A

$x,y : A$

p : x =_{A} y

$p : x =_A y$

A

$A$

x, y

$x,y$ . Namun, saya tahu sesuatu tentang jenis tertentu kesetaraan: memiliki konstruktor tunggal,

Oleh karena itu,

untuk beberapa

, tapi ini akan memaksa

. Karenanya, jika kita memiliki elemen

untuk semua

{r e f l}_{Sebuah} : Sebuah =_{SEBUAH} Sebuah, untuk apa saja Sebuah : SEBUAH

$\mathsf{refl}_a : a =_A a, \text{ for any } a : A$

p \equiv {r e f l}_{a}

$p \equiv \mathsf{refl}_a$

a : A

$a : A$

x = a = y

$x=a=y$

C (x, x, {r e f l}_{x})

$C(x,x,\mathsf{refl}_x)$

; yaitu jika kita memiliki fungsi

(untuk

spesifik kami), maka fungsi kami

dapat didefinisikan sebagai berikut:

x : A

$x : A$

b Sebuah s e_{C} : \prod_{x : SEBUAH} C (x, x, {r e f l}_{x})

$base_C : \prod_{x:A}C(x,x,\mathsf{refl}_x)$

C

$C$

f_{A}

$f_A$

f_{SEBUAH} (x, y, hal) : = b Sebuah s e_{C} (x, x, hal)

$f_A(x,y,p) := base_C(x,x,p)$ .

Menyingkirkan langganan mengarah ke definisi induktif umum.

Semoga itu bisa membantu!

$e$ $E$ $E$

Musa Al-hassy
sumber

1

Mungkin Anda bisa memahaminya, atau setidaknya khawatir tentang intuisi Anda saat ini dengan memeriksa math.andrej.com/2013/08/28/the-elements-of-an-inductive-type di mana saya mencoba menjelaskan mengapa itu berbahaya untuk berpikir bahwa syarat tertutup dari suatu jenis semua ada pada suatu jenis.

Andrej Bauer

2

r e f l

$\mathsf{refl}$

3

$A\times B$ $A\times B$

hal Sebuah saya r : SEBUAH \to B \to SEBUAH \times B

$\mathrm{pair}\ :\ A\rightarrow B\rightarrow A\times B$

f

$f$

A \times B

$A\times B$ $\mathrm{pair}$

$\mathrm{pair}$ $f:A\times B\rightarrow C$ $A$ $B$

f^{'} : SEBUAH \to B \to C

$f':A\rightarrow B\rightarrow C$

f

$f$

A \times B

$A\times B$

(SEBUAH \to B \to C) \to (SEBUAH \times B \to C)

$(A\rightarrow B\rightarrow C)\rightarrow(A\times B\rightarrow C)$

{i n d}_{A \times B}

$\mathrm{ind}_{A\times B}$

$f$ $\mathrm{pair}(a,b)$ $f$ $f'$

f (hal Sebuah saya r (Sebuah, b)) : = f^{'} Sebuah b

$f(\mathrm{pair}(a,b))\ :=\ f'\ a\ b$

{saya n d}_{SEBUAH \times B} f^{'} hal Sebuah saya r (Sebuah, b) : = f^{'} Sebuah b

$\mathrm{ind}_{A\times B}\ f'\ \mathrm{pair}(a,b)\ :=\ f'\ a\ b$

=

$=$

Jadi Anda melihat bahwa definisi eliminator untuk tipe induktif dengan konstruktor yang diberikan datang dalam 2 langkah:

$\mathrm{ind}$
$\mathrm{ind}$

$=_A$ $x,y:A$ $p:x=y$ $C$ $p$ $x=y$ $\mathrm{refl}(z)$ $z$

f : Π x, y : SEBUAH, x = y \to C

$f:\Pi x, y:A, x=y\rightarrow C$

f^{'} : Π z : SEBUAH, C

$f':\Pi z:A, C$

r e f l (z)

$\mathrm{refl}(z)$

C

$C$

$f$ $f'$

f z z r e f l (z) : = f^{'} z

$f\ z\ z\ \mathrm{refl}(z):= f'\ z$

$A\times B$ $=_A$

cody
sumber

Apakah path induction konstruktif?

Jawaban: