Einfach eingegebener Lambda-Kalkül und Logik höherer Ordnung

Welche Beziehung besteht zwischen einfach getipptem Lambda-Kalkül und Logik höherer Ordnung?

Unter Curry-Howard scheint es, dass einfach getippter Lambda-Kalkül der Aussagenlogik entspricht. Wie hängt es mit der Logik höherer Ordnung zusammen? Laut diesem Tutorial von Geuvers: http://typessummerschool07.cs.unibo.it/courses/geuvers-1.pdf scheint die Sprache von HOL STT zu sein. Sollte es nicht PROP sein? Was bedeutet das?

Hatte Church bei der Definition von STT HOL im Sinn?

lo.logic typed-lambda-calculus curry-howard Lambda2
quelle

Ja, Church hatte HOL im Sinn. Der Trick, um HOL von STT zu erhalten, besteht darin , zusätzlich zur Funktionsanwendung und Funktionsabstraktion Gleichheit zu verwenden . Dann können Sie unter anderem

schreiben als

. Ich mag "Die sieben Tugenden der einfachen Typentheorie" als Einführung in STT, die diese Art von Fragen behandelt. Vielleicht sollte ich eine Antwort schreiben ...

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

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

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

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

Thomas Klimpel

Also, wenn wir über Curry-Howard sprechen, was wäre die richtige Logik, die STT entspricht? HOL oder PROP?

Lambda2

In Bezug auf Curry-Howard glaubt es nicht, dass es HOL sein wird. Vielleicht ist es das multiplikative Fragment von intuitionistischem PROP, dh intuitionistischem PROP ohne "oder". Aber das war für CCC (kartesische geschlossene Kategorie) und ich bin im Moment etwas müde. Lambda wird wahrscheinlich als "Implikation" übersetzt, was im CCC das "Exponential" war. Das "Produkt" von CCC war "und", daher benötigen Sie dafür ein "Paar" in STT. Und "oder" wäre dann ein "Summen" -Typ in STT, dh eine disjunkte Vereinigung, vielleicht ein Wenn "a" dann "b" sonst "c" das tut.

Thomas Klimpel

Ich denke, ich verwirre etwas (oder alles). Wenn STT ~ = PROP (über Curry-Howard) und STT auch HOL ist, kann ich PROP in gewissem Sinne verwenden, um HOL zu haben?

Lambda2

@ThomasKlimpel: Sie sollten Ihre Kommentare in eine Antwort verwandeln.

Cody

Antworten:

Der Unterschied ist folgender: Wenn STLC als primitive Sprache auf Typebene verwendet wird, reicht das Hinzufügen von Konstruktoren und einer kleinen Anzahl von Axiomen aus, um Ihnen die volle Ausdruckskraft von HOL zu verleihen.

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

\forall_{τ}

$\forall_\tau$

\supset

$\supset$

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

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

Was sind diese klugen Axiome bitte? Ich denke, dies hat damit zu tun, einen Weg zu finden, um die Gleichheit zu beweisen. Kennen Sie auch einen Namen, um die Ebenen der HOL-Erweiterungen explizit zu unterscheiden? (mit Gleichheit, dann mit polymorphem Typ, dann mit abhängigen Typen).

Hibou57

@ Hibou57 Die Axiome werden in dem ausgezeichneten Artikel Die sieben Tugenden der einfachen Typentheorie beschrieben . Ich weiß nicht, dass es explizite Namen gibt, um andere STT-Erweiterungen als die von Ihnen verwendeten zu unterscheiden.

Cody