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

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

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

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

руктивной математике. Отметим, что при неформальном изложении математического анализа мы часто встречаем процедуры и рассуждения, которые можно принять за алгоритмические. Например, при доказательстве существования предельной точки ограниченного множества вещественных чисел М описывается процесс построения стягивающей последовательности вложенных друг в друга отрезков [ак', Ьк]. При этом на каждом шаге осуществляется неалгоритмический шаг, связанный с распознаванием непустоты и бесконечности множеств вида [а*; Ь^глМ. Примеры подобных неалгоритмических шагов встречаются и в других ситуациях. Понятно, что можно было бы ограничиться рассмотрением только тех множеств континуума, для которых эти шаги являлись бы алгоритмическими. Но может случиться, что класс таких множеств очень беден или даже пустой. Поэтому возникает мысль произвести моделирование континуума в подходящем обобщенном языке программирования, который помимо обычных алгоритмических команд содержал бы специальные команды, позволяющие осуществлять необходимые неалгоритмические шаги. Удобным средством для такого моделирования является язык обобщенных вычислений на машинах с оракулом. При подходящем выборе оракула в таких вычислениях указанные неалгоритмические шаги можно осуществлять с помощью орашивающих команд.
Конечно, при таком подходе возникает вопрос о возможности построения соответствующего оракула, т.е. имеем некоторый вид проблемы обоснования языка программирования. Не касаясь основания математического анализа, мы решаем такую проблему, привлекая уже методы теории множеств. А именно, используя аксиомы системы ZFC, мы доказываем существование необходимых нам оракулов. Таким образом, язык программирования обобщенных вычислений с оракулом становится посредником между основанием анализа и теорией множеств. Заметим также, что вычислимость каждого вещественного числа для математического анализа, даже нацеленного на практическое применение, - не существенна. Так что, переходя к вычисления с оракулом, мы ничего не теряем. Дело не в самой по себе вычислимости, а в переходе от логического языка к алгоритмическому языку, т.е. к языку программирования, хотя бы и нереализуемому фактически.
Используя вычисления на машинах с оракулом, мы строим обобщенно-конструктивный континуум Г аналогично тому, как это делалось в конструктивной математике. Оказалось, что даже при выборе достаточно простого гиперарифметического оракула в Г легко доказываются аналоги всех начальных свойств классического анализа, включая все свойства вещественных чисел и непрерывных функций, и устраняются многие трудности конструктивного анализа, о которых упоминалось выше. Более того, в Г выполняется континуум-гипотеза. С другой стороны, в Г, как и в конструктивном континууме, точки имеют обобщенно-вычислимые коды, и функции над этими точками определяются с помощью обобщенно-вычислимых

Термы и формулы системы А (В) определяются стандартный образом, включая формулы вида Лх) = у, где х,у - некоторые термы. Кванторы навешиваются только на предметные переменные. Подразумевается, что предметные переменные принимают значения из Ы, символы арифметических операций, отношений =, < и константы 0,1,2,... имеют свой очевидный смысл.
Каждое рекурсивное отношение может быть описано в языке элементарной арифметики, который полностью содержится в языке системы А (В). Поэтому в А(В) существуют формулы, описывающие отношения вида:
(и е ЛО, щ =.(«)/, V с и, (/ < /А(м)), ( 2 - геделвеский номер неинициальной или неинициальной машины с оракулом), ( инициальная машина 2 вычислила вопрос Н/),ит. д.
Далее, пусть 2 - инициальная машина с оракулом, и, У - соответственно номера кортежей (ии ... , и„), (V,, ... , Уп) одинаковой длины. Через В{2, /, и, V) обозначим формулу системы А(В), описывающую отношение: {инициальная машина 2 работает I тактов, в процессе работы вычисляет вопросы иь ..., и„ и получает на них ответы У{, ... , у„, соответственно).
Так же существует формула Т2{г, /, у, И, У), описывающая предыдущее отношение с дополнительным условием: ( 2 останавливается с результатом у ). Если при этом нужно выразить условие: ( 2 работает с оракулом Р), то к указанным формулам добавляется формула:
(.Дм,) = г?! а ... л/мп) = уп).
Теперь, например, отношения г е В{В) и {д}^(х) = у выражаются . следующими формулами:
V/ (Эи, V е Я) Щи) = //г(г?) л Тх{г, /, и, у) л (V/ < №(и))/(и),) = (г?),]; Э/(Зи, V е ЛО Щи) = Ну) л Г2(<г, х>, (,у, и, у) л(У/< 1Ыи))ЛШ = (г?),].
Конечно, эти записи не являются формулами языка А(В), но построение настоящих формул по этим записям не составит труда. Аналогично показывается, что отношения 2 еВ{В), г еВ'(В), ~рг2 также выразимы в А (В) (даже, если мы не знаем, что обозначают символы Ъ, с, У, д). После этого отношение 2 еО(В) выражается следующей формулой:
2 еВ’{В) л(Уи е #)[{д}^(и) е{0,1} л({2}р(и) = 0 -»
(Уг;си)({д}>) = 0))].
Если 2 еВ(В), то формулы /п ({2}р(<п>) = 1) и {2}р{и) = 0 означают соответственно: тг= {< >} и и ет*. Параметр Ь обозначает ^номер функции • Ь{2, п). Поэтому для этого символа Ь в А (В) вводится следующая аксиома: (Уд е£>(Л))Уи [{2}р(<п>) = 0 -> ({р}р(2, п) еВ(В) Л
(Vие Ы){{{Ь}Р{2, п)}р(и) = {д}*(<и>.и)))].