Paper 4, Section II, F

Logic and Set Theory
Part II, 2016

(a) State Zorn's Lemma, and use it to prove that every nontrivial distributive lattice LL admits a lattice homomorphism L{0,1}L \rightarrow\{0,1\}.

(b) Let SS be a propositional theory in a given language L\mathcal{L}. Sketch the way in which the equivalence classes of formulae of L\mathcal{L}, modulo SS-provable equivalence, may be made into a Boolean algebra. [Detailed proofs are not required, but you should define the equivalence relation explicitly.]

(c) Hence show how the Completeness Theorem for propositional logic may be deduced from the result of part (a).