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

• Автор: Стукачев, Алексей Ильич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Новосибирск
• Количество страниц: 81 с.

Оглавление

1 Предварительные сведения

2 Свойство униформизации в наследственно конечных

надстройках

3 Е-допустимые семейства в НУР-надстройках

§3.1 Е-регулярные семейства

§3.2 Фундаментальные множества

§3.3 Фундаментальные семейства в линейных порядках

§3.4 Д*-множества в НУР-иадстройках

4 Е-определимость специальных допустимых множеств

§4.1 О парах рекурсивно насыщенных систем

§4.2 Е-определимость классов моделей
с-простых теорий
§4.3 Е-определимость специальных допустимых множеств
Литература
Работы автора по теме диссертации

Введение
Теория допустимых множеств, возникшая в середине 60-х годов прошлого века и полудившая наиболее полное описание в классической монографии Дж. Барвайса ’’Admissible sets and structures” [22], изучает вопросы, находящиеся на стыке различных направлений математической логики: теории моделей, теории вычислимости и теории множеств. Развитие этой теории началось с обобщения теории вычислимости, при котором классическая теория вычислимости на натуральных числах становилась частным случаем теории вычислимости на ординалах. В работах С. Крипке и Р. Платека. было введено понятие допустимого ординала и предложен подход, при котором вопросы, связанные с вычислимыми свойствами некоторых объектов (множеств натуральных чисел, ординалов), превращаются в вопросы определимости этих свойств в некоторой конструктивной части теоретико-множественного универсума при помощи специальных Е-формул. Развитие теории вычислимости на допустимых ординалах отражено в книге Дж. Сакса [31]. Одним из наиболее сложных вопросов этой теории является, в частности, исследование тьюринговой сводимости на ординалах.
Важным шагом в дальнейшем развитии стали работы Дж. Барвайса, в которых было введено понятие допустимого множества с праэлементами. Допустимые множества — это модели теории KPU (аббревиатура происходит от имен создателей этой теории - Крипке и Платека, - а также от первой буквы слова ’’urelements” - ’’праэлементы”), носителями которых служат транзитивные подмножества теоретико-множественного универсума с праэлементами — объектами, не наделенными структурой множества. То,

что в качестве множества праэлементов может выступать носитель некоторой абстрактной структуры, оказывается очень важным для развития теории обобщенной вычислимости. Подход к пониманию вычислимости над абстрактной структурой как Е-определимости в допустимых множествах над этой структурой, в последнее время активно развивается. Классической монографией, в которой принят за основу такой подход, является монография Ю.Л. Ершова ’’Определимость и вычислимость” [4].
Как и в случае теории вычислимости на натуральных числах, имеется довольно много различных способов формализации обобщенной вычислимости для произвольной структуры Ш. Можно указать, например, монографию Я. Московакиса ’’Elementary induction on abstract structures” [29], где за основу принято понятие индуктивной определимости в 9)1, а также работу Р. Монтегю ” Recursion theory as a branch of model theory” [28], использующую в качестве базисного понятие определимости в некотором многосортном языке, расширяющем язык структуры ЯК. С.С, Гончаровым, Ю.Л. Ершовым и Д.И. Свириденко был предложен подход, при котором вычислимость в структуре 9Л понимается как Е-определимость в наследственно конечной списочной надстройке над моделью 971 (см. [2]). Примером еще одного подхода к обобщенной вычислимости служит формализация, предложенная омскими учеными И.В. Ашаевым, В.Я. Беляевым и А.Г. Мясниковым [1], использующая понятие некоторого абстрактного вычислительного устройства (BSS-машины), заданного на наследственно конечной списочной надстройке над структурой 9)1. Наконец, Ю.Л. Ершовым был предложен общий подход к пониманию обобщенной вычислимости на структуре 9)1 как Е-определимости в допустимых множествах над 9J1 (именно этот подход используется в работах A.C. Морозова, В.А. Руднева [15, 16], А.Н. Хисамиева, В.Г. Пузаренко [14], A.B. Роминой и др.). Следует отметить, что, как и в случае классической теории вычислимости, с точки зрения конечного результата (например, описания всех вычислимых отношений на структуре 9)1) все вышеназванные подходы оказываются эквивалентными (см., например, работу [23]).
В подходе, при котором вычислимость на абстрактной структуре трак-

КР1Г+-теорией (сигнатуры ст") называется теория, аксиомами которой являются аксиомы экстенсиональности, пустого множества, пары, объединения, схемы аксиом До-выделения, схемы аксиом фундирования (для всех формул сигнатуры ст”) и приводимой ниже схемы аксиом До-ограниченности: для любой х-специальной Д0-формулы Ф(х,у,г,тг)
Уж £ иЗуЗтт С РФ -> ЗиЗп С РУх £ г>Эу £ мФ
Пусть А — КРП-модель сигнатуры о. Согласно [4], семейство £+(И) подмножеств А называется Т.-допустимым, если для любого п £ и> и любых <Эо, • € £+(-А) выполняются следующие условия:
— А+ ^ (А, <50,... , дп_х) есть КРи+-модель сигнатуры ст"
— если д„ — £+-подмножество А+, то £}п £ £+(А).
Пусть А —допустимое множество, и Ф(ж) — £+-формула сигнатуры о и {Р} с параметрами из А. Определим £-оператор Гф : Т(А) —¥ Т(А), положив
ГФ@) = {х £ А(А,С1) М(*)}
для любого <5 С А. Из Р-позитивности формулы Ф следует монотонность оператора ГФ, то есть УСЗ,11(£2 С Гф(д) С ГФ(Р)). Таким образом,
для произвольного подмножества Р С А имеем ГФ (я) С Гф (Р) для всякого А-конечного 7г С Р, поэтому включение и Гф(тг) С Гф(Р) имеет место
тгС Р
для любой Р-позитивной формулы Ф (здесь и далее в условии вида л С Р подразумевается, что тг £ А). Обратное включение выполняется не всегда. В терминах Е-операторов сформулируем важное
Определение 3.1. Подмножество Р С А называется Е»-множеством в А, если Гф(Р) = и Гф(тг) для любой Р-позитивной Е-формулы Ф(х).
тгС р
Таким образом, если Р — ^»-множество в А, и Ф(х) — Е+-формула, то из а £ Гф(Р) следует, что а £ Гф(х) для некоторого 7г С Р. Определение £,-множества можно также сформулировать в терминах Р-негативных П-формул. А именно: подмножество Р С А будет £*-множеством в А, если для всякой Р-негативной П-формулы Ф (ж) и любого элемента а £ А выполняется следующее: если а £ Г® (ж) для всех ж С Р, то а £ Гф(Р).