Paper 1, Section II, I

Logic and Set Theory
Part II, 2015

State and prove the Completeness Theorem for Propositional Logic.

[You do not need to give definitions of the various terms involved. You may assume the Deduction Theorem, provided that you state it precisely.]

State the Compactness Theorem and the Decidability Theorem, and deduce them from the Completeness Theorem.

Let SS consist of the propositions pn+1pnp_{n+1} \Rightarrow p_{n} for n=1,2,3,n=1,2,3, \ldots. Does SS prove p1p_{1} ? Justify your answer. [Here p1,p2,p3,p_{1}, p_{2}, p_{3}, \ldots are primitive propositions.]