Аннотация:
Рассматривается переход от произвольных Lω1ω-формул к вычислимым формулам в классе вычислимых моделей. Показывается, что такой переход возможен, при этом сложность формул удваивается. Анализируется также скачок сложности при переходе от произвольного семейства Скотта из Lω1ω-формул к вычислимому семейству Скотта в фиксированной вычислимой модели, находятся его точные оценки.
Ключевые слова:
вычислимая модель, вычислимая формула, семейство Скотта.
Образец цитирования:
П. Е. Алаев, “Конструктивные и неконструктивные бесконечные формулы в вычислимых моделях”, Алгебра и логика, 42:4 (2003), 391–412; Algebra and Logic, 42:4 (2003), 219–231