Abstract

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

Translated title of the contributionОценка алгоритмической сложности классов вычислимых моделей
Original languageEnglish
Pages (from-to)512-523
Number of pages12
JournalSiberian Mathematical Journal
Volume49
Issue number3
DOIs
Publication statusPublished - May 2008

Keywords

  • computable model
  • index set

Cite this