Comprender la prueba de una fuerte normalización del cálculo de las construcciones

Tengo dificultades para comprender la prueba de una fuerte normalización para el cálculo de las construcciones. Trato de seguir la prueba en el documento de Herman Geuvers "Una prueba corta y flexible de Normalización Fuerte para el Cálculo de Construcciones".

Puedo seguir bien la línea principal de razonamiento. Geuvers construye para cada tipo $T$ una interpretación $[\![T]\!]_\xi$ basado en alguna evaluación de las variables de tipo $\xi(\alpha)$ . Y luego construye algún término interpretación $(\!|M|\!)_\rho$ basado en alguna evaluación de las variables de término $\rho(x)$ y demuestra que para evaluaciones válidas la afirmación $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ para todos $\Gamma\vdash M:T$ sostiene.

Mi problema: para los tipos fáciles (como los tipos del sistema F), la interpretación de tipos $[\![T]\!]_\xi$ es realmente un conjunto de términos, por lo que la afirmación $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ tiene sentido. Pero para los tipos más complejos, la interpretación $[\![T]\!]_\xi$ no es un conjunto de términos, sino un conjunto de funciones de algún espacio de funciones apropiado. Creo que casi entiendo la construcción de los espacios de funciones, sin embargo, no puede asignar ningún significado a $(\!|M|\!)_\rho \in [\![T]\!]_\xi$ para los tipos más complejo $T$ .

¿Alguien puede explicar o dar enlaces a algunas presentaciones más comprensibles de la prueba?

Editar: Déjame intentar aclarar la pregunta. Un contexto $\Gamma$ tiene declaraciones para las variables de tipo $\alpha:A$ y las variables de objeto. Una valoración de tipo es válida, si para todos $(\alpha:A) \in \Gamma$ con $\Gamma\vdash A:\square$ entonces $\xi(\alpha) \in \nu(A)$ es válida. Pero $\nu(A)$ puede ser un elemento de $(SAT)^*$ y no solo $SAT$ . Por lo tanto, no se puede definir un término válido de evaluación para $\rho(\alpha)$ . $\rho(\alpha)$ debe ser un término y no una función de un espacio de funciones.

Edición 2: ejemplo que no funciona

Hagamos la siguiente derivación válida:

\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}$

En el último contexto, una evaluación de tipo válida debe satisfacer $\xi(\beta) \in \nu(\Pi \alpha:*.*) = \{f| f:\text{SAT} \to \text{SAT}\}$ . Para este tipo de evaluación no existe un término válido de evaluación.

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

La mitad de las personas que lean esto pensarán que

es SAT. Deberías explicar de qué se trata. Además, su derivación parece un poco extraña. La segunda línea no debería mencionar

en su conclusión, debería leer algo como

, ¿no debería?

S A T

$SAT$

α

$\alpha$

[α : *] ⊢ * : ◻

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

Andrej Bauer el

Estoy usando la notación de Herman Geuvers (que parece ser estándar en este dominio).

es el conjunto de todos los conjuntos saturados de expresiones lambda. Para la segunda línea de mi derivación: es la regla de introducción para las variables de un sistema de tipo puro. Esta regla dice

SAT

$\text{SAT}$

donde

es algún tipo.

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

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

s

$s$

helmut

Entiendo cómo obtuviste la segunda línea, pero no es la premisa correcta para la formación de la tercera línea, ¿verdad? Qué regla da la tercera línea.

Andrej Bauer el

La regla de formación de producto de PTS dice

. El cálculo de las construcciones tiene la regla

. Esto me permite usar la primera y la segunda línea para derivar la tercera. Sin embargo, tuve un error tipográfico en mi publicación. Faltaba el tipo en la tercera línea que agregué ahora.

\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

¿No debería entonces la primera línea leer

? ¿O

alguna parte? La segunda línea no puede ser la segunda premisa de la regla de formación del producto, porque eso significaría que está tratando de formar algo como

lugar de

[] ⊢ * : *

$[] \vdash * : *$

*

$*$

◻

$\Box$

\prod α : * . α

$\prod \alpha : * . \alpha$

\prod α : * . *

$\prod \alpha : * . *$

Andrej Bauer el

Desafortunadamente, no estoy seguro de que haya más recursos amigables para principiantes que la cuenta de Geuvers. Puede probar esta nota de Chris Casinghino que da cuenta de varias pruebas con detalles insoportables.

No estoy seguro de comprender la esencia de su confusión, pero creo que una cosa importante a tener en cuenta es el siguiente lema (Corolario 5.2.14), probado en el texto clásico de Barendregt :

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

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

Esto significa que mientras $[\![T]\!]_\xi$ puedeser una función complicada,si $\Gamma \vdash M:T$ tiene, entonces $[\![T]\!]_\xi$

$(\!|t|\!)_\sigma\in[\![T]\!]_\xi$ $\Gamma \vdash t:T :*$ ${\cal V}(*)\subseteq{\cal P}(\mathrm{Term})$ ${\cal V}(*)=\mathrm{SAT}$

$*$ $\mathrm{SAT}^*$ $*$ $\square$

cody
fuente

Gracias por la explicación. Eso resuelve mi problema de no entender las funciones utilizadas en la prueba de Geuver. Ya tenía una sospecha al leer y releer el artículo de Geuver, pero lo dejaste muy claro.

helmut

Comprender la prueba de una fuerte normalización del cálculo de las construcciones

Respuestas: