An Escape from Vardanyan's Theorem

Abstract

Vardanyan’s Theorems [36, 37] state that QPL(PA)—the quantified provability logic of Peano Arithmetic—isΠ02 complete, and in particular that this already holds when the language is restricted to a single unary predicate. Moreover, Visser and de Jonge [38] generalized this result to conclude that it is impossible to computably axiomatize the quantified provability logic of a wide class of theories. However, the proof of this fact cannot be performed in a strictly positive signature. The system QRC1 was previously introduced by the authors [1] as a candidate first-order provability logic. Here we generalize the previously available Kripke soundness and completeness proofs, obtaining constant domain completeness. Then we show that QRC1 is indeed complete with respect to arithmetical semantics. This is achieved via a Solovaytype construction applied to constant domain Kripke models. As corollaries, we see that QRC1 is the strictly positive fragment of QGL and a fragment of QPL(PA).