The Complexity of the Set of Validities of a Theory

Denis R. Hirschfeldt, Henry Towsner, Scott Weinstein

We study the collection of first-order logical schemata all of whose instances are theorems of a given theory $T$; we call these the validities of $T$ ($\mathsf{V}(T)$). It is easy…