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

На правах рукописи

ПУЗАРЕНКО Вадим Григорьевич

НАТУРАЛЬНЫЕ ЧИСЛА И ОБОБЩЕННАЯ ВЫЧИСЛИМОСТЬ

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Новосибирск 2013

1 * фев гт

005049769

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук

Научный консультант: доктор физико-математических наук, профессор, академик РАН Ершов Юрий Леонидович

Официальные оппоненты: Перетятькин Михаил Георгиевич, доктор физико-математических наук, профессор, Министерство образования и науки республики Казахстан, комитет науки, республиканское государственное предприятие Институт математики и математического моделирования, главный научный сотрудник

Ремесленников Владимир Никанорович, доктор физико-математических наук, профессор, Омский филиал Федерального государственного бюджетного учреждения науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук, заведующий лабораторией

Селиванов Виктор Львович, доктор физико-математических наук, профессор, Федеральное государственное бюджетное учреждение науки Институт систем информатики им. А.П. Ершова Сибирского отделения Российской академии наук, главный научный сотрудник

Ведущая организация: федеральное государственное автономное образовательное учреждение высшего профессионального образования "Казанский (Приволжский) федеральный университет"

Защита диссертации состоится «25» апреля 2013 г. в «14» ч. на заседании диссертационного совета Д003.015.02 при Федеральном государственном бюджетном учреждении науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук, находящегося по адресу: 630090, Новосибирск, пр. Акад. Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

Автореферат разослан марта 2013 г.

Ученый секретарь диссертационного совета ___

кандидат физико-математических наук X / ) А.И. Стукачев

Общая характеристика работы

Постановка задачи и актуальность темы диссертации. Обобщенная вычислимость — новое направление математической логики, зародившееся на стыке теории вычислимости, определимости, теории моделей и теоретической информатики в работах Г. Крейзеля. Дж. Сакса и Я. Московакиса (см. [41, 45, 46, 47]).

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

Кроме вышеупомянутых, выделим подход Шёнфилда ([12, 50]), использующий абстрактные вычислительные устройства с программами, написанными на языке, близком и по духу, и по содержанию к языку АССЕМБЛЕР, а также подход ^-программирования (или семантического программирования), разработанный С.С. Гончаровым, Ю.Л. Ершовым и Д.Н. Свириденко[10]. "Вычислительным устройством" в семантическом программировании, в отличие от остальных формализации, в основе которых лежат алшритмы н абстрактные вычислительные машины, служит семантика, а роль программ выполняют формулы специального вида — Е-формулы, — что позволяет определить вычислимость над абстрактной структурой М? как £-определимость в допусти-

пых множествах над ОТ. Эт.1 идея была предложена Ю.Л. Ершовым в 1983 голу (["]) и нашла свое отражение б работах Р.Ю. Вайценавичю-са, С.Г. Дворникова, И.Ш. Калимуллина, H.A. Кирпотиной, .VI.В. Коровиной, О.В. Кудинова, A.C. Морозова, A.B. Роминой, В.А. Руднева, А.И. Стукачева, А.Н. Хпсамиева, а также автора (см., например, [4, 5, 19, 20, 21, 29, 38, 40, 53, 54]). В связи с этим следует упомянуть монографию Ю.Л. Ершова "Определимость и вычислимость" ([9]; здесь же можно найти все используемые понятия), выдержавшую два издания и ставшую фундаментальной в данной области.

Примером еще одного подхода к обобщенной вычислимости служит формализация, предложенная И.В. Ашаевым, В.Я. Беляевым и А.Г. Мясниковым ([1]), использующая понятие абстрактного вычислительного устройства (BSS-машины [32]), заданного на наследственно списочной надстройке над абстрактной структурой. Следуя [10], можно определить вычислимость над моделью 9Л как Е-определимость в наследственно списочной надстройке над ОТ. Отметим, что наследственно списочная надстройка над ОТ вычислимо эквивалентна наследственно конечной надстройке над этой моделью — наименьшей по включению модели теории KPU над ОТ.

Активно развивается также HF-логика — теория моделей на наследственно конечных надстройках, — которая является частным случаем ш-логшт (см., например, [2, 3, 16, 26]). Определенные аспекты данного раздела отражены также в работах автора ([56, 59, 65]).

Аксиомы теории KP (происходит от начальных букв фамилий основателей Kripke, Platek) были введены в [49]. Р. Платек определил допустимое множество как транзитивное, непустое множество, замкнутое относительно операции ТС и удовлетворяющее До-выделению и £-рефлексии. С. Крипке независимо ввел аналогичное понятие, заменив £-рефлексию ^-замещением ([42]). Завершающий вид теория допустимых множеств приобрела в работах Дж. Варвайса (см. [30, 31]), предложившего рассматривать допустимые множества с праэлементами (буква U в сокращении KPU — это начальная буква слова Urelemeiit). Понятия До~ и Si-формул, служащие фундаментом этой теории, были введены в [43].

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

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

Важный подкласс допустимых множеств образуют наследственно конечные надстройки, упомянутые выше. Для наследственно конечных надстроек имеется единое представление Е-нодмножеств в терминах вычислимых последовательностей, предложенное в [4]; синтаксическая характеризация всех определимых множеств в наследственно конечных надстройках дается в [2] (доказательство этого утверждения приводится в предварительных сведениях диссертации; см. теоремы 1.5, 1.6). Идея представления Е-предиката в виде вычислимой дизъюнкции 3-формул сигнатуры модели, лежащей в основании наследственно конечной надстройки, активно используется при изучении вычислимости на наследственно конечных надстройках (см., например, [1, 9, 21, 39]). Данный метод активно используется и в настоящей работе.

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

В работе [33] Ю.Л. Ершовым было высказано предположение о том, что имеется равномерный перенос классической вычислимости на произвольные мощности, который осуществляется наследственно конечными надстройками над плотными линейными порядками, причем этот перенос универсален в следующем смысле:

Проблема 1. Если теория Т имеет несчетную модель, ^-определимую в ЮТ(9Л) над моделью 9Л (—простой теории, то теория Т имеет также несчетную модель, Е -определимую о НР(£) над некоторым плотным линейным порядком

С одной стороны, вычислимость на наследственно конечных надстройках над моделями <—простых теорий (напомним, что теория на-

зывается с-иростой, если она разрешима, полна, модельно полна, счетно категорична и имеет разрешимое множество полных формул) совпадает с классической (даже если модель несчетна); с другой стороны, с-простая теория имеет единственную с точностью до вычислимого изоморфизма вычислимую модель, являющуюся, к тому же, разрешимой. Подробно мотивация этой гипотезы изложена в [34].

В связи с данной проблемой следует упомянуть работы [22, 25].

С моделями с-щюстых теорий тесно связана проблема существования элементарных расширений для определимых моделей. В общем случае, теорема об элементарных расширений не справедлива даже для наследственно конечных надстроек над несчетными моделями (см., например, [50, 59]). В работе [8] изучается класс моделей, названных достаточно насыщенными, дня которого справедлива теорема об элементарных расширений для определимых моделей в случае, когда наследственно конечные надстройки строятся над моделями ш-стабильных или счетно категоричных теорий. Там же формулируется следующая проблема (см. замечание 3.4.319]):

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

С моделями с-простых теорий связана еще одна проблема, которая обсуждается в диссертации, также сформулированная Ю.Л. Ершовым.

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

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

В работах [6, 18| дается алгебраическое описание полурешетки т-стеиенон натуральных чисел. В [55] показано, что полурешетка т-степеней дистрибутивна в любом допустимом множестве. Там же показано, что подмножества натуральных чисел образуют идеал т-степеней в

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

В диссертации также исследуются свойства семейств подмножеств натуральных чисел (более точно, дается решение проблемы, сформулированной A.C. Морозовым и автором), соотношения между свойствами дескриптивной теории множеств на вычислимо перечислимых подмножествах в допустимых структурах, а также изучается сводимость на допустимых множествах, характеризующая меру их вычислимости.

Проблемы »определимости подмножеств множества конечных ординалов и в допустимых множествах изучались и ранее (см. [20, 55]), однако там исследовались взаимосвязи Г-сводимости с S-опреде.тимос-тыо. Было показано, что семейство Д-подмножеств ш в допустимом множестве замкну то относительно Т-сводимости и операции Ф сочленения. Для каждого Г-идеала Т были построены примеры допустимых множеств, в которых семейство Т-степеней Д-подмножеств образует идеал 1. Однако далеко не всегда по идеалу Г-степеней Д-подмножеств можно однозначно восстановить семейство Е-подмножес гв. Впервые взаимосвязи между- с—сводимостью и семейством Е-подмножеств ш и допустимых множествах были отмечены в [13].

Значение натуральных чисел в вычислимости на допустимых множествах во многом обуславливает название этой диссертации.

Основные результаты диссертации.

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

2. Доказано существование неподвижной точки оператора скачка на допустимых множествах и на струк турах. Ослабленная версия этого результата была получена одновременно и независимо А. Мон-талбаном.

3. Был построен контрпример к гипотезе Ю.Л. Ершова об универсальности плотных линейных порядков.

4. Были охарактеризованы всевозможные семейства подмножеств натуральных чисел, состоящих из вычислимо перечислимых множеств на допустимых структурах. Результат был получен одновременно и независимо профессором A.C. Морозовым.

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

6. Найден критерий определимости поля вещественных чисел в терминах определимости семейства всех подмножеств натуральных чисел.

7. Построен контрпример к гипотезе Ю.Л. Ершова о характеризации достаточно насыщенных моделей как арифметически насыщенных моделей.

8. Найдены всевозможные соотношения между свойствами из дескриптивной теории множеств на допустимых структурах. Большинство примеров было построено автором самостоятельно; кроме того, использовался результат, полученный совместно с И.Ш. Кали-муллиным.

9. Подтверждена гипотеза Ю.Л. Ершова об изоморфизме полурешеток классических пг-степеней и пг-степеней в наследственно конечных надстройках над моделями специального вида.

Научная новизна. Все основные результаты диссертации являются новыми.

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

Методы исследования. Для доказательства основных результатов 1, 4-6, 8, 9 применяются в основном методы вычислимости на наследственно конечных надстройках. Кроме вышеупомянутых методов, для доказательства основного результата 2 используются методы Барвайса, разработанные для моделей бесконечных языков, а для доказательства результатов 3, 7 — методы конструктивных моделей. В работе также активно используются методы теории степеней и теории моделей.

Апробация работы. Результаты диссертации в период с 2001 но 2012 год были представлены на международных конференциях в Новосибирске, Казани, Сиене (Италия), Хельсинки (Финляндия), Ниймегене (Нидерланды), Суонси (Великобритания), Чикаго (США). В частности,

на международных конференциях «Мальцевские чтения» (Новосибирск, 2003 (совместно с И.Ш. Калимуллиным), 2004, 2006, 2010 и 2011 г.г.), «Computability in Europe» (Сиена, 2007 г.; совместно с Ю.Л. Ершовым и А.И. Стукачевым) и международной конференции «Алгебра и математическая логика», посвященной 100-летию В.В. Морозова (Казань, 2011 г.) автором были сделаны пленарные доклады но теме диссертации. Результаты неоднократно докладывались на семинарах Института математики СО РАН и НГУ «Теория вычислимости», «Теория моделей» и «Алгебра и логика», на логических семинарах К(П)ФУ (Казань), Университетов в Дармштадте (Германия), Лидсе (Великобритания), Гейдельберге (Германия), Вашингтоне (США) и на общеинститутском семинаре Института математики СО РАН.

Публикации. Основные результаты по теме диссертации опубликованы в форме статей в ведущих отечественных изданиях [52]-[67], которые входят в перечень ВАК российских рецензируемых научных журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученых степеней доктора и кандидата наук.

Структура и объем диссертации. Диссертация состоит из шести глав и введения, указателя терминов, предметного указателя и списка литературы. Она изложена на 333 страницах текста, набранного в ре-дакционно-издательской системе 1Я]еХ2£, библиография содержит 99 наименований.

Содержание диссертации.

Общая структура диссертации. Диссертации разбита на главы, которые в свою очередь подразделяются на параграфы, а некоторые подразделяются на подпараграфы. Основные результаты каждой главы (теоремы и их следствия) явным образом сформулированы во введении. Нумерация всех результатов (теорем, лемм, следствий), а также определений сквозная внутри главы и состоит из двух чисел: первое число — номер главы и второе — порядковый номер внутри главы. Нумерация формул одинарная: число определяет порядковый номер.

Введение

В данной главе приведена характеристика основных результатов работы.

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

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

Глава 2. Сводимость между КРТ1—моделями В данной главе вводится понятие Е-сводимости на допустимых множествах, согласованное (в некотором вполне естественном смысле) с такими понятиями, активно исследуемыми различными учеными, как Е-определимость модели в допустимом множестве, и производная сводимость на структурах, свойством семейства быть вычислимым в допустимом множестве и т.д. -Здесь и далее в скобках указана позиция утверждения или определения в диссертации.

Определение 1. (2.1) Будем говорить, что допустимое множество А Е-сводится к допустимому множеству В (и обозначать как А ¡В), если существует отображение V из носителя В на носитель А такое, что справедливо соотношение 1/-1(Е(А2)) С Е(В2).

Данное отношение сводимости появилось как ослабленная форма основного понятия из [15|. Эту сводимость можно рассматривать как меру сложности вычислимости на допустимых множествах, при этом наименьшей оказывается классическая вычислимость (которая может быть отождествлена с Ш(0)). Оказалось, что отношение Е-сводимости согласовано с Е-определимостью моделей в допустимых множествах.

Предложение 1. (фактически доказано Ю.Л.Ершовым) Пусть Ш1 — модель конечной сигнатуры иА - допустимое множество. Тогда Ш А, если и только если НР(9Л) СЕ А.

Введенное таким образом отношение сводимости на допустимых множествах является рефлексивным и транзитивным, поэтому отношение (называемое отношением Е-эквивалентности), определенное как

А=5В»(АС!: В)&(В А).

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

Теорема 1. (2.1) Пусть А — допустимое множество с носителем А. Тогда существует ориентированный граф без петель с носителем Л. удовлетворяющий следующим условиям (п > 1):

1. А. Ту-эквивилентно НР(ОЛ^):

2. А удовлетворяет принципу п-Р. если и только еслг* ШШ^ШТа. ) также удовлетворяет п-Р. где Р — одно из следующих основных

свойств: перечислимости, униформизации, отделимости, тотальной продолжимости, существования упиверс(ыъной ({0:1}-значний) функции.

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

Непосредственно из теоремы 1 вытекает

Теорема 2. (2.2) Пусть А, В — допустимые множества. Тогда А Ек В, если и только если ОТ А влечет ОТ В, для любой модели ОТ конечной сигнатуры.

Таким образом, преложенная здесь сводимость на счетных допустимых множествах ведет себя так же, как и сводимость, введенная в [28]. На классах допустимых множеств произвольной мощности она себя ведет так же, как и сводимость, предложенная в [23].

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

Пусть А — допустимое множество с носителем А. Определим допустимое множество ,7е(А), называемое 'Е-скачком допустимого множества А, как №((.4.1/)), где и С А3 — £-предикат, универсальный для класса всех бинарных Е-предикатов на А.

Определим итерированный Е-скачок следующим образом: ^¿°'(А) = А, ^¿"+1)(А) = ^(^¿"'(А)) при п < и.

Теорема 3. (2.6) Пусть А — допустимое множество, а 9Л — модель конечной сигнатуры. Тогда ОТ определима в А. если и только если ОТ Т.-определ.има в ^"'(А) для некоторого » < и;.

Определенный таким образом скачок согласован как с тыоринговым, так и с в-скачками. Более того, как показано в [24], для данного скачка справедливо свойство инверсии. Однако в отличие от классических

операторов скачка, не имеющих неподвижных точек, Е-скачок обладает неподвижными точками.

Теорема 4. (2.11) Существует допустимое множество любой наперед виданной мощности, эквивалентное относительно Е-сводимости своему Т.-скачку.

Данная теорема имеет серию приложений как в рамках вычислимости на допустимых множествах, так и в классической вычислимости. К примеру, наличие неподвижной точки оператора Е-скачка влечет существование допустимого множества, в котором группа всех перестановок, вычислимых в данном допустимом множестве, будет Е-определимой. С одной стороны, этот результат можно рассматривать как обобщение одного нз основных результатов из [14], при доказательстве которого использовалась гипотеза о существовании недостижимого кардинала; с другой стороны, он контрастирует с известным результатом А. Нурта-зина[17], гласящим, что группа всех вычислимых перестановок не имеет вычислимой копни. Так как в любом допустимом множестве А группа всех его Е-иерестановок определима, существование допустимого множества с Е-определимой группой Е-перестановок вытекает из следующего утверждения.

Теорема 5. (2.12 и замечание 2.4) Для допустимого множества В следующие уыовия эквивалентны:

1. В является неподвижной точкой оператора Е-скачка (т.е. выполняется соотношение ^/е(В) Ш);

2. Для любой модели 9Л конечного языка, определимость модели ОТ в допустимом множестве В влечет ее И-определимость в В.

Кроме того, счетный граф С5, дня которого НР(Й) будет неподвижной точкой оператора Е-скачка, имеет спектр, замкнутый вниз относительно операции тьюрннгова скачка. В частности, неподвижные точки не имеют гиперарифметических копий.

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

Мы обсуждаем, к тому же, соотношения между данной сводимостью и сводимостямн, введенными ранее.

Результаты данной главы получены автором лично; они опубликованы в работах [61, 66J. Эти результаты докладывались на международных конференциях в Сиене (Италия) («Computability in Europe», 18-23 нюня, 2007), в Новосибирске («Мальцевские чтения», 16-18 ноября, 2004, 1114 октября, 2011), в Казани («Алгебра и математическая логика», 25-30 сентября, 2011), в Чикаго («Definability in Computable Structures», 12-13 мая, 2012), на семинарах «Теории моделей», «Вычислимость» и «Алгебра и логика» в Новосибирске и на логическом семинаре в университете г. Дармштадт (Германия).

Глава 3. О счетно категоричных теориях

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

Теорема 6. (3.1) Существует с-простая теория Т конечной сигнатуры такая, что ни для какого плотного линейного порядка £ не существует несчетных моделей meopmt Т, Т,-определилшх в HF(£).

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

Результаты данной главы получены автором лично и опубликованы в [67J. Они докладывались на международных конференциях в Казани («Алгебра и математическая логика», посвященная 100-летию В.В. Морозова, 25-30 сентября, 2011), в Новосибирске («Мальцевские чтения», 13-15 ноября, 2012) и в Чикаго («Definability in Computable Structures», 12-13 мая, 2012), а. также на семинарах «Алгебра и логика» и «Теория моделей» в Новосибирске. Результаты также докладывались на оби ^институтском семинаре ИМ СО РАН.

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

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

Д-подмножеств конечных ординалов и Т-сводимостью впервые были установлены в [20]. Однако, как следует из результатов настоящей работы, по семейству всех Д-подмножеств конечных ординалов невозможно однозначно восстановить семейство всех таких Е-подмножеств. Как оказалось, в этом случае наиболее адекватной будет е-сводимость. Впервые соотношения между е-сводимостью и свойствами семейства Е-нодмножеств натуральных ординалов допустимых множеств отмечены в [13]. Здесь дается полное описание всевозможных семейств Е-подмножеств в терминах именно е-сводимости.

Теорема 7. (4.6)

1. В любом допустимом множестве А семейство Е-подмножеств ш представимо в виде \}Х для некоторого е-идеалаХ.

2. Для любого е.-идеала X существует модель 9Л такая, что \_)Х совпадает с семейством всех Т,-подмножеств ш в ШШГ(ОЛ). Кроме того, эту модель можно выбрать так, что сагг1(9Л) = сагс1(их).

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

Теорема 8. (4.7) Для любых е-идеала X и кардинала а ^ сагс1(и1) существует модель 9Ло лющности а, Е-определимая в любом допустимом множестве мощности а, в котором семейство всех Т,-под-множеств совпадает с У_}1, причем семейство всех ^-подмножеств натуральных чисел в ШПР^ОЛо) также совпадает с и X.

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

по идеалам е-степеней. Попутно строится пример допустимого множества А, не имеющего разрешимой (даже позитивной) вычислимой А-нумерации семейства всех Е-подмножеетв. (Напомним, что в классическом случае существует разрешимая (даже однозначная) вычислимая нумерация семейства всех вычислимо перечислимых множеств[35, 11J.)

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

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

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

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

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

Этой тематике также посвящены работы, написанные автором совместно с И. Ш. Калимуллиным (см. [52, 53]), а также работы, написанные А.Н. Хисамиевым (см., например, [29]).

Теорема 7 была доказана независимо и одновременно А. С. Морозовым [54]. Остальные основные результаты из этой главы были получены автором лично; опубликованы в работах [58, 54, 65]; докладывались на международных конференциях в Новосибирске («Мальцевские чтения», 17-19 ноября, 2003, 16-18 ноября, 2004), в Сиене («Computability in Europe», 18-23 июня, 2007), в Казани («Алгебра и математическая логика», посвященная 100-летию В.В. Морозова, 25-30 сентября, 2011), на семинарах «Вычислимость» и «Алгебра и логика» в Новосибирске и на логическом семинаре в Лидсе (Великобритания). Результаты также докладывались на общеинститутском семинаре ИМ СО РАН.

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

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

Под ЦР (иГг) будем понимать свойства существования Е-функций, универсальных для классов всех ({0; 1}-значных) частичных Е-функций. Допустимое множество А будем называть кваэипроецируемым, если существует частичная Е-функция, определенная на некотором подмножестве натуральных чисел, действующая на носитель А. Дескриптивные свойства таких допустимых множеств подробно изучаются в работе [52].

Основной результат данной главы имеет следующий вид:

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

Все переходы в диаграмме, приведенной выше, строгие. В случаях (0-6,

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

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

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

Отметим, что кроме упомянутых выше ученых, эти свойства изучались также Р ЛО. Вайценавичюсом, М. В. Коровиной, А. Н. Хисамие-вым, В. А. Рудневым ([4, 20, 27, 39]).

Основной результат данной главы в окончательном виде был опубликован в работе [63]; докладывался на международных конференциях в Новосибирске («Мальцевские чтения», 2-6 мая, 2010), в Казани («Алгебра и математическая логика», посвященная 100-летию В.В. Морозова, 25-30 сентября, 2011), на семинарах «Вычислимость» и «Алгебра и логика» в Новосибирске, и на семинаре по вычислимости в Сиене (Италия). Результат также докладывался на общеинститутском семинаре в ИМ СО РАН.

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

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

Теорема 12. (6.1) Пусть Т — с-простая теория конечной сигнатуры и ОТ — счетная модель этой теории. Тогда, полурешетка ;нумераций'

к-элементных множеств на HF(ÎOT), А; > 1, изолюрфна полурешетке m-степеней.

Данная теорема, в частности, служит позитивным решением проблемы 3.

Данные результаты получены автором лично; опубликованы в работе [64]; докладывались на международной конференции в Новосибирске («Мальцевские чтения», 2-6 мая, 2010), в Казани («Алгебра и математическая логика», 25-30 сентября, 2011), на семинарах «Вычислимость» и «Алгебра и логика» в Новосибирске.

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

Работа выполнена при поддержке Российского фонда фундаментальных исследований (коды проектов 99-01-00600-а, 02-01-00540-а, 01-01-04003-ННИО_а, 03-01-06454-мас, 05-01-00481-а, 08-01-00442-а, 06-01-04002-НН1Ю_а, 09 01-12140 офи_м, 10-01-92881-АНФ_з и 11-01-00688-а), грантов Президента. РФ для молодых ученых кандидатов наук (МК-2452.2003.1), программы ФЦП •■Интеграция", проект 274, грантов Президента РФ по поддержке ведущих научных школ (коды проектов 00-15-96184, НШ-2069.2003.1, НШ-4787.2006.1, НШ-3606.2010.1 и НШ-276.2012.1), СО РАН дня молодых ученых 2003 и 2005 гг., I.XTAS YSF 05-109-4919 п Российского Фонда содействия отечественной науке.

В 2005 г. соискатель удостоен премии СО РАН имени академика А.И. Мальцева для молодых ученых.

Литература

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[32] L. Blum, M. Shub, and S. Sinale. On a theory of computation and complexity over the real numbers: Np-completeness, recursive functions and universal ina.chines, Bull. Am. Math. Soc., 21, 1(1989), 1-46.

[33] Yu. L. Ershov. E-Definability of algebraic structures, in Handbook of recursive mathematics, Vol. 1, ed's Yu. L. Ershov, S. S. Goncharov, A. Xerode, J. B. Reinmel, Elsevier, 1998, 235-260.

[34] Yu.L. Ershov, Y.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.

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

W. Hodges. Model Theory. Cambridge University Press, Cambridge, 1993.

H. A. Kierstead, J. B. Remmel. Indiscernibles and decidable models, J. Symb. Log., 48, 1(1983), 21-32.

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

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

M. V. Korovina, O. V. Kudinov. Xew approach to computability, Sib. Adv. Math., 8, 3(1998), 59-73.

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

S. Kripke. Transfinite recursion on admissible ordinals, I, II (abstracts), J. Symbolic Logic, 33(1964), 161-162.

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

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

Y. X". Moschovakis. Abstract computability and invariant definability, J. Symb. Log., 34(1969), 605-633.

Y. X. Moschovakis. Abstract first order computability I, Trans. Am. Math. Soc., 138(1969), 427-464.

Y. X. Moschovakis. Abstract first order computability II, Trans. Am. Math. Soc.. 138(1969). 465-504.

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

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

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

[51] 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.

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

[52] И. Ш. Калимуллин, В. Г. ПузареНКО. О принципах вычислимости на допустимых множествах, Математические труды, 7, 2(2004), 35-71.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пузаренко Вадим Григорьевич

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

Автореферат диссертации на. соискание ученой степени доктора физико-математических наук

Подписано в печать 12.01.13. Формат 60x84 1/16. Усл. печ. л. 1,3. Уч.-изд. л. 1,0.

Тираж 150 экз. Заказ Л"5 3

Редакционно-издательский центр НГУ 630090, Новосибирск-90, ул. Пирогова, 2

Федеральное Государственное Бюджетное Учреждение Науки Институт Математики им. С. Л. Соболева Сибирского Отделения Российской Академии Наук

Пузаренко Вадим Григорьевич

НАТУРАЛЬНЫЕ ЧИСЛА И ОБОБЩЕННАЯ ВЫЧИСЛИМОСТЬ

(01.01.06 — математическая логика, алгебра и теория чисел)

Диссертация на соискание учёной степени доктора физико-математических наук

05201350782

На правах рукописи

УДК 510.5

Научный консультант профессор, д.ф.-м.н., акад. РАН Ю. Л. Ершов

Новосибирск 2013

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.5 Существование неподвижной точки..............131

2.6 Основные свойства неподвижной точки............148

2.7 Открытые проблемы ......................153

3 О счетно категоричных теориях 155

3.1 Введение .............................155

3.2 Об упорядочиваемости категоричной модели.........166

3.3 Неразличимые элементы....................170

3.4 Свертка теорий..........................179

3.5 Применения в обобщенной вычислимости ..........183

4 О подмножествах натуральных чисел 187

4.1 Представления семейств ....................187

4.2 О сводимости на семействах..................197

4.3 Семейство всех Е-подмножеств и...............206

4.4 Соотношения между классами.................210

4.5 Квазипроецируемые допустимые множества.........214

(2) (Ч^

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

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

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

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

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

5.1 Введение .............................266

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература 322

Введение

Обобщенная вычислимость — новое направление математической логики, зародившееся на стыке теории вычислимости, определимости, теории моделей и теоретической информатики в работах Я. Московакиса, Дж. Сакса и Г. Крейзеля (см. [Мо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. Отличительной особенностью этой сводимости является то, что семейство рассматривается как абстрактный математический объект без фиксации какого-либо определенного представления. Две предыдущие теоремы доказываются в настоящей работе как следствия характеризационной теоремы для данной сводимости на семействах. Приводится серия примеров допустимых множеств, в которых отсутствует универсальная Е-функция. В настоящей работе построение таких примеров основано на трансляции определенных принципов с идеалов на допустимые множества. Кроме того, подробно исследуются

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