Memahami Bukti Normalisasi Kuat dari Kalkulus Konstruksi

Saya mengalami kesulitan dalam memahami bukti normalisasi yang kuat untuk kalkulus konstruksi. Saya mencoba mengikuti bukti dalam makalah Herman Geuvers "Sebuah bukti pendek dan fleksibel dari Normalisasi Kuat untuk Kalkulus Konstruksi".

Saya bisa mengikuti jalur utama penalaran dengan baik. Geuvers mengkonstruksi untuk setiap tipe interpretasi berdasarkan beberapa evaluasi variabel tipe . Dan kemudian dia membangun beberapa istilah interpretasi berdasarkan beberapa evaluasi variabel istilah dan membuktikan bahwa untuk evaluasi yang valid pernyataan untuk semua berlaku. $T$ $[\![T]\!]_\xi$ $\xi(\alpha)$ $(\!|M|\!)_\rho$ $\rho(x)$ $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ $\Gamma\vdash M:T$

Masalah saya: Untuk tipe yang mudah (seperti tipe sistem F) interpretasi tipe benar-benar seperangkat istilah, jadi pernyataan masuk akal. Tetapi untuk tipe yang lebih kompleks, interpretasi bukanlah seperangkat istilah tetapi seperangkat fungsi dari beberapa ruang fungsi yang sesuai. Saya pikir, saya hampir mengerti konstruksi ruang fungsi, tetapi tidak dapat memberikan makna apa pun pada untuk yang lebih kompleks jenis . $[\![T]\!]_\xi$ $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ $[\![T]\!]_\xi$ $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ $T$

Adakah yang bisa menjelaskan atau memberikan tautan ke beberapa presentasi bukti yang lebih dimengerti?

Sunting: Biarkan saya mencoba untuk membuat pertanyaan lebih jelas. Konteks memiliki deklarasi untuk variabel tipe dan variabel objek. Suatu penilaian tipe adalah valid, jika untuk semua dengan maka valid. Tetapi dapat menjadi elemen dan bukan hanya . Oleh karena itu tidak ada evaluasi istilah yang valid dapat didefinisikan untuk . harus berupa istilah dan bukan fungsi dari ruang fungsi. $\Gamma$ $\alpha:A$ $(\alpha:A) \in \Gamma$ $\Gamma\vdash A:\square$ $\xi(\alpha) \in \nu(A)$ $\nu(A)$ $(SAT)^*$ $SAT$ $\rho(\alpha)$ $\rho(\alpha)$

Sunting 2: Contoh yang tidak berfungsi

Mari kita membuat derivasi yang valid berikut:

\begin{array}{llll} [] & ⊢ & * : ◻ & axiom \\ [α : *] & ⊢ & α : * & variable introduction \\ [α : *] & ⊢ & * : ◻ & weaken \\ [] & ⊢ & (Π α : * . *) : ◻ & product formation \\ [β : Π α : * . *] & ⊢ & β : (Π α : * . *) & variable introduction \end{array}

$\begin{array}{llll} [] &\vdash & *:\square &\text{axiom} \\ [\alpha:*] &\vdash& \alpha:* &\text{variable introduction} \\ [\alpha:*] &\vdash& *:\square &\text{weaken} \\ [] &\vdash & (\Pi \alpha:*.*):\square &\text{product formation} \\ [\beta:\Pi \alpha:*.*] &\vdash& \beta:(\Pi \alpha:*.*) &\text{variable introduction} \end{array}$

Dalam konteks terakhir evaluasi jenis yang valid harus memenuhi . Untuk jenis evaluasi ini tidak ada evaluasi istilah yang valid. $\xi(\beta) \in \nu(\Pi \alpha:*.*) = \{f| f:\text{SAT} \to \text{SAT}\}$

lo.logic type-theory lambda-calculus typed-lambda-calculus helmut
sumber

Setengah dari orang yang membaca ini akan berpikir bahwa adalah SAT. Anda harus menjelaskan apa itu. Juga, derivasi Anda agak aneh. Baris kedua tidak boleh menyebutkan dalam kesimpulannya, ia harus membaca sesuatu seperti , bukan?

S A T

$SAT$

α

$\alpha$

[α : *] ⊢ * : ◻

$[\alpha : *] \vdash * : \Box$

Andrej Bauer

Saya menggunakan notasi Herman Geuvers (yang tampaknya menjadi standar dalam domain ini). adalah set dari semua set ekspresi lambda jenuh. Untuk baris kedua derivasi saya: Ini aturan pengantar untuk variabel sistem tipe murni. Aturan ini berbunyi mana adalah semacam.

SAT

$\text{SAT}$

\frac{Γ ⊢ T : s}{Γ, x : T ⊢ x : T}

$\frac{\Gamma \vdash T:s}{\Gamma,x:T\vdash x:T}$

s

$s$

helmut

Saya mengerti bagaimana Anda mendapatkan baris kedua tetapi itu bukan premis yang benar untuk pembentukan baris ketiga, bukan? Aturan apa yang memberi garis ketiga.

Andrej Bauer

Aturan pembentukan produk PTS mengatakan . Kalkulus konstruksi memiliki aturan . Ini memungkinkan saya menggunakan baris pertama dan kedua untuk mendapatkan yang ketiga. Namun saya memiliki kesalahan ketik pada posting saya. pada baris ketiga telah hilang yang saya tambahkan sekarang

\frac{r (s_{1}, s_{2}, s_{3}; Γ ⊢ A : s_{1}; Γ, x : A ⊢ B : s_{2}}{Γ ⊢ (Π x : A . B) : s_{3}}

$\frac{r(s_1,s_2,s_3;\, \Gamma\vdash A:s_1;\: \Gamma,x:A\vdash B:s_2}{\Gamma\vdash (\Pi x:A.B): s_3}$

r (*, *, *)

$r(*,*,*)$

helmut

baris pertama membaca ? Atau apakah Anda mencampuradukkan dan suatu tempat? Baris kedua tidak boleh menjadi premis kedua dari aturan pembentukan produk, karena itu berarti Anda mencoba membentuk sesuatu seperti bukannya .

[] ⊢ * : *

$[] \vdash * : *$

*

$*$

◻

$\Box$

\prod α : * . α

$\prod \alpha : * . \alpha$

\prod α : * . *

$\prod \alpha : * . *$

Andrej Bauer

Sayangnya, saya tidak yakin ada lebih banyak sumber daya ramah pemula daripada akun Geuvers. Anda dapat mencoba catatan ini dari Chris Casinghino yang memberikan akun beberapa bukti dengan detail yang luar biasa.

Saya tidak yakin saya mengerti inti dari kebingungan Anda, tetapi saya pikir satu hal penting yang perlu diperhatikan, adalah lemma berikut (Corollary 5.2.14), terbukti dalam teks Barendregt klasik :

Γ ⊢ M : T \Rightarrow Γ ⊢ T : * or ◻

$\Gamma \vdash M:T\ \Rightarrow\ \Gamma \vdash T:*\mbox{ or }\square$

Ini berarti bahwa sementara dapat berupa beberapa fungsi yang rumit, jika berlaku, maka harus merupakan set istilah . $[\![T]\!]_\xi$ $\Gamma \vdash M:T$ $[\![T]\!]_\xi$

Ini disindir dalam garis besar (bagian 3.1), di mana hanya jika , yang sejalan dengan harapan kami, yaitu bahwa interpretasi suatu tipe haruslah seperangkat istilah, yaitu (memang, !) $(\!|t|\!)_\sigma\in[\![T]\!]_\xi$ $\Gamma \vdash t:T :*$ ${\cal V}(*)\subseteq{\cal P}(\mathrm{Term})$ ${\cal V}(*)=\mathrm{SAT}$

Ini adalah situasi umum dalam teori tipe bahwa meskipun kami hanya tertarik pada "jenis dasar" (di sini ), kami masih harus mendefinisikan semantik untuk hal-hal pada jenis yang lebih tinggi (maka kebutuhan untuk memperkenalkan ). Hal-hal kemudian bekerja pada akhirnya, karena hanya jenis yang dihuni oleh jenis adalah (dan , tapi itu tidak terlalu penting). $*$ $\mathrm{SAT}^*$ $*$ $\square$

cody
sumber

Terima kasih untuk penjelasannya. Itu memecahkan masalah saya karena tidak memahami fungsi yang digunakan dalam bukti Geuver. Saya sudah curiga membaca dan membaca ulang kertas Geuver, tetapi Anda membuatnya sangat jelas.

helmut

Memahami Bukti Normalisasi Kuat dari Kalkulus Konstruksi

Jawaban: