zbMATH — the first resource for mathematics

Index sets of computable structures. (Russian, English) Zbl 1164.03325
Algebra Logika 45, No. 5, 538-574 (2006); translation in Algebra Logic 45, No. 5, 306-325 (2006).
Summary: The index set of a computable structure \(\mathcal A\) is the set of indices for computable copies of \(\mathcal A\). We determine the complexity of the index sets of various mathematically interesting structures, including different finite structures, \(\mathbb Q\)-vector spaces, Archimedean real-closed ordered fields, reduced abelian \(p\)-groups of length less than \(\omega^2\), and models of the original Ehrenfeucht theory. The index sets for these structures all turn out to be \(m\)-complete \(\Pi_n^0\), \(\text{d-}\Sigma_n^0\), or \(\Sigma_n^0\), for various \(n\). In each case the calculation involves finding an optimal sentence (i.e., one of the simplest form) that describes the structure. The form of the sentence (computable \(\Pi_n\), \(\text{d-}\Sigma_n\), or \(\Sigma_n\)) yields a bound on the complexity of the index set. Whenever we show \(m\)-completeness of the index set, we know that the sentence is optimal. For some structures, the first sentence that comes to mind is not optimal, and another sentence of simpler form is shown to serve the purpose. For some of the groups, this involves Ramsey’s theory.

03C57 Computable structure theory, computable model theory
PDF BibTeX Cite
Full Text: DOI