Сложность индексных множеств некоторых классов моделей

Abstract

При исследовании вопроса о существовании вычислимой характеризации классов моделей широко используется подход, предложенный Гончаровым и Найт [1]. В рамках этого похода оценка алгоритмической сложности классов вычислимых моделей является шагом на пути к получению вычислимой характеризации соответствующих классов. В работе для универсальной вычислимой нумерации всех вычислимых моделей нетривиальной вычислимой сигнатуры найдены точные оценки в аналитической иерархии следующих индексных множеств: модели с эренфойхтовой теорией (Π1^1), модели с теорией, допускающей бесконечное число счетных моделей (Σ1^1).