Über die Entsprechung der linken Einführung und Beseitigung der Implikation in Sequent Calculus und in Natural Deduction resp.

8

Könnte jemand eine intuitive ( nicht intutionistische) Erklärung für die Entsprechung der linken Einführung und der Beseitigung von Implikationen in Sequent Calculus (SC) bzw. Natural Deduction (ND) geben? Ich weiß, dass sie durch die Symmetrie von SC sollten, aber ich sehe nicht, wie sie einander entsprechen. Im Allgemeinen verstehe ich nicht, wie die linke Einführung eines Konnektivs in SC genau die Eliminierung in ND intuitiv macht.

Tag
quelle

Antworten:

9

In rechnerischer Hinsicht ist ein sequentieller Kalkülterm eine Sequentialisierung eines Lambda-Terms. Das heißt, als Typensystem betrachtet, kann die sequentielle Berechnung so gesehen werden, dass sie eine Bewertungsreihenfolge eines Lambda-Terms ergibt.

So nehme und & Ggr; e 2 : A .Γe1:ABΓe2:A

In natürlicher Ableitung lautet der Begriff für die Implikationseliminierung - dh Anwendung. Beachten Sie jedoch, dass dies uns nicht sagt, ob wirzuerst e 1 oder zuerst e 2 bewerten sollen.Γe1e2:Be1e2

In der sequentiellen Berechnung muss eine entsprechende Zuordnung der Beweisbegriffe so aussehen

letf=e1inletv=e2inletx=fvinx

sonst muss es so aussehen

letv=e2inletf=e1inletx=fvinx

Hier ist die Let-Form der Beweisbegriff, der der Verwendung der Cut-Regel entspricht, und da alle linken Regeln nur auf Hypothesen / Variablen wirken, zwingt dies uns, alle Zwischenergebnisse an Variablen zu binden. Diese Anforderung stellt sicher, dass wir gezwungen sind, explizit zu sagen, welches von oder e 2 wir zuerst reduzieren und an eine Variable binden.e1e2

Für rein funktionale Sprachen spielt diese Aussage keine Rolle, aber wenn Sie Effekte hinzufügen, wird es einfacher, mit sequentiellen Kalkülen zu arbeiten. Aus diesem Grund werden Dinge wie Steuereffektkalküle / klassische Logik typischerweise als sequentielle Kalküle dargestellt.

Neel Krishnaswami
quelle
Neel, danke auch für diese interessante Interpretation aus rechnerischer Sicht.
Tag
Neel, kannst du irgendwelche Papiere oder Buchkapitel geben, in denen man mehr Details finden kann?
Bellpeace
8

Um es noch einmal zusammenzufassen: In ND sagt uns die Eliminierung eines Konnektivs, wie man es verwendet:

AB

A

AB

B

ABAB

Ebenso in SC:

Γ,AΔ

Γ,ABΔ

Γ,BΔ

Γ,ABΔ

ABABAB

Im Allgemeinen geben SC-Einführungsregeln an, wann wir eine Verbindung verwenden können, und ND-Eliminierungsregeln geben an, wie eine Verbindung verwendet werden soll.

Nun, implizit haben wir in ND:

AB       A

B

In SC:

ΓA,Δ       Σ,BΠ

Γ,Σ,ABΔ,Π

ΔΣ

ΓA       BΠ

Γ,ABΠ

ΓAB(Π)ABΠ

Mark Reitblatt
quelle
Schöne Antwort, aber die Frage fragt nach Implikation, nicht nach Konjunktion.
Dave Clarke
@ Radu ja, aber das macht sie winzig. Ich denke, dieser Weg funktioniert gut genug.
Mark Reitblatt