О разрешимой категоричности и индексных множествах
Ключевые слова:
decidable categoricity, autostability relative to strong constructivizations, index set, real closed field, equivalence structure, strong constructivization, decidable structure.Аннотация
Структуру S называют разрешимо категоричной, если S имеет разрешимую копию и для любых разрешимых копий A и B структуры S существует вычислимый изоморфизм, действующий из A на B. С.С. Гончаров и М.И. Марчук доказали, что индексное множество разрешимо категоричных графов является $\Sigma^0_{\omega+2}$-полным. В данной работе выделено два естественных класса структур K, таких что индексное множество разрешимо категоричных структур из K имеет относительно низкую сложность в арифметической иерархии. Доказано, что индексное множество разрешимо категоричных, вещественно замкнутых полей является $\Sigma^0_3$-полным. Получено полное описание разрешимо категоричных структур эквивалентности. Доказано, что сильно конструктивизируемые структуры эквивалентности обладают $\Sigma^0_4$-полным индексным множеством. Аналогичный результат получен для разрешимо категоричных структур эквивалентности.
