Фокина Е. Б.
Индексные множества разрешимых моделей

Изучаются индексные множества класса d-разрешимых моделей и класса d-разрешимых счетно-категоричных моделей для произвольной арифметической тьюринговой степени d. Доказано, что первое из них является m-полным Σ₃^0,d , а второе — m-полным Σ₃^0,d \ Σ₃^0,d в универсальной вычислимой нумерации вычислимых моделей сигнатуры с одним бинарным предикатом.

Fokina E. B.
Index sets of decidable models

We study the index sets of the class of d-decidable structures and of the class of d-decidable countably categorical structures, where d is an arbitrary arithmetical Turing degree. It is proved that the first of them is m-complete Σ₃^0,d, and the second is m-complete Σ₃^0,d \Σ₃^0,d in the universal computable numbering of computable structures for the language with one binary predicate.

Полный текст статьи / Full texts:

• PDF file (240 KB)
• PostScript file (1 MB)