Моделирование оснований математических теорий Ганов Валерий Александрович

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

Введение

Глава 1. Основные принципы оракульного моделирования математического анализа 23

1.1. Вычисления с оракулом 24

1.2. Необходимые условия для конструктивизации анализа 32

1.3. Обобщенно-конструктивный континуум 39

1.4. Измеримых множеств и функций 48

1.5. Обобщенно-конструктивное пространство Бэра 57

Глава 2. Проблемы построения оракулов и вычислимые функционалы трансфинитных типов 67

2.1. Распознавание пустоты и несчетности В-множеств 68

2.2. Теоремы о существовании точных границ ограниченных множеств 78

2.3. Вычислимые функционалы трансфинитных типов 83

2.4. Модель арифметики трансфинитных типов 94

2.5. S-множества и бесконечные формулы 99

2.6. Оракульная конструктивизация метарекурсии 111

Глава 3. Множества, классы, принципы рефлексии и интенсиональности 124

3.1. Рефлексия и аксиомы подстановки 126

3.2. Рефлексия, интенсиоиальность и большие кардиналы 132

3.3. Аксиома конструктивности и существование измеримого кардинала 140

3.4. Аксиомы рефлексии и интенсиональности в ZF 146

3.5. Интенсиоиальность и принцип согласованного выбора 154

3.6. О проблеме совместности аксиом рефлексии и интенсиональности 161

Литература 166

• Необходимые условия для конструктивизации анализа
• Обобщенно-конструктивное пространство Бэра
• Теоремы о существовании точных границ ограниченных множеств
• Аксиома конструктивности и существование измеримого кардинала

Введение к работе

Настоящие исследования относятся к общей теории рекурсии, возникшей в конце пятидесятых годов прошлого века. Они касаются оснований математики, и поэтому для более полного описания рассматриваемых задач мы вынуждены пояснить некоторые философские моменты исследуемых проблем. Основным инструментом исследований является язык обобщенных вычислений с оракулом. Эти вычисления можно рассматривать, как вычисления на абстрактных вычислительных машинах с оракулом. Такая машина работает согласно своей программе, записанной в специальном языке программирования, и может осуществлять в качестве элементарных шагов некоторые неконструктивные акты, которые формализуются в виде вопросов к "оракулу". Оракул - частичная числовая функция, присоединяемая к специальному входу машины, вопросы представляются числовыми кодами, ответами являются значения функции, используемой в качестве оракула. Предметом исследований являются основные конструкции классической математики. Метод исследований - моделирование этих конструкций в языке программирования рассматриваемых вычислений.

Формализация оснований математики в рамках канторовской теории множеств (точнее, в ее аксиоматической системе Цермело-Френкеля ZFC), обладает, на наш взгляд, одним скрытым дефектом. Например, принцип математической индукции, используется применительно только к свойству, выраженному в языке этой теории. И, так сказать, из неформального мышления нам известны "нечеткие" свойства, к которым этот принцип не применим (парадокс "кучи", принцип практической осуществимости и т. п.) ([66]). Таким образом, в ZFC все рассматриваемые понятия как бы полагаются абсолютно "четкими". С другой стороны, аксиома выбора утверждает существование некоторой функции, позволяющей выбрать по элементу из каждого непустого множества произвольного семейства множеств. Но каждый конкретный человек фактически не представляет себе такую функцию, как однозначно определенный объект мысли. Эта функция является чем-то "размытым". Такие же обстоятельства возникают каждый раз, когда мы применяем квантор существования к бесконечным множествам, без точного указания запаса тех средств, которыми соответствующий элемент может быть построен. Аналогичное и даже более сильное возражение подобного рода можно высказать в адрес аксиомы степени. Итак, канторовская теория множеств постулирует для своих объектов такую четкость, которую она сама не может обеспечить.

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

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

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

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

В данной диссертации для моделирования математического анализа вместо алгоритмической вычислимости мы используем язык обобщенных вычислений с оракулом, и легко видеть, что такое применение придает определенную гибкость самому математическому аппарату и отодвигает алгоритмически неразрешимые проблемы от традиционных конструкций, не по-зволяялм смешиваться неудобным образом, как это наблюдается в конст руктивной математике. Отметим, что при неформальном изложении математического анализа мы часто встречаем процедуры и рассуждения, которые можно принять за алгоритмические. Например, при доказательстве существования предельной точки ограниченного множества вещественных чисел М описывается процесс построения стягивающей последовательности вложенных друг в друга отрезков [# ; Ьк]. При этом на каждом шаге осуществляется неалгоритмический шаг, связанный с распознаванием непустоты и бесконечности множеств вида [я ; bk]f M. Примеры подобных неалгоритмических шагов встречаются и в других ситуациях. Понятно, что можно было бы ограничиться рассмотрением только тех множеств континуума, для которых эти шаги являлись бы алгоритмическими. Но может случиться, что класс таких множеств очень беден или даже пустой. Поэтому возникает мысль произвести моделирование континуума в подходящем обобщенном языке программирования, который помимо обычных алгоритмических команд содержал бы специальные команды, позволяющие осуществлять необходимые неалгоритмические шаги. Удобным средством для такого моделирования является язык обобщенных вычислений на машинах с оракулом. При подходящем выборе оракула в таких вычислениях указанные неалгоритмические шаги можно осуществлять с помощы/з спрашивающих команд.

Конечно, при таком подходе возникает вопрос о возможности построения соответствующего оракула, т.е. имеем некоторый вид проблемы обоснования языка программирования. Не касаясь основания математического анализа, мы решаем такую проблему, привлекая уже методы теории множеств. А именно, используя аксиомы системы ZFC, мы доказываем существование необходимых нам оракулов. Таким образом, язык программирования обобщенных вычислений с оракулом становится посредником между основанием анализа и теорией множеств. Заметим также, что вычислимость каждого вещественного числа для математического анализа, даже нацеленного на практическое применение, - не существенна. Так что, переходя к вычисления с оракулом, мы ничего не теряем. Дело не в самой по себе вычислимости, а в переходе от логического языка к алгоритмическому языку, т.е. к языку программирования, хотя бы и нереализуемому фактически.

Используя вычисления на машинах с оракулом, мы строим обобщенно-конструктивный континуум Г аналогично тому, как это делалось в конструктивной математике. Оказалось, что даже при выборе достаточно простого гиперарифметического оракула в Г легко доказываются аналоги всех начальных свойств классического анализа, включая все свойства вещественных чисел и непрерывных функций, и устраняются многие трудности конструктивного анализа, о которых упоминалось выше. Более того, в Г выполняется континуум-гипотеза. С другой стороны, в Г, как и в конструктивном континууме, точки имеют обобщенно-вычислимые коды, и функции над этими точками определяются с помощью обобщенно-вычислимых функций над кодами. Это обстоятельство оставляет возможность для построения разных "аномальных" объектов. И действительно, в диссертации построен пример ограниченного множества в Г, которое не имеет точной верхней границы в Г. Построение этого множества использует диагональное манипулирование с указанными кодами. Таким образом, мы вновь наблюдаем проникновение в математический анализ неразрешимых проблем, но уже не теории алгоритмов, а теории вычислений с оракулом.

Но вычисления на машинах с оракулом предоставляют нам новые возможности для моделирования математических конструкций. Например, в главе 2 мы используем вычисления на тех же машинах, но относительно специальных семейств оракулов. В таких семействах каждой точке а классического континуума соответствует некоторый оракул Fa, с которым эта точка является вычислимой. Это позволяет ввести новый способ задания вещественных функций в Г. Считаем, что машина q вычисляет функцию ф вещественного переменного, если для каждой точки а эта машина с оракулом Fa вычисляет соответствующее, значение ф(а) этой функции; другими словами, в машине q аргумент а заменяется соответствующим ему оракулом Fa. В этом случае работа q зависит только от оракула Fa и не зависит от кода точки а. Тем самым, исключаются из рассмотрения искусственные функции и множества, получаемые за счет вычислимых процедур над кодами точек Г, и, в частности, упомянутый контрпример становится невозможным. Более того, удается построить специальное семейство оракулов указанного вида и определить соответствующее ему обобщенно-конструктивное пространство, в котором выполняется положительный аналог теоремы о существовании точных границ ограниченных множеств.

Заметим также, что в указанных семействах индекс а оракулов пробегает все точки классического континуума, следовательно, этот подход позволяет имитировать представление о континууме, как о чистой непрерывной протяженности. Кроме того, в качестве индексов оракулов можно рассматривать любые другие функции или функционалы. Это дает возможность определять вычислимость функционалов других типов и видов, и в этом смысле открываются новые возможности при моделировании математических конструкций. Яркое проявление таких возможностей мы наблюдаем при конструктивизации формальных систем арифметики с функционалами трансфинитных типов. Такая система содержит переменные трансфинитных типов, которые являются обозначениями ординалов некоторой ординальной нумерации. В этой системе, кроме обычных аксиом арифметики натуральных чисел, для каждого типа сформулирован соответствующий вид аксиом выделения. Обобщая указанный метод задания функций на функционалы трансфинитных типов, мы строим разнообразные оракульные модели для таких систем. В ходе этих исследований были обнаружены особые теоретико-множественные ситуации, которым были присвоены специальные термины "принцип рефлексии" и "принцип интенсиональности". Более подробно эти ситуации рассматриваются чуть ниже.

В самом общем плане тему диссертации можно также рассматривать, как исследование структуры так называемых "оболочек" алгоритмической вычислимости. До возникновения теории алгоритмов все известные в математике алгоритмы фактически были тотальными (с точностью до тривиальных оговорок, которые ничего не меняли). Поэтому сначала алгоритмы ассоциировались скорее с общерекурсивными функциями, а частичные алгоритмы не рассматривались. Затем возникла универсальная функция, которая создавала определенные удобства в описании некоторых алгоритмов. Эта функция уже не могла быть общерекурсивной, и по этой причине, понятие алгоритма было распространено на частично рекурсивные функции. Таким образом, общерекурсивные функции составили основное "ядро" теории алгоритмов, а частично рекурсивные функции образовали "оболочку", предназначенную для вспомогательных целей. Но внутри самой теории алгоритмов основное внимание уделялось частично рекурсивным функциям, и уже, поэтому становится достаточно интересным вопрос о варьировании этой "оболочки" при сохранении "ядра", состоящего из тотальных вычислимых функций. Подобное обстоятельство более ярко проявляется при переходе к обобщенным вычислениям.

Для данного оракула F в качестве основного "ядра" обобщенной вычислимости рассмотрим множество всех тотальных функций, а в качестве "оболочки" - множество частичных функций, вычислимых с этим оракулом. Тогда применение какого-то другого оракула приводит к изменению "оболочки", но при этом "ядро" вычислимости может остаться неизменным. И действительно, при таком подходе обнаружилось, что один и тот же запас тотальных объектов ("ядро") можно снабдить разными "оболочками" так, что соответствующие версии вычислимости сильно различаются по своим свойствам ([12]).

Еще раз заметим, что хотя речь идет именно об абстрактных вычислениях, т.е. физически не реализуемых, тем не менее, с эвристической точки зрения изучение возможных видов "оболочек" можно представить как исследование основных принципов программирования, реализующихся в разнообразных вариантах вычислений с оракулом. Например, в работах [28], [46] исследованы вычисления с нетрадиционным способом общения машины с оракулом, при котором машине разрешается получить регламенти- рованное число отказов. В результате были выявлены некоторые необычные и даже уникальные "программистские эффекты".

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

Отметим также, что исследование вычислений с оракулом имеет са мостоятельный интерес, касающийся проблемы представления математических знаний. Очевидно, что многие логические трудности зависят не. от природы вещей, а от тех способов, как мы эти вещи определяем. В этом плане язык вычислений с оракулом оказывается на наш взгляд иногда более удобным и более естественным, как, например, это имеет место при описании а-рекурсии и рекурсии высших ступеней, а-рекурсия - это обобщение теории рекурсии на бесконечные ординалы, а основным методом определения её понятий являлось исчисление равенств ([59]). В диссертации мы обобщаем рекурсию на ординалы, вычислимые с оракулом F, при этом основные понятия определяем двумя способами: с помощью исчисления равенств и в терминах вычислений с оракулом. Легко видеть, что второй способ оказывается технически более удобным. Рекурсия высших ступеней -это обобщение рекурсии на случай, когда в качестве вспомогательных объектов используются некоторые функционалы высоких типов. Ее первоначальное описание использовало индуктивную форму определения и язык схем рекурсии ([57]). Такой способ описания, ввиду его громоздкости, создавал значительные технические трудности для понимания, и потому до сих пор рекурсия высших ступеней считается трудной и доступной лишь посвященным. В работе [2] было показано, что клиниевскую вычислимость функционалов конечного типа можно довольно просто определить с помощью вычислений на машинах относительно семейств оракулов указанного выше вида. В диссертации это определение мы распространяем на функционалы трансфинитных типов.

В связи с обнаружением парадоксов в канторовской теории множеств возникла необходимость кроме множеств ввести классы. Характерным примером может служить система Геделя-Бернайса (BG). При этом возникла ситуация аналогичная ситуации с "оболочками" в теории алгоритмов. При ближайшем рассмотрении обнаружилось, что классы, по существу, играют вспомогательную роль, сходную с ролью предикатных переменных. Говоря .конкретнее, мыслится некоторый универсум множеств, и над ним имеется классовая надстройка, где каждый класс выражает некое допустимое к рассмотрению свойство множеств этого универсума. Эта надстройка может варьироваться - при сохранении запаса множеств. Например, в системе BG от классов требуется лишь замкнутость относительно геделевских операций и выполнение аксиомы подстановки, в которой функции задаются с помощью классов.

Сравнение BG с теорией полумножеств TSS ([66]) показывает, что с одним и тем же универсумом множеств можно соотнести существенно разные классовые надстройки так, что теоремы о множествах при этом не изменяются. Более того, в BG можно обойтись достаточно узким запасом классов, а именно запасом тех классов, которые определимы посредством ZF-формул. С другой стороны, в теории TSS запас множеств можно считать таким же, как в системе ZF, а классов больше чем в BG. С изложенной сейчас точки зрения, последнее обстоятельство не выглядит как обязательное, так как классы - это все-таки вспомогательные объекты и нас интересует не обширность их запаса, а то, насколько этот запас хорошо структурирован. Для нас гораздо важнее замкнутость семейства классов относительно некоторых часто употребляемых в математике операций. Поэтому, можно взять еще более узкую классовую надстройку, чем это требует система BG. Подобная ситуация возникает при отказе от требования, что каждое множество является классом. Такой отказ расходится со сложившимися традициями, но его можно мотивировать следующим образом.

В контексте теории ZF неестественно предполагать, чтобы каждое множество было как-то описано. Этому препятствует, например, наличие аксиомы степени. Но применительно к тем свойствам, которые мы хотим включить в классовую надстройку, это требование можно вставить, т.е. можно считать, что классы описаны какими-то воображаемыми "текстами", структура которых более или менее подобна структуре формул языка ZF..B этой ситуации легко подметить, что запас "определимых" классов может быть малым, и даже меньше, чем запас всех множеств. Разумеется, что эта интуиция должна быть как-то отражена при выборе аксиом соответствующей теории множеств и классов. При этом сам выбор аксиом должен быть настолько удачным, чтобы давать конкретные интересные результаты. И здесь хорошим ориентиром служит сформулированный ниже принцип рефлексии.

Добавим к языку теории BG константу М для множества и будем предполагать, что допустимые к рассмотрению классы задаются ZF-фор-мулами, но только с параметрами из М. Затем, опираясь на известную теорему Леви [31; с.32], мы постулируем следующую схему аксиом.

ПРИНЦИП РЕФЛЕКСИИ: каждая ZF-формула ф с параметрами из М эквивалентна своей релятивизации фм к множеству М: (\/хеМ)( ф(х) «- рм(х)).

Полученное расширение BG будет, конечно, консервативным, однако напрашивается специальный способ его усиления, который существенно расширяет его первоначальные дедуктивные возможности. Трактуя классы как свойства множеств, описанные в каком-нибудь неопределенно мыслимом языке, мы можем распространить принцип рефлексии и на выражения этого предполагаемого языка. Тогда, согласно принципу рефлексии, реля-... . тивизация фм формулы ф, задающей некоторый класс Х3 будет выделять из Мто же подмножество, что и сама ф : {х е Ml фм(х)} = {х є Ml ф ( )} = ХпМ. . Это подсказывает нам, что при релятивизацию нормальных BG-фор-мул, не содержащих кванторов по переменным для классов, помимо ограничения кванторов по множествам константой М надо каждое свободное вхождение переменной для классов заменить на ее пересечение с М (например, X заменяется на ХпМ). Теперь усиленный принцип рефлексии формулируется для каждой нормальной #С/-формулы, более того, ситуация становится особенно интересной, если мы дополнительно постулируем регулярность ранга множества М. Например, в полученной системе выводимо существование некоторых больших кардиналов, таких, как кардиналы Мало, гипер-Мало, гипергипер-Мало и т. д. Далее, этот принцип дает жесткое ограничение на объем классовой надстройки этой системы. Оказывается, что подразумеваемую совокупность всех классов можно взаимно однозначно заиндексировать элементами некоторого множества Wm вида Wm с Р(М). Возникает вопрос, насколько широким может быть это множество Wm, и не исчерпывает ли оно все Р{М) Описанный выше способ релятивизации нормальных 2?Є-формул сохраняет свое интуитивное содержание, и это в значительной степени избавляет нас от необходимости принимать какие-нибудь формальные постулаты, касающиеся упомянутого воображаемого нами языка. Более того, мы можем формализовать вышеизложенные соображения о классах, избегая разговоров о "текстах" воображаемого языка, для этого достаточно принять следующую аксиому.

ПРИНЦИП ИНТЕНСИОНАЛЬНОСТИ: Ух (х с Л/- ЗХ(х=ХпМ)).

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

2. История развития проблемы

Одним из основных принципов канторовской "наивной" теории множеств был принцип свертывания, который утверждал, что каждая формула языка теории множеств определяет множество. Этот принцип приводил к различного рода парадоксам, обнаруженным в математике на рубеже XIX и XX веков, и для преодоления этих парадоксов были построены различные аксиоматические системы теории множеств, главная цель которых состояла в ограничении этого принципа. В 1908 году была построена первая такая система Э. Цермело Z, в которой принцип свертывания был заменен схемой аксиом выделения. В системе Z можно развивать арифметику, математиче ский анализ, функциональный анализ, можно рассматривать кардиналы, меньшие, чем Ки. Но в Z нельзя доказать существование Кт и более высоких кардиналов. В 1922 году А. Френкель дополнил Z схемой аксиом подстановки, и полученная система стала обозначаться через ZFC. Система ZFC значительно сильнее Z , в ней доказуемы все обычные математические теоремы и доказуема непротиворечивость Z. Аксиоматический метод позволил точно определить проблему эффективности в теории множеств, интенсивно обсуждавшуюся в начале XX века в работах Р. Бэра, Э. Бореля, А. Лебега, Н. Н. Лузина и др. Теоретико-множественный объект, удовлетворяющий свойству R, задается эффективно в системе S, если может быть построена формула языка S, про которую в S можно доказать, что ей удовлетворяет единственный объект, и этот объект удовлетворяет свойству R.

Укажем некоторые факты, полученные в аксиоматической теории множеств и касающиеся затронутых в диссертации вопросов. Пусть ZFОбозначает систему ZFC без аксиомы выбора (АС). В 1939 году К. Гедель показал, что если ZF непротиворечива, то она остается непротиворечивой и после добавления к ней АС и КГ. Для доказательства этого результата К. Гедель построил модель теории ZFC, состоящую из так называемых конструктивных по Геделю множеств, которые играют важную роль и в современной теории множеств. В 1963 г. П. Коэн, с помощью разработанного им метода вынуждения, показал, что если ZF непротиворечива, то она остается таковой и после присоединения любой комбинации из АС, КГ или их отрицаний. АС была впервые сформулирована в 1904 году и встретила отрицательное отношение многих математиков. Это объяснялось, во-первых, ее чисто экзистенциональным характером, отличающим ее от аксиом ZFt а во-вторых, некоторыми "необычными" следствиями, противоречащими интуиции "здравого смысла". Например, с помощью АС выводимо существование неизмеримого по Лебегу множества и существование упомянутого выше парадоксального разбиения шара. С другой сторона, АС широко используется в классической математике, например, с ее помощью доказываются: принцип вполне упорядочения; счетность объединения счетного семейства счетных множеств; эквивалентность двух форм определения непрерывной вещественной функций; счетная аддитивность меры Лебега. Но было замечено, что для доказательства последних двух утверждений достаточно счетной аксиомы выбора. А в связи с этим отметим, что существует модель ZFt в которой выполняется счетная аксиома выбора, а также каждое множество действительных чисел измеримо по Лебегу. Такая модель была построена в предположении существования недостижимого кардинала [32, с.48].

В начале XX века, в связи с указанными выше трудностями, Л. Брауэр и Г. Вейль подвергли критике некоторые принципиальные стороны логических основ классической математики и предложили собственные идеи по строения основ математического анализа. Первая идея - это отказ от использования абстракции актуальной бесконечности; вторая идея - введение особой логики для разработки математических теорий, основывающейся на абстракции потенциальной осуществимости; третья идея - это такое построение математического анализа, при котором рассматриваются только конструктивные объекты, допускающие индивидуальное задание в рамках некоторой отчетливо описываемой символики. В их теории не только термин "рациональное число", но и термины "вещественное число", "множество вещественных чисел", "вещественная функция" связывались с конструктивными объектами.

Однако в то время математика еще не располагала строгим понятием алгоритма, и потому лишь некоторые из этих идей (отказ от аксиомы выбора, ограничение трансфинитной рекурсии счетными ординалами) были приняты на вооружение дескриптивной теории множеств, возникшей тогда же. Эта теория зародилась в трудах Э. Бореля, Р. Бэра и А. Лебега в связи с проблемой измеримости множеств. В ней классические вещественные числа не подвергались каким-либо изменениям, а в качестве допустимых множеств континуума сначала рассматривались только 2?-множества, которые можно было построить из интервалов с помощью операций счетного объединения и счетного пересечения. Указанные операции имели достаточно четкое определение и потому Л-множества считались "эффективными" объектами в указанном выше смысле. Тем самым, была произведена эффекти-визация множеств вещественных чисел. При таком подходе, например, континуум-гипотеза и проблема измеримости множеств получили положительное решение. Затем оказалось, что класс измеримых множеств шире класса 2?-множеств, и потому к построению допустимых множеств континуума были привлечены операции проецирования и взятия дополнения, с помощью которых были определены и введены в рассмотрение -множества и проективные множества. Но для новых множеств указанные выше проблемы возникли вновь. И тогда все больший интерес стала вызывать позиция, согласно которой континуум состоит только из четко определимых точек. Например, в [37] приведены замечания Н. Н. Лузина о том, что в континууме встречаются точки, трудно определимые или вообще не поддающиеся строгому определению, и что пора пересмотреть представление о континууме, как о точечном множестве.

Еще одна программа обоснования математики - это разветвленная теория типов, которая была введена Б. Расселом в 1908 году. Считалось, что основной причиной возникновения противоречий теории множеств являлись непредикативные определения математических объектов, когда определяемый объект может участвовать в своем определении. Было предложено расчленить предметную область на конечные типы, соответствующие натуральным числам, и для каждого типа ntO была сформулирована схема аксиом свертывания: ЗУ+W. ( jc" є у+1 - q (xT)).

Таким образом, свойство У+1 и объекты, которые этим свойством обладали ;е", были отнесены к разным типам. Разветвленная теория типов оказалась достаточно сильной теорией. В нее можно погрузить арифметику и анализ, рассматривать кардиналы К0 , К і,..., К„. Она имела простую интуитивную теоретико-множественную модель. Доказательство ее непротиворечивости можно произвести в рамках системы Цермело Z.

В 30-х годах было получено строгое определение алгоритма, и сразу же начались попытки применения этого понятия. Сначала А. Тьюринг ([65]) определил вычислимые действительные числа и функции над ними. Чуть раньше А. Черч определил вычислимые ординалы, а затем А. Тьюринг использовал их для итерирования геделевского диагонального процесса и построения иерархий формальных систем арифметики. В России в начале 50-х годов А. А. Марков, Н. А. Шанин и их ученики начали создавать конструктивную математику.

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

Например, Е. Шпекером ([64]) была построена возрастающая конструктивная последовательность рациональных чисел, которая являлась ограниченной и в то же время не являлась фундаментальной. Кроме того, она не имела точной верхней границы, и из нее нельзя было выбрать сходящуюся подпоследовательность. И. Д. Заславским ([30]) были построены примеры, показывающие, что конструктивная функция может быть всюду определенной и неограниченной на единичном сегменте, или может быть ограниченной на [0; 1], но не иметь точной верхней границы. Г. С. Цейтиным ([50]) было доказано, что всякая конструктивная функция непрерывна в любой точке, где она определена. В конструктивном континууме не верна лемма Бореля о покрытиях отрезка интервалами.

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

Для преодоления указанных трудностей Н. А. Шанин ([48]) предпринял особую радикальную попытку. Вольно выражаясь, он предпочел работать в духе функционального анализа. Сначала он ввел в рассмотрение ступенчатые функции с рациональными особыми точками. Такие функции являлись конструктивными объектами, и для них легко было определить ту или иную метрику. Затем он производил метрическое пополнение построенного пространства функций, аналогично тому, как Г. Кантор пополнял вещественную прямую. Только на сей раз Н. А. Шанин требовал, чтобы везде были алгоритмы, а соответствующие рассуждения опирались на законы конструктивной логики (хотя последнее совсем не необходимо). В результате были получены хорошие аналоги известных функциональных пространств и практически весь классический анализ был реконструирован. Единственно, что при этом терялось, это точечное представление вещест-венной функции. Фактически это было возвращение к старинному представлению о вещественной функции, как о чем-то заданном аналитически (т.е. посредством некоторой формулы или чем-то вроде "текста" в некотором не вполне формальном языке). Хотя в работе Н. А. Шанина этот момент, так сказать, оставался в тени, он скорее ориентировался на приемы современного функционального анализа.

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

Независимо от теории вычислений возникла теория иерархий. Иерархия - классификация тех или иных математических объектов в соответствии с их сложностью. Первые иерархии были построены в дескриптивной теории множеств, и одна из них - это иерархия проективных множеств ([35], [1]). Д. Деккер, Д. Майхилл и В. А. Успенский предприняли попытки построения иерархии рекурсивно перечислимых множеств, используя чисто алгоритмические аналоги понятий дескриптивной теории множеств. Это привело к возникновению понятий продуктивного и креативного множеств, которые сыграли заметную роль в теории степеней неразрешимости ([47, с. 158]). Хотя такая аналогия с дескриптивной теорией множеств была не слишком органичной, скорее, чисто внешней. Затем в математической логике были построены арифметическая и аналитическая иерархии числовых множеств и отношений, задаваемых формулами логических языков ([56], [61]). Эти иерархии были распространены на функции, появились арифметические и гиперарифметические функции. Такие функции уже являлись некоторым видом обобщенных вычислений, и В. Риттер ([63]) и Л. Хоудз ([55]) использовали их для моделирования основных понятий математического анализа ([47, с.477]). Далее, развитие теории иерархий и теории типов привело к созданию теории вычислимых функционалов конечных типов [57], и в работах [60], [62] эта теория получила дальнейшее развитие.

Понятие рекурсии употребляется не только в теории рекурсивных функций, но в теории множеств издавна существует понятие трансфинитной рекурсии; так что осмысление этого понятия с некоторой единой точки зрения достаточно естественно. Поэтому в современной математике рекурсия была.распространена на абстрактные теоретико-множественные объекты. В 60-х годах в работах [58], [59] была создана теория а-рекурсии, в которой различные формы определения алгоритма были перенесены на ординальный отрезок длины а. В связи с этим, возникли концепции обобщенных машин Тьюринга, в ячейках которых могут стоять ординалы а, и последовательность тактов работы которых могла занимать не натуральный ряд, а более длинный отрезок ординальных чисел. При этом чтобы получались хо- рошие теории, было введено понятие допустимого ординала а. В результате выяснилось, например, что допустимый ординал является хорошим эффек-тивистским аналогом понятия регулярного кардинала. Затем появились так же метарекурсивные аналоги для недостижимых кардиналов и кардиналов Мало, гипер-Мало и т.д. В дальнейшем в работе [52] а-рекурсия разрослась в обширный предмет допустимых структур и связанных с ними бесконечных языков. Отметим также, что метарекурсия быстро превратилась в некую, довольно ослабленную аксиоматическую версию теории множеств. Там где основные аксиомы типа подстановки и выделения ограничивались только -формулами, т.е. формулами, которые абсолютны вверх и потому можно говорить, что они задают некоторую эффективность.

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

Понятие частичного оракула появилось в работе [33] в связи с описанием вычислений относительно функционала G конечного типа, при этом первоначальное представление об оракуле присутствовало лишь неявно, как комментарий к довольно громоздкому определению. На определенном этапе изучения таких вычислений обнаружилось, что их удобнее представлять в виде функций, вычислимых на машинах с частичным оракулом Fg, ответами которого являются значения рассматриваемого функционала G ([2]). Затем в работах Н. В. Белякина и его учеников, "машинно-оракульная" версия обобщенных вычислений получила дальнейшее развитие, и с ее помощью были построены оракульные модели классической арифметики второй и третьей ступени ([2],-[3]),,исследованы разнообразные вопросы теории иерархий ([12], [20], [43] и др.).

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

3. Обзор диссертации

Диссертация состоит из данного введения, трех глав и списка цитированной литературы. В главе 1 произведена обобщенная конструктивизация математического анализа и дескриптивной теории множеств в языке обобщенных вычислений на машинах с оракулом. В 1.1 сначала описаны основные понятия, связанные с вычислениями на машинах с частичным оракулом F. Затем рассмотрены основные свойства гиперарифметического оракула F0 и эти свойства распространены на случай произвольного оракула. В 1.2 на основе этих свойств разработаны минимальные условия, которым - должен удовлетворять оракул F, чтобы обеспечить определенные удобства при конструктивизации анализа и устранить причины возникновения указанных выше аномалий конструктивной математики. В частности, эти условия позволяют: 1) осуществлять бесконечные переборы элементов любой / -вычислимой последовательности чисел; 2) выбирать элемент из непустого числового множества, перечислимого с F; 3) вводить на множестве Т -вы-числимых объектов, достаточно согласованную и i -вычислимую трансфинитную структуру; 4) вводить канонические номера / -вычислимых тотальных числовых функций. Показано, что введение этих условий не нарушает общности данных исследований. Кроме того, введена аксиоматическая система A(F)y которая показывает, что формально рассматриваемые здесь по нятия и рассуждения осуществимы в рамках системы ZFu обычной логики. В 1.3 введен обобщенно-конструктивный континуум Г, точки которого определены, как пределы -вычислимых фундаментальных последовательностей рациональных чисел; геделевские номера машин, задающих эти последовательности названы / -кодами точек. Функции вещественного переменного в Г задаются с помощью -вычислимых функций над і -кодами точек Г, а множества в Г вводятся с помощью характеристических функций в Г. Аналогично предыдущему определены F-коды этих объектов. Кроме того, последовательности каких-либо объектов в Г задаются с помощью F-вычислимых последовательностей .F-кодов этих объектов. Показано, что при выполнении этих условий в Г выполняются положительные аналоги многих классических утверждений математического анализа, включая все аксиомы вещественных чисел и все свойства непрерывных функций вещественного переменного.

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

Поэтому в 1.4 в тех случаях, когда это возможно, конструктивизация соответствующих объектов анализа осуществлена с помощью / -вычислимых процессов, которые определяют их как объекты типа 1. Для таких объектов указанные ситуации уже не возникают, и, тем самым, частично возникшие трудности конструктивизации анализа были преодолены. Тогда были введены подходящие / -вычислимые аналоги измеримых множеств и функций, и определен интеграл Лебега в Г. Показано, что для этих понятий верны аналоги соответствующих классических свойств.

В 1.5 определено обобщенно-конструктивное пространство Бэра If, как множество / -вычислимых бесконечных последовательностей натуральных чисел, / -множества в If определены индуктивно с помощью операций счетного объединения и счетного пересечения, применяемых к интервалам Бэра и ранее полученным / -множествам. При этом совокупность интервалов Бэра и применяемые операции задаются с помощью / -вычислимых деревьев с обрывом цепей; F-kor такого дерева назван / индексом /?-множе-ства в If. С помощью F-индексов введена трансфинитная классификация В-множеств в If: (If), Qf) где у пробегает вычислимые ординалы. Вве денные классы монотонно расширяются с ростом у и инвариантны относительно операций конечного объединения и пересечения. Для каждого такого класса доказана его топологическая инвариантность и доказано существование плоского 2?-множества.в If, универсального для множеств этого класса. Для дальнейшей конструктивизации дескриптивной теории множеств необходимо, чтобы операция проецирования плоских 5-множеств в If была jF-вычислимой. В лемме 1.17 доказано, что .F-вычислимость. этой операции влечет -вычислимость процедуры распознавания непустоты В-множеств в If. Затем показано, что по і -кодам 5-множеств эта процедура не является jp-вычислимой. А в случае гиперарифметического оракула F0 эта процедура не является -вычислимой даже по -Fo-индексам. Аналогичная ситуация имеет место в связи с процедурой распознавания несчетности -множеств в If . Возникла проблема построения специальных оракулов F, для которых эти процедуры будут -вычислимыми.

В главе 2 некоторые подобные проблемы решаются положительно. Сначала в 2.1 построены оракулы, которые непосредственно распознают пустоту и несчетность соотнесенных к ним -множеств по их F-индексам. Для таких оракулов определены л -множества в If, как проекции плоских В-множеств в If. Показано, что такие множества обладают аналогами многих свойств классических -множеств; в частности, в теореме 2.3 доказано, что л -множества в If суть непрерывные образы пространства If, а в теореме 2.4 доказано существование -множества в If, не являющегося і?-множеством в If Затем, в 2.2 произведена конструктивизация пространства Бэра в языке вычислений относительно семейств оракулов вида р - {Fa/ а є JV }. При этом применен особый способ задания Я-вычислимых функций в If, описанный выше в пункте 1. Построено специальное семейство оракулов Яа/ , в котором для выделенного оракула Fao в соответствующем пространстве Ifo выполняется положительный аналог теоремы о существовании точных границ ограниченных множеств. В теореме 2.7 доказано, что для такого оракула две формы определения открытых и замкнутых множеств являются эквивалентными.

В 2.3 определена.формальная система L[v], в которой функциональные переменные g"", И1 имеют трансфинитные типы т, к, являющиеся номерами ординалов некоторой ординальной нумерации V. Кроме обычных аксиом арифметики натуральных чисел в L[v] для каждого типа введена соответствующая схема аксиом свертывания вида: (V h )(3g")(y )[ g(/ ) = 0 о Ф( h, А»)], где ф( h, /г ) - формула L[v], не содержащая переменной g".

Далее, определены одноместные тотальные функционалы трансфинитных типов. Введены семейства оракулов = {Fq/ G є Zg» S V}, в которых оракулы F G имеют индексы G, являющиеся конечными кортежами указанных функционалов. Относительно такого семейства 3 определены вычислимые функционалы аналогично тому, как это сделано в 2.2. Затем построено семейство оракулов .5?, в котором оракулы позволяют распознавать истинность формул системы L[v], проинтерпретированных на -вычислимых функционалах. Из таких функционалов построено семейство моделей { Ms/ 8 V } для L[v] и ее подсистем Ls[v]. Доказано, что эти модели не зависят от длины нумерации V.

В 2.4 эта конструкция модернизируется и строится новое семейство оракулов 3 такого же вида, обладающее следующим свойством. Пусть F — оракул семейства 3, соответствующий пустому кортежу, и v2 - нумерация jp-вычислимых ординалов. Тогда с помощью 3-вычислимых функционалов строится модель М2 системы L[v2]t т.е. построена модель арифметики трансфинитных типов, в которой в качестве типов используются ординалы, принадлежащие этой же модели. Доказывается, что при естественной интерпретации функционалов в М2 выполняются аналоги всех аксиом системы ZF. При этом оказывается, что система Z,[v2] является полуформальной и такая аналогия не является полной.

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

Дальнейшее рассмотрение вопросов эффективности этих конструкций неизбежно приводит к а-рекурсии, поэтому в 2.6 произведена "оракуль-ная" конструктивизация основных понятий а-рекурсии. Для ординала a = 7](F), являющегося длиной отрезка / -вычислимых ординалов, рассмотрены две формы определения / -вычислимого аналога а-рекурсивных функций. С помощью подходящего исчисления равенств L0(F) определены ТХ/ -рекурсивные функции, и с помощью .F-вычислимых функций на F-кодах ординалов определены Д/ -вычислимые функции. Доказана эквивалентность этих определений при достаточно простом оракуле F. Затем определены ДТ -конечные множества ординалов, как ограниченные T(F)-pQ-курсивные множества. Показано, что для этого понятия верны аналоги основных свойств конечных множеств чисел. Но, с другой стороны, в лемме 2.19 указано ограниченное Д/ -перечислимое множество, не являющееся T(F)-kohq4huu. Исследование этой ситуации приводит к понятию T(F)-проектируемого ординала. В теореме 2.20 указаны необходимые и доста точные условия, при которых ординал a = \T(F)\ не является 7]( )-проекти-руемым.

В 2.5 произведена "оракульная" конструктивизация абстрактных множеств, при этом процесс построения множеств представлен соответствующим образом в виде і -вьічислимого дерева с обрывом цепей. При подходящем оракуле F совокупность таких множеств ffl(F) образует модель теории множеств и классов, в которой выполняются все аксиомы ZF (без аксиомы степени). Этот же метод применен для моделирования формул языка теории множеств, в результате получен бесконечный квазиязык Loq(F), подобный бесконечным языкам, рассматриваемым в работе Дж. Бар-вайса [52]. Затем построены оракул F и более широкий оракул //, позволяющие распознавать истинность формул квазиязыков Loo(F) и Loo(H)t проинтерпретированных на ЩР) и Ж(Н), соответственно. С помощью F и Н построена модель 7Н(Н) теории множеств и классов, в которой выполня-. ются аналоги описанных выше принципов рефлексии и интенсиональности.

В заключительной части главы 2 подведены итоги проведенной "ора-кульной" конструктивизации математики и дана некоторая философская оценка полученным результатам.

Дальнейшие исследования показали, что формальная система, содержащая принципы рефлексии и интенсиональности и минимальный набор других аксиом теории множеств, по своим дедуктивным свойствам значительно превосходит известные системы ZFn BG. В указанной выше модели Ж(Н) полный аналог принципа интенсиональности не выполняется, т.е. полной согласованности между указанными принципами в модели "ЩН) достичь не удалось. И, по-видимому, это не удалось потому, что здесь возникли такие проблемы теории множеств, которые в языке вычислений с оракулами заведомо не могут быть разрешены. В связи с этим, в главе 3 осуществлено исследование различных форм этих принципов в рамках аксиоматической теории множеств.

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

В 3.1 принцип рефлексии рассмотрен без классов и без принципа интенсиональности. Введена формальная система So, которая описывает теорию множеств с двумя видами объектов: М-объекгы и С-объекты. Для С-объектов выполняются все аксиомы ZF, включая схему аксиом подстановки, распространенную на все формулы S0, и такая же полная схема аксиом подстановки введена для Af-объектов. Каждой формуле ф, составлен ной из переменных для С-объектов, соответствует двойственная формула Ф, получаемая из р путем замены этих переменных на одноименные переменные для М-объектов. Для таких формул в So введен принцип рефлексии в следующем виде схемы:

(V )( ф( х) - ф( х) ) . Доказано, что в S0 выводимо существование сильно недостижимого кардинала, но если в So удалить аксиомы подстановки для М-объектов, то это утверждение становится не выводимым. В теореме 3.3 доказано, что непротиворечива относительно системы ZFC плюс следующая формульная схема Мало: УоЭ!рф( х, р) - 35( Regfi) л Va, Р( a 5 л ф(а, Р) -» р 8))), где ф(а, Р) - произвольная формула S0, составленной из переменных для С-объектов.

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

1). Доказуемы все аксиомы , кроме "каждое множество есть класс". 2). Доказуемо существование регулярного и сильно недостижимого кардинала.

3). Доказуемы формульная схема Мало, существование кардинала Мало и существование кардиналов гипер-Мало любых трансфинитных порядков. 4). S\ совместна с аксиомой конструктивности.

Затем ,& усиливается путем распространения схемы аксиом выделения на все формулы системы 5i, тогда в полученной системе S2 доказуемо существование измеримого кардинала.

Так как системы S\ и S2 имеют довольно нетрадиционный характер, то желательно было бы оценить возможные виды на их непротиворечивость относительно какой-нибудь гипотезы, сформулированной в языке ZF. Естественно, что в формулировке такой гипотезы должно быть задействовано предположение о существовании достаточно больших кардиналов. Поэтому в 3.4 произведено сравнение этих систем с системой ZF, расширенной некоторыми видами подобных гипотез. В результате была получена специальная аксиома согласованного выбора (СВ), которая достаточно просто фор-- - мулируются в языке ZF. Доказано, система S2 непротиворечива относительно ZF + СВ. Заметим, что непротиворечивость системы ZF + СВ весьма проблематична, но, по крайней мере, в формулировке СВ отсутствуют какие-либо ссылки на воображаемые "тексты" неопределенно мыслимого языка и тому подобное. И так как вопрос о совместности рассматриваемых принципов остается открытым, то в заключительной части главы 3 подробно обсуждается создавшаяся ситуация.

В заключение этого раздела приводим сведения о публикациях автора по теме диссертации. Общая теория вычислений с частичным оракулом, основные понятия которой изложены в 1.1 и 1.2, есть результат коллективного творчества. Она была создана в 1970-х годах в работах Н. В. Белякина и его учеников, в число которых входит автор. Некоторые результаты этой теории, связанные с существованием селекторных функций и со свойствами сильно фундированных и разложимых оракулов, принадлежат автору. Они опубликованы в [13], и вошли в учебные пособия [16], [27]. Остальные результаты главы 1, связанные с конструктивизацией математического анализа и дескриптивной теории множеств, сначала были опубликованы в [13], [14], а затем в более общем виде были изложены в [17], [21], [27].

Методы построения оракулов, рассматриваемые в 2.1 и 2.2 главы 2, были изложены в [14]. Основные конструкции 2.3 - 2.5, связанные с моделированием арифметики трансфинитных типов, опубликованы в [15], [18], [19], и некоторые вопросы, связанные с разработкой используемой здесь техники, опубликованы в [20], [22]. Оракульное моделирование ct-pe-курссии опубликовано в [23].

Формальные системы, рассматриваемые в 3.1 - 3.3 главы 3, построены и исследованы автором, результаты этих исследований опубликованы в [24], [25], [26]. Исследования 3.4, 3.5, связанные с обоснованием непротиворечивости этих систем, осуществлены в неразделимом сотрудничестве с Н. В. Белякиным и их результаты опубликованы в [7], [8], [10].

Также основные результаты данных исследований были анонсированы в тезисах докладов Всесоюзных и Всероссийских конференций по математической логике (1974-1992), Сибирской школы по многообразиям (Барнаул, 1988), Ш Международной конференции по алгебре (Красноярск, 1993), П Сибирского конгресса по прикладной и индустриальной математике (Новосибирск, 1996), Международной конференции "Логика и приложения" (Новосибирск, 2000). Результаты, связанные с моделированием математических конструкций, докладывались автором на научном семинаре Ленинградского отделения ИМ АН СССР (Ленинград, 1974) и на семинаре Вычислительного центра Латвийской ССР (Рига, 1974). Методы построения оракулов докладывались на Всероссийской конференции "Прикладная логика" (Новосибирск, 1994). Исследования формальных систем докладывались на научном семинаре "Теория моделей"(Новосибирск, 1993), на семинаре "Алгебра и Логика"(Новосибирск,1995), на Сибирском конгрессе по -v прикладной и индустриальной математике (Новосибирск, 1996), на конференции "Логика и приложения" (Новосибирск, 2000). 

Необходимые условия для конструктивизации анализа

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

Наиболее четкое описание в языке программирования получают те математические объекты, которые можно выразить конечным множеством натуральных чисел, т.е. представить их как объекты типа 0. Рассматриваемые нами вычисления с оракулом позволяют осуществлять бесконечные переборы элементов любой вычислимой с этим же оракулом последовательности чисел. Поэтому достаточно четкое описание в языке таких вычислений имеют также объекты, выразимые с помощью бесконечных вычислимых последовательностей чисел, т.е. представимы как объекты типа 1. Моделирование объектов типа 2 и более высокого типа осуществляется с помощью подходящих вычислимых функций, которые применяются к соответствующим кодам аргументов этих объектов. Такие коды определяются не однозначно и могут образовывать неразрешимые совокупности, поэтому требуемая четкость описания моделируемых объектов исчезает, и полученные вычислимые аналоги моделируемых конструкций могут создавать аномальные или искусственные ситуации. Основная цель исследований - выделить условия, которые позволяют избежать подобные ситуации при данной конст-руктивизации математического анализа и дескриптивной теории множеств.

Первоначально такие исследования мы производили с помощью вычислений на машинах с так называемым гиперарифметическим оракулом. При этом сравнительно легко удалось конструктивизовать значительную часть математического анализа. Поэтому в 1.1 мы описываем основные свойства гиперарифметического оракула и обобщаем эти свойства на случай произвольного оракула. Затем в 1.2 из полученного набора условий выделяем минимальные требования, которым должен удовлетворять оракул F, чтобы обеспечить определенные удобства при оракульной конструктивиза-ции анализа. Ясно, что мы не сможем строго обосновать необходимость таких условий и что можем лишь говорить об их эвристической необходимости. Поэтому при отборе необходимых условий сначала мы ориентировались на указанные выше трудности конструктивной математики. В 1.3-1.5 в терминах вычислений на машинах с оракулом F, удовлетворяющим выделенным условиям, мы производим обобщенную конст-руктивизацию основных понятий математического анализа и дескриптивной теории множеств. При этом мы отдаем себе отчет в том, что данная конст-руктивизация утрачивает всякую связь с философскими и методологическими принципами конструктивной математики. Формально рассматриваемые нами модели анализа можно построить в рамках системы ZF и обычной логики.

Машина с оракулом - это пара объектов (М, F), один из которых является конструктивным (машина М и ее программа), а другой - теоретико-множественным (оракул F). Такая машина работает согласно своей программе и может вычислять вопросы, представляемые числовыми кодами, которые передаются на выход оракулу. Программа - это программа обычной машины Тьюринга, дополненная специальными спрашивающими командами. Оракул - частичная числовая функция F, присоединяемая к специальному входу машины. Заметим, что к одной и той же машине можно присоединять разные оракулы, и с каждым из них она будет работать по-разному. Ответом на произвольный вопрос и является значение оракула F(u), это значение передается спрашивающей машине, и она продолжает работу. Если F(u) не определено, то работа машины не определена, и мы говорим, что машина застряла с оракулом F на вопросе и. Тогда в работе машины возможны три ситуации: 1) машина получает ответы на все свои вопросы и останавливается с некоторым результатом; 2) машина получает ответы на все свои вопросы и работает бесконечно; 3) машина застряла на некотором вопросе. В первых двух ситуациях считаем, что машина хорошо работает с данным оракулом. Производить фактические вычисления на машинах с оракулом невозможно, но, тем не менее, основные принципы программирования для таких машин совпадают с принципами обычного программирования. Классические машины Тьюринга (и их программы) мы можем рассматривать как машины с оракулом, которые при своей работе не задают вопросов. Тогда все процедуры, осуществимые с помощью обычных машин Тьюринга, непосредственно воспроизводятся на машинах с любым оракулом F. С другой стороны, наличие особой ситуации застревания не позволяет механически переносить некоторые стандартные конструкции из теории алгоритмов, и лишь при подходящем выборе оракула удается осуществить необходимые построения. Обычным способом строим геделевскую нумерацию программ машин с оракулом, и отождествляем машины с номерами их программ. Геде-левский номер пары г, Х , где z - номер машины с оракулом и х - ее аргумент, называется инициальной машиной. Запись z, JC F обозначает инициальную машину z, д; , соединенную с F. Через {z}F(xu ..., xk) обозначим числовую функцию от переменных . ,,..., Xk, вычислимую на машине с номером z, соединенной с оракулом F; такая функция называется F-вычисли-мой, Z.Z- F-номером этой функции. F-номера zb z2 одной и той же і -вьі-числимой функции называются F-эквивалентными; обозначение: zx F їг Пусть N= {О, 1,... , «, ...} - множество натуральных чисел; 7V - множество тотальных одноместных функций вида N - N; AF - область определения оракула F; B\F) - множество всех -номеров / -вычислимых функций из А ; B(F) - множество всех инициальных машин, хорошо работающих с оракулом F; B(F) - множество инициальных машин, которые с оракулом Постанавливаются.

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

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

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

Обобщенно-конструктивное пространство Бэра

Выделим минимальные условия, которым должен удовлетворять оракул F, чтобы обеспечить определенные удобства при конструктивизации математического анализа. Эти условия должны устранить причины возникновения указанных выше аномалий конструктивной математики. В первую очередь необходимо, чтобы оракул F позволял распознавать равенство чисел. При конструктивизации континуума F-вычислимые вещественные числа задаются с помощью F-кодрв, которые являются некоторыми элементами множества В (F). Тогда процедура распознавания равенства чисел сводится к проверке F-эквивалентности этих F-кодов. Легко показать, что -вычислимость такой процедуры влечет преднормальность оракула F. Поэтому рассматриваемый оракул F должен быть преднормальным.

Далее, каждое -F-вычислимое вещественное число имеет счетное множество і -кодов, поэтому некоторые алгоритмы, применяемые к F-кодам одного и того же числа, могут вести себя по-разному в зависимости от того, какой F-код рассматривается. Это создает определенные трудности при конструктивизации функций вещественного переменного. Но эти трудности исчезают, если существует -вычислимая процедура, позволяющая по произвольному .F-коду числа найти определенный канонический .F-код этого числа. Это условие приводит к следующему специальному понятию, не имеющему аналога в теории алгоритмов и конструктивной математике.

ОПРЕДЕЛЕНИЕ 1.8. Оракул F обладает каноническими номерами на B (F)t если существует F-вычислимая функция kid) такая, что Ыа) называется кодирующей функцией, а ее значения - каноническими F-номерами. \ Укажем некоторые условия, при которых F обладает каноническими номерами на B\F). ТЕОРЕМА І.І. Регулярный, слабо фундированный и разложимый по T(F) оракул F обладает каноническими номерами на B (F). ДОКАЗАТЕЛЬСТВО. Пусть а є B\F). Тогда канонический Р-номер На) определим следующим образом. По лемме 1.3, существует z е T(F) такой, что a[F] a[F2]. Поэтому следующее множество непустое: Da={zeT(F)/a[F\ a[Fz]AVn( n eTz a[F\ a[Fbi2;n)])}. Согласно регулярности и нормальности F, множество Da является іміере-числимым равномерно по а є B (F), тогда с помощью селекторной функции можно выбрать некоторый элемент z(a) є Da. Для такого элемента, в силу разложимости F, множество Са- { а є B (FZ(a)) I a [Fz(a)] a[F\} является F-разрешимым. Тогда с помощью F выбираем наименьшее а є Са, для которого г{а ) имеет наименьший ранг z(a% Выбранное а есть канонический F-номер к(а). Теорема доказана. Итак, условия регулярности, слабой фундированности и разложимости по T(F) устраняют две основные причины возникновения аномальных ситуаций при моделировании анализа. Кроме того, требование регулярности оракула F является достаточно естественным, так как оно дает определенное комфортное обращение с .F-перечислимыми множествами. Теперь покажем, что введение этих условий не нарушает общности рассуждений в данных исследованиях. Основные элементы рассматриваемого ниже континуума .Л определяются с помощью тотальных F-вычисли 34 мых функции. Как было отмечено во введении, такие функции составляют "ядро" -вычислимости. Поэтому если при замене оракула F другим оракулом "ядро" остается неизменным, то и соответствующие этим оракулам континуумы будут совпадать, а изменится только "оболочка" континуума. Это наблюдение приводит к следующему понятию равнообъемности оракулов. ОПРЕДЕЛЕНИЕ 1.9. Оракулы F\ и F2 называются равнообъем-ными, если любая одноместная тотальная функция, вычислимая с одним из них, равномерно вычислима также и с другим оракулом, т.е. существуют машины qi и q2, для которых справедливы соотношения z є B\Fi) - {qi}F\z) определено и VJC{{qx}F\z))F\X) = {z}F\X)\ z є B\F2) - {q2}F\z) определено и VJC{ {q2}F\z)}F\X) = {z)F\x). Заметим, что здесь условие существования машин q\ и q2 является существенным, ибо известен пример оракулов, у которых классы вычислимых одноместных тотальных функций совпадают, но оракулы не равнообъемные в смысле данного определения ([11]). ЛЕММА 1.6. Для любого оракула F можно построить равнообъ-емный ему слабо фундированный оракул Н. ДОКАЗАТЕЛЬСТВО. Для построения оракула Н трансфинитной индукцией по у определяем последовательность функций Н Н1 Н Н +1 в которой FP = 0; и если у - предельный ординал, то Н1= и{ Н / а у}. Далее, если Н1 определена, то полагаем: Стандартным способом доказывается, что последовательность" функций Н1 монотонно расширяется и стабилизируется на некотором счетном ординале у0. Тогда искомый оракул Н есть Н \ Лемма доказана. Отсюда следует, что при моделировании континуума рассматриваемый оракул F всегда можно считать слабо фундированным. Кроме того, легко доказывается, что если оракул F преднормальный, то любой равно-объемный ему оракул также является преднормальным ([27, с.81]). Поэтому, в данных исследованиях можно считать, что любой преднормальный оракул одновременно является слабо фундированным. Далее, нас интересуют оракулы Ft которые обладают каноническими номерами на B\F), поэтому особое значение имеет следующий факт. ТЕОРЕМА 1.2. Если оракул Fi обладает каноническими номерами на B\Fi), то любой равнообъемный ему оракул F2 также обладает каноническими номерами на В (F2). ДОКАЗАТЕЛЬСТВО. Пусть Fu F2 удовлетворяют условию.теоремы, машины qlt q2 из определения 1.9 и kx(z) - кодирующая функция, соответствующая F\. Тогда для F2 в качестве кодирующей функции можно взять функцию k2(z)3 определяемую согласно следующим пунктам 1-2. 1. Сначала находим номер машины W, которая с оракулом Fi по дан-номуг последовательно вычисляет значения Zi= {q2} \z), z2=ki(Zi), и выдает z2 в качестве результата работы. 2. Затем находим значения Wi ={qx} F\w)t z2={Wi} F\z), z3 = {qi} F\z2), и полагаем k2(z) =z3. Из определений 1.8 и 1.9 легко следует, что k2(z) является -вычислимой кодирующей функцией для B\F2). Теорема доказана. Теперь, не нарушая общности рассуждений, можно считать, что любой оракул F, обладающий каноническими номерами на B (F), является также слабо фундированным. Более того, в этом случае F- нормальный." ТЕОРЕМА 1.3. Если оракул F слабо фундированный и обладает каноническими номерами на B\F)t то он нормальный. ДОКАЗАТЕЛЬСТВО. Пусть k(z) - .F-вычислимая кодирующая функция. Каждому х ставим в соответствие номер zx машины, которая с аргументом / и оракулом F копирует первые t тактов работы инициальной машины X F. Если х р остановилась, то zx выдает результат 1; если х ? не остановилась, то zx выдает результат 0; если х р застряла, то zx тоже застревает. Теперь, используя k(zx) и свойства (С12), (С13), легко показать і -вьічислимость функции hF из определения 1.4. Теорема доказана.

Теоремы о существовании точных границ ограниченных множеств

Рассмотрим объединение множеств: М= VJ{ М„ / « eTV}. Ясно, что Л/содержится в интервале (-1; 1) , а так как множество T(F) бесконечное, то точная верхняя граница М в классическом континууме равна р0 = sup{$n / п eN). Здесь все рл є/ ] поэтому число р0 является точной верхней границей Мив континууме Г. Тогда, согласно первоначальным замечаниям, теорема доказана.

Отметим так же, что указанные выше рациональные числа рл , образуют фундаментальную последовательность точек Г9 но эта последовательность не имеет предела в Г. Тогда, согласно замечанию, сделанному после определения 1.11, эта последовательность не является -вычислимой. Отсюда следует, что не существует / -вычислимой процедуры, позволяющей по F-коду множества Мп вычислять F-код его точной верхней границы.

Доказанное утверждение описывает ситуацию в Г, которая, с точки зрения классического анализа, является необычной. Анализ этих рассуждений показывает, что определение множества М существенно использует алгоритмические свойства F-кодов точек Г. А эти свойства тесно связаны с множеством T{F), не являющимся / -разрешимым. Тем самым, возникла ситуация, при которой неразрешимая проблема теории вычислений создала неразрешимую проблему математического анализа.

С другой стороны, налагаемые на оракул/7, условия являются достаточно сильными. Они позволили построить / -вычислимую кодирующую функцию ki, определить канонические коды С для точек Г и, тем самым, были преодолены определенные трудности при данной конструктивизации анализа. Далее, эти условия позволили ввести согласованную и / -вычисли 46 мую трансфинитную структуру на множестве Г, и благодаря этому, мы можем доказать положительный аналог континуум-гипотезы в Г. Для этого произведем конструктивизацию соответствующих понятий в Г. Пусть запись G:A= В обозначает отношение: "функция G взаимнооднозначно отображает множество А на В ".

ОПРЕДЕЛЕНИЕ 1.13. Пусть М,иМ2 - множества в Г. Мх равно-мощно Мг в Г, если существует функция G в / такая, что G: Мх М2\ обозначение: М\ =r -. Бесконечное множество М в Г называется счетным в Г, если M=rN в противном случае М называется несчетным в Г. Легко доказывается, что отношение =р коммутативно и транзитивно, при этом существенно используется свойство (С12). Для доказательства континуум-гипотезы вГмы применим специальную технику, охватывающую практически все методы теории алгоритмов и обобщенных вычислений с оракулами. Главным моментом этой техники является сведение отношения счетности множества в Г сводим к / -разрешимости множества канонических F-кодов точек этого множества. ТЕОРЕМА 1.6. Для того чтобы бесконечное F-конструктивное множество М было счетным в Г, необходимо и достаточно, чтобы отношение х є Мг\С было F-разрешимым. ДОКАЗАТЕЛЬСТВО. Пусть М- счетно в Г и машина # вычисляет взаимно однозначное отображение Nr\C на МпС. Тогда доказуемо соотношение: х є МпС - (3 п є NnC){ {q}F(ri) = д:). Согласно (С9), для каждого натурального числа п с помощью F можно вычислить его F-код п = &(п), затем вычислить его канонический F-код k\(n ) и значение {q}F(ki(nr)). А так как F - нормальный оракул, то правая часть предыдущего соотношения F-разрешима. Обратно, если отношение X є Мс\С F-разрешимо, то существует машина, которая с оракулом F вычисляет взаимно-однозначное отображение . МпС на N. Отсюда легко следует, что множество Мечетно в Г. Теорема доказана. Заметим, что, по лемме 1.8, отношение х е С не является -F-разрешимым, поэтому обобщенно-конструктивный континуум Ґ несчетен в Г. С другой стороны, очевидно, что для натуральных чисел множество NnC является F-разрешимым, ТОТ да множество N счетно в Г. Во введении мы отметили, что при неформальном изложении анализа встречаются рассуждения, в которых подразумевается возможность распознавания непустоты и бесконечности множеств. Покажем, что аналог такой процедуры в Г отсутствует. ЛЕММА 1.10. Процедура распознавания несчетности множества в Г по его F-коду не является F-вычислимой. ДОКАЗАТЕЛЬСТВО. В лемме 1.9 по каждому z эффективно строится імсод множества Az в Г такого, что АгпС = { а є С / \z\ , \\а\\). Согласно свойству (С8), а также по лемме 1.8 и теореме 1.6, отсюда следует, что z. є T(F) - А2 несчетно в Г. Тогда если бы рассматриваемая процедура распознавания была -F-вычислимой, то множество T(F) было бы F-разрешимым, что невозможно. Лемма доказана. Заметим, что данное утверждение описывает еще одну необычную ситуацию в Г, и причина ее возникновения в том; что определение множеств Az вновь существенно использует свойства .F-кодов точек/1. Следующее утверждение - F-вычислимый аналог континуум-гипотезы. ТЕОРЕМА 1.7. Если бесконечное множество М в Гне является счетным в Г, то оно равномощно Г в Г. ДОКАЗАТЕЛЬСТВО(с помощью леммы о рекурсии). Сначала произведем полное упорядочение множества С. Ранг \\а\\ определен для всех натуральных чисел, поэтому для любыххгу є N полагаем хЛГу, если x IMIv(x»yAX ). По лемме 1.8, для каждого а є С отношение х /.га является і -разреши-мым равномерно по а. Теперь, пусть множество М несчетно ъГи р-F-код М. В силу регулярности Fn -разрешимости х /.гО., эффективно по р находится наименьший (относительно /г) элемент Ъм є МпС. Пусть а є С и е- общерекурсивная функция, определенная на множестве Са - {х є С / х Zrd},n такая, что функция g = Ах {e(x)}F(0) взаимно однозначно отображает множество Са в МпС с сохранением отношения х Z-гУ Полагаем е(а) есть номер машины w\ которая на аргументе 0 осуществляет следующие процедуры. 1. Если а —наименьший элемент С, то w выдает Ъм. 2. В остальных случаях w вычисляет перечисляющий F-номер следующего множества Ма : Ма={Ье МпС I (Ve eCX a Zra -» {e(a)}F(0) Ь)л (yb e MnQib Zrb - {3a,eC){a,Z.ra)A{e{ar)}F{Q)) = b,y)}. Заметим, что для каждого b є МпС указанные в правой части Ма отношения / -разрешимы по е, Ь,аир,а само Ма/ -перечислимо равномерно по е а и р. Множество Ма не может быть пустым множеством, ибо в противном случае МпС равнялось бы множеству: { ЪI (За е Q( a Zr а л {e(a)}F(0) = b)}, которое является F-разрешимым, а это противоречит несчетности М. Кроме того, из определения отношения Zr следует, что Ма содержит только один элемент. Этот элемент является наименьшим і -кодом из МпС, не имеющим прообраза в Са при отображении g. Поэтому w , с помощью селекторной функции Цр, выбирает b є Ма и выдает его в качестве результата. Функция е(Х) определена для всех X є С . Индукцией по рангам канонических і -кодов доказывается, что функция g = 7JC. {e(x)}F(0) отображает С на МпС взаимно однозначно с сохранением отношения Zr. (Заметим, что такая индукция легко формулируется в рамках системы A(F) и обосновывается с помощью принципа lzl-индук-ции, рассмотренного в 1.2). Отсюда следует, что М =гГ. Теорема доказана. Добавим, что, согласно лемме о рекурсии, данная теорема выполняется равномерно по F-кору несчетного множества М в Г.

Аксиома конструктивности и существование измеримого кардинала

Считаем, что оракул F - регулярный, слабо фундированный и разложимый по T(F). Известно, что Л взаимно однозначно отображается на множество иррациональных чисел (например, с помощью непрерывных дробей [42, с.24]). При этом можно сделать так, чтобы точки пространства IF отображались в / -вычислимые иррациональные числа, и существовала рекурсивная функция, которая по F-кору точки 1р вычисляет .F-код соответствующего і -вьічислимого иррационального числа. Поэтому точки 1р можно рассматривать как точки Г, и каждое 5-множество в 1р можно рассматривать как подмножество Г. Тогда данные понятия - аналоги соответствующих понятий континуума Г, и все утверждения, доказанные в Г, без существенных изменений применимы к данным понятиям. В частности, основные свойства непрерывных функций в Г распространяются на і -конст-руктивные непрерывные отображения рассматриваемых пространств.

Множество интервалов ранга къв 1риъ IF является счетным. Поэтому существует эффективное соответствие между интервалами ранга к в IF и интервалами ранга к в 1р. Тогда можно построить .F-вычислимое отображение G всех интервалов пространства 1р на интервалы пространства IF такое, что каждый интервал си ранга к+1, содержащийся в некотором интервале Сщ ранга к, отображается в интервал Gv = G(ou) пространства IF , который имеет тот же ранг к+1 и содержится в соответствующем интервале Gvi= G(Gui) ранга к. Каждая точка а єіропределяет бесконечную -конструктивную последовательность вложенных друг в друга интервалов вида {а« / Щ = 0, а(&) , к= 1, 2,...}, содержащих единственную общую точку a . Эту последовательность интервалов G отобразит в такую же і -конструктивную последовательность вложенных друг в друга интервалов пространства IF. Полученная последовательность интервалов в IF будет содержать единственную общую точку р EIF и легко увидеть, что і -код точки р .F-вычислим по F-коду а. Тогда отображение a - Р является искомым гомеоморфизмом If на IF. Теорема доказана.

Используя преднормальность F и свойство (С6), легко доказать, что если G — непрерывное -конструктивное отображение вида Ip - IF, то для любых интервалов си с IF\ GV С: IF2 отношения G[GU] С GV, G[GU] С: GV F-разрешимы по и ,V.

Переходим к определению Д-множеств в /g. Пусть z є T(F) и g --F-номер і -вьічислимой функции, определенной на т2 так, что если и -внутренняя вершина тг, то g(u) є {0, 1}, и если и - концевая вершина TZ, то {и) есть индекс интервала или его дополнения в 1р. (Здесь функция g отождествляется с ее і -номером). Тогда индукцией по тг каждой вершине и етг ставим в соответствие следующее множество Еи с IF : 1) если и - концевая, то Еи есть интервал или его дополнение в/ с индексом g(u); 2) если и- внутренняя и g(w) = 0, то Е„ =KJ{Eu nl и п ет2}; 3) если и - внутренняя и g(u) = 1, то Еи = С\{ Еи „ I и п ет2}. Множество Ек , соответствующее начальной вершине т2, называется В-множеством elF , z,g - его F-индекс; \z\ - ранг индекса z, g . F-конструктивные последовательности В-множеств в 1р определяются с помощью -F-вычислимых последовательностей -индексов этих объектов. Прежде, чем рассматривать свойства -множеств в 1р, покажем, что они являются -конструктивными в смысле определения 1.11.Ъ данном параграфе мы рассматриваем IF как основное пространство, поэтому все понятия определений 1 ЛО и 1.11 мы переносим в IF, заменяя в этих определениях F-коды точек Г на F-коды точек IF И отношение т на отношение /. При этом, как уже было отмечено выше, все утверждения, доказанные в Г, без существенных изменений переносятся в IF. ЛЕММА 1.1 б. Каждое В-множество в Ір является F-конструк-тивным множеством в смысле определения 1.11 и его F-код находится эффективно по его F-индексу.

Доказательство( с помощью леммы о рекурсии). Пусть z, g -і -индекс 5-множества Е и е - частично рекурсивная функция такая, что если у, h - F-индекс Л-множества Е и \у\ z, то е( у, h ) - F-код множества Е . Тогда e( z, g ) есть номер машины W, которая с оракулом F на произвольном аргументе сначала выясняет: верно ли, что \z\ = О Если это верно, то Е есть интервал Бэра или его дополнения, его і -индекс равен g( ). Поэтому в этом случае w работает, как машина, вычисляющая характеристическую функцию Е в 1р . Если \z\ 0, то w вычисляет значение g( ). Если g( ) = 0, то w работает, как машина, вычисляющая характеристическую функцию множества и{ Еиш1 /w exz}; если g( ) = 1, то W работает, как машина, вычисляющая характеристическую функцию множества п{ Еит1 т етг}. Здесь Еит — Л-множества, соответствующие вершинам /я ет2; F-кощл этих множеств находятся эффективно по z, g и ё. Лемма доказана.

Непосредственно из определения 2?-множеств в 1р следует, что интервалы в 1р, ИХ дополненияв 1р и -конструктивные последовательности точек или интервалов в IF являются Л-множествами в IF . В частности, любое счетное множество в 1р является Л-множеством в IF . Легко доказывается, что класс -множеств в 1р замкнут относительно операций объединения и пересечения, применяемых к -конструктивным последовательностям JB-МНОЖЄСТВ, а так же замкнут относительно операции взятия дополнения. Эти свойства позволяют ввести следующую классификация 5-множеств в IF, которая является .F-вычислимым аналогом классической иерархии боре-левских множеств.