No escape from Vardanyan’s Theorem

Abstract

Vardanyan’s Theorem states that the set of PA-valid principles of Quantified Modal Logic, QML, is complete II02. We generalize this result to a wide class of theories. The crucial step in the generalization is avoiding the use of Tennenbaum’s Theorem.