Estimation of the algorithmic complexity of classes of computable models

摘要

We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models (Σ 2 0 -complete), computable models with ω-categorical theories (Δ ω 0 -complex Π ω+2 0 -set), prime models (Δ ω 0 -complex Π ω+2 0 -set), models with ω 1-categorical theories (Δ ω 0 -complex Σ ω+1 0 -set. We obtain a universal lower bound for the model-theoretic properties preserved by Marker’s extensions (Δ ω 0 .