Натуральные числа и обобщенная вычислимость

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

СОДЕРЖАНИЕ

Содержание
1 Предварительные сведения
1.1 Теория КР11. Примеры допустимых множеств
1.1.1 Основы теории КРи
1.1.2 Определимые подмножества, их основные свойства
1.1.3 Сохранение и абсолютность
1.1.4 Аппроксимации для Е-подмножеств. Теорема Ганди
1.2 Элементы теории моделей
1.3 Наследственно конечные надстройки
1.4 Сведения из теории полурешеток
1.5 А-Нумерации и А-коиструктивизации
1.6 О вычислимости и е-сводимости
1.7 Свойства из дескриптивной теории множеств
2 Сводимость между КРЦ-моделями
2.1 Е-Сводимость: понятие, основные свойства
2.2 Е-Скачок: определение, основные свойства
2.3 Е-Сводимость: алгебраические свойства
2.4 Обобщение Е-сводимости на класс КРИ -моделей
2.5 Существование неподвижной точки
2.6 Основные свойства неподвижной точки
2.7 Открытые проблемы
3 О счетно категоричных теориях
3.1 Введение
3.2 Об упорядочиваемости категоричной модели
3.3 Неразличимые элементы
3.4 Свертка теорий
3.5 Применения в обобщенной вычислимости
4 О подмножествах натуральных чисел
4.1 Представления семейств
4.2 О сводимости на семействах
4.3 Семейство всех Е-подмножеств и>
4.4 Соотношения между классами
4.5 Квазипроецируемые допустимые множества
4.6 Свойства моделей из классов вида К'!£} и К.}
СОДЕРЖАНИЕ З
4.7 О фридберговых нумерациях
4.8 Об определимости поля действительных чисел
4.9 Достаточно насыщенные модели
5 Дескриптивная теория множеств
5.1 Введение
5.2 Принцип редукции
5.3 О существовании универсальной функции
5.4 Универсальная функция
5.5 Доказательство теоремы
5.6 О семействе Д-подмножеств
6 Верхняя полурешетка нумераций
6.1 Определение и свойства оператора Ф
6.2 Основная конструкция
6.2.1 (/-преобразование
6.2.2 Д-преобразование
6.2.3 (До, Дг, п)-преобразование
6.2.4 (п, -преобразование
6.3 Основная теорема
Указатель обозначений
Предметный указатель
Литература
СОДЕРЖАНИЕ

Введение
Обобщенная вычислимость — новое направление математической логики, зародившееся на стыке теории вычислимости, определимости, теории моделей и теоретической информатики в работах Я. Московакиса, Дж. Сакса и Г. Крейзеля (см. [Мо8оЬоуа1ш1969, МобсЬоуй кж 1969а, Кгегзе13аекя 1965],
[МозсЬоуакМЭбЭЬ]).
Первые результаты в области вычислимости появились еще задолго до появления строгого математического понятия алгоритма. С глубокой древности до нас дошли известные многим со школьной скамьи алгоритм Евклида, “решето” Эратосфена, алгоритмы нахождения приближений трансцендентных чисел 7Г и е, метод Штурма и т. д. Одним из фундаментальных вкладов математической логики в развитие математики и науки в целом стала формализация понятия вычислимых функций и изучение их алгоритмических свойств. Эта программа получила огромный толчок в 1931 году в связи с появлением известной теоремы Гёделя о неполноте, использующей понятие примитивно рекурсивной функции, и привела к возникновению в течение первой половины 1930-х годов ряда определений вычислимых функций: по Чёрчу, Гёделю, Клини, Посту и Тьюрингу. Вскоре было доказано, что все эти подходы задают один и тот же класс математических функций, который, как принято считать (согласно тезису Чёрча), состоит в точности из “эффективно вычислимых” функций. Неформально, эти функции можно вычислить с помощью современного компьютера, игнорирующего ограничения на время вычислений и используемую память. С данным понятием тесно связано понятие вычислимо перечислимого подмножества множества натуральных чисел — множества, перечислимого посредством
1 ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ

Определение 1.8. 1. Допустимое множество А назовем Е-
перечислимым (recursively listed[Barwisel975]), если существует Е-функция / : Ord(A) -» dom(A).
2. Допустимое множество А назовем Sп-перечислимым, если существует Е-функция /, такая что Sf — и> и pf — dom(A).
3. Допустимое множество А назовем п-квазипроецируемым (в и), если существует Е-функция /, такая что Sf С ш и pf = dom(A).
4. Говорят, что допустимое множество А проецируемо в U), если существует Е-функция / : i?:+dom(A) для некоторого В С и>.
Отметим, что Ei-перечислимые допустимые множества являются Е-перечислимыми. На самом деле, Е-перечислимые допустимые множества — это те структуры, на которых фактически исследуется вычислимость на допустимых ординалах (см. [Barwisel975, Sacksl990]). Отметим также, что если допустимое множество А проецируемо в ш, то А будет 1-квазипро-ецируемым.
Предложение 1.3. Пусть А — допустимое множество и п 1. Тогда выполняются следующие условия:
1. если А является Yi-перечислимым, то А — наследственно конечная надстройка;
2. если А является Ип-перечислимым, то А будет Е-пе-речислимым для любого к п;
3. если А является п-квазипроецируемым, то А — E„+i-перечислимое допустимое мпоэюест,во;