AN ESCAPE FROM VARDANYAN'S THEOREM

Vardanyan's Theorems [36, 37] state that QPL {PA})-the quantified provability logic of Peano Arithmetic-is pi(0)(2) 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 QRC(1) 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 QRC(1) is indeed complete with respect to arithmetical semantics. This is achieved via a Solovay-type construction applied to constant domain Kripke models. As corollaries, we see that QRC(1) is the strictly positive fragment of QGL and a fragment of QPL{PA} .