Abstract:
We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models ($\Sigma_2^0$-complete), computable models with $\omega$-categorical theories ($\Delta_\omega^0$-complex $\Pi_{\omega+2}^0$-set), prime models ($\Delta_\omega^0$-complex $\Pi_{\omega+2}^0$-set), models with $\omega_1$-categorical theories ($\Delta_\omega^0$-complex $\Sigma_{\omega+1}^0$-set). We obtain a universal lower bound for the model-theoretic properties preserved by Marker's extensions ($\Delta_\omega^0$).