Автоустойчивость и представимость моделей в допустимых множествах

• Автор: Ромина, Анна Валерьевна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Новосибирск
• Количество страниц: 73 с.

Оглавление
Введение.
Предварительные сведения
1 Автоустойчивость гиперарифметических моделей.
1.1 Связь автоустойчивости и ранга Скотта
1.2 Автоустойчивостъ булевых алгебр
2 Е- определимость в наследственно конечных надстройках.
2.1 Однозначность и автоустойчивость
2.2 Определимость линейных порядков над булевыми
алгебрами и булевых алгебр над линейными порядками.
Введение.
Работа посвящена обобщённой вычислимости моделей, а именно, их представимости в допустимых множествах: А} - конст-руктивизируемости и Е - определимости и существованию различных неэквивалентных эффективных представлений модели (в смысле обобщённой вычислимости).
Существуют различные подходы к обобщению понятия вычислимости. Одни возникли из попыток решать алгоритмические проблемы, относящиеся к объектам, отличным от натуральных чисел (ординалы, вещественные числа и т.д.) Другие — из построений более сложных машин Тьюринга или вычислений при условии возможности использовать информацию о принадлежности числа определенному множеству (вычисления на обобщённых машинах, вычисления с оракулом). В данной работе рассматривается два подхода к обощению

понятия вычислимости (оба, в конечном итоге, приводят к рассмотрению допустимых множеств).
Допустимые множества были введены Крипке [19] и Пла-теком [20]. Они перенесли обычную теорию рекурсии на ординалы, меньшие некоторого допустимого ординала. Первоначально допустимые ординалы были определены в терминах теории рекурсии, изложенной в стиле исчисления равенств Эрбрана-Гёделя. Позднее условия допустимости ординала были преобразованы в систему аксиом Крипке- Платека (КР), и произошёл переход от допустимых ординалов к допустимым множествам.
Результаты о том, что:
(a) наименьшее нетривиальное допустимое множество есть НКР(ш) = Ьцск , то есть множество всех подмножеств, конструируемых до уровня ординала Чёрча-Клини (наименьший нерекурсивный ординал) к, и
(b) а С ш является гиперарифмстическим тогда и только тогда, когда а 6 НУ Р(ш)
были получены Крипке и Платеком. Таким образом, существует нетривиальная связь между гиперарифметической вычислимостью и вычислимостью в допустимом множестве НГ Р{ш)

Легко видеть, что конструкция рекурсивна с оракулом #7 (лежит в Д7), и
9 = U 9г

— требуемая эквивалентность.
ТЕОРЕМА 2 Пусть — ЯЛ — Д{ - копструктивизируе-мая модель. Пусть sr(ЯЛ) = ш^к и и — ее конструкти-визация. Тогда
1. Существуют конечное константное обогащение модели ЯЛ и конечный набор с Є М<ш такой, что класс 9^ всех (с точностью до А-автоэквивалентности) Д^ -конструктивизаций (ЯЛ, с) не являеися Д{ -вычислимым.
2. Существует ординал а < такой, что ЯЛ не авто-устойчива пи в какой степени Сл7+1) для всех 7 > а.
Доказательство:
1. (от противного) В качестве такого набора подойдёт любой набор с Є М<ы такой, что г(с) = к. Для дальнейших рассужений зафиксируем набор ї Є иі<ш такой, что и(ї) = с. По 2 Є ш<и и Д} - конструктивизации и модели ЯЛ определим Д^ - конструктивизацию v% модели (ЯЛ, v{z)), полагая v~{x) ^ v{x).