There is no classification of the decidably presentable structures

2017/02/21 by Harrison-Trainor, Matthew
#FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1702.06587

Abstract

A computable structure A is decidable if, given a formula φ(x) of elementary first-order logic, and a tuple a ∈ A, we have a decision procedure to decide whether φ holds of a. We show that there is no reasonable classification of the decidably presentable structures. Formally, we show that the index set of the computable structures with decidable presentations is Σ¹₁-complete. This result holds even if we restrict out attention to groups, graphs, or fields. We also show that the index sets of the computable structures with n-decidable presentations is Σ¹₁-complete for any n.

Related

• Computability for tree presentations of continuum-size structures
• The Complexity of the Set of Validities of a Theory
• Model completeness and relative decidability
• Generalized effective completeness for continuous logic
• The First-Order Theory of Sets with Cardinality Constraints is Decidable