Моделирование оснований математических теорий тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

ВВЕДЕНИЕ

1. Общая характеристика темы

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

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

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

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

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

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

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

Конечно, при таком подходе возникает вопрос о возможности построения соответствующего оракула, т.е. имеем некоторый вид проблемы обоснования языка программирования. Не касаясь основания математического анализа, мы решаем такую проблему, привлекая уже методы теории множеств. А именно, используя аксиомы системы 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. В этой ситуации легко подметить, что запас "определимых" классов может быть малым, и даже меньше, чем запас всех множеств. Разумеется, что эта интуиция должна быть как-то отражена при выборе аксиом соответствующей теории множеств и классов. При этом сам выбор аксиом должен быть настолько удачным, чтобы давать конкретные интересные результата. И здесь хорошим ориентиром служит сформулированный ниже принцип рефлексии.

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

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

Vx е М) ((р(х) <-> (рм(х)).

Полученное расширение BG будет, конечно, консервативным, однако напрашивается специальный способ его усиления, который существенно расширяет его первоначальные дедуктивные возможности. Трактуя классы как свойства множеств, описанные в каком-нибудь неопределенно мыслимом языке, мы можем распространить принцип рефлексии и на выражения этого предполагаемого языка. Тогда, согласно принципу рефлексии, реля-. . тивизация фм формулы ф, задающей некоторый класс Х3 будет выделять из Мто же подмножество, что и сама ф : хеМ1(^(х)} = {хеМ/ц?(х)}=ХпМ. Это подсказывает нам, что при релятивизацию нормальных 2?(7-фор-мул, не содержащих кванторов по переменным для классов, помимо ограничения кванторов по множествам константой М надо каждое свободное вхождение переменной для классов заменить на ее пересечение с М (например,

X заменяется на ХпМ). Теперь усиленный принцип рефлексии формулируется для каждой нормальной £С?-формулы, более того, ситуация становится особенно интересной, если мы дополнительно постулируем регулярность ранга множества М. Например, в полученной системе выводимо существование некоторых больших кардиналов, таких, как кардиналы Мало, гипер-Мало, гипергипер-Мало и т. д. Далее, этот принцип дает жесткое ограничение на объем классовой надстройки этой системы. Оказывается, что подразумеваемую совокупность всех классов можно взаимно однозначно заиндексировать элементами некоторого множества Wm вида Wm с Р(М). Возникает вопрос, насколько широким может быть это множество и не исчерпывает ли оно все Р(М) ?

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

ПРИНЦИП ИНТЕНСИОНАЛЬНОСТИ:

Vx(xczM-> ЗХ(х=ХпМ)).

В главе 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 году и встретила отрицательное отношение многих математиков. Это объяснялось, во-первых, ее чисто экзистенциональным характером, отличающим ее от аксиом ZF, а во-вторых, некоторыми "необычными"едствиями, противоречащими интуиции "здравогоысла". Например,помощью АС выводимоществование неизмеримого по Лебегу множества иществование упомянутого выше парадоксального разбиения шара. С другойорона, АС широко используется в классической математике, например,ее помощью доказываются: принцип вполне упорядочения;етностъ объединенияетногомействаетных множеств; эквивалентность двух форм определения непрерывной вещественной функций;етная аддитивность меры Лебега. Но было замечено, что для доказательства последних двух утверждений достаточноетной аксиомы выбора. А вязиэтим отметим, чтоществует модель ZFy в которой выполняетсяетная аксиома выбора, а также каждое множество действительных чисел измеримо по Лебегу. Такая модель была построена в предположенииществования недостижимого кардинала [32,48].

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

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

Еще одна программа обоснования математики - это разветвленная теория типов, которая была введена Б. Расселом в 1908 году. Считалось, что основной причиной возникновения противоречий теории множеств являлись непредикативные определения математических объектов, когда определяемый объект может участвовать в своем определении. Было предложено расчленить предметную область на конечные типы, соответствующие натуральным числам, и для каждого типа ntO была сформулирована схема аксиом свертывания:

3y+vVx". (xf е y+1 <-> у(хГ)).

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

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

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

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

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

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

Единственно, что при этом терялось, это точечное представление вещественной функции. Фактически это было возвращение к старинному представлению о вещественной функции, как о чем-то заданном аналитически (т.е. посредством некоторой формулы или чем-то вроде "текста" в некотором не вполне формальном языке). Хотя в работе Н. А. Шанина этот момент, так сказать, оставался в тени, он скорее ориентировался на приемы современного функционального анализа.

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

Независимо от теории вычислений возникла теория иерархий. Иерархия - классификация тех или иных математических объектов вответствииихожностью. Первые иерархии были построены в дескриптивной теории множеств, и одна из них - это иерархия проективных множеств ([35], [1]). Д. Деккер, Д. Майхилл и В. А. Успенский предприняли попытки построения иерархии рекурсивно перечислимых множеств, используя чисто алгоритмические аналоги понятий дескриптивной теории множеств. Это привело к возникновению понятий продуктивного и креативного множеств, которыеграли заметную роль в теорииепеней неразрешимости ([47, 158]). Хотя такая аналогиядескриптивной теорией множеств была неишком органичной,орее, чисто внешней. Затем в математической логике были построены арифметическая и аналитическая иерархии числовых множеств и отношений, задаваемых формулами логических языков ([56], [61]). Эти иерархии были распространены на функции, появились арифметические и гиперарифметические функции. Такие функции уже являлись некоторым видом обобщенных вычислений, и В. Риттер ([63]) и JI. Хоудз ([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) вводить на множестве /^вычислимых объектов, достаточно согласованную и /^-вычислимую трансфинитную структуру; 4) вводить канонические номера /^-вычислимых тотальных числовых функций. Показано, что введение этих условий не нарушает общности данных исследований. Кроме того, введена аксиоматическая система A(F)y которая показывает, что формально рассматриваемые здесь понятия и рассуждения осуществимы в рамках системы ZF и обычной логики.

В §1.3 введен обобщенно-конструктивный континуум Г, точки которого определены, как пределы ^-вычислимых фундаментальных последовательностей рациональных чисел; геделевские номера машин, задающих эти последовательности названы .F-кодами точек. Функции вещественного переменного в Г задаются с помощью /^-вычислимых функций над ^-кодами точек Г, а множества в Г вводятся с помощью характеристических функций в Г. Аналогично предыдущему определены F-коды этих объектов. Кроме того, последовательности каких-либо объектов в Г задаются с помощью F-вычислимых последовательностей .F-кодов этих объектов. Показано, что при выполнении этих условий в Г выполняются положительные аналоги многих классических утверждений математического анализа, включая все аксиомы вещественных чисел и все свойства непрерывных функций вещественного переменного.

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

Поэтому в

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

В §1.5 определено обобщенно-конструктивное пространство Бэра If как множество /^-вычислимых бесконечных последовательностей натуральных чисел, /^-множества в If определены индуктивно с помощью операций счетного объединения и счетного пересечения, применяемых к интервалам Бэра и ранее полученным /^-множествам. При этом совокупность интервалов Бэра и применяемые операции задаются с помощью /^-вычислимых деревьев с обрывом цепей; F-код такого дерева назван /^индексом Л-множе-ства в If. С помощью F-индексов введена трансфинитная классификация В-множеств в If. gf(IF), где у пробегает вычислимые ординалы. Введенные классы монотонно расширяются с ростом у и инвариантны относительно операций конечного объединения и пересечения. Для каждого такого класса доказана его топологическая инвариантность и доказано существование плоского /^-множества в If, универсального для множеств этого класса. Для дальнейшей конструктивизации дескриптивной теории множеств необходимо, чтобы операция проецирования плоских ^-множеств в If была jF-вычислимой. В лемме 1.17 доказано, что F-вычислимость. этой операции влечет ^-вычислимость процедуры распознавания непустоты В-множеств в If . Затем показано, что по i^-кодам /^-множеств эта процедура не является jp-вычислимой. А в случае гиперарифметического оракула F0 эта процедура не является /^-вычислимой даже по /^-индексам. Аналогичная ситуация имеет место в связи с процедурой распознавания несчетности ^-множеств в If . Возникла проблема построения специальных оракулов F, для которых эти процедуры будут /^-вычислимыми.

В главе 2 некоторые подобные проблемы решаются положительно. Сначала в

§2.1 построены оракулы, которые непосредственно распознают пустоту и несчетность соотнесенных к ним ^-множеств по их F-индексам. Для таких оракулов определены yl-множества в If, как проекции плоских В-множеств в If. Показано, что такие множества обладают аналогами многих свойств классических /^-множеств; в частности, в теореме 2.3 доказано, что ^-множества в If суть непрерывные образы пространства If, а в теореме 2.4 доказано существование ^-множества в If, не являющегося ^-множеством в If. Затем, в

§2.2 произведена конструктивизация пространства Бэра в языке вычислений относительно семейств оракулов вида 7 = {Fa/ а е А^}. При этом применен особый способ задания ^-вычислимых функций в If, описанный выше в пункте 1. Построено специальное семейство оракулов "Рм*, в котором для выделенного оракула Fa0 в соответствующем пространстве Ifoo выполняется положительный аналог теоремы о существовании точных границ ограниченных множеств. В теореме 2.7 доказано, что для такого оракула две формы определения открытых и замкнутых множеств являются эквивалентными.

В §2.3 определена.формальная система L[v], в которой функциональные переменные g", И1 имеют трансфинитные типы т, к, являющиеся номерами ординалов некоторой ординальной нумерации v. Кроме обычных аксиом арифметики натуральных чисел в L[v] для каждого типа введена соответствующая схема аксиом свертывания вида:

V /Г)(Э^)(\//2*)[ = 0 о ф( /Г, /**)], где ф( /г, /г*) - формула Z[v], не содержащая переменной g".

Далее, определены одноместные тотальные функционалы трансфинитных типов. Введены семейства оракулов *?= {Fq/ G е zs, 5 < |v|}, в которых оракулы F q имеют индексы G, являющиеся конечными кортежами указанных функционалов. Относительно такого семейства I? определены ^вычислимые функционалы аналогично тому, как это сделано в

§2.2. Затем построено семейство оракулов .5?, в котором оракулы позволяют распознавать истинность формул системы Z[v], проинтерпретированных на вычислимых функционалах. Из таких функционалов построено семейство моделей { М&/ 5 < |V| } для Z[v] и ее подсистем Z,g[v] . Доказано, что эти модели не зависят от длины нумерации V.

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

ZF. При этом оказывается, что система Z,[v2] является полуформальной и такая аналогия не является полной.

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

Дальнейшее рассмотрение вопросов эффективности этих конструкций неизбежно приводит к а-рекурсии, поэтому в

§2.6 произведена "оракуль-ная" конструктивизация основных понятий а-рекурсии. Для ординала а = |T(F)|, являющегося длиной отрезка /^-вычислимых ординалов, рассмотрены две формы определения /^-вычислимого аналога а-рекурсивных функций. С помощью подходящего исчисления равенств L0(F) определены /"(/^-рекурсивные функции, и с помощью /^-вычислимых функций на F-кодах ординалов определены Д/^-вычислимые функции. Доказана эквивалентность этих определений при достаточно простом оракуле F. Затем определены Д/^-конечные множества ординалов, как ограниченные T(F)-pe-курсивные множества. Показано, что для этого понятия верны аналоги основных свойств конечных множеств чисел. Но, с другой стороны, в лемме 2.19 указано ограниченное Д/^-перечислимое множество, не являющееся ДР)-конечным. Исследование этой ситуации приводит к понятию T(F)-проектируемого ординала. В теореме 2.20 указаны необходимые и достаточные условия, при которых ординал а = |2XF)| не является 7ХР)-проекти-руемым.

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

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

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

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

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

V *)( ф( х) <-» ф( х) ) . Доказано, что в So выводимо существование сильно недостижимого кардинала, но если в So удалить аксиомы подстановки для М-объектов, то это утверждение становится не выводимым. В теореме 3.3 доказано, что непротиворечива относительно системы ZFC плюс следующая формульная схема Мало:

V<x3!рф(а, р) 35( Regfi) л Vet, Р( а < 5 л ф(а, Р) -» р < 5))), где ф(а, Р) - произвольная формула S0, составленной из переменных для С-объектов.

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

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

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

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

4). Si совместна с аксиомой конструктивности.

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

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

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

1. Арсенин В .Я., Ляпунов А.А. Теория А-множеств.Н Успехи матем. наук, 1950, т.5, вып.5, с.41-80.

2. Белякин Н.В. Обобщенные вычисления и арифметика второй ступени.// Алгебра и логика, 1970, т.9, №4, с.375-405.

3. Белякин Н.В. Обобщенные вычисления и арифметика третьей ступени. //Алгебра и логика, 1974, т.13, №2, с. 132-144.

4. Белякин Н.В. Об одном способе моделирования классической арифметики второй ступени./'/Алгебра и логика, 1983, т.22, №1, с.3-25.

5. Белякин Н.В. Вычисления с оракулом.// Труды ИМ СО АН СССР, 1989, т.12, с .4-24.

6. Белякин Н.В. Вычисления с оракулом: обобщенная селекция.// Сиб. мат. журнал, 1990, т.31, №4, с.192-196.

7. Белякин Н.В., Ганов В.А. Принцип рефлексии и схема Мало.// Вычислит, системы, Новосибирск: ИМ СО АН СССР, 1997, Вып. 158, с. 3-8.

8. Белякин Н.В., Ганов В.А. Обобщенный принцип рефлексии.// Вычислит, системы, Новосибирск: ИМ СО АН СССР, 1998, Вып. 162, с. 3-13.

9. Белякин Н.В., Ганов В.А Интенсионалъностъ, рефлексия, большие кардиналы.//Сиб. мат. журнал (ярхшш-ц печать) -loci, GJUl-ШУ.

10. Вопенка П. Математика в альтернативной теории множеств. -М.: "Мир", 1983.

11. Гамова А.Н. Обобщенные вычисления с оракулом.//Алгебра и логика, 1988, т.27, №2, с. 131-147.

12. Гамова А.Н. Метарекурсивность автономных нумераций.// Вычислит, системы, Новосибирск: ИМ СО АН СССР, 1987, Вып. 122, с. 145-156.

13. Ганов В.А. Обобщенно-конструктивный анализ.//Сиб. мат. журнал, 1973. т.14, №5, с.957-977.

14. Ганов В.А Обобщенные вычисления и дескриптивная теория множеств.// Сиб. мат. журнал, 1974, т.15, №6, С.1244-1261.

15. Ганов В.А. Функционалы порядковых типов. Ред." Сиб. мат. журнала", 1980, Деп. в ВИНИТИ №3230-80.

16. Ганов В.А. Обобщенные вычисления и джамп-операция. -Барнаул, Изд. Алтайского гос. ун-та, 1980, 52с.

17. Ганов В.А. Селекторная функция и континуум-гипотеза. -Ред." Сиб. мат. журнала", 1981, Деп. в ВИНИТИ № 94-81.

18. Ганов В.А. Машинно-оракулъное моделирование теории типов. -Ред. " Сиб. мат. журнала", 1985, Деп. в ВИНИТИ № 8092.

19. Ганов В.А. Вычислимые функционалы и арифметика ординальных типов.// Сиб. мат. журнал, 1986, т.27, №4, с.41-51.

20. Ганов В.А. Релятивизация итерированной клиниевской вычислимости. -Ред." Сиб. мат. журнала", 1987, Деп. в ВИНИТИ Ж7972-В.

21. Ганов В.А. Аксиоматизация вычислений с оракулами и континуум-гипотеза.// Вычислит, системы, Новосибирск, 1990, Вып. 13, с.135-152.

22. Ганов В.А. Об одном обобщении примитивных нумераций Белякина. -Ред." Сиб. мат. журнала", 1991, Деп. вВИНИТИ№158-В91.

23. Ганов В.А. Рекурсия на обобщенно-вычислимых ординалах.Н Сиб. мат. журнал, 1993, т.34, №4, с.61-65.

24. Ганов В.А. Об одном расширении теории SCT Нуделъмана.// Вычислит, системы, Новосибирск: ИМ СО АН СССР, 1995, Вып. 152, с.202-208.

25. Ганов В.А. О противоречивости метатеории Нуделъмана.ПАлгебра и логика, 1995, т.34, №1, с.41-43.

26. Ганов В.А. О границах применимости принципа рефлексии.!!Алгебра и логика, 1998, т.37, №2, С.127-143.

27. Ганов В.А., Белякин Н.В. Общая теория вычислений с оракулом. -Новосибирск, Изд. Ин-т математики СО АН СССР, 1989.136с.

28. Ганова Р.В. Обобщенные вычисления с двуместными оракулами.!'/Алгебра и логика, 1993, т.32, №5, с.479-496.

29. Девлин К.Д. Конструктивность.ИСиравочная книга по мат. логике, -М.: "Наука", ч.2,1982, С.158-200.

30. Заславский И.Д. Некоторые свойства конструктивных вещественных чисел и конструктивных функций.!! Труды Матем. ин-та им. В.А. Стек-лова, 1962, т.67, с.385-457.

31. Йех Т. Теория множеств и метод форсинга. -М.: "Мир", 1973.

32. Кекрис А., Московакис Я. Рекурсия в высших /ягшах.//Справочная книга по мат. логике, -М.:"Наука", ч.З, .1982, с. 166-223.

33. Клини С. Функционалы конечных типов, вычислимые на машинах Тьюринга Л В сб." Мат. логика и ее приложения", -М.: "Мир", 1965, с. 37- 46.

34. Коэн П. Дж. Теория множеств и континуум-гипотеза. -М.: "Мир", 1969.

35. Куратовский К., Мостовский А Теория множеств. -М.:"Мир", 1970.

36. Кюнен К. Комбинаторика.!/Справочная книга по мат. логике, М.: "Наука", ч.2, 1982,с.64-98.

37. Лузин Н.Н. Собрание сочинений. -М.: Изд. АН СССР, Т.2, 1958.

38. Лузин Н.Н. Лекции об аналитических мноэ/сествах и их приложениях. -М.: Гостехиздат, 1953.

39. Маккаи М. Допустимые множества и бесконечная логика.!I Справочная книга по мат. логике, -М.:"Наука",ч.1, 1982, с.235-288.

40. Марков А.А. Теория алгорифмов.!! Труды Мат. ин-та им. В.А.Стеклова, 1951, т.38, с.176-189.

41. Мендельсон Э. Введение в математическую логику. -М.: "Наука",-1971.

42. Натансон И.П. Теория функций вещественной переменной. -М.: Гос. из-дат. тех.-теор. лит., 1957.

43. Никифорова Е.Г. Некоторые модификации итерированной клиниевской вычислимости.!!Алгебра, и логика, 1986, т.25, №3, с.292-314.

44. Нудельман А.С. Об одном уточнении "наивной" теории множествГ.Кантора.//Вычис. системы, Новосибирск, 1990, Вып. 133, с.153-185.

45. Нудельман А.С. О метатеории множеств.!! Алгебра и логика, 1991,т. 30, №6, с.671-692.

46. Победил Л.Н Некоторые вопросы обобщенной вычислимости .//Алгебра и логика, 1973, т. 12, №2, с.220-231.

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

48. Шанин Н.А. Конструктивные вещественные числа и конструктивные функциональные пространства.Н Труды Мат. ин-та им. В.А. Стеклова, 1962, т.67, с.15-294.

49. Шор Р. А. Теория а-рекурсии.П Справочная книга по мат. логике. -М.: "Наука", 4.3,1982, С.134-165.

50. Цейтин Г.С. Алгорифмические операторы в конструктивных метрических пространствах.IУ Труды Мат. ин-та, 1962, т.67,с.295-361.

51. Щегольков ЕА. Элементы теории В-множеств.ИУспехи мат. наук, 1950, т.5, вып.5, с. 14-40.

52. Barwise J. Infinitary logic and admissible sets-.// J. symb. logic., 1969, v.34, №2, p.226-252.

53. Church A., Kleene S. Formal definitions in the theory of ordinal numbers.H Fundam. Math., 1936, v.28, p. 11-21.

54. Feferman S. Arithmetization of metamathematics in a general setting.// Fun-dam. Math., 1960, v.49, p.35-92.

55. Hodes L. Hyperarithmetical real numbers and hyperarithmetical analysis. Ph. D. Diss., Massachusetts Institute of Technology, Cambridge, 1962.

56. Kleene S. Recursive predicates and quantifiers.// Trans. Amer. Math. Soc., 1943, v.53, p. 41-73.

57. Kleene S. Recursive functional and quantifiers offinite types./! Trans. Amer. Math. Soc., 1959, v.91, p. 1-52. .

58. Kreisel G., Sacks G. Metarecursive sets.//J. symb. logic, 1965, v.20, p.318-338.

59. Kripke S. Transfinite recursion on admissible ordinals, I, II (Abstracts).// J. Symb. logic, 1964, v.29, №3, p.161-162.

60. Moschovakis Y. Abstract first order computability.il Trans. Amer. Math. Soc., 1969, v.132, p. 465-504.

61. Mostowski A. On definable sets of positive integers. //Fundam. Math., 1947, v.34, p.81-112.

62. Platek R. Foundations of recursion theory. -Thesis Stanford, Stanford University, 1966.

63. Ritter W. Some results in hyperarithmetical analysis. Ph. D. Diss., Massachusetts Institute of Technology, Cambridge, 1962.

64. Specker E. Nicht konstruktiv beweisbare Satze der Analisis./U. Symb. logic, 1949, v.14, p.145-158.

65. Turing A.M. On computable numbers, with an application to the Entschei-dungs-problem.H Proc. London Math. Soc.,1936, ser. 2, v.42, p. 230-265.

66. Vopenka P., Hajek P. The Theory ofSemisets. -North-Holland Publishing Co., Amsterdam, Academia Praha, 1972.ОГЛАВЛЕНИЕВВЕДЕНИЕ.:.:. 3

67. Общая характеристика темы. 3