Alam semesta dalam teori tipe dependen

Saya membaca tentang teori tipe dependen dalam buku online Homotopy Type Theory .

Di bagian 1.3 dari bab Type Theory , ia memperkenalkan gagasan tentang hierarki Semesta : , di mana $\mathcal{U}_0 : \mathcal{U}_1 : \mathcal{U}_2 : \cdots$

setiap alam semesta adalah elemen dari alam semesta selanjutnya . Selain itu, kami mengasumsikan bahwa alam semesta kami bersifat kumulatif, yaitu bahwa semua elemen alam semesta juga merupakan elemen dari alam semesta . $\mathcal{U}_i$ $\mathcal{U}_{i+1}$ $i^{\mathrm{th}}$ $(i+1)^{\mathrm{th}}$

Namun, ketika saya melihat aturan pembentukan untuk berbagai jenis dalam lampiran A, sekilas, jika sebuah alam semesta muncul di atas mistar sebagai premis, alam semesta yang sama muncul di bawah. Misalnya untuk aturan pembentukan tipe coproduct:

\frac{Γ ⊢ A : U_{i} Γ ⊢ B : U i}{Γ ⊢ A + B : U_{i}} (+ - F O R M)

$\dfrac{\Gamma \vdash A : \mathcal{U}_i \quad \Gamma \vdash B : \mathcal{U}i}{\Gamma \vdash A + B : \mathcal{U}_i}(+\mbox{-}FORM)$

Jadi pertanyaan saya adalah mengapa hierarki diperlukan? Dalam keadaan apa Anda perlu melompat dari alam semesta ke alam yang lebih tinggi dalam hierarki? Sangat tidak jelas bagi saya bagaimana diberikan kombinasi , Anda bisa berakhir dengan tipe yang tidak ada di . Secara lebih rinci: aturan pembentukan di bagian lampiran A.2.4, A.2.5, A.2.6, A.2.7, A.2.8, A.2.9, A.2.10, A.3.2, disebutkan dalam premis dan penilaian, atau hanya dalam penilaian. $A_m: \mathcal{U}_i$ $B$ $\mathcal{U}_i$ $\mathcal{U}_i$

Buku ini juga mengisyaratkan bahwa ada cara formal untuk menetapkan alam semesta:

Jika ada keraguan tentang apakah argumen itu benar, cara untuk memeriksanya adalah dengan mencoba menetapkan level secara konsisten untuk semua alam semesta yang muncul di dalamnya.

Bagaimana proses untuk menetapkan level secara konsisten?

$\mathcal{U}:\mathcal{U}$ akan mengarah ke paradoks Russell . Menghindari paradoks Russell secara eksplisit disebutkan dalam buku (halaman 24). Hal ini juga masuk ke dalam perincian lebih lanjut halaman 54, 55 yang menggunakan "alam semesta gaya Russell" daripada "alam semesta gaya Tarski". Jadi pada tingkat yang sangat tinggi, saya menerima begitu saja bahwa teorinya ingin menghindari paradoks. Sayangnya saya tidak memiliki latar belakang untuk memahaminya secara langsung. Apa yang saya kejar dalam pertanyaan ini, benar-benar hanya menggaruk permukaan dengan mendapatkan beberapa contoh hal dalam dan tidak dalam untuk dan mungkin hal lain yang memberi saya rasa untuk cara kerja hierarki. $\mathcal{U}_j$ $\mathcal{U}_i$ $j > i$

type-theory homotopy-type-theory dependent-types huynhjl
sumber

@huynhjl Menggunakan alam semesta tidak perlu untuk menghindari paradoks, misalnya baik teori set ZF maupun Quine's NF, dua yayasan matematika alternatif menggunakannya. Alam semesta adalah cara yang nyaman untuk menghindari paradoks (atau lebih dari itu kami berharap) sementara pada saat yang sama memiliki kemampuan untuk membangun tipe yang sangat ekspresif.

Martin Berger

Jawaban:

Pertanyaan dalam keadaan apa kita perlu melompat dari alam semesta ke alam yang lebih tinggi dalam hierarki adalah pertanyaan yang bagus. Memiliki hierarki dan kemampuan untuk mendaki itu penting. Anda perlu melompat level ketika Anda ingin memperlakukan alam semesta sebagai tipe atau sebagai bagian dari tipe. Sebagai contoh untuk mendefinisikan fungsi (tidak bergantung) tipe Anda harus menunjukkan bahwa berada di alam semesta. Tapi itu tidak bisa atau alam semesta yang lebih kecil. Jadi apa yang kita lakukan? Untuk mengatasi masalah ini (tanpa menggunakan yang tidak sehat ), kita perlu melompat ke atas semesta. Aturan yang memungkinkan kita melakukan lompatan ini adalah -Intro

A \to U_{i}

$A \rightarrow \mathcal{U}_i$

A \to U_{i}

$A \rightarrow \mathcal{U}_i$

U_{i}

$\mathcal{U}_i$

U_{i} : U_{i}

$\mathcal{U}_i : \mathcal{U}_i$

U

$\mathcal{U}$

\frac{⊢ Γ : c t x}{Γ ⊢ U_{i} : U_{i + 1}},

$\frac{\vdash \Gamma : ctx}{\Gamma \vdash \mathcal{U}_i : \mathcal{U}_{i+1}},$ diberikan dalam Lampiran A.2.3. Inti hierarki alam semesta adalah kita bisa melakukan ini. Ini dapat dilihat sebagai perkiraan yang aman untuk memiliki alam semesta mengandung diri mereka sendiri.

Martin Berger
sumber

Saya akan sedikit mengubah jawaban Martin untuk menjelaskan dari mana kumulatifitas datang (aturan yang mengatakan bahwa dan memerlukan ). Misalkan kita memiliki dan kami ingin memberikan tipe ke . Aturan pembentukan untuk adalah ini: (Jika adalah singkatan untuk maka aturan di atas dapat diturunkan dari aturan pembentukan untuk $X : \mathcal{U}_i$ $i \leq j$ $X : \mathcal{U}_j$ $A : \mathcal{U}_{42}$ $A \to \mathcal{U}_{99}$ $\to$

\frac{Γ ⊢ X : U_{i} Γ ⊢ Y : U_{i}}{Γ ⊢ (X \to Y) : U_{i}}

$\frac{\Gamma \vdash X : \mathcal{U}_i \qquad \Gamma \vdash Y : \mathcal{U}_i}{\Gamma \vdash (X \to Y) : \mathcal{U}_i}$

X \to Y

$X \to Y$

Π_{x : X} Y

$\Pi_{x : X} Y$

Π

$\Pi$ , tapi jangan khawatir.) Untuk menggunakan aturan ini, kedua tipe yang terlibat dalam pembentukan tipe fungsi harus berada di alam semesta yang sama. Dalam kasus kami, kami memiliki dalam dan dalam . Jadi pertama-tama kita menggunakan kumulatif untuk menyimpulkan bahwa juga, dan kemudian melanjutkan untuk menunjukkan bahwa memiliki tipe .

A

$A$

U_{42}

$\mathcal{U}_{42}$

U_{99}

$\mathcal{U}_{99}$

U_{100}

$\mathcal{U}_{100}$

A : U_{100}

$A : \mathcal{U}_{100}$

A \to U_{99}

$A \to \mathcal{U}_{99}$

U_{100}

$\mathcal{U}_{100}$

Kita bisa menyingkirkan kumulatif, tetapi kemudian aturannya menjadi lebih kompleks. Misalnya, pembentukan membaca atau Dalam kasus apa pun, teori jenis memiliki banyak variasi yang halus, dan membuat semuanya bermain bersama dengan baik sepertinya menjadi sedikit seni. $\to$

\frac{Γ ⊢ X : U_{i} Γ ⊢ Y : U_{j}}{Γ ⊢ (X \to Y) : U_{max (i, j)}}

$\frac{\Gamma \vdash X : \mathcal{U}_i \qquad \Gamma \vdash Y : \mathcal{U}_j}{\Gamma \vdash (X \to Y) : \mathcal{U}_{\max(i,j)}}$

\frac{Γ ⊢ X : U_{i} Γ ⊢ Y : U_{j} i \leq k j \leq k}{Γ ⊢ (X \to Y) : U_{k}}

$\frac{\Gamma \vdash X : \mathcal{U}_i \qquad \Gamma \vdash Y : \mathcal{U}_j \qquad i \leq k \qquad j \leq k}{\Gamma \vdash (X \to Y) : \mathcal{U}_k}$

Andrej Bauer
sumber