Index sets of decidable models. (Russian, English) Zbl 1164.03326
Sib. Mat. Zh. 48, No. 5, 1167-1179 (2007); translation in Sib. Math. J. 48, No. 5, 939-948 (2007).
Summary: We study the index sets of the class of \(d\)-decidable structures and of the class of \(d\)-decidable countably categorical structures, where \(d\) is an arbitrary arithmetical Turing degree. It is proved that the first of them is \(m\)-complete \(\Sigma_3^{0,d}\), and the second is \(m\)-complete \(\Sigma_3^{0,d}\setminus\Sigma_3^{0,d}\) in the universal computable numbering of computable structures for the language with one binary predicate.
MSC:
03C57 | Computable structure theory, computable model theory |
03D45 | Theory of numerations, effectively presented structures |
03C35 | Categoricity and completeness of theories |