There is no classification of the decidably presentable structures

Abstract

A computable structure $\mathcal{A}$ is decidable if, given a formula $\phi (\bar{x})$ of elementary first-order logic, and a tuple $\bar{a}\in \mathcal{A}$, we have a decision procedure to decide whether $\phi$ holds of $\bar{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 ${\Sigma }_1^1$-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 ${\Sigma }_1^1$-complete for any $n$.

26 pages