СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ

АННОТАЦИИ

Оценивается алгоритмическая сложность индексных множеств
естественных классов вычислимых моделей:
конечных вычислимых моделей ($\Sigma^0_2$-полное), вычислимых моделей с
$\omega$-категоричными теориями ($\Delta^0_\omega$-сложное
$\Pi^0_{\omega+2}$-множество), простых моделей ($\Delta^0_\omega$-сложное
$\Pi^0_{\omega+2}$-множество), моделей с
$\omega_1$-категоричными теориями ($\Delta^0_\omega$-сложное
$\Sigma^0_{\omega+1}$-множество).
Получена универсальная нижняя оценка для теоретико-модельных свойств,
сохраняющихся при маркеровских расширениях ($\Delta^0_\omega$).