Quantified provability logic
George Boolos · Cambridge University Press eBooks · 1994
Here and in our final chapter we study quantified (or predicate) provability logic. We consider translations of formulas of quantified modal logic (QML) into the language of arithmetic under which the box □ of modal logic is taken, as in earlier parts of this work, to represent provability in arithmetic. In the “pure” predicate calculus, function signs, the equals-sign =, and modal logical symbols such as □ and ◊ do not occur. We shall define an expression to be a formula of QML if and only if it can be obtained from a formula of the “pure” predicate calculus, by replacing (zero or more) occurrences of the negation sign ¬ with occurrences of □. Thus □ and ¬ have the same syntax in QML, as was the case in propositional modal logic. Our results are negative: we show that there are no simple characterizations of the always provable or always true sentences of QML. Apart from the definition of the sentence D and Lemma 7 below, curiously little use is made of the quantificational–modal–logical properties of Bew( x ). Indeed, the main definitions, techniques, and theorems that are to follow may seem to come from a branch of logic rather unrelated to the one we have been studying up to now. We shall suppose that the variables, v 0 , v 1 ,…, are common to the languages of QML and of arithmetic. The first n variables are, of course, v 0 ,…, v n −1 .