Аннотация:
We prove that for every nontrivial language $\sigma$, the index set of the class of $d$-decidable prime computable models of $\sigma$ is $\Sigma_3^{0,d}\setminus\Sigma_3^{0,d}$-complete and that the
index set of all prime computable models of $\sigma$ is $\Pi_{\omega+2}^0$-complete.
Ключевые слова:
prime model, computable model, index sets, model-theoretic constructions, hyperarithmetic hierarchy.