Простое типизированное лямбда-исчисление и логика высшего порядка

Какова связь между просто типизированным лямбда-исчислением и логикой более высокого порядка?

При Карри-Говарде кажется, что просто типизированное лямбда-исчисление соответствует логике высказываний. Как это связано с логикой высшего порядка? Согласно этому руководству Geuvers: http://typessummerschool07.cs.unibo.it/courses/geuvers-1.pdf язык HOL выглядит как STT. Разве это не должно быть PROP? Что это значит?

Имел ли в виду Церковь HOL при определении STT?

lo.logic typed-lambda-calculus curry-howard lambda2
источник

Да, Церковь действительно имела в виду HOL. Хитрость в получении HOL от STT состоит в том, чтобы использовать равенство в дополнение к применению функции и абстракции функции. Тогда вы можете написать

как

, среди прочих. Мне нравится «Семь достоинств теории простого типа» как введение в STT, в котором рассматриваются вопросы такого рода. Может быть, я должен написать ответ ...

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

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

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

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

Томас Климпел

Итак, говоря о Карри-Ховарде, что будет правильным логическим эквивалентом STT? ХОЛ или ПРОП?

lambda2

Что касается Curry-Howard, то не думаю, что это будет HOL. Может быть, это мультипликативный фрагмент интуиционистского PROP, то есть интуиционистский PROP без «или». Но это было для ССС (декартовой закрытой категории), и я немного устал в данный момент. Лямбда, вероятно, будет переводиться как «импликация», которая была «экспоненциальной» в КХЦ. «Продукт» из CCC был «и», так что для этого вам понадобится «пара» в STT. И тогда «или» будет типом «сумма» в STT, т. Е. Дизъюнктное объединение, может быть, если «a», то «b», иначе «c» делает это.

Томас Климпел

Я думаю, что я что-то путаю (или все). Если STT ~ = PROP (через Curry-Howard) и STT также является HOL, тогда я могу использовать PROP в некотором смысле, чтобы иметь HOL?

lambda2

@ThomasKlimpel: вы должны превратить ваши комментарии в ответ.

Cody

Ответы:

Различие заключается в следующем: если STLC принимается как примитивный язык на конструкторах добавления на уровне типов и достаточно небольшого числа аксиом, чтобы дать вам полную выразительную силу HOL.

Взяв за базовый тип чисел ans за базовый тип предложений, вы можете добавить константы $\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{φ (Икс)}{\forall_{τ} (λ Икс, φ (Икс))} Икс : τ не свободен в гипотезах

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

Коди
источник

\forall_{τ}

$\forall_\tau$

\supset

$\supset$

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

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

Что это за умные аксиомы, пожалуйста? Я предполагаю, что это связано с предоставлением способа доказать равенство ... Кроме того, знаете ли вы имя для явного различения уровней расширений HOL? (с равенством, затем с полиморфным типом, затем с зависимыми типами).

Hibou57

@ Hibou57 аксиомы описаны в превосходной статье «Семь достоинств теории простого типа» . Я не знаю, что существуют явные имена, чтобы отличать разные расширения STT, кроме тех, которые вы использовали.

Коди