Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 2 / 16G / i / Solution

One Hilbert axiomatization of classical propositional logic uses the schemas $A\to (B\to A)$, $[A\to (B\to C)]\to [(A\to B)\to (A\to C)]$ and $(\neg B\to \neg A)\to (A\to B)$, with modus ponens as its inference rule. Other connectives can be defined from implication and negation. Syntactic entailment $\Gamma ⊢A$ means that a finite formal proof derives $A$ from the schemas and members of $\Gamma$. Consistency means that no formula and its negation are both derivable, equivalently no contradiction is derivable.

Use the standard deduction theorem, closure of derivability under modus ponens, and the maximal-consistency properties: a maximal consistent set contains exactly one of $A,\neg A$, is closed under derivability, and satisfies $A\to B\in \Phi$ exactly when $A\notin \Phi$ or $B\in \Phi$. These follow from the deduction theorem and the classical schemas; in particular adjoining a missing formula to a maximal set must yield a contradiction. Define $v(p)=T$ iff $p\in \Phi$. Induction on formula construction now provesFor negation use the exactly-one property, and for implication use its displayed membership rule, which is precisely the Boolean truth table. Thus every member of $\Phi$ is true under $v$, providing the required valuation.