Abstract:
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^{0,d}_3$, and the second is $m$-complete $\Sigma^{0,d}_3\setminus\Sigma^{0,d}_3$ in the universal computable numbering of computable structures for the language with one binary predicate.
Fulltext:
PDF file (347 kB)
