Cálculo lambda simplemente escrito y lógica de orden superior

¿Cuál es la relación entre el cálculo lambda simplemente escrito y la lógica de orden superior?

Bajo Curry-Howard parece que el cálculo lambda simplemente escrito corresponde a la lógica proposicional. ¿Cómo se relaciona con la lógica de orden superior? Según este tutorial de Geuvers: http://typessummerschool07.cs.unibo.it/courses/geuvers-1.pdf, el lenguaje de HOL parece ser STT. ¿No debería ser PROP? Qué significa eso?

¿Tenía Church en mente HOL cuando definió STT?

lo.logic typed-lambda-calculus curry-howard lambda2
fuente

Sí, Church tenía HOL en mente. El truco para obtener HOL de STT es utilizar la igualdad , además de la aplicación de funciones y la abstracción de funciones. Luego puede escribir

como

, entre otros. Me gusta "Las siete virtudes de la teoría simple de tipos" como una introducción a STT, que aborda este tipo de preguntas. Tal vez debería escribir una respuesta ...

(\forall x : α . A_{*})

$(\forall x:\alpha.A_*)$

(λ x : α . A_{*}) = (λ x : α . ⊤)

$(\lambda x:\alpha.A_*)=(\lambda x:\alpha.\top)$

Thomas Klimpel

Entonces, cuando se habla de Curry-Howard, ¿cuál sería la lógica correcta equivalente a STT? HOL o PROP?

lambda2

Con respecto a Curry-Howard, no creo que sea HOL. Quizás sea el fragmento multiplicativo de la PROP intuicionista, es decir, la PROP intuicionista sin "o". Pero eso fue para CCC (categoría cerrada cartesiana), y estoy un poco cansado en este momento. Lambda probablemente se traducirá como "implicación", que era el "exponencial" en CCC. El "producto" de CCC era "y", por lo que necesitaría un "par" en STT para eso. Y "o" sería un tipo de "suma" en STT entonces, es decir, una unión disjunta, tal vez un "si" a "entonces" b "más" c "hace eso.

Thomas Klimpel

Creo que estoy confundiendo algo (o todo). Si STT ~ = PROP (a través de Curry-Howard), y STT también es HOL, ¿puedo usar PROP en algún sentido para tener HOL?

lambda2

@ThomasKlimpel: debes convertir tus comentarios en una respuesta.

cody

Respuestas:

La distinción es esta: si STLC se toma como un lenguaje primitivo en los constructores de adición de nivel de tipo y un pequeño número de axiomas es suficiente para darle el poder expresivo completo de HOL.

$\iota$ $\omicron$

\forall_{τ} : (τ \to ο) \to ο \supset: ο \to ο \to ο

$\forall_\tau:(\tau\rightarrow \omicron)\rightarrow \omicron\quad \supset:\omicron\rightarrow\omicron\rightarrow \omicron$

$\tau$ $\forall$

\frac{ϕ (x)}{\forall_{τ} (λ x . ϕ (x))} x : τ not free in the hypotheses

$\frac{\phi(x)}{\forall_\tau(\lambda x.\phi(x))}\mbox{$x:\tau$ not free in the hypotheses}$

\frac{\begin{matrix} [ψ] \\ . \\ . \\ . \\ ϕ \end{matrix}}{ψ \supset ϕ}

$\frac{\Large{\substack{[\psi]\\ \\ .\\ .\\ .\\ \\ \phi}}}{\psi\supset \phi}$

$[\psi]$ $\psi$ $\exists_\tau, \vee$

$\lambda$

cody
fuente

\forall_{τ}

$\forall_\tau$

\supset

$\supset$

=_{τ} : τ \to τ \to ο

$=_\tau :\tau\rightarrow\tau\rightarrow\omicron$

¿Cuáles son esos axiomas inteligentes, por favor? Supongo que esto tiene que ver con proporcionar una forma de demostrar la igualdad ... Además, ¿conoces un nombre para distinguir explícitamente los niveles de las extensiones HOL? (con igualdad, luego con tipo polimórfico, luego con tipos dependientes).

Hibou57

@ Hibou57 los axiomas se describen en el excelente artículo Las siete virtudes de la teoría simple de tipos . No sé si hay nombres explícitos para distinguir diferentes extensiones de STT, además de las que usó.

cody