Hilbert proof system 2026-10-31
A Hilbert proof system specifies axiom schemes and inference rules, commonly including modus ponens. A formal proof is a finite sequence of axiom instances, permitted assumptions and conclusions obtained from preceding lines by those rules. Soundness and completeness compare this syntactic derivability with semantic validity or semantic entailment. These properties concern the particular chosen axioms and rules.
Past exam of the logic and set theory course of the University of Oxford 2008 A 2 d Solution 2026-10-31
There is a three-line Hilbert formal proof. Use A1 with , ; then use A3 with , :This is a direct logical derivation in the displayed Hilbert proof system. Neither the deduction theorem for propositional logic nor a completeness theorem for propositional logic is needed: the desired logical implication is just the contrapositive, supplied by A3, of the particular A1 instance on line 1.
Past exam of the logic and set theory course of the University of Oxford 2008 A 2 e Solution 2026-10-31
Yes, for soundness and completeness of theoremhood. An axiom-only complete propositional calculus is obtained as follows. Declare every propositional tautology, and only such a tautology, to be an axiom; supply no inference rules. A formal proof then consists of a single axiom. Every proved logical formula is valid, giving soundness, and every valid logical formula is already an axiom, giving completeness.
This is not merely an unspecified collection: whether a finite propositional formula is a tautology is decidable by its finite truth table, so the axiom set can be recognized effectively. It is a deliberately uninformative Hilbert proof system, since all the work has been put into axiom recognition. If one instead asked for strong completeness of derivations from arbitrary additional assumptions, a system whose only formal proof lines are axioms or assumptions would not suffice; the affirmative construction here concerns versus .