Wir vergleichen Shoenfields Variante des Hilbert-Systems (vgl. Übungsblatt 2, Aufgabe H2) mit dem Sequenzenkalkül.
(a) Man zeige, dass die Sequenz Γ ,ϕ ∆,ϕ für jede aussagenlogische Formel ϕ im Sequenzenkalkül SK herleitbar ist.
(Tipp: Induktion über den Aufbau von ϕ.)
(b) Man zeige die folgende Aussage: Wenn es im Kalkül von Shoenfield einen Beweisbaum mit Blättern Γ = ϕ1
, . . . ,ϕn
und Wurzel ψ gibt, dann ist die Sequenz Γ
ψ im Sequenzenkalkül SK+
(also mit der Schnittregel) herleitbar.
Hinweis: Sie können Abschwächungslemma, Inversionslemma und Kontraktionslemma verwenden