Натуральные числа и обобщенная вычислимость тема диссертации и автореферата по ВАК РФ 01.01.06, доктор физико-математических наук Пузаренко, Вадим Григорьевич

• Пузаренко, Вадим Григорьевич
• доктор физико-математических наук
• 2013

Оглавление диссертации доктор физико-математических наук Пузаренко, Вадим Григорьевич

Содержание

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

1.1 Теория KPU. Примеры допустимых множеств

1.1.1 Основы теории KPU

1.1.2 Определимые подмножества, их основные свойства

1.1.3 Сохранение и абсолютность

1.1.4 Аппроксимации для Е-подмножеств. Теорема Ганди

1.2 Элементы теории моделей

1.3 Наследственно конечные надстройки

1.4 Сведения из теории полурешеток

1.5 Â-Нумерации и А-конструктивизации

1.6 О вычислимости и е-сводимости

1.7 Свойства из дескриптивной теории множеств

2 Сводимость между KPU-моделями

2.1 Е-Сводимость: понятие, основные свойства

2.2 Е-Скачок: определение, основные свойства

2.3 Е-Сводимость: алгебраические свойства

2.4 Обобщение Е-сводимости на класс KPU-моделей

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 Квазипроецируемые допустимые множества

(2) (Ч^

4.6 Свойства моделей из классов вида К\1 и /ф

4.7 О фридберговых нумерациях

4.8 Об определимости поля действительных чисел

4.9 Достаточно насыщенные модели

5 Дескриптивная теория множеств

5.1 Введение

5.2 Принцип редукции

5.3 О существовании универсальной функции

5.4 Универсальная функция

5.5 Доказательство теоремы 5.1

5.6 О семействе Д-подмножеств

6 Верхняя полурешетка нумераций

6.1 Определение и свойства оператора Ф

6.2 Основная конструкция

6.2.1 ^-преобразование

6.2.2 /¿-преобразование

6.2.3 (R0, Ri, Я2, п)-преобразование

6.2.4 (п, ^-преобразование

6.3 Основная теорема

Указатель обозначений

Предметный указатель

Литература

Введение диссертации (часть автореферата) на тему «Натуральные числа и обобщенная вычислимость»

Введение

Обобщенная вычислимость — новое направление математической логики, зародившееся на стыке теории вычислимости, определимости, теории моделей и теоретической информатики в работах Я. Московакиса, Дж. Сакса и Г. Крейзеля (см. [Мо8сЬоуак1з1969, МоБсЬоуаИв1969а, Кге1зе18аск81965], [МозсЪоуаШЭбЭЬ]).

Первые результаты в области вычислимости появились еще задолго до появления строгого математического понятия алгоритма. С глубокой древности до нас дошли известные многим со школьной скамьи алгоритм Евклида, "решето" Эратосфена, алгоритмы нахождения приближений трансцендентных чисел 7г и е, метод Штурма и т. д. Одним из фундаментальных вкладов математической логики в развитие математики и науки в целом стала формализация понятия вычислимых функций и изучение их алгоритмических свойств. Эта программа получила огромный толчок в 1931 году в связи с появлением известной теоремы Гёделя о неполноте, использующей понятие примитивно рекурсивной функции, и привела к возникновению в течение первой половины 1930-х годов ряда определений вычислимых функций: по Чёрчу, Гёделю, Клини, Посту и Тьюрингу. Вскоре было доказано, что все эти подходы задают один и тот же класс математических функций, который, как принято считать (согласно тезису Чёрча), состоит в точности из "эффективно вычислимых" функций. Неформально, эти функции можно вычислить с помощью современного компьютера, игнорирующего ограничения на время вычислений и используемую память. С данным понятием тесно связано понятие вычислимо перечислимого подмножества множества натуральных чисел — множества, перечислимого посредством

*

1

некоторой вычислимой функции (см., например, [Soarel987]).

Кроме вышеупомянутых, выделим подход Шёнфилда ([Morozovl996, Shoenfieldl993]), использующий абстрактные вычислительные устройства с программами, написанными на языке, близком и по духу, и по содержанию к языку АССЕМБЛЕР, а также подход Е-программирования (или семантического программирования), разработанный С.С. Гончаровым, Ю.Л. Ершовым и Д.И. CBHpHfleHKo[GoncharovSviridenkol985]. "Вычислительным устройством" в семантическом программировании, в отличие от остальных формализации, в основе которых лежат алгоритмы и абстрактные вычислительные машины, служит семантика, а роль программ выполняют формулы специального вида — Е-формулы, — что позволяет определить вычислимость над абстрактной структурой Ш как £-определимость в допустимых множествах над Эта идея была предложена Ю.Л. Ершовым в 1983 году ([Ershovl983]) и нашла свое отражение в работах Р.Ю. Вайценавичюса, М.В. Коровиной, С.Г. Дворникова, И.Ш. Калимуллина, H.A. Кирпоти-ной, О.В. Кудинова, A.C. Морозова, A.B. Роминой, В.А. Руднева, А.И. Стукачева, А.Н. Хисамиева, а также автора (см., например, [Rudnevl987, Stukachevl998, KalimullinPuzarenko2009, Vaicenavichyusl989, Khisamiev2006, MorozovPuzarenko2004], [KorovinaKudinovl998a, DvornikovRudnevl986, Romina2000], [Kirpotinal993]). В связи с этим стоит упомянуть монографию "Определимость и вычислимость" ([Ershov2000]), выдержавшую два издания и ставшую фудаментальной в данной области.

Примером еще одного подхода к обобщенной вычислимости служит формализация, предложенная А.Г. Мясниковым, И.В. Ашаевым и В.Я. Беляевым ([AshaevBelyaevMyasnikovl993]),

использующая понятие абстрактного вычислительного устройства (Вб'б'-машины [В1ит81шЬ8та1е1989]), заданного на наследственно списочной надстройке над абстрактной структурой. Следуя [СопсЬагоу8ушс1епко1985], можно определить вычислимость над моделью Ш1 как Е-определимость в наследственно списочной надстройке над ЭДТ. Отметим, что наследственно списочная надстройка над 9Я вычислимо эквивалентна наследственно конечной надстройке над этой моделью — наименьшей по включению модели теории КРИ над ШТ.

Активно развивается также НЕ-логика — теория моделей на наследственно конечных надстройках, — которая является частным случаем (¿-логики (см., например, [ТгоАтоу1975, Ве1уаеуТа^з1т1979, Ве1уаеуЬуи^коуаГ1ете81епткоу1995], [Муа8шкоуКетез1епшкоу1992]). Определенные аспекты данного раздела отражены также в работах автора ([Ригагепко2002, Ригагепко2004а, Ригагепко2011]).

Аксиомы теории КР (происходит от начальных букв фамилий основателей Кпрке, Р^ек) были введены в [Р1а1ек1966]. Р. Платек определил допустимое множество как транзитивное, непустое множество, замкнутое относительно операции ТС и удовлетворяющее До-выделению и Е-рефлексии. С. Крипке независимо ввел аналогичное понятие, заменив Е-рефлексию Е-замещением ([Кпрке1964]). Завершающий вид теория допустимых множеств приобрела в работах Дж. Барвайса (см. [Ваг\у18е1974, Ват18е1975]), предложившего рассматривать допустимые множества с праэлементами (буква и в сокращении КРи — это начальная буква слова иге1еше^). Понятия До- и Ех-формул, служащие фундаментом этой теории, были введены в [Ьеуу1965].

С момента своего основания в начале 60-х годов, теория до-

пустимых множеств становится основой взаимодействия между такими областями математической логики как теорией модели, теорией вычислимости и теорией множеств. Данные теории имеют дело, в частности, с проблемами определимости.

В классической вычислимости вычислимо перечислимые множества изучаются наряду с вычислимыми функциями. В теории допустимых множеств основное внимание прежде всего уделяется изучению свойств Е-подмножеств — подмножеств, определимых Е-формулами, — служащих аналогом вычислимо перечислимых множеств. Последнее обстоятельство связано во многом с отсутствием в общем случае универсальной функции, играющей ключевую роль в классической вычислимости.

Важный подкласс допустимых множеств образуют наследственно конечные надстройки, упомянутые выше. Для наследственно конечных надстроек имеется единое представление Е-подмножеств в терминах вычислимых последовательностей, предложенное в [Уа1сепау1сЬуи81989]; синтаксическая харак-теризация всех определимых множеств в наследственно конечных надстройках дается в [Ве1уаеуТа^зНп1979] (см. также теоремы 1.5, 1.6). Идея представления Е-предиката в виде вычислимой дизъюнкции Э-формул сигнатуры модели, лежащей в основании наследственно конечной надстройки, активно используется при изучении вычислимости на наследственно конечных надстройках (см., например, [ЕгбЬоу2000, Когоуша1992, АзЬаеуВе^аеуМуаяшкоуШЗ, Б^касЬеуШЗ]). Данный метод активно используется и в настоящей работе.

В главе 2 вводится понятие Е-сводимости на допустимых множествах, согласованное (в некотором вполне естественном смысле) с такими понятиями, активно исследуемыми различ-

ными учеными, как Е-определимость модели в допустимом множестве, и производная сводимость на структурах, свойством семейства быть вычислимым в допустимом множестве и т.д. Эту сводимость можно рассматривать как меру сложности вычислимости на допустимых множествах. Основным результатом данной главы является следующее утверждение.

Теорема. Пусть А — допустимое множество с носителем А. Тогда существует ориентированный граф ШТд без петель с носителем А, удовлетворяющий следующим условиям (п ^

1. А эквивалентно относительно Т>-сводимости ЮТ(9Яа)/

2. А удовлетворяет принципу п-Р, если и только если НЕ(ШТд) также удовлетворяет п-Р, где Р — одно из следующих основных свойств: перечислимости, унифор-мизации, отделимости, тотальной продолжимости, существования универсальной ({0; 1}~значной) функции.

Эта теорема носит в большей мере методологический характер: для изучения большинства аспектов вычислимости на допустимых множествах, исследуемых в настоящей работе, достаточно ограничиться рассмотрением наследственно конечных надстроек — наименьших по включению допустимых множеств. С другой стороны, этот результат демонстрирует выразительную силу наследственно конечных надстроек. Если же проводить параллели между алгоритмическими системами и допустимыми множествами, то для того, чтобы допустимое множество трансформировать в наследственно конечную надстройку, следует фактически произвести замену всех вычислений ('множеств') структурами данных ('праэлементами').

Вводится также понятие Е-скачка, которое позволяет с единых позиций исследовать свойства Е-определимости и определимости моделей в допустимых множествах. В этой главе также строится допустимое множество, в котором любая определимая модель будет Е-определимой. А именно,

Теорема. Существует допустимое множество любой наперед заданной мощности, эквивалентное относительно £-сводимости своему И-скачку.

Данная теорема имеет серию приложений как в рамках вычислимости на допустимых множествах, так и в классической вычислимости. К примеру, наличие неподвижной точки оператора Е-скачка влечет существование допустимого множества, в котором группа всех перестановок, вычислимых в данном допустимом множестве, будет Е-определимой. С одной стороны, этот результат можно рассматривать как обобщение одного из основных результатов из [Могогоу2002], при доказательстве которого использовалась гипотеза о существовании недостижимого кардинала; с другой стороны, он контрастирует с известным результатом А. Нуртазина[]Чш1;агт1976], гласящим, что группа всех вычислимых перестановок не имеет вычислимой копии. Кроме того, счетный граф для которого ЮТ (65) будет неподвижной точкой оператора Е-скачка, имеет спектр, замкнутый вниз относительно операции тьюрингова скачка.

В 2011 году, когда уже статья автора [Ригагепко2011а] была подготовлена к печати, А. Монталбан ([Моп1а1Ьап2011]) анонсировал доказательство существования неподвижной точки в предположении множества О*. В настоящей работе этот результат доказывается при естественных предположениях (более точно, КР+'существование кардинала (Лшск)+').

Мы обсуждаем, к тому же, соотношения между данной сводимостью и сводимостями, введенными ранее. Похожая сводимость была введена в [Могогоу2004]. Производные структуры отношения Е-определимости активно исследуются другими учеными в последнее время ([К1ша1шеу2006, 31;икасКеу2007, Б1;икасЬеу2009]).

В главе 3 обсуждаются алгоритмические свойства наследственно конечных надстроек над моделями счетно категоричных теорий. В работе [Ег8ЬоуРигагепко31икасЬеу2011] предлагается обобщение классической вычислимости на несчетные структуры, причем в качестве основного класса структур выдвигаются плотные линейные порядки. В связи с этим естественным образом возникает проблема 'универсальности' данного класса (см. также [ЕгзЬоу1998]):

Проблема. (Ю.Л.Ершов (1996)) Если теория Т имеет несчетную модель, Е-определимую в НЕ(ШТ) над моделью Ш с-простой теории, то теория Т имеет также несчетную модель, Е-определимую в ]№(£) над некоторым плотным линейным порядком £.

Строгое определение с-простой теории формулируется ниже. Здесь отметим лишь, что такая теория счетно категорична и имеет одну с точностью до вычислимого изоморфизма вычислимую модель, являющуюся, к тому же, разрешимой.

Основным результатом данной главы служит следующая теорема, из которой в частности следует негативное решение вышеупомянутой проблемы.

Теорема. Существует с-простая теория Т конечной сигнатуры такая, что ни для какого плотного линейного по-

рядка £ не существует 71есчетных моделей теории Т, Е-определимых в ЕПК(£).

Основная идея доказательства этой теоремы состоит в построении теории, у разрешимой модели которой отсутствует бесконечное вычислимое множество упорядоченно неразличимых элементов. В этой главе также обсуждаются следующие проблемы для счетно категоричных теорий: упорядочиваемо-сти моделей таких теорий с сохранением свойства счетной категоричности, счетно категоричного обогащения теоретико-модельной пары моделей таких теорий со свойством ограниченной двухкардинальности. В качестве основного способа построения моделей используется метод Фрайссе. Вариации данного метода приводятся в настоящей работе.

В связи с основной проблемой этой главы следует упомянуть работы [81;икасЬеу2004, Б1;икасЬеу2010] (см. замечание в конце главы.)

Глава 4 посвящена изучению семейств подмножеств натуральных чисел. Взаимосвязи между семействами всех Д-под-множеств конечных ординалов и Т-сводимостью впервые были установлены в [1111с1пеу1987]. Однако, как следует из результатов настоящей работы, по семейству всех Д-подмножеств конечных ординалов невозможно однозначно восстановить семейство всех таких Е-подмножеств. Как оказалось, в этом случае наиболее адекватной будет е-сводимость. Впервые соотношения между е-сводимостью и свойствами семейства £-подмножеств натуральных ординалов допустимых множеств отмечены в [Могогоу2000]. Здесь дается полное описание всевозможных семейств Е-подмножеств в терминах именно е-сводимости.

Теорема. 1. В любом допустимом множестве А семейство Т,-подмножеств и) представимо в виде для некоторого е-идеала X.

2. Для любого е-идеала X существует модель ШТ такая, что УХ совпадает с семейством всех Е-подмножеств си в ЮТ (ПК). Кроме того, эту модель можно выбрать так, что сагс!(ШТ) = сагс!(уХ).

Данная теорема была доказана независимо и одновременно А. С. Морозовым [МогогоуРигагепко2004].

К тому же, автором доказывается свойство минимальности моделей, построенных при доказательстве предыдущей теоремы.

Теорема. Для любых е-идеала X и кардинала а ^ сагс1(их) существует модель ШТо; определимая в любом допустимом множестве мощности а, в котором семейство всех Е-подмножеств совпадает с УХ.

В данной главе также вводится отношение Е-сводимости на семействах подмножеств натуральных чисел, согласованное со сводимостью на допустимых множествах, изучаемой в главе 2. Отличительной особенностью этой сводимости является то, что семейство рассматривается как абстрактный математический объект без фиксации какого-либо определенного представления. Две предыдущие теоремы доказываются в настоящей работе как следствия характеризационной теоремы для данной сводимости на семействах. Приводится серия примеров допустимых множеств, в которых отсутствует универсальная Е-функция. В настоящей работе построение таких примеров основано на трансляции определенных принципов с идеалов на допустимые множества. Кроме того, подробно исследуются

свойства допустимых множеств, построенных по идеалам е-степеней. Попутно строится пример допустимого множества А, не имеющего разрешимой (даже позитивной) вычислимой А-нумерации семейства всех Е-подмножеств. (Напомним, что в классическом случае существует разрешимая (даже однозначная) вычислимая нумерация семейства всех вычислимо перечислимых множеств[Рпес1Ье^1958, МаГсеу1965].)

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

Теорема. Поле вещественных чисел определимо в допустимом множестве А, если и только если семейство всех подмножеств натуральных чисел определимо в А.

В завершение главы 4 обсуждается проблема, поставленная Ю.Л. Ершовым в [ЕгзЬоу2000] (замечание 3.4.3), касающаяся достаточно насыщенных моделей.

Проблема. В любой достаточно насыщенной модели реализуется любой (не обязательно полный) арифметический тип из формул с ограниченным числом перемен кванторов над конечным подмножеством ее носителя. Является ли это условие эквивалентным достаточной насыщенности?

Здесь дается негативное решение вышеупомянутой проблемы.

Теорема. Существует модель модельно полной теории, в которой реализуются все арифметические типы над конечными множествами, не являющаяся достаточно насыщенной.

Этой тематике также посвящены работы, написанные совместно с И. Ш. Калимуллиным (см. [КаНпшШпРигагепко2004, КаНти1ИпРигагепко2009]), а также [КЫ8агшеу2006].

В главе 5 изучаются детальные соотношения между свойствами из дескриптивной теории множеств на допустимых множествах. Как и для большинства подходов к вычислимости, семейства всех Е-предикатов на допустимых множествах конечных сигнатур (играющих роль вычислимо перечислимых множеств) не замкнуты относительно дополнения, что вынуждает рассматривать всевозможные свойства, позволяющие обойти это препятствие. Большинство рассматриваемых здесь свойств изучалось и ранее, однако исследовать соотношения между ними на допустимых множествах было предложено автором. Основной результат данной главы имеет следующий вид:

Теорема. Для свойств на допустимых множествах справедливы следующие соотношения:

Все переходы в диаграмме, приведенной выше, строгие. В случаях (0-6, 10) можно выбрать наследственно конечные надстройки над вычислимыми моделями. В случаях (7-9) таких допустимых множеств не существует. Все модели для

(8) имеют неарифметическую сложность. В случаях (7,9) можно выбрать наследственно конечные надстройки над 0'-вычислимыми моделями.

За исключением переходов 0 и 1 (допустимые множества для перехода 0 подробно изучены в работах Дж. Барвайса и Дж. Сакса; пример для перехода 1 был предложен в книге [ЕгзЬоу2000], а его обоснование фактически приведено в [Б1;икас11еу1998]), в обосновании и (или) построении примеров автор принимал непосредственное участие: на данный момент все примеры для переходов 3, 5, 8 были построены автором; примеры для перехода 2 впервые были предложены автором в [Ригагепко2000] (существование универсальной Е-функции в допустимых множествах из этого класса следует из результатов [ЕгзИоу2000]); для перехода 4 для почти всех ныне известных примеров отсутствие свойства редукции было доказано методом, предложенным автором; для перехода 6 известны лишь две вычислимые структуры, одна из которых была предложена автором; для перехода 7 пример О'-вычислимой структуры был построен совместно с И. Ш. Калимуллиным [КаНпшШпРигагепко2004].

В конце главы приводится пример допустимого множества, у которого семейство всех А-подмножеств не вычислимо. (Следует напомнить, что семейство всех вычислимых множеств вычислимо [МисЬшк1963].)

Отметим, что кроме упомянутых выше ученых, эти свойства изучались также Р .Ю. Вайценавичюсом, М. В. Коровиной, А. Н. Хисамиевым, В. А. Рудневым ([Уа1сепау1сЬуи81989, Когоуша1992, 11ис1пеу1987, КЫва1шеу2001]).

Глава 6 посвящена изучению свойств 'нумераций' на допустимых множествах. Понятие таких 'нумераций' было введено

Ю.Л. Ершовым. Отличительной особенностью этого понятия является то, что сводимость одной 'нумерации' к другой осуществляется Е-предикатом, а не эффективной функцией, как в классической вычислимости. Последнее согласовывается со значением Е-предикатов в теории допустимых множеств. В настоящей работе описаны с точностью до изоморфизма полурешетки классов 'нумераций' конечных множеств на допустимых множествах специального вида. В [ЕгзЬоу1975] было введено понятие с-универсальной полурешетки и показано, что в предположении континуум-гипотезы, полу решетка нумераций А;-элементного множества, к > 1, будет с-универсальной полурешеткой мощности континуума. В частности, все такие полурешетки изоморфны полурешетке т-степеней. В [Ра1уи1йп1975] было показано, что континуум-гипотезу можно опустить.

Перейдем к формулировке основного результата данной главы.

Теорема. Пусть Т — с-простая теория конечной сигнатуры иШ — счетная модель этой теории. Тогда полурешетка 'нумераций' к-элементных множеств каЮТ(9Я); к > 1, изоморфна полурешетке т-степеней.

Данная теорема отвечает на следующие вопросы:

Проблема. (Ю.Л.Ершов(1996)) Будет ли полурешетка т-степеней допустимого множества над счетным

мноэюеством изоморфна полурешетке обычных т-степеней натуральных чисел?

Проблема. (Ю.Л.Ершов(2007)) Будет ли полурешетка т-степеней наследственно конечной надстройки ЕПР((ф,

над множеством рациональных чисел относительно естественного порядка изоморфна классической полурешетке т-степеней натуральных чисел?

Основные определения, методы и конструкции, используемые в этой работе, содержатся в главе 1. В ней также излагаются некоторые ключевые идеи, применяемые в доказательствах основных результатов.

Автор выражает благодарность своему учителю академику Ю.Л. Ершову, под чьим огромным влиянием была выполнена данная работа; чл.-корр. РАН С.С. Гончарову и д.ф.-м.н. A.C. Морозову за оказанную поддержку, представителям казанской логической школы д.ф.-м.н. М.М. Арсланову и особенно своему соавтору д.ф.-м.н. И.Ш. Калимуллину, зарубежным учёным проф. Б. Куперу, проф. Дж. Макферсону, проф. А. Пиллаю и проф. А. Сорби, обсуждения с которыми сыграли решающую роль в появлении этого манускрипта, а также участникам логических семинаров Новосибирского Государственного Университета и Института математики имени С.Л. Соболева СО РАН; отдельно хотелось бы отметить участников семинара по теории моделей под руководством д.ф.-м.н. Е.А. Палютина, особенно д.ф.-м.н. C.B. Судоплатова, под влиянием чьих работ автору удалось получить один из основных результатов, а также к.ф.-м.н. A.A. Викентьева за проявленный интерес к работам автора.

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

В данной главе излагаются основные сведения из различных областей математической логики и теории вычислимости, а также обозначения, используемые автором в остальных главах. Основы математической логики и теории алгоритмов содержатся в [ЕгзЬоуРа1у^1п1987].

Символ ^ будем использовать для равенства по определению.

Через □ будем обозначать конец доказательства. Более точно, этот символ будет означать, что полное доказательство может быть легко (как правило) восстановлено, исходя из имеющихся в тексте рассуждений.

Если / — операция, то через 6/ и р/ будем обозначать область определения и область значения данной операции соответственно, а через Г/ будем обозначать график функции /. Иногда операции будем отождествлять с их графиками.

Пусть / — операция и X С <5/; тогда через / I4 X будем обозначать сужение функции / на множество X.

Записи / будут означать, что отоб-

ражение / является инъективным и сюръективным соответственно.

Запись / : А^В служит сокращением для "/ является взаимно однозначным отображением А на

Через ш будем обозначать множество всех натуральных чисел или натуральных ординалов (последнее будет ясно из контекста).

Если X — множество произвольной природы, то через 'Р(Х) будем обозначать степень данного множества, т.е. множество всех его подмножеств.

Если Я — бинарное отношение, то через Рг^К) и Ргг(Я)

будем обозначать проекции R на первую и вторую координаты соответственно.

Пусть Rq, Ri, ..., Rn-i, п G ш — множества. Тогда через R0 х Ri х ... х Rn-i будем обозначать декартово произведение этих множеств (в случае, когда п — О, ,будем считать, что декартово произведение равняется {0}.)

Для каждого п € ш и множества R через Rn будем обозначать п-ую декартову степень множества R, а через R<U) — семейство (Jn<w Rn всех конечных кортежей элементов из R.

Для каждого п £ ш и множества R через R^ будем обозначать множество всех кортежей элементов из R длины п, имеющих попарно различные координаты, а через R— семейство U n<UJRZ-

Через

. будем обозначать конечные последовательности (более точно, это сокращения для последовательностей вида (а0,..., afc-i), (60, • • •, k-i), (с0,..., cm_i), где к, I, т £ ш.)

Для произвольного множества X, обозначение card(X) будет использоваться для кардинального числа данного множества (напомним, что если X — конечное множество, то card(X) — это число элементов множества X).

Для любого множества X, через idx будем обозначать тождественное отображение на X. Если из контекста ясно, чему равна область задания тождественной функции, то символ X будем опускать.

Через ~ будем обозначать сигнатурное отношение равенства.

Допустимые множества будем обозначать большими латинскими буквами А, В, С, ... (возможно, с индексами) из начала алфавита, а их носители — dom(A), dom(B), dom(C), ...

соответственно (также с соотвествующимн индексами), если не оговорено особо. Произвольные структуры будем обозначать большими готическими буквами 21, (Г, ... (возможно, с индексами), а их носители — dom(2l), dom(*B), dom((£) соответственно (также с соответствующими индексами), вновь если не оговорено особо. В ряде случаев будем задавать модель его носителем с операциями и отношениями на ней (например, (L, — множество L с заданным на нем отношением Теорию модели WI будем обозначать через ТЬ(ШТ). В теории моделей мы будем придерживаться терминологии, принятой в [Barwisel975, Hodgesl993, ChangKeislerl973].

Пусть (р(хо, • • •, Xk-i), к > 0 — формула сигнатуры модели 21 (возможно, с параметрами из dorn(21)). Тогда через •. •, Xk-i] будем обозначать предикат, определимый формулой (р, а именно,

{(Ьо, • • •, Ьк-1> е dorn (21)| 21 f= <р(Ь0}..., Ьк^)}.

Иногда данное множество будем обозначать как <¿>(21).

Пусть 21 — модель сигнатуры сг и s G er. Через s21 будем обозначать отношение, операцию или выделенный элемент, соответствующий сигнатурному символу s в 21.

Если не оговорено особо, мы ограничимся здесь рассмотрением лишь структур конечных сигнатур (это касается как моделей, так и допустимых множеств).

1.1 Теория KPU. Примеры допустимых множеств.

Напомним здесь основные понятия и конструкции теории KPU. В теории допустимых множеств мы будем придерживаться терминологии, принятой в [Ershov2000, Barwisel975].

1.1.1 Основы теории КР11.

Сначала напомним аксиомы теории КР11 Крипке-Платека с праэлементами. Пусть а — фиксированная сигнатура, содержащая двухместный символ £ для отношения принадлежности и одноместный символ и для множества праэлементов.

Экстенсиональность: \/хУу({~"\1(х) А ""\]{у)) —> ех) ^ (ге у)) (х и у)))-

Аксиома пары: \/хУуЭг((х <Е г) А (у е г));

Аксиома объединения: УхЗу(~"\](у) А\/г\/ю(((г £ х) А (т € г)) у)))-

Аксиома праэлементов: \/х(Х](х) £ х));

Аксиома пустого множества: Зге^ТДж) А\/у~'(у £ х));

Схема аксиом фундированности: \/!?(Зх(р(х, —>

Зх(ф, А Уу((у ех)^ Ху, -?)))),

для любой формулы <р сигнатуры а, в которой у не встречается, где — кортеж, состоящий из всех свободных переменных формулы </?, отличных от х (переменные у и х различны).

Для формулировки остальных аксиом нам понадобится определение До-формулы.

Определение 1.1. Класс Ао~формул сигнатуры а — это наименьший класс формул данной сигнатуры, содержащий атомарные формулы и замкнутый относительно следующих логических операций: V, А, \/у £ Зу Е где £ — терм сигнатуры сг, а у — переменная, не встречающаяся в £ (здесь и

в дальнейшем \/у £ £... и Зу £ £... служит сокращением для Уу((у £ £) ~^ • • •) и £ £) Л ...) соответственно).

Схема аксиом Ао-выделения: —> Зу(~"\](у) А

Уги((ги £ у) <-)• ((ги е х) А (р(ги,1?))))), для любой А0-формулы (р сигнатуры сг, в которую у не входит свободно, где — кортеж, состоящий из всех свободных переменных формулы </?, отличных от ш (переменные х и у различны);

Схема аксиом Ад-выборки: У^Уг^Ц^а;) —»

(Уш £ хЭу<р(ии, у, —>• ЗкУш £ хЗт/ € и(р(ъи, у, ^))),

для любой Ад-формулы </? сигнатуры сг, в которую и не входит свободно, где — кортеж, состоящий из всех свободных переменных формулы </?, отличных от ю, у (переменные х, у и и попарно различны).

Для любой КРЦ-модели 21 элементы иа[хо] называются праэлементами, а скш1(21)\иа[а;о] — 'множествами'. На множестве праэлементов может быть задана алгебраическая система (модель) с операциями и отношениями.

К примеру, система аксиом КРИ позволяет доказать существование декартова произведения а х Ь для любых 'множеств' а и Ъ.

Из этого списка аксиом также следует, что для любых элементов х,у существуют пара {ж,?/}, упорядоченная пара (х,у) ^ {{ж}, {а:, ?/}}, объединение и ж, значения обычных теоретико-множественных операций х и у, х П у, х \ у.

Из аксиомы экстенсиональности следует, что 'множество', не содержащее элементов, т.е. пустое 'множество', единственно.

Из схемы аксиом фундированности непосредственно вытекает, что не существует 'множеств' ао, а\,..., ап, п Е ш, для которых выполняется следующее: ао £ а1 £ • • • £ € ао-

Система аксиом КР сигнатуры сг, содержащей символ но не содержащей и, может быть получена из системы аксиом КРи путем замены подформул и(£) на « ¿), где £ — терм. Другими словами, модели КР — это модели КР11, не содержащие праэлементов.

Теория КРи может быть рассмотрена как фрагмент теории ZF с праэлементами, поэтому в рамках данной теории мы можем определить понятия транзитивного 'множества' ('множества', содержащего все свои элементы как подмножества) и ординала (транзитивного 'множества', все элементы которого также являются транзитивными 'множествами'). Отметим, что для любого 'множества' х существует транзитивное замыкание ТС (ж) — наименьшее по включению транзитивное 'множество', содержащее х в качестве подмножества (более того, ТС(ж) будет Е-функцией). То, что ординалы в КРЦ-модели линейно упорядочены отношением принадлежности и каждое непустое формульное подмножество ординалов имеет наименьший элемент, можно получить, используя схему аксиом фундированности [Ваг\у1зе1975, ЕгзЬоу2000]. КРЦ-Модель 21 называется допустимым множеством, если отношение € вполне упорядочивает множество всех ординалов Огс1(21) данной КРи~модели. Такое определение, предложенное в книге [ЕгвЬоу2000], является абстрактным, по сравнению с определением из [Вагш8е1975], в том смысле, что оно замкнуто относительно взятия изоморфных образов. Однако любое допустимое множество будет изоморфно некоторому допустимому множеству в смысле [Ват18е1975], что следует из предложе-

ния Н.8.1[Вагд\ч8е1975]. Ординал а называется допустимым, если Огс1(А) = а для некоторого допустимого множества А. КРи~Модель, не являющуюся допустимым множеством, иногда будем называть нестандартной КР11 -моделью.

Приведем серию примеров (а также некоторые способы построения) допустимых множеств.

1. Как уже было сказано выше, любая стандартная модель теории Цермело-Френкеля ZF с праэлементами будет допустимым множеством.

2. Пусть N — произвольный бесконечный кардинал, а ШТ — любая структура сигнатуры т (возможно, пустая) с носителем М. Тогда модель Н^(ШТ) сигнатуры г и {II, £} с носителем {а е ¥м | сагс1(ТС(а)) < К} (здесь Vм — универсум над М(И.1[Вагул8е1975])) будет допустимым множеством и Огс1(Нк(ШТ)) = N. Таким образом, любой бесконечный кардинал будет допустимым ординалом.

3. Допустимое множество Нш(ШТ) называется наследственно конечной надстройкой над моделью и обозначается как №(9Я). Это допустимое множество является наименьшим по включению допустимым множеством над моделью ШТ. Носитель этой наследственно конечной надстройки можно также определить следующим образом:

• Я^о(М) = 0;

• НРп+1(М) = ГШ(М и Я^П(М)) и Я^П(М) (здесь Vш(Х) — множество всех конечных подмножеств множества X), п < и);

. Я^(М) = и я^п(м).

п<и

Тогда HF(M) U М будет искомым.

Класс наследственно конечных надстроек играет весьма важную роль в данной работе.

4. Пусть и)\ — первый несчетный ординал. Тогда допустимое множество HWl(9JT) над моделью ШТ называется наследственно счетной надстройкой над ШТ и обозначается как НС(ШТ) (в этом случае также допускается пустая структура ШТ).

5. Пусть ШТ — произвольная модель конечной сигнатуры ст. Тогда найдется наименьшее по включению допустимое множество Н¥Р(ШТ), содержащее ШТ в качестве элемента, причем множеством его праэлементов будет множество с!от(ШТ). Более того, его носитель может быть конструктивно найден в любом таком допустимом множестве А, а именно, существует Е-функция L : dom(A) х Ord(A) —> dom(A) такая, что оно совпадает с L(9JT, ао) ^ (Ua<aoL№«)>^0> ДЛЯ ao = СЫ(Н¥Р(ШТ)) (см. [Barwisel975, Ershov2000]). Рассмотрим И¥Р(9Т), где ОТ -стандартная модель арифметики. Множество ординалов Ord(HYP(OT)) (называемое также высотой) этого допустимого множества будет совпадать с первым неконструктивным ординалом и)iK (называемым также ординалом Черча-Клини): а семейства Д- и Е-подмножеств натуральных чисел в HYP(9t) будут совпадать с классами А\ и П{ аналитической мерархии соответственно (определение аналитической иерархии можно найти, например, в [Rogers1972]). Напомним, что подмножество натуральных чисел называется гиперарифметическим, если оно принадлежит Д}. Подробно свойства допустимых множеств

вида Н¥Р(Ш1) изучаются в [Barwisel975].

6. Пусть 21 — КРЦ-модель предикатной сигнатуры, а О — наибольший вполне упорядоченный начальный сегмент множества Огс1(21) его ординалов. Тогда модель УУ/(21) 21 С {а е с!от(21) | гк(а) £ О}, называемая вполне упорядоченной частью модели 21, будет допустимым множеством (предложение 2.7.4[ЕгзЬоу2000]).

7. Если А — допустимое множество, то

{а е аот(А) I ТС ({а}) П \]А[х] = 0}

будет носителем допустимого множества, называемого чистой частью А. Подмножества чистой части иногда будем называть "чистыми".

В качестве следствия отметим, что ординал «о — допустимый, если и только если 1Ьао (У;8<ао Ь(0,/5), 0) допустимо. Допустимые множества такого вида называются конструктивными. Множество Ь(0,/3) будем обозначать просто через Ц/З), где (3 — ординал.

На самом деле, чистая часть любого допустимого множества с ординалом, равным ш, совпадает с ЮТ(0) — наименьшим по включению допустимым множеством (П.2.12[Ваг\у1зе1975]).

Отметим также, что если А — допустимое множество над моделью то замыкание множества М праэлементов относительно значений теоретико-множественных термов 0, {-}1 и и2 будет равняться в точности НГ(М) и М.

1.1.2 Определимые подмножества, их основные свойства.

В настоящей работе под вычислимостью на допустимых множествах будем понимать определимость с помощью формул

специального вида.

В отличие от классического случая, основным объектом изучения на допустимых множествах является предикат, имеющий эффективное представление, а не функция. Во многом это связано как со способами их задания, так и с отсутствием в общем случае универсальной функции. Как будет показано ниже, основные способы задания предикатов, к тому же, будут обладать свойством недетерминированности.

Пусть а Э {е} — сигнатура, а 21 — КРИ-модель данной сигнатуры.

Определение 1.2. 1. Класс Е -формул сигнатуры а — это наименьший класс, содержащий До-формулы и замкнутый относительно следующих логических операций: v, а, Зу, Vу € Зу е где £ — терм сигнатуры сг, а у — переменная, не входящая в

2. Класс П-формул сигнатуры а — это наименьший класс, содержащий До-формулы и замкнутый относительно следующих логических операций: v, а, Уу, \/у е Зу е где £ — терм сигнатуры <т, а у — переменная, не входящая в 1

3. Е 1~Формулой называется формула, имеющая вид Зхсро, где (¿>о ~ До-формула.

Роль вычислимых и вычислимо перечислимых предикатов в нашем подходе будут играть Д- и Е-предикаты соответственно.

Определение 1.3. Пусть 1 ^ п < ш. п-Местный предикат на 21 называется

1. Y>-(Т1-)предикатом, если он определим некоторой Е-(П-)формулой (возможно, с параметрами);

2. ¿^-предикатом, если он является одновременно и Е-, и П-предикатом;

3. Ei-предикатом, если он определим некоторой Ei-форму-лой (возможно, с параметрами).

Одноместные предикаты, как обычно, будем называть подмножествами.

Определение 1.4. Частичная операция на 21 называется (частичной) Т,-функцией, если ее график является Е-предика-том на 21.

Определение 1.5. n-Местная Е-функция F на 21 называется всюду определенной или тотальной, если 5F = dom(2l)n.

Таким образом, в рамках данного подхода за основу понятия Д-предиката берется теорема Поста, а Е-функции — теорема о графике (формулировки вышеупомянутых теорем можно найти, например, в [Rogersl972]).

Приведем примеры основных А-предикатов и Е-функций, используемых в данной работе.

• Ord(a;) (а; — ординал);

• Nat(a;)(^ Ord(:r) А Уу < х((у & 0) V 3z(y ^ z U {z}))) (x — натуральный ординал);

• TC(a?) — наименьшее транзитивное 'множество', содержащее х в качестве подмножества;

• sp(x) {у Е ТС(х) | U(y)} — носитель (support) элемента х;

• гк(ж) = 8ир{гк(?/) + 1 | у е х} — ранг элемента х.

Как обычно, (ж, у) {ж, у}}, () ^ 0, (я) ^ х,

(Х\) Х2, • • • 5 ^ {{^1, • • • ? Хп}.

Через Г и г* будем обозначать частичные Е-функции, действующие на упорядоченных парах и выдающие левую и правую координаты соответственно. Для каждого п ^ 1, через рг-г, 1 ^ г ^ п, будем обозначать проекции на соответствующие координаты. Они могут быть определены индуктивно следующим образом: рг} ^ 1(1, рг™ ^ г*, рг™ ^ рг™-1 о Г, г < п, п > 1.

Как и в классическом случае, достаточно рассматривать только подмножества допустимых множеств, поскольку функция упорядоченной пары определима До-формулой в любой КРи-модели, причем эту формулу можно выбрать не зависящей от рассматриваемой КР11-модели. Иногда мы будем использовать другое представление упорядоченного кортежа:

(а0,..., ап-\) ^ щ) \ I < п}, п е и;

(другими словами, представление в виде функции из собственного начального сегмента натуральных чисел, называемого длиной и обозначаемого как 1Ь). При таком представлении функция рг^((ао,..., ап-1)) ^ щ, I < п, не зависит от п.

Через Е(21п) и Д(21п) будем обозначать семейство всех п-местных Е- и Д-предикатов на 21 соответственно. При п = 1 индекс будем опускать.

Сейчас приведем несколько эквивалентных определений Е-подмножеств в любой КРИ-модели.

Предложение 1.1. Пусть 21 — КРИ-модель и В С. с1от(21). Тогда следующие условия эквивалентны:

*

(1) В — Е -подмножество в 21; (п) В — Ех-подмножество в 21;

(ш) В = 5Р для некоторой частичной Е-функции Р;

(1у) В — рР для некоторой частичной Е -функции F;

(у) В = 0 или В = рР для некоторой всюду определенной Т*-функции Г.

Доказательство. (1) —(11) следует из принципа Е-рефлек-сии (предложение 1.4.3[Ват1зе1975]). (и) —> (у) Пусть В — непустое Ех-подмножество и Зу<ро(х, у) определяет множество В, где </?о — До-формула. Зафиксируем Ьо Е В. Тогда определим Е-формулу ф(х,у) следующим образом:

(ЗиЗу((х « {и, у)) А ((<£>о(и, у) Д (у « и))У

("(ж — упорядоченная пара) А (у « Ьо))).

Нетрудно проверить, что Е-формула ф(х,у) определяет график некоторой тотальной функции Г и В = рР. (у) —> (1у) Если В = 0, то Е-формула ~ а;) определяет график нигде не определенной функции, область значений которой пуста. Если же В 0, то условие (1у), очевидно, выполняется. (1у) —>■ (1), (111) —>• (1) Пусть Е-формула ф(х, у) определяет график функции Р. Тогда формулы Зхф(х, у) и Зуф(х, у) определяют множество В для (1у) и (ш) соответственно. (1) —> (Ш) Предположим, что множество В определимо Е-формулой 9{х). Тогда формула (0(х) А (х рз у)) определяет график некоторой функции Р, область определения которой совпадает с В. □

Бесконечное Е-подмножество В в 21 может и не иметь всюду определенной Е-функции, 'перечисляющей' его без повторений (т.е. являющейся 1-1-функцией из с!от(21) на В). Приведем несколько примеров.

Примеры 1.1. 1. Любое допустимое множество А всегда имеет счетное А-подмножество со С Огс1(А).

2. Если допустимое множество А таково, что со < Огс1(А), то со не может быть 'перечислено' без повторений никакой всюду определенной Е-функцией, иначе выполнялось бы с!от(А) £ ск>т(А), по теореме Е-замещения (теорема 1.4.6[Ваг-ш8е1975]). Более того, если а £ ёот(А), то а не может быть 'перечислено' без повторений никакой всюду определенной Е-функцией.

3. Существует наследственно конечная надстройка над счетной моделью конечной сигнатуры, в которой имеется бесконечное Е-подмножество В С ш, не имеющее бесконечных кобесконечных Е-подмножеств (см. теорему 2.1[МогогоуРигагепко2004]). В частности, В нельзя 'перечислить' без повторений никакой всюду определенной Е-функцией или даже частичной Е-функцией с областью определения со.

К проблеме существования 'перечислений' на допустимых множествах вернемся ниже. Сейчас же введем в рассмотрение иерархию определимых предикатов на КРЦ-моделях.

Определение 1.6. Определим индукцией по к < и класс формул сигнатуры а:

1. Е0 = По = До;

2. Tik+i-формулой называется формула вида 3?/Фо, где Фо — Щ-формула, а у — переменная;

3. Uk+i-формулой называется формула вида УуФо, где Фо — Sfc-формула, а у — переменная.

Определение 1.7. Пусть 1 ^ п < и, а к < со.

1. n-Местный предикат на 21 называется Е&-(Щ-) предикатом, если он определим некоторой Е^-(П^-)формулой (возможно, с параметрами).

2. n-Местный предикат на 21 называется Ак-предикатом, если он является одновременно и Е^-, и Щ-предикатом.

Классы всех Е^-, Щ-, Д^-предикатов на KPU-модели 21 будем обозначать через Е®, П^, Д^ соответственно, k ^ 1. Будем говорить, что предикат R С dom(2l)n, п ^ 1, определим (формулен) в 21, если R 6 UmE^.

Под Е^ -функцией будем понимать частичную функцию на dom(2l), график которой принадлежит Е^, п ^ 1.

В случае, когда в 21 имеется универсальный Е^-предикат (если 21 — KPU-модель конечной сигнатуры, данное свойство выполняется; см., например, [Ershov2000, Barwisel975]), классы Efc- и Щ-предикатов на 21 различны. А именно, справедлив следующий вариант теоремы об иерархии (см. [Rogers1972]).

Теорема 1.1. Пусть 21 — KPU-модель. Тогда между классами иерархии определимых предикатов на 21 выполняются следующие соотношения:

Ч°П?...

Более того, все включения строгие. Кроме того, для всех т ^ 1 справедливы следующие условия:

1. для всех п ^ 1 существует п + 1-арный ^^-(И^-)предикат, универсальный для всех п-арных Т^-^П.^-)предикатов;

2. для всех п ^ 1 не существует п + 1 -арного Д^-предиката., универсального для всех п-арных предикатов;

3. замкнут относительно А, У, Зх, Зх £ а и не замкнут относительно

4■ П^ замкнут относительно А, У, Ух, Ух £ а и не замкнут относительно

5. А^ замкнут относительно А, У,

6. Я(х 6 если и только если найдется

Уъ • • ■, Уп) Е &1, для которого Я — {(а1,...,ап) \ ЗуЯ(у,аъ...,ап)}, п ^ 1;

7. Я{х\,... ,хп) £ если и только если найдется Я{У,УЪ- ■ • ,Уп) Е для которого Я = {(аь ..., ап) | УуЯ(у,аь .. • ,ап)}; п ^ 1.

Ниже будут приведены примеры допустимых множеств А, для которых классы П^, Д^, т ^ 1, не замкнуты относительно ограниченных кванторов, не указанных в пунктах 3, 4, 5 теоремы 1.1 (см. замечание после предложения 1.3). Для этого определим вспомогательную иерархию семейства определимых предикатов на А (п ^ 1):

• — наименьший класс множеств, содержащий и замкнутый относительно Л, V, Зх, Зх Е а, Ух Е а;

*

• Я е если и только если е

• т>а = 5а п т>а.

Список литературы диссертационного исследования доктор физико-математических наук Пузаренко, Вадим Григорьевич, 2013 год

Список литературы

[AshKnight2000] С. Ash, J. F. Knight. Computable Structures and the Hyperarithmetical Hierarhy, North-Holland, (2000).

[AshaevBelyaevMyasnikovl993] И. В. Ашаев, В. Я. Беляев, А. Г. Мясников. Подходы к теории обобщенной вычислимости, Алгебра и логика, 32, 4(1993), 349-386.

[Avdeev2011] P.P. Авдеев. О допустимых множествах вида И¥Р(ШТ) над рекурсивно-насыщенными моделями, Сибирский Математический Журнал, 52, 6(2011), 1199— 1220.

[Barwisel974] J. Barwise. Admissible sets over Models of Set Theory, Generalized Recursion Theory, Amsterdam, North-Holland, 1974, 97-122.

[Barwisel975] J. Barwise. Admissible Sets and Structures. Springer-Verlag, Berlin, Göttingen, Heidelberg, 1975.

[BelyaevTaitslinl979] В.Я.Беляев, М.А.Тайцлин. Об элементарных свойствах экзистенциально замкнутых систем, Успехи мат. наук, 34, 2(1979), 43-107.

[BelyaevLyutikovaRemeslennikovl995] В. Я. Беляев, Е. Е. Лю-тикова, В. Н. Ремесленников. Категоричность конечно порожденных алгебраических систем в HF-логике, Алгебра и логика, 34, 1(1995), 12-32.

[BlumShubSmalel989] L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: Np-completeness, recursive functions and

universal machines, Bull. Am. Math. Soc., 21, 1(1989), 146.

[ChangKeislerl973] С. C. Chang, H. J. Keisler. Model Theory, North-Holland, Amsterdam-London, (1973).

[CHMM2011] B.F. Csima, V.S. Harizanov, R. Miller, A. Montalban. Computability of Frai'sse Limits, J. Symb. Log., 76, 1(2011), 66-93.

[Degtevl998] А. И. Дегтев. Рекурсивно перечислимые множества и сводимости табличного типа, Москва, Наука, 1998.

[DvornikovRudnevl986] С. Г. Дворников, В. А. Руднев. О теореме Райса в допустимых множествах, Восьмая Всесоюзная Конференция по Математической Логике, Тезисы докладов, Москва, 1986, 56.

[Ershovl975] Ю. JI. Ершов. Верхняя полурешетка нумераций конечного множества, Алгебра и логика, 14, 3(1975), 258284.

[Ershovl977] Ю. JI. Ершов. Теория нумераций. Наука, Москва, 1977.

[Ershovl980] Ю. JI. Ершов. Проблемы разрешимости и конструктивные модели. М., Наука, 1980.

[Ershovl983] Ю. JI. Ершов. Принцип Е-перечисления, Доклады АН СССР, 270, 5(1983), 792-794.

[Ershovl985] Ю. JI. Ершов. Е-определимость в допустимых множествах, Докл. АН СССР, 285, 4(1985), 792-795.

[Ershovl993] Ю. Л. Ершов. Теорема Левенгейма-Скулема-Мальцева для определимых моделей, Логические методы в информатике (Вычислительные системы, 148), 917, Институт математики СО РАН, Новосибирск, 1993.

[Ershovl998] Yu.L. Ershov.E-Defiriability of algebraic structures, in Handbook of recursive mathematics, Vol. 1, ed's Yu.L. Ershov, S.S. Goncharov, A. Nerode, J.B. Remmel, Elsevier, 1998, 235-260.

[Ershov2000] Ю. Л. Ершов. Определимость и Вычислимость. Научная книга, Новосибирск, Экономика, Москва, 2000.

[ErshovGoncharovl999] Гончаров С.С., Ершов Ю.Л. Конструктивные модели. Новосибирск, Научная книга, 1999.

[ErshovPalyutinl987] Ершов Ю.Л., Палютин К.,Математическая логика. М., Наука, 1987.

[Friedbergl958] Friedberg R.M. Three Theorems on recursive enumeration: I, Decomposition, II, Maximal Set, III, Enumeration without duplication, J. of Symb. Log., 23(1958), 309-316.

[Friedmanl969] Friedman H. Algorithmic procedures, generalized Turing algorithms and elementary recursion theory, Logic Colloqium'69 (R.O. Gandy and C.E.M. Yates eds), North-Holland, 1971, 361-390.

[Friedman 1973] Friedman H. Countable models of set theories, Cambridge Summer School in Math. Logic (Lecture Notes in Math., vol 337), Springer, 1973, 539-573.

[GoncharovSviridenkol985] С. С. Гончаров, Д. И. Свириденко. Е-программирование, в сб.: "Логико-математические проблемы МОЗ" (Вычислительные системы, 107), Новосибирск, Ин-т матем. СО АН СССР, 1985, 3-29.

[GHKMMS2005] S. S. Goncharov, V. S. Harizanov, J. F. Knight, С. McCoy, R. Miller, R. Solomon. Enumerations in computable structure theory, Annals of Pure and Applied Logic 136 (2005), 219-246.

[Gorbunovl999] В. А. Горбунов. Алгебраическая теория квазимногообразий. Научная книга, Новосибирск, 1999.

[Hodgesl993] W. Hodges. Model Theory. Cambridge University Press, Cambridge, 1993.

[Jockushl972] C. G. Jockush. Degrees in which the recursive sets are uniformly recursive, Canad. J. Math., 24(1972), 10921099.

[JockushSoarel972] C. G. Jockusch, Jr., R. I. Soare. П® classes and degrees of theories, Trans. Amer. Math. Soc., 173(1972), 33 - 56.

[Khisamiev2001] A.H. Хисамиев. О квазирезольвентных моделях и Б-моделях, Алгебра и логика, 40, 4 (2001), 484-499.

[Khisamiev2004] А. Н. Хисамиев. О верхней полурешетке Ершова Сиб. мат. журнал, 45, 1(2004), 211-228.

[Khisamiev2006] А. Н. Хисамиев. О Е-подмножествах натуральных чисел над абелевыми группами, Сибирский математический журнал, 47, 3(2006), 695-706.

[Khisamiev2010] А.Н. Хисамиев. E-Ограниченные алгебраические системы и универсальные функции, I, Сиб. мат. журнал, 51, 1(2010), 217-235.

[Khisamiev2010a] А.Н. Хисамиев. E-Ограниченные алгебраические системы и универсальные функции, I, Сиб. мат. журнал, 51, 3(2010), 676-693.

[KiersteadRemmell983] Н.А. Kierstead, J.В. Remmel. Indiscernibles and decidable models, J. Symb. Log., 48, 1(1983), 21-32.

[Kirpotinal993] N. A. Kirpotina. Elementary equivalence in the language of list superstructures, Sib. Adv. Math., 3, 4(1993), 46-52.

[Korovinal992] M. V. Korovina. Generalised computability of real functions, Sib. Adv. Math., 2, 4(1992), 1-18.

[KorovinaKudinovl998a] M. V. Korovina, О. V. Kudinov. New approach to computability, Sib. Adv. Math., 8, 3(1998), 5973.

[KreiselSacksl965] G. Kreisel, G. Sacks. Metarecursive sets, J. Symbolic Logic, 30(1965), 318-338.

[Kripkel964] S. Kripke. Transfinite recursion on admissible ordinals, I, II (abstracts), J. Symbolic Logic, 33(1964), 161162.

[Levyl965] A. Levy. A hierarchy of formulas in set theory, Memoir Amer. Math. Soc., 57(1965).

[Mal'cevl965] Мальцев А.И. Алгоритмы и рекурсивные функции, М., Наука, 1965.

[Marchenkovl971] С. С. Марченков. О минимальных нумерациях систем рекурсивно перечислимых множеств, ДАН СССР, 198, 3(1971), 530-532.

[Montalban2011] A. Montalban. A fixed point for the jump operator on structures, arXiv: 1106.0908.

[Morozovl996] А. С. Морозов. Машины Шёнфилда: методические рекомендации, Новосибирск, НГУ, 1996.

[Morozov2000] А. С. Морозов. Е-Множество натуральных чисел, не перечислимое с помощью натуральных чисел. Сибирский математический журнал, 41 (6): 1404-1408, 2000.

[Morozov2002] Морозов А.С., О представимости групп Е-представимых перестановок над допустимыми множествами, Алгебра и логика, 41, 4 (2002), 459-480.

[Morozov2004] А. С. Морозов. Об отношении Е-сводимости между допустимыми множествами, Сиб. мат. журнал, 45, 3 (2004), 634-652.

[Morozov2006] Морозов, А.С. Элементарные подмодели параметризуемых моделей. Сибирский математический журнал, 47, 3(2006), 595-612.

[Moschovakisl969] Y. N. Moschovakis. Abstract computability and invariant definability, J. Symb. Log., 34(1969), 605-633.

[Moschovakis1969a] Y. N. Moschovakis. Abstract first order computability I, Trans. Am. Math. Soc., 138(1969), 427464.

[Moschovakisl969b] Y. N. Moschovakis. Abstract first order computability II, Trans. Am. Math. Soc., 138(1969), 465504.

[Muchnikl963] A. Muchnik. Solution of Post reduction problem and of certain other problems in theory of algorithms, Amer. Mat.Soc., 29(1963), 197-215.

[MyasnikovRemeslennikovl992] А. Г. Мясников, В. H. Ремесленников. Допустимые множества в теории групп, Алгебра и логика, 31, 4(1992), 413-433.

[Nurtazinl976] А. Т. Нуртазин. О конструктивных группах, в Докл. Всесоюзной конференции по мат. логике, Кишинев, 1976, с. 106.

[Odifreddi 1989] P. Odifreddi. Classical recursion theory. The theory of functions and sets of natural numbers. Studies in Logic and the Foundations of Mathematics, 125, Amsterdam etc.: North-Holland, 1989.

[Palyutinl975] E. А. Палютин. Дополнения к статье Ю.Л. Ершова "Верхняя полурешетка нумераций конечного множества", Алгебра и логика, 14, 3(1975), 284-287.

[Platekl966] R. Platek. Foundations of recursion theory, Doctoral Dissertation and Supplement, Stanford, CA: Stanford Univ., 1966.

[Ricel956] H. G. Rice. On completely recursively enumerable classes and their key arrays, J. of Symb. Log., 21, 3(1956), 304-308.

[Rogersl972] X. Роджерс. Теория рекурсивных функций и эффективная вычислимость. Мир, Москва, 1972.

[Romina2000] А. В. Ромина. Определимость булевых алгебр в HF-надстройках, Алгебра и логика, 39, 6(2000), 711-719.

[Rudnevl986] В. А. Руднев. Об универсальной рекурсивной функции на допустимых множествах, Алгебра и логика, 25, 4(1986), 425-435.

[Rudnevl987] В. А. Руднев. О существовании неотделимой пары в рекурсивной теории допустимых множеств. Алгебра и логика, 27, №1(1987), 48-56.

[Sacksl976] G. Sacks. Countable admissible ordinals and hyperdegrees, Advances in Math., 20, 2(1976), 213-262.

[Sacksl990] Sacks G. Higher Recursion Theory. Springer-Verlag, Berlin, Gottingen, Heidelberg, 1990.

[Selmanl971] A. L. Selman. Arithmetical reducibilities I, Z. Math. Logik Grundlag. Math., 17(1971), 335-350.

[Shoenfieldl993] J. R. Shoenfield. Recursion theory, Lecture Notes in Logic, 1, Berlin, Springer-Verlag, 1993.

[Soarel987] R.I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Berlin, Heidelberg, New York, London, Paris, Tokyo, Springer-Verlag, 1987.

[Sorbi2000] A. Sorbi. Open problems in the enumeration degrees. Cholak, Peter A. (ed.) et al, Computability theory and its applications. Current trends and open problems. Proceedings of a 1999 AMS-IMS-SIAM joint summer research conference, Boulder, CO, USA, 2000, 309-320.

[SoskovSoskova2009] Soskova A., Soskov I. A jump inversion theorem for the degree spectra, J. Log. Comput., 13,1(2009), 199-215.

[Stukachevl998] А. И. Стукачев. Теорема об униформизации в наследственно конечных надстройках, в сб.: "Обобщенная вычислимость и определимость" (Вычислительные системы, 161), Новосибирск, Ин-т матем. СО РАН, 1998, 3-14.

[Stukachev2004] А.И. Стукачев. Е-Определимость в наследственно конечных надстройках и пары моделей, Алгебра и Логика, 43, 4(2004), 459-481.

[Stukachev2007] А. И. Стукачев. О степенях представимостей моделей, I, Алгебра и логика, 46, 6(2007), 763-788.

[Stukachev2009] А. И. Стукачев. Теорема об обращении скачка для полу решетки Е-степеней, Сиб. Электрон. Мат. Изв., 6(2009), 182-190.

[Stukachev2010] А.И. Стукачев. Е-Определимость несчетных моделей с-простых теорий, Сиб. мат. журнал, 51, 3(2010), 649-661.

[Trofimovl975] В. Ю. Трофимов. Об определимости в алгебраически замкнутых системах, Алгебра и логика, 14, 3(1975), 320-327.

[Vaicenavichyusl989] Р. Ю. Вайценавичюс. О необходимых условиях существования универсальной функции на допустимом множестве. Математическая логика и применения, 6(1989), Вильнюс, 21-37.

Работы автора по теме диссертации.

[ErshovPuzarenkoStukachev2011] Yu.L. Ershov, V.G. Puzarenko,

A.I. Stukachev. HF-Computability, in Computability in Context: Computation and logic in the real world (eds. S.B. Cooper and A. Sorbi), 2011, 169-242.

[KalimullinPuzarenko2004] И. Ш. Калимуллин, В. Г. Пузаренко

B.Г. О принципах вычислимости на допустимых множествах, Математические труды, 7, 2(2004), 35-71.

[KalimullinPuzarenko2009] И. Ш. Калимуллин, В. Г. Пузаренко. О сводимости на семействах, Алгебра и логика, 48, 1(2009), 31-53.

[MorozovPuzarenko2004] А. С. Морозов, В. Г. Пузаренко. О £-подмножествах натуральных чисел, Алгебра и логика, 43, 3(2004), 291-320.

[Puzarenko2000] В. Г. Пузаренко. О вычислимости над моделями разрешимых теорий. Алгебра и логика, 39, №2(2000), 170-197.

[Puzarenko2002] В. Г. Пузаренко.О теории моделей на наследственно конечных надстройках, Алгебра и логика, 41, 2(2002), 199-222.

[Puzarenko2002a] В. Г. Пузаренко.О разрешимых вычислимых А-нумерациях, Алгебра и логика, 41, 5(2002), 568-584.

[Puzarenko2003] В. Г. Пузаренко. Допустимые множества: элементарное описание и вычислимость. Материалы III Конференции молодых ученых СО РАН, посвященной М. А. Лаврентьеву, Новосибирск, 2003, 39-44.

[Puzarenko2003a] В. Г. Пузаренко. Обобщенные нумерации и определимость поля M в допустимых множествах, Вестник НГУ: сер. мат., мех., инф., 3, 2(2003), 107-117.

[Puzarenko2004] В. Г. Пузаренко. Допустимые множества: элементарное описание и вычислимость (часть 2). Материалы IV Конференции молодых ученых СО РАН, посвященной М. А. Лаврентьеву, Новосибирск, 2004, 34-36.

[Puzarenko2004a] В. Г. Пузаренко. О теореме Левенгейма-Сколема-Мальцева для lHIF-структур, Алгебра и логика, 43, 6(2004), 748-757.

[Puzarenko2005] В. Г. Пузаренко. К вычислимости на специальных моделях, Сиб. мат. журнал, 46, 1(2005), 185208.

[Puzarenko2008] В. Г. Пузаренко. О семействе вычислимых множеств на допустимых множествах, Сиб. Электр. Мат. Изв., 5(2009), 1-7.

[Puzarenko2009] В. Г. Пузаренко. Об одной сводимости на допустимых множествах, Сиб. мат. журнал, 50, 2(2009), 415-429.

[Puzarenko2009a] В. Г. Пузаренко. Об одной полурешетке нумераций, Математические труды, 12, 2(2009), 170-209.

[Puzarenko2010] В. Г. Пузаренко. О свойствах из дескриптивной теории множеств, Алгебра и логика, 49, 2(2010), 238262.

[Puzarenko2010a] В. Г. Пузаренко. Об одной полурешетке нумераций II, Алгебра и логика, 49, 4(2010), 498-520.

список литературы

[Ригагепко2011] В. Г. Пузаренко. О существовании насыщенных моделей, Сиб. мат. журнал, 52, 2(2011), 393-399.

[Ри2агепко2011а] В.Г. Пузаренко. Неподвижные точки оператора скачка, Алгебра и логика, 50, 5(2011), 615-646.

[Ригагепко2012] В.Г. Пузаренко. О счетно категоричных теориях, Алгебра и логика, 51, 3(2012), 358-384.