2025/06/10 by Denis R. Hirschfeldt, Hirschfeldt, Denis, Henry Towsner +3
Computer Science · #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Computability, Logic, AI Algorithms
paper · pdf · doi:10.48550/arxiv.2506.08901
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 (V(T)). It is easy to see that if T is a decidable theory, then V(T) is distinct from the set of valid formulas of first-order logic as customarily understood. We provide a complete model-theoretic characterization of the complexity, in the sense of Turing degree, of V(T) for decidable theories T, and answer a question posed by Vaught in 1960 concerning the complexity of the collection of validities common to all decidable theories.