RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 2003, том 42, номер 4, страницы 391–412 (Mi al37)

Эта публикация цитируется в 1 статье

Конструктивные и неконструктивные бесконечные формулы в вычислимых моделях

П. Е. Алаев

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Рассматривается переход от произвольных $L_{\omega_1\omega}$-формул к вычислимым формулам в классе вычислимых моделей. Показывается, что такой переход возможен, при этом сложность формул удваивается. Анализируется также скачок сложности при переходе от произвольного семейства Скотта из $L_{\omega_1\omega}$-формул к вычислимому семейству Скотта в фиксированной вычислимой модели, находятся его точные оценки.

Ключевые слова: вычислимая модель, вычислимая формула, семейство Скотта.

УДК: 510.5+510.67

Поступило: 27.04.2001
Окончательный вариант: 01.08.2002


 Англоязычная версия: Algebra and Logic, 2003, 42:4, 219–231

Реферативные базы данных:


© МИАН, 2024