Введение
Актуальность темы исследования Третий кризис в основаниях математики, порожденный созданием Г. Кантором в конце XIX века учения о множествах (теории множеств), вызвал бурный рост различного рода течений математической философской мысли, связанных в первую очередь с возможностью преодоления возникшего кризиса (ликвидацией различного рода парадоксов в теории множеств (и не только в теории множеств, но и в самой логике)), а во вторую очередь переосмыслением философских оснований всего математического здания, которое к тому времени имело, казалось бы, прочное основание. Известные предложения по преодолению создавшейся кризисной ситуации и сохранению всего математического знания, накопленного к тому времени, не имели полного, признаваемого всеми математиками того времени, успеха, однако эти попытки преодоления кризиса в основаниях математической науки дали могучий рост разных течении философской математической мысли, начиная от позиции формализованного подхода Д. Гильберта, Б. Рассела, Э. Цермело и заканчивая появлением такого интересного направления в основаниях математики, как интуиционизм Л. Брауэра.
Интуиционизм мыслился его создателем Л. Брауэром как полностью невозможное к формализации математическое знание, ибо в основу математической деятельности Л. Брауэр положил интуитивную ясность и точность математических определений и конструкций.
Однако интуиционистская математика, созданная Л. Брауэром, была недостаточно четким образованием (для сравнения приведем ситуацию, которая сложилась чуть позже в теории алгоритмов, когда стало ясным, что существуют неразрешимые проблемы и что для успешного решения такого рода задач необходимо было уточнить неформальное понятие
алгоритма, что и было сделано различными эквивалентными способами). В 1930 г. один из последователей Л. Брауэра, А. Рейтинг, предложил формализацию трёх основных логических исчислений интуиционизма: интуиционистского исчисления высказываний IL, интуиционистского исчисления предикатов IPC и интуиционистской арифметики НА. Стало возможным изучать интуиционистскую математику с точки зрения теории доказательств (метаматематики) и её соотношение с классической математикой, т.е. математикой, применяющей полный закон исключённого третьего. Было доказано (с использованием негативной интерпретации К. Гёделя), что все три упомянутые исчисления получаются из их классических аналогов исключением полного закона снятия двойного отрицания (последнее не означает, что частные случаи этого закона не выводятся в том или ином виде в соответствующих интуиционистских исчислениях) и что классические исчисления и соответствующие их интуиционистские аналоги равнонепротиворечивы.
Дальнейшие исследования в области формализованной интуиционистской математики сосредоточились в первую очередь вокруг системы арифметики НА, которая рассматривалась как базисная система арифметики. Различные расширения НА, такие, как арифметика Пеано, традиционный конструктивизм А.А.Маркова-младшего,
антитрадиционный конструктивизм, арифметика реализуемости и ряд других оказались непротиворечивыми относительно базисной системы арифметики НА. Каждая из этих формализованных теорий имела свою семантику, с которой НА оказалась согласована.
Во вторую очередь исследования коснулись математического анализа или теории действительного числа и здесь спектр рассматриваемых формализованных теорий оказался неизмеримо богаче арифметического. Обозрения работ в этой области можно найти в ряде монографий А. Г.
Драгалина, М. Бизона и периодических обзоров А. Трулстры, хотя полного изложения результатов исследований на данную тему не существует. Наконец, очередь дошла и до систем теории множеств.
Первые формализованные системы теории множеств, базирующиеся на интуиционистской логике, появляются в конце 60-х и начале 70-х годов XX века. Здесь одними из первых необходимо отметить работы Дж. Майхилла по интуиционистской теории типов и еще очень несовершенные, как бы наполовину бестиповые, теории множеств Л. Тарпа и Л. Позгея. Основной пик исследований формализованных систем теорий множеств приходится на 1973 - 1990 г.г. Здесь нельзя оставить без внимания работы Х.Фридмана, А. Щедрова, Дж. Майхилла, посвященные интуиционистскому варианту ZF, работы Г.Шварца по интуиционистской теории типов; замечательные работы В.Поуэлла (в которой строится расширение интерпретации Гёделя для арифметики НА до уровня некоторой бестиповой системы теории множеств Цермело-Френкеля) и Р.Грайсона (для интуиционистского варианта теории множеств со схемой собирания (collection) строится VH - гейтингозначный универсум над полной алгеброй Гейтинга Н). Полный перечень работ занял бы не одну страницу и здесь приведены наиболее важные и интересные работы.
Актуальность исследований по формализованным исчислениям с подлежащей интуиционистской логикой состоит в том, что такие исследования дают возможность получить богатый и тонкий спектр моделей с целью уточнения различных оттенков трактования эффективности в математике, выявить влияние интуиционистской логики (как наиболее глубоко исследованной на данный момент среди неклассических логик) на различное понимание таких фундаментальных математических объектов, как натуральные числа, действительные числа, функциии различного рода, множества и т.д. Для теории множеств
трудность и актуальность такого рода исследований состоит в построении различного спектра моделей для универсума множеств, для понимания поведения и роли разного вида дополнительных, специфически как интуиционистских так и конструктивных, а также и чисто теоретико-множественных принципов, метаматематики их соотношений на уровне теории множеств (как правило, бестиповой).
Степень разработанности проблемы Как уже упоминалось в предыдущем разделе, первые работы в области теории множеств с подлежащей интуиционистской логикой, появляются в конце 60-х и начале 70-х годов прошлого столетия. Здесь необходимо отметить исследования Дж. Майхилла и Г.Ф. Шварца по теории типов с интуиционистской логикой (эти исследования в определенной степени опираются на исследования по формализованному математическому анализу А. Трулстры (арифметика всех конечных типов), Дж. Московакис, А.Г. Драгалина, М. Д. Кроля, А. М. Левина, В.Г. Кановея, Е. Бишопа, школы исследователей-конструктивистов во главе с A.A. Марковым-младшим (Н.А.Шанин, Б.А. Кушнер, И.Д. Заславский, Г.С. Цейтин и ряд других), М. Бизона, Г. Крайзеля, И. Стаплса, С.К. Клини, Р. Весли, Б. Скарпеллини и др.). По теориям множеств полубестиповым и полуинтуиционистским назовем уже упоминавшихся Л. Тарпа и Л. Позгея. По бестиповым теориям множеств с интуиционистской логикой типа Цермело-Френкеля (которые в основном и являются целью исследований автора диссертации) имеются исследования X. Фридмана (доказательство
равнонепротиворечивости интуиционистского и классического вариантов теории множеств Цермело-Френкеля), А.Щедрова (интуиционистский вариант теории множеств, расширяющий систему формализованного анализа со схемой Крипке), В. Поуэлла (расширившего геделеву негативную интерпретацию на теорию множеств с принципом двойного
дополнения множеств), Р. Грайсона (построившего для теории множеств со схемой собирания гейтингозначные модели) и ряда других авторов как в России, так и за рубежом. Все приведенные работы и ряд других, использованных в диссертации, цитируются в ней. Цели и задачи исследования Основная цель работы заключается в том, чтобы предложить формализованный вариант бестиповой односортной теории множеств с подлежащей интуиционистской логикой, который мог бы играть роль базисной теории множеств такого типа и был бы признаваем исследователями других направлений (классиками, интуиционистами, конструктивистами и т.д.) как нейтральный по отношению к развиваемым ими вариантам теории множеств. Это позволило бы также оценить влияние интуиционистской логики на бестиповые теории множеств. С этой целью в диссертации решается ряд следующих задач:
• исследование вопроса о совместности и независимости предлагае-40 мого базисного варианта теории множеств с рядом конструктивных,
интуиционистских и теоретико-множественных принципов, в том числе с некоторым вариантом стандартной аксиомы выбора;
• исследование свойств класса ординалов в предлагаемом варианте теории множеств с интуиционистской логикой;
• усиление ряда результатов (Р. Грайсона, X. Фридмана) для рассматриваемой системы теории множеств;
• построение для исследуемого базисного варианта теории множеств двух классов моделей, построенных ранее для интуиционистской арифметики А.Г. Драгалиным.
Также стояла задача предложить интуиционистский вариант для теории множеств Куайна «New Foundations» и исследовать вопрос о возможности погружения (интерпретации) классической теории Куайна в
ее интуиционистский вариант.
Перечисленные выше задачи оказались тесно связанными между собой с точки зрения построения необходимых моделей и их решение дало возможность положительно ответить на основной вопрос исследования. Теоретико-методологические основания исследования Исследование обсуждаемых в диссертации проблем основано на построении ряда моделей для теории множеств с интуиционистской логикой, которые имеют в целом и общем по своей структуре характер универсума, чьё построение осуществляется с помощью трансфинитной индукции по ординалам (напомним, что метатеорией является в большинстве случаев та же теория множеств с интуиционистской логикой и таким образом классические свойства ординалов не используются). Универсумы такого вида строились ранее в работах Х.Фридмана, Дж. Майхилла, Л. Тарпа и ряда других исследователей. Однако в диссертации предлагается единый метод построения таких моделей (и целых классов моделей), который ¦ч') однако формализованного обобщения не имеет. Модели этого вида (и
первую очередь их разновидность реализуемостного типа) дали возможность получить ряд метаматематических результатов для бестипового варианта теории множеств с интуиционистской логикой типа Цермело-Френкеля, которые не удавалось до сих пор получить (в сферу приложимости моделей такого вида попал даже интуиционистский вариант теории множеств Куайна «Новые основания»). Отметим также, что в диссертации самым непосредственным образом используются результаты, полученные в области исследования теории множеств с интуиционистской логикой Х.Фридманом, Дж. Майхиллом, А. Щедровым, В. Поуэллом.
А Научная новизна работы. Основные результаты, выносимые на
защиту В диссертации строится ряд новых моделей для теории множеств
8
с интуиционистской логикой, с помощью которых получены следующие новые результаты, выносимые на защиту:
1. Исследованы свойства класса ординалов в теории множеств с интуици- онистской логикой.
2. Исследованы соотношения ряда дополнительных постулатов интуиционистского, конструктивного и теоретико-множественного характера в базисном варианте теории множеств с интуиционистской логикой.
3. Доказана независимость схемы собирания от принципа двойного дополнения множеств и обратно в теории множеств с подлежащей интуиционистской логикой.
4. Доказана допустимость правила Маркова с параметрами только по множествам в рассматриваемом варианте теории множеств; построены обобщенные модели типа предикатов реализуемости для теории множеств.,
5. Исследован ограниченный вариант аксиомы выбора в форме АС на вопрос ее совместности и независимости с теорией множеств с интуиционистской логикой.
6. Предложен интуиционистский вариант для классической теории множеств Куайна и доказана непротиворечивость классической NF относитель но этого варианта.
7. Построен класс функциональных алгебраических моделей для интуиционистской теории множеств с принципом двойного дополнения множеств и доказана теорема о корректности для этого класса моделей; доказано, что штрих-реализуемость Клини не является функциональной алгебраической моделью для арифметики НА.
8. Как итог всех полученных результатов, предложен вариант аксиоматической базисной системы теории множеств с интуиционистской логикой, как удовлетворяющий большинству естественных требований к такому варианту со стороны исследователей
9
различных направлений в основаниях математики (предварительно изложена история развития формализованных интуиционистских теорий множеств за все время их существования и основные результаты в этой области за последние 30 лет).
Теоретическое и практическое значение диссертации Примененные в диссертации методы построения моделей для теории множеств с интуиционистской логикой могут найти практическое применение у специалистов по логике в области решения проблем построения моделей для формализованных исчислений высокого порядка. Полученные в работе результаты могут быть использованы при создании новых курсов по логике (по теории множеств с неклассической логикой), составить содержание ряда специальных курсов для студентов, специализирующихся по данной тематике.
Апробация работы Все основные результаты диссертации были доложены на ряде международных Конгрессов по логике, методологии и философии науки (YII (1983), (только опубликованы тезисы),УШ (1987), IX (1991), (только опубликованы тезисы), X (1995), XI (1999), XII (2003) (только опубликованы тезисы)), на ряде международных конференций Logic Colloquium (1998, 2001, 2002, 2003), на международной конференции 5-th Kurt Godel Colloquium (1997), на ряде всесоюзных и всероссийских конференций по математической логике (1979,1982,1984,1986,1988,1991, 1993,1995 и др.), на ряде зарубежных конференций по математической логике (1988,1990,1993, 1996 и др.), на научно-исследовательском семинаре им. A.A. Маркова кафедры математической логики и теории алгоритмов механико-математического факультета МГУ под руководством академика СИ. Адяна и профессора * В.А. Успенского (2002), на заседании семинара сектора логики ИФРАН
под руководством докторов философских наук В.А. Смирнова, Е.Д.
10
Смирновой и A.C. Карпенко (1990-2003), на семинаре кафедры логики философского факультета МГУ под руководством профессора Е.Д. Смирновой (2004), на заседании семинара кафедры алгебры УрГУ под руководством профессора Ю.М.Важенина (1997), на семинаре отдела алгебры Уральского отделения МИР АН (1997).
Структура диссертации Диссертация состоит из Введения, девяти Глав, Заключения и списка литературы.
К концу XIX и началу XX века учение Г. Кантора о множествах оформилось окончательно и математическая наука, казалось, могла бы наконец получить надёжный и прочный фундамент. Но именно в это время в созданном Г. Кантором учении обнаружились противоречия (парадокс Рассела, парадокс Кантора, парадокс Бурали-Форти и др.). Противоречия имели место не только математике, но и в логике. Ситуация была критической и получила название «третий кризис в основаниях математики». Были предложены различные выходы из создавшегося положения. , Один из таких выходов состоял в создании строго формализованной системы теории множеств и такая система была создана усилиями Э. Цермело и А. Френкеля (1908 и 1925 гг. соответственно) и получила название теории множеств Цермело-Френкеля или ZF.
Другой выход был предложен Л. Я. Брауэром в 1907-1908 гг. в [63] и получил название интуиционистской математики или интуиционизма. В основу математической деятельности Брауэр положил интуитивную ясность и точность математических определений и конструкций (были предложены и другие выходы из создавшегося положения, из которых необходимо отметить формализованный вариант теории множеств -теорию типов Б. Рассела, см. [113] и появившийся значительно позже также формализованный вариант теории множеств В. Куайна «New Foundations» («Новые основания»), см. [111], однако последний не
11
получил широкую известность среди математиков и логиков; но все отмеченные системы теории множеств использовали в качестве подлежащей логики классическую логику предикатов). Стоит также отметить, что ни один из выходов из создавшейся ситуации выходом не оказался, ибо никакой из этих путей не удалось по тем или иным причинам пройти до конца, планируемого создателями.
Интуиционистская математика, созданная Л. Брауэром, была недостаточно чётким образованием и уже в 1930 г. один из последователей Л.Брауэра, А. Рейтинг, см. [84] и [7], дал формулировку трёх основных логических исчислений интуиционизма: интуиционистского исчисления высказываний IL, интуиционистского исчисления предикатов IPC и интуиционистской арифметики НА. Было доказано (с использованием негативной интерпретации К. Гёделя, см. [77]), что все три упомянутые исчисления получаются из их классических аналогов опусканием полного закона снятия двойного отрицания (последнее не означает, что частные случаи этого закона не выводятся в том или ином виде в соответствующих интуиционистских исчислениях) и что классические исчисления и соответствующие их интуиционистские аналоги равнонепротиворечивы.
Дальнейшие исследования в области формализованной интуиционистской математики сосредоточились в первую очередь вокруг системы арифметики НА, которая рассматривалась как базисная система арифметики. Различные расширения НА, такие как арифметика Пеано, традиционный конструктивизм А.А.Маркова-младшего,
антитрадиционный конструктивизм, арифметика реализуемости и ряд других (см. [9], а также [57]) оказались непротиворечивыми относительно базисной системы арифметики НА, но каждая из этих формализованных теорий имела свою семантику, согласованную с НА.
12
Во вторую очередь исследования коснулись математического анализа
или теории действительного числа и здесь спектр рассматриваемых
формализованных теорий оказался неизмеримо богаче арифметического.
* у За обозрением работ в этой области мы отсылаем читателя к монографии
А.Г.Драгалина [9]. Наконец, очередь дошла и до систем теории множеств.
Первые формализованные системы теории множеств, базирующиеся на интуиционистской логике, появляются в конце 60-х и начале 70-х годов XX века. Здесь одной из первых необходимо отметить работу Дж. Майхилла по интуиционистской теории типов [102], еще очень несовершенные, как бы наполовину бестиповые, теории множеств Тарпа [122] и Позгея [ПО]. Основной пик исследований формализованных систем теорий множеств приходится на 1973 - 1990 г.г. Здесь нельзя оставить без внимания работы Х.Фридмана [70] - [72], [76] (совместно с А. Щедровым), [73] (обзор нерешенных проблем); работы Дж. Майхилла [103] и [104], посвященные интуиционистскому варианту ZF и ^Г') формализации конструктивного анализа Бишопа соответственно; работу
Г.Шварца по интуиционистской теории типов [55]; замечательные работы В.Поуэлла [109] (в которой строится расширение интерпретации Гёделя для арифметики НА до уровня некоторой бестиповой системы теории множеств типа Цермело-Френкеля) и Р.Грайсона [79] (для интуиционистского варианта теории множеств со схемой собирания (collection) строится VH — гейтингозначный универсум над полной алгеброй Рейтинга Н). Полный перечень работ занял бы не одну страницу и здесь приведены наиболее важные и интересные работы.
Настоящая работа представляет исследования автора по бестиповым
теориям множеств типа Цермело-Френкеля, в которых подлежащей
'*' логикой является логика IPC и, безусловно, является продолжением
работы [31], в которой эти исследования были начаты. В работе
13
исследуются бестиповые интуиционистские ( т.е. базирующиеся на логике IPC) варианты классической системы теории множеств ZF, которые могут содержать на первом уровне как арифметику Рейтинга НА (см. [9]), так и систему Клини и Весли, формализующую интуиционистский анализ FIM (см. [9] или [18]). Точные формулировки всех рассматриваемых в работе теорий множеств (конечно, как уже отмечалось, подлежащая логика является интуиционистской) приведены Главе 2. Дадим теперь описание полученных результатов по главам.
Глава 1 диссертации посвящена вопросам философского характера и выводы, полученные в этой главе, опираются на современное состояние исследований разных логиков как в области теории множеств (в первую очередь), так и в области арифметики и анализа, которые, вместе с теорией множеств, составляют основания математической науки. С философской точки зрения необходимо отметить работы философов-логиков Б.В. Бирюкова, В.А. Бочарова, A.M. Анисова, В.Л. Васюкова, 'ifc'J Е.К.Войшвилло, Ю.В. Ивлева, В.И. Маркина, В.А. Смирнова, Е.Д.
Смирновой. Как уже отмечалось, к концу XIX и началу XX веков открытие Г.Кантора оформилось в отдельную ветвь математики и теория множеств стала с успехом и широко применяться в различных разделах математики. Однако открытие противоречий привело к новому (третьему) кризису в основаниях математики, что повлекло бурное развитие математической мысли в разных направлениях, но ни одно из направлений ни привело к общепризнанному выходу из кризиса (последнее признается и авторами [30], см. стр. 416, которые являются крупнейшими специалистами в области оснований математики). В этой же Главе даётся краткий обзор развития формализованных систем интуиционизма от
из1
арифметики до теории множеств, причем последним уделяется главное
внимание.
14
В Главе 3 рассматриваются свойства ординалов в теориях множеств с интуиционистской логикой и некоторые свойства упорядочений (порядков). Все эти свойства исследовались в [79] с помощью геитингозначных моделей, а также устанавливались свойства ординалов, которые остаются верными при замене классической логики предикатов на интуиционистскую. Доказательства из [79] использовали внешним образом, т.е. метатеоретически, схему собирания, которая не является выводимой из схемы подстановки (см. [76]). В [32] доказано, что достаточно внешним образом воспользоваться только схемой подстановки, что, в силу вышесказанного, ослабляет доказательство из [79]. Также, в работе из [79] отсутствовали многие доказательства тех фактов, что ряд свойств ординалов влечет полный закон исключенного третьего и некоторые, наиболее интересные из этих доказательств, приводятся в работе.
Далее даётся доказательство совместности тезиса Черча с ^V) интуиционистской теорией множеств (для теории с двумя сортами
переменных), причем внешним образом достаточно воспользоваться только теорией множеств с двумя же сортами переменных, со схемой аксиом подстановки и с аксиомой двойного дополнения множеств. Естественно, что схема аксиом собирания отсутствует. Таким образом, метаматематика доказательства использует интуиционистскую логику (в отличие, скажем, от [31] или [43], где внешним образом используется теория множеств ZF; это означает, что не используется в полном объёме классическое исчисление предикатов, т.е. методы доказательства носят чисто интуиционистский характер). Доказательство впервые было анонсировано в [32] и [87]. В [33] и [88] были приведены полные J доказательства отмеченного факта. Эти доказательства (используя технику
из [32]) переносятся и на односортную теорию множеств. Полученный
15
результат являлся ответом на вопрос Х.Фридмана из [76] «.. .it is not known whether ZFIR is equiconsistent with ZFIR + «Every /ею is recursive»». ZFIR - это далее ZFIR.
В Главе 4 даётся сводка результатов о соотношении различных принципов конструктивного, интуиционистского и теоретико-множественного характера в теории множеств с интуиционистской логикой, к которой добавлены принцип двойного дополнения множеств DCS и схема аксиом собирания. Часть этих результатов была получена в [31]. В данной работе доказывается независимость сильного теоретико-множественного принципа униформизации от тезиса Чёрча с выбором,что решает вопрос о взаимной независимости этих фундаментальных принципов, однако теория множеств берется без аксиомы объёмности. Известно, что (см. [55]) в присутствии аксиомы объёмности принцип униформизации с единственностью выводим из тезиса Чёрча с единственностью (этот же результат остается верным и для теории множеств с интуиционистской логикой). Таким образом, в качестве нерешенной остается только задача доказательства невыводимости сильного принципа униформизации из тезиса Черча с единственностью (или без единственности) или из слабого же принципа униформизации. Решение последней задачи позволило бы полностью закрыть вопрос о соотношении отмеченных принципов в теории множеств с интуиционистской логикой и с аксиомой объёмности. Здесь только отметим, что техника, примененная в [55] для теории типов, к бестиповым теориям не применима. Еще ряд приводимых метасоотношений между разного рода принципами является, как правило, легким следствием либо результатов из [31], либо сформулированного выше результата, J полученного в диссертации. Рассматриваемые при этом теории множеств
могут содержать в языке один, два или три сорта переменных, причем в
16
первом случае те же результаты могут быть получены и для односортной теории множеств, но технически это гораздо труднее.
В Главе 5 рассматривается теория множеств с интуиционистской ¦д логикой, с принципом двойного дополнения множеств и со схемой
подстановки, которая, с нашей точки зрения, претендует на роль базисной аксиоматической системы теории множеств с интуиционистской логикой, играющей в теории множеств роль, аналогичную роли НА в арифметике. Доказывается, что такая система теории множеств обладает свойствами дизъюнктивно сти и полной экзистенциальности. С этой целью модель Майхилла из [103] расширяется до отмеченной теории множеств. Так как система теории множеств со схемой собирания свойством полной экзистенциальности не обладает (см. [76]), то в виде следствия получаем, что схема собирания не является выводимой из принципа двойного дополнения множеств (см. [92] или [42]). Это ещё один результат о независимости, полученный работе.
Т''' В этой же Главе доказывается, что принцип двойного дополнения
множеств DCS не зависит от схемы аксиом собирания (сравни со следствием из этой же Главы ) в интуиционистской теории множеств. С этой целью основная модель, использованная ранее в [31], модифицируется так, что все постулаты нашей теории множеств снова выполняются в новой модели, а принцип двойного дополнения множеств — нет. Основное изменение модели связано с некоторым ограничением на множества из универсума, а именно: множество теперь принадлежит универсуму, если выполнено еще одно, дополнительное, условие: пересечение множеств натуральных чисел из первых членов пар нашего множества по всем множествам из вторых членов пар нашего множества
J должно быть пусто и этим же свойством должно обладать любое
множество, являющееся вторым членом некоторой пары нашего
17 |
