Exercise 126 (Hilbert-styles vs. Natural Deduction). Read Exercise 125, without necessarily

solving it, before you attempt this one. The preceding exercise proposes a strictly proof-theoretic

approach to showing that a Hilbert-style proof system and a natural-deduction proof system have

equal deductive power. In this exercise we consider an alternative semantic approach, which

invokes Soundness and Completeness for both proof systems. Specifically, each of the two sys-

tems as here presented is sound and complete relative to the standard (classical) semantics of

propositional logic based on Boolean algebras. There are three parts in this exercise, the first

two of which are just plans in outline to prove the equivalence of the two systems:

1. If I, then I by Soundness of the Hilbert system. By Completeness of the natural

deduction system, it follows that I END 4.

2. If I END 4, then I by Soundness of the natural deduction system. By Completeness

of the Hilbert system, it follows that I ₁9.

Provide the details of the two preceding parts, given only in outline here, pointing out missing

prerequisites (e.g., we do not prove Soundness and Completeness for the Hilbert system in these

notes) and propose ways of filling the gaps and how to prove them. (We do not add subscripts

"H" and "ND" to "", because the two systems are sound and complete relative to the same

semantics.)

3. Compare and discuss the pros and the cons of the proof-theoretic approach in Exercise 125

and the approach in this Exercise 126 which makes a detour through semantics.

0