Интуиционистская логика и теория множеств

Хаханян, Валерий Христофорович

автореферат диссертации по философии, специальность ВАК РФ 09.00.07
диссертация на тему: Интуиционистская логика и теория множеств

Год: 2004
Автор научной работы: Хаханян, Валерий Христофорович
Ученая cтепень: доктора философских наук
Место защиты диссертации: Москва
Код cпециальности ВАК: 09.00.07

450 руб.

Диссертация по философии на тему 'Интуиционистская логика и теория множеств'

Полный текст автореферата диссертации по теме "Интуиционистская логика и теория множеств"

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

ХАХАНЯН Валерий Христофорович

ИНТУИЦИОНИСТСКАЯ ЛОГИКА И ТЕОРИЯ МНОЖЕСТВ.

Специальность 09.00.07 - логика

АВТОРЕФЕРАТ

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

МОСКВА - 2004

Работа выполнена на кафедре логики философского факультета МГУ им. Ломоносова.

Официальные оппоненты:

доктор философских наук Васюков В.Л.

доктор философских наук, профессор Панов М.И.

доктор физико-математических наук Хомич В. И.

Ведущая организация - кафедра логики философского факультета Санкт-Петербургского Государственного Университета

диссертационного совета № Д 501.001.48 по защите диссертаций на соискание ученой степени доктора философских наук при философском факультете МГУ им. Ломоносова по адресу: 119992, ГСП-2, Москва, В-234, Ленинские Горы, МГУ им. М.В. Ломоносова, 1-ый корпус гуманитарных факультетов, 11-ый этаж, философский факультет, ауд. 1161.

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

Автореферат разослан «_» 2004 г.

"Ч

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

кандидат философских наук ™ " Зайцев

Защита состоится

2004 г. на заседании

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

Актуальность темы исследования Третий кризис в основаниях математики, порожденный созданием Г. Кантором в конце XIX века учения о множествах (теории множеств), вызвал бурный рост различного рода течений математической философской мысли, связанных в первую очередь с возможностью преодоления возникшего кризиса (ликвидацией различного рода парадоксов в теории множеств (и не только в теории множеств, но и в самой логике)), а во вторую очередь переосмыслением философских оснований всего математического здания, которое к тому времени имело, казалось бы, прочное основание. Известные предложения по преодолению создавшейся кризисной ситуации и сохранению всего математического знания, накопленного к тому времени, не имели полного, признаваемого всеми математиками того времени, успеха, однако эти попытки преодоления кризиса в основаниях математической науки дали могучий рост разных течений философской математической мысли, начиная от позиции формализованного подхода Д. Гильберта, Б. Рассела, Э. Цермело и заканчивая появлением такого интересного направления в основаниях математики, как интуиционизм Л. Брауэра.

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

алгоритма, что и было

В 1930 г. один из последователей Л. Брауэра, А. Гейтинг, предложил формализацию трёх основных логических исчислений интуиционизма: интуиционистского исчисления высказываний IL, интуиционистского исчисления предикатов IPC и интуиционистской арифметики НА. Стало возможным изучать интуиционистскую математику с точки зрения теории доказательств (метаматематики) и её соотношение с классической математикой, т.е. математикой, применяющей полный закон исключённого третьего. Было доказано (с использованием негативной интерпретации К. Гёделя), что все три упомянутые исчисления получаются из их классических аналогов опусканием полного закона снятия двойного отрицания (последнее не означает, что частные случаи этого закона не выводятся в том или ином виде в соответствующих интуиционистских исчислениях) и что классические исчисления и соответствующие их интуиционистские аналоги равнонепротиворечивы.

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

Во вторую очередь исследования коснулись математического анализа или теории действительного числа и здесь спектр рассматриваемых формализованных теорий оказался неизмеримо богаче арифметического. Обозрения работ в этой области можно найти в ряде монографий А. Г. Драгалина, М. Бизона и периодических обзоров А. Трулстры, хотя полного

изложения результатов исследований на данную тему не существует. Наконец, очередь дошла и до систем теории множеств.

Первые формализованные системы теории множеств, базирующиеся на интуиционистской логике, появляются в конце 60-х и начале 70-х годов XX века. Здесь одними из первых необходимо отметить работы Дж. Майхилла по интуиционистской теории типов и еще очень несовершенные, как бы наполовину бестиповые, теории множеств Л. Тарпа и Л. Позгея. Основной пик исследований формализованных систем теорий множеств приходится на 1973 - 1990 г.г. Здесь нельзя оставить без внимания работы Х. Фридмана, А. Щедрова, Дж. Майхилла посвященные интуиционистскому варианту ZF, работы Г.Шварца по интуиционистской теории типов; замечательные работы В.Поуэлла (в которой строится расширение интерпретации Гёделя для арифметики НА до уровня некоторой бестиповой системы теории множеств Цермело-Френкеля) и Р.Грайсона (для интуиционистского варианта теории множеств со схемой собирания (collection) строится VH - гейтингозначный универсум над полной алгеброй Рейтинга Н). Полный перечень работ занял бы не одну страницу и здесь приведены наиболее важные и интересные работы.

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

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

равнонепротиворечивости интуиционистского и классического вариантов теории множеств Цермело-Френкеля), АЩедрова (интуиционистский вариант теории множеств, расширяющий систему формализованного анализа со схемой Крипке), В. Поуэлла (расширившего геделеву негативную интерпретацию на теорию множеств с принципом двойного дополнения множеств), Р. Грайсона (построившего для теории множеств со схемой собирания гейтингозначные модели) и ряда других авторов как

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

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

• исследование вопроса о совместности и независимости предлагаемого базисного варианта теории множеств с рядом конструктивных, интуиционистских и теоретико-множественных принципов, в том числе с некоторым вариантом стандартной аксиомы выбора;

• исследование свойств класса ординалов в предлагаемом варианте теории множеств с интуиционистской логикой;

• усиление ряда результатов (Р. Грайсона, X. Фридмана) для рассматриваемой системы теории множеств;

• построение для исследуемого базисного варианта теории множеств двух классов моделей, построенных ранее для интуиционистской арифметики А.Г. Драгалиным.

Ставилась также задача предложить интуиционистский вариант для теории множеств Куайна «New Foundations» и исследовать вопрос о возможности погружения (интерпретации) классической теории Куайна в ее интуиционистский вариант.

Теоретико-методологические основания исследования Исследование обсуждаемых в диссертации проблем основано на построении; ряда моделей для теории множеств с интуиционистской логикой, которые имеют в целом и общем по своей структуре характер универсума, чьё построение осуществляется с помощью трансфинитной индукции по ординалам (напомним, что метатеорией является в большинстве та же теория* множеств с интуиционистской логикой и таким образом классические свойства ординалов не используются). Универсумы похожего вида строились ранее в работах Х.Фридмана, Дж. Майхилла, Л. Тарпа и ряда других исследователей. Однако в диссертации предлагается единый метод построения таких моделей (и целых классов моделей), который однако формализованного обобщения не имеет. Модели этого вида (и в первую очередь их разновидность реализуемостного типа) дали возможность получить ряд метаматематических результатов для варианта теории множеств с интуиционистской логикой типа Цермело-Френкеля, которые не удавалось до сих пор решить (в сферу приложимости моделей такого вида попал даже интуиционистский вариант теории множеств Куайна «New Foundations»). Отметим также, что в диссертации самым непосредственным образом используются результаты, полученные в области исследования теории множеств с интуиционистской логикой Х.Фридманом, Дж. Майхиллом, А. Щедровым, В. Поуэллом. Научная новизна работы. Основные результаты, выносимые на защиту В диссертации строится ряд новых моделей для теории множеств с интуиционистской логикой, с помощью которых получены следующие новые результаты, выносимые на защиту:

1. Исследованы свойства класса ординалов в теории множеств с интуиционистской логикой: доказано, что ряд классически верных свойств ординалов влекут полный закон исключённого третьего, т.е. усиливают интуиционистскую логику до классической; дано интуиционистское доказательство совместности тезиса Чёрча с теорией множеств.

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

следствие получены такие результаты:

СТ!; гИС + СТ! + и 1/-СТ; гИСех V- и.', где СТ - тезис Чёрча и U -принцип униформизации.

3. Доказана независимость схемы собирания от принципа двойного дополнения множеств и обратно в теории множеств с подлежащей интуиционистской логикой.

4. Доказана допустимость правила Маркова с параметрами только по множествам в рассматриваемом варианте теории множеств; построены обобщенные модели типа предикатов реализуемости для теории множеств.

5. Доказана совместность и независимость варианта аксиомы выбора АС0 с теорией множеств с интуиционистской логикой.

6. Предложен интуиционистский вариант для классической теории множеств Куайна и доказана непротиворечивость классической NF относитель но этого варианта.

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

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

логикой, как удовлетворяющий большинству естественных требований к такому варианту со стороны исследователей различных направлений в основаниях математики (предварительно изложена история развития формализованных интуиционистских теорий множеств за все время их существования и основные результаты в этой области за последние 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 и др.), на научно-исследовательском семинаре им. А.А. Маркова кафедры математической логики и теории алгоритмов механико-математического факультета МГУ под руководством академика С.И. Адяна и профессора

В.А. Успенского (2002), на заседании семинара сектора логики ИФРАН под руководством докторов философских наук В.А Смирнова, Е.Д. Смирновой и А.С. Карпенко (1990-2003), на семинаре кафедры логики философского факультета МГУ под руководством профессора Е.Д. Смирновой (2004), на заседании семинара кафедры алгебры УрГУ под руководством профессора Ю.М.Важенина (1997), на семинаре отдела алгебры Уральского отделения МИРАН (1997).

Структура диссертации Диссертация состоит из Введения, девяти Глав, Заключения и списка литературы.

Основное содержание работы

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

К концу XIX и началу XX века учение Г. Кантора о множествах оформилось окончательно и математическая наука, казалось, могла бы наконец получить надёжный и прочный фундамент. Но именно в это время в созданном Г. Кантором учении обнаружились противоречия (парадокс Рассела, парадокс Кантора, парадокс Бурали-Форти и др.). Противоречия имели место не только в математике, но и в логике. Ситуация была критической и получила название «третий кризис в основаниях математики». Были предложены различные выходы из создавшегося положения. Один из таких выходов состоял в создании строго

формализованной системы теории множеств и такая система была создана усилиями Э. Цермело и А. Френкеля (1908 и 1925 гг. соответственно) и получила название теории множеств Цермело-Френкеля или ZF.

Другой выход был предложен Л. Я, Брауэром в 1907-1908 гг. и получил название интуиционистской математики или интуиционизма. В основу математической деятельности Брауэр положил интуитивную ясность и точность математических определений и конструкций (были предложены и другие выходы из создавшегося положения, из которых необходимо отметить формализованный вариант теории множеств -теорию типов Б. Рассела и появившийся значительно позже также формализованный вариант теории множеств В. Куайна «New Foundations» («Новые основания»), однако последний не получил широкую известность среди математиков и логиков; но все отмеченные системы теории множеств использовали в качестве подлежащей логики классическую логику предикатов). Стоит также отметить, что ни один из выходов из создавшейся ситуации выходом не оказался, ибо любой из этих путей не удалось по тем или иным причинам пройти до конца, планируемого создателями.

Интуиционистская математика, созданная Л. Брауэром, была недостаточно чётким образованием и уже в 1930 г. один из последователей Л.Брауэра, А. Гейтинг, дал формулировку трёх основных логических исчислений интуиционизма: интуиционистского исчисления высказываний IL, интуиционистского исчисления предикатов. IPC и интуиционистской арифметики НА. Было доказано (с использованием негативной интерпретации К. Гёделя), что все три упомянутые исчисления получаются из их классических аналогов опусканием полного закона снятия двойного отрицания (последнее не означает, что частные случаи этого закона не выводятся в том или ином виде в соответствующих

интуиционистских исчислениях) и что классические исчисления и соответствующие их интуиционистские аналоги равнонепротиворечивы.

Дальнейшие исследования в области формализованной интуиционистской математики сосредоточились в первую очередь вокруг системы арифметики НА; которая рассматривалась как базисная система арифметики. Различные расширения НА, такие как арифметика Пеано, традиционный конструктивизм А. А. Маркова-младшего,

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

Во вторую очередь исследования коснулись математического анализа или * теории действительного числа и здесь спектр рассматриваемых формализованных теорий оказался неизмеримо богаче арифметического. Обозрение работ в этой области можно найти в прекрасной монографии А.Г.Драгалина «Математический интуиционизм. Введение в теорию доказательств», выдержавшей уже два издания. Наконец, очередь дошла и до систем теории множеств.

которой строится расширение интерпретации Гёделя для арифметики НА до уровня некоторой бестиповой системы теории множеств типа Цермело-Френкеля) и Р.Грайсона (для интуиционистского варианта теории множеств со схемой собирания (collection) строится V1 — гейтингозначный универсум над полной алгеброй Гейтинга Н). Полный перечень и характеристика работ заняли бы не одну страницу и наиболее важные и интересные работы приведены в Главе 1.

Настоящая работа представляет исследования автора по бестиповым теориям множеств типа Цермело-Френкеля, в которых подлежащей логикой является логика IPC и, безусловно, является продолжением кандидатской диссертации, в которой эти исследования были начаты. В работе исследуются бестиповые интуиционистские (т.е. базирующиеся на логике IPC) варианты классической системы теории множеств ZF, которые могут содержать на первом уровне как арифметику Гейтинга НА, так и систему Клини и Весли, формализующую интуиционистский анализ FIM. Для точного описания всех рассматриваемых в работе теорий множеств (конечно, как уже отмечалось, подлежащая логика является интуиционистской) см. Главу 2: «Описание базисных теорий множеств с интуиционистской логикой и дополнительных постулатов конструктивного, интуиционистского и теоретико-множественного характера». Дадим теперь описание полученных результатов по главам.

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

B.A. Бочарова, A.M. Анисова, В.Л. Васюкова, Е.К.Войшвилло, Ю.В. Ивлева, В.И. Маркина, В.А. Смирнова, Е.Д. Смирновой. Как уже отмечалось, к концу XIX и началу XX веков открытие Г.Кантора оформилось в отдельную ветвь математики и теория множеств стала с успехом и широко применяться в различных разделах математики. Однако открытие противоречий привело к новому (третьему) кризису в основаниях математики, что повлекло бурное развитие математической мысли в разных направлениях, однако ни одно из направлений ни привело к общепризнанному выходу из кризиса (последнее признается и авторами книги «Основания теории множеств» И. Бар-Хиллелом и А. Френкелем (см. стр. 416), которые являются крупнейшими специалистами в области оснований математики). В этой же Главе даётся краткий обзор развития формализованных систем интуиционизма от арифметики до теории множеств, причем последним уделяется главное внимание.

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

Далее даётся доказательство совместности тезиса Черча с интуиционистской теорией множеств (для теории с двумя сортами переменных), причем внешним образом достаточно воспользоваться

только теорией множеств с двумя же сортами переменных, со схемой аксиом подстановки и с аксиомой двойного дополнения множеств. Естественно, что схема аксиом собирания отсутствует. Таким образом, метаматематика доказательства использует интуиционистскую логику (в отличие от ранних работ автора, где внешним образом используется теория множеств ZF). Приведено полное доказательство отмеченного факта, где внешним образом используется теория ZFIR. Эти доказательства можно (используя также ранние результаты автора) из перенести и на односортную теорию множеств. Полученный результат являлся ответом на вопрос, поставленный в одной из работ Х.Фридмана «...it is not known whether ZFIR is equiconsistent with ZFIR + «Every /ею is recursive»». - это и есть в наших обозначениях ZFIR.

В Главе 4 даётся сводка результатов о соотношении различных принципов конструктивного, интуиционистского и теоретико-множественного характера в теории множеств с интуиционистской логикой, к которой добавлены принцип двойного дополнения множеств DCS и схема аксиом собирания. В данной работе доказывается независимость сильного теоретико-множественного принципа униформизации от тезиса Чёрча с выбором, однако теория множеств берется без аксиомы объёмности. Известно, что в присутствии аксиомы объёмности принцип униформизации с единственностью выводим из тезиса Чёрча с единственностью (Г.Ф.Шварц; этот же результат остается верным и для теории множеств с интуиционистской логикой). Таким образом, в качестве нерешенной остается задача доказательства невыводимости сильного принципа униформизации из тезиса Черча с единственностью (или без единственности) или из слабого принципа униформизации. Здесь только отметим, что техника, примененная Г.Ф. Шварцем для теории типов, к бестиповым теориям не применима. Еще ряд приводимых метасоотношений между разного рода принципами является,

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

В Главе 5: «Независимость схемы собирания от принципа двойного дополнения множеств и vice versa в теории множеств с интуиционистской логикой» рассматривается теория множеств с интуиционистской логикой, с принципом двойного дополнения множеств и со схемой подстановки, которая, с нашей точки зрения, претендует на роль базисной аксиоматической системы теории множеств с интуиционистской логикой, играющей в теории множеств роль, аналогичную роли НА в арифметике. Доказывается, что такая система теории множеств обладает свойствами дизъюнктивности и полной экзистенциальности. С этой целью известная модель Майхилла расширяется до отмеченной теории множеств. Так как система теории множеств со схемой собирания свойством полной экзистенциальности не обладает (X. Фридман, А. Щедров), то в виде следствия получаем, что схема собирания не является выводимой из принципа двойного дополнения множеств.

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

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

В Главе 6 исследуется вопрос о допустимости сильного правила Маркова с параметрами только по множествам в теории • множеств с интуиционистской логикой, со схемой собирания и аксиомой двойного дополнения множеств (вопрос о допустимости правила Маркова актуален в силу того, что допустимость этого правила в теории множеств с интуиционистской логикой говорит о конструктивном характере этой теории). Доказано, что сильное правило Маркова с параметрами по множествам и с единственным параметром по натуральным числам допустимо в теории множеств со схемой собирания и с принципом двойного дополнения множеств. Для арифметики и для HAS (арифметики второго порядка) этот результат был получен в 1973г. Трулстрой, который применил для доказательства очень сложную технику, используя функционалы высоких порядков или нормализацию выводов. Позднее А.Драгалин , а также несколько ранее А.Драгалина и независимо Х.Фридман , предложили очень изящный и простой метод доказательства допустимости слабого правила Маркова для интуиционистских теорий (от арифметики до теории типов). Однако этот метод не мог быть прямо применен к теории множеств с интуиционистской логикой типа ZF. Построив универсум специального вида и определив понятие реализуемости формулы с использованием техники Драгалина-Фридмана, в Главе 6 и доказана допустимость соответствующего правила Маркова для бестиповой теории множеств с интуиционистской логикой. Затем удалось получить этот же результат как следствие обобщенного модельного подхода типа предикатов реализуемости к теории множеств.

Также, приведённый результат переносится и на односортную теорию множеств.

Затем в Главе 6 даётся обобщение на теорию множеств результата А.Г.Драгалина, полученного для интуиционистской арифметики НА с целью упорядочения различных моделей, которые были построены для получения разных результатов метаматематического характера. Техника А.Г.Драгалина получила название предикатов реализуемости для арифметики. Работает эта техника следующим образом: предположим, что для арифметики построена модель типа предиката реализуемости (при этом описывается именно класс реализуемостей в стиле Клини). Тогда из данного предиката типа реализуемости можно построить другой предикат и доказать, что он также - типа реализуемости (это - основной момент работ Драгалина). После этого показано на ряде примеров, как из одних моделей реализуемостного типа можно получать другие, более сложные, модели того же типа и доказывать для арифметики НА не только многие уже полученные ранее результаты, но и получать новые. Примерами служат: допустимость правила Маркова (без параметров) в НА, доказательство того факта, что доказательство допустимости правила Маркова не может быть формализовано в НА, исследование ослабленной формы этого же правила, чьё доказательство уже формализуется в НА и ряд других результатов. Здесь нужно отметить, что все метаматематические результаты, полученные ранее с использованием закона исключенного третьего, могут быть получены с помощью техники предикатов реализуемости и что попытки, предпринимавшиеся ранее с целью придать операции Сморинского интуиционистский характер, к успеху не приводили.

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

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

В Главе 7 рассматриваются варианты аксиомы выбора, которые не усиливали бы подлежащую интуиционистскую логику до классической. Известно, что стандартная форма аксиомы выбора (в ZFI (интуиционистской теории множеств) не все известные формы аксиомы выбора эквивалентны) влечет полный закон исключенного третьего (здесь ситуация такая же, как с эквивалентными классически аксиомой регулярности и схемой трансфинитной индукции по множествам: первая влечет полный закон исключенного третьего). В. Поуэлл доказал, что лемма Цорна совместна с интуиционистской теорией множеств, а также без доказательства утверждал, что интуиционистски приемлемой является аксиома выбора в виде счетной стандартной формы, обозначаемой у которой все множества являются дискретными (множество дискретно, если любые два его элемента либо равны, либо не равны (интуиционистски!)). В работе доказывается, что некоторая счетная форма аксиомы выбора по множествам натуральных чисел совместна и независима с некоторым вариантом теории множеств с интуиционистской логикой, к которому добавлен принцип двойного дополнения множеств. Все результаты, полученные в этой Главе, являются опубликоваными.

Глава 8 посвящена построению интуиционистского варианта для теории множеств Куайна «Новые основания» ("New Foundations", NF). Система Куайна является мало известной, достаточно нестандартной формализованной системой теории- множеств, которая, с одной стороны, напоминает теорию типов Рассела, а с другой стороны является бестиповой теорией множеств, в которой есть только одна аксиома -объёмности и одна схема аксиом - свёртки, однако свёртка осуществляется

не по всем формулам языка теории, а только по так называемым стратифицируемым формулам (формула языка первого порядка теории множеств называется стратифицируемой, если можно так приписать индексы всем переменным этой формулы, что в элементарных формулах вида Х€у переменная у получит индекс, на единицу больший индекса переменной х и одинаковые переменные получат одинаковые индексы). Конечно, логика в теории множеств Куайна - классическая. Относительно теории NF Шпеккер доказал, что аксиома бесконечности выводима в этой теории (первоначально это была действительно аксиома), что в NF выводимо отрицание аксиомы выбора и что система Куайна может быть получена из системы Рассела добавлением принципа типовой неопределенности. Для NF не удалось пока построить модель какого-либо вида и выяснить ее соотношение с теорией ZF (в смысле взаимной интерпретируемости).

Для системы Куайна в работе впервые строится ее интуиционистский аналог NFI, который получается следующим образом: подлежащая логика является интуиционистской, а к постулатам теории NF добавляется следующий, классически верный, принцип: если двойные дополнения множеств х и у равны между собой, то равны и сами эти множества (интересно, является ли этот принцип независимым от остальных двух постулатов теории NFI?) У автора диссертации имеется гипотеза, что удастся получить модель для интуиционистского варианта теории Куайна. Для теории Куайна NF строится погружение её в интуиционистский вариант NFI с помощью негативной интерпретации Гёделя и доказывается, что все переводы аксиом и правил вывода выводимы в интуиционистском варианте, что и доказывает равнонепротиворечивость теорий NF и NFI. В конце Главы 8 формулируется ряд нерешенных проблем для интуиционистского варианта системы Куайна и для ее ослабления, в

котором в аксиоме объёмности все множества являются непустыми. Все результаты Главы 8 опубликованы автором.

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

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

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

Основное содержание диссертации опубликовано в следующих работах:

1.Хаханян В.Х. Интуиционистская теория множеств: модели и метама-

тематика. М., МИИТ, 2003, 120 С.

2. Хаханян В.Х. Интуиционистская теория множеств. В кн.: «Логика и

основания математики». Тезисы УШ Всесоюзной конференции «Логика и Методология науки», Паланга 26-28 сентября 1982 г., С.91-94.

3. Хаханян В.Х. Интуиционистское доказательство совместности тезиса

Чё'рча с теорией множеств. Известия ВУЗов, серия «Математика», №2,1993, С.81-83.

4. Хаханян В.Х. О допустимости правила Маркова. II Межреспубли-

канская конференция по математической логике. Казань, 6-8 октября, 1992. Тезисы сообщений, Казань, 1992, С.150.

5. Хаханян В.Х. О допустимости правила Маркова в интуиционистской

теории множеств. В кн.: Логические исследования. Выпуск З.М., Наука, 1995, С.174-177.

6. Хаханян В.Х. Независимость частного случая аксиомы выбора от

двусортной теории множеств.Х Всесоюзная конференция по логике, методологии и философии науки, 24-26 сентября 1990 г., г.Минск. Тезисы докладов и выступле ний, секции 1-5, Минск, 1990, С.21- 22.

7. Хаханян В.Х. Независимость частного случая аксиомы выбора в инту-

иционистской теории множеств.Успехи математических наук (УМН), т. 52, вып. 4, 1997, С.219-220.

8. Хаханян В.Х. Аксиома выбора и нестандартная теория множеств.

Труды семинара сектора логики ИФРАН, XII, 1997, С.24-26

9. Хаханян В.Х. Интуиционистский вариант для КБ. Труды семинара

сектора логики ИФРАН, XIV, 2002, С. 109-111.

10. Хаханян В.Х. Система КБ! равнонепротиворечивая с системой

Куайна КБ. В кн.: Логические исследования. Выпуск 9, М., Наука, 2002, С.245-250.

11. Хаханян В.Х.

12. Хаханян В.Х.

13. Хаханян В.Х.

14. Хаханян В.Х.

15. Хаханян В.Х.

16. Хаханян В.Х.

17. Хаханян В.Х.

18. Хаханян В.Х.

19. Хаханян В.Х.

Система NFI, равнонепротиворечивая с системой Куайна NF. Математика и информатика в модерниза ции современного гуманитарного образования. Изд-во Урал. Гум.Ун-та, Екатеринбург, 2003, С.32-34. Независимость аксиомы «collection» от принципа «DC» в интуиционистской теории множеств. Известия ВУЗов, сер. «Математика», № 2, 1993, С.81-83. Теория множеств и тезис Чёрча. В кн.: Исследования по неклассическим логикам и формальным системам. М., Наука, 1983, С. 198-208.

Независимость принципа двойного дополнения множеств от схемы собирания в теории множеств с интуиционистской логикой. В кн.: Логические исследования. Выпуск 5,М., Наука, 1998, С. 160-162. Предикаты реализуемости для теории множеств. В кн.: Логические исследования. Выпуск 8. М., Наука, 2001, С.217-222.

Функциональная алгебраическая модель, эквивалентная штрих-реализуемости Клини. Математические заметки, т.75, выпуск 1, январь 2004, С. 155- 157. Функциональная алгебраическая модель, соответствующая штрих-реализуемости Клини.В кн.: Логические исследования. Выпуск 10. М., Наука, 2003, С.198-203. Функциональные алгебраические модели для неклас-неклассической теории множеств. В кн.: Логические исследования. Выпуск 4. М., Наука, 1997, С. 192-195. Невыводимость принципа униформизации из тезиса Чёрча в интуиционистской теории множеств. Математические Заметки, т. 43, № 5,1988, С.685-691.

20. Khakhanyan V. Set theory with intuitionistic logic and the method of

recursive readability. Logic,methodology and philisophy of science(papers of Soviet scientists submitted to Soviet National Organization Committee for the YII International Congress on Logic, Methodology and Philosophy of Science, Austria, Zalzburg, 11-16 July, 1983), abstracts, section 1-5,7, Moscow, 1983, P.71-74.

21 .Khakhanian V. ZFIR + CT is equiconsistent with ZFIR. SERDICA -Bulgaricae mathematicae publicationes. № 19 (1993), P.8-11.

22.Khakhanian V. Markov's Rule is Admissible in the Set Theory with Intuiti-

onistic Logic. Lect. Notes in Comp.Science, v.1289,1997, P.167-171.

23.Khakhanian V. About admissibility of Markov's rule in set theory with

intuitionistic logic. 10-th International Congress of LMPS Augugt 19-25,1995, Florence, Italy. Volume of abstracts, P.52.

24.Khakhanian V. The independence ofa partial form of axiom of choice of

intuitionistic set theory. Russian Mathematical Surveys, v.52, n.4, 1997. Communications of Moscow Mathematical Society.

25.Khakhanian V. Independence ofthe collection on the double complement

and vice versa in set theory. The J. Symb. Logic, v.57, n.l, 1992, P.378. Abstracts ofVIII Latin American conference of mathematical logic.

26.Khakhanian V. Functional algebraic models for non-classical set theory.

Bulletin ofthe Section of Logic, v. 27, № 1/2 (march-june), 1998,P.53-54.

Хаханян Валерий Христофорович Интуиционистская логика и теория множеств 09.00.07. Логика

Подписано к печати 08*.(?§,.(№*.....Формат бумаги 60x84/16

Объём .../¡7.5.,.... Заказ № ...3.6.СИ*...... Тираж 100 экз.

127994, Москва, ул. Образцова 15, Типография МИИТа

И0247

Оглавление научной работы автор диссертации — доктора философских наук Хаханян, Валерий Христофорович

1. Введение.

2. Глава 1. История развития теории множеств с интуиционистской логикой: метаматематика и философские аспекты.

3. Глава 2. Описание базисных теорий множеств с интуиционистской логикой и дополнительных постулатов конструктивного, интуиционистского и теоретико-множественного характера.

4. Глава 3. Свойства ординалов в интуиционистской теории множеств.

Интуиционистское доказательство совместности тезиса Чёрча с теорией множеств.

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

6. Глава 5. Независимость схемы собирания от принципа двойного дополнения множеств и vice versa в теории множеств с интуиционистской логикой.

7. Глава 6. О допустимости правила Маркова в теории множеств с интуиционистской логикой. Предикаты реализуемости для теории множеств с интуиционистской логикой.

8. Глава 7. Аксиома выбора в теории множеств с интуиционистской логикой.

9. Глава 8. Вариант теории множеств "New Foundations" Куайна с интуиционистской логикой.

Ю.Глава 9. Функциональные алгебраические модели для НА и теории множеств с интуиционистской логикой.

Введение диссертации2004 год, автореферат по философии, Хаханян, Валерий Христофорович

Однако интуиционистская математика, созданная Л. Брауэром, была недостаточно четким образованием (для сравнения приведем ситуацию, которая сложилась чуть позже в теории алгоритмов, когда стало ясным, что существуют неразрешимые проблемы и что для успешного решения такого рода задач необходимо было уточнить неформальное понятие алгоритма, что и было сделано различными эквивалентными способами). В 1930 г. один из последователей JI. Брауэра, А. Гейтинг, предложил формализацию трёх основных логических исчислений интуиционизма: интуиционистского исчисления высказываний IL, интуиционистского исчисления предикатов IPC и интуиционистской арифметики НА. Стало возможным изучать интуиционистскую математику с точки зрения теории доказательств (метаматематики) и её соотношение с классической математикой, т.е. математикой, применяющей полный закон исключённого третьего. Было доказано (с использованием негативной интерпретации К. Гёделя), что все три упомянутые исчисления получаются из их классических аналогов исключением полного закона снятия двойного отрицания (последнее не означает, что частные случаи этого закона не выводятся в том или ином виде в соответствующих интуиционистских исчислениях) и что классические исчисления и соответствующие их интуиционистские аналоги равнонепротиворечивы.

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

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

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

XX века. Здесь одними из первых необходимо отметить работы Дж.

Майхилла по интуиционистской теории типов и еще очень несовершенные, как бы наполовину бестиповые, теории множеств Л.

Тарпа и Л. Позгея. Основной пик исследований формализованных систем теорий множеств приходится на 1973 - 1990 г.г. Здесь нельзя оставить без внимания работы Х.Фридмана, А. Щедрова, Дж. Майхилла, посвященные интуиционистскому варианту ZF, работы Г.Шварца по интуиционистской теории типов; замечательные работы В.Поуэлла (в которой строится расширение интерпретации Гёделя для арифметики НА до уровня некоторой бестиповой системы теории множеств Цермело-Френкеля) и

Р.Грайсона (для интуиционистского варианта теории множеств со схемой

• н собирания (со11есйоп) строится V - гейтингозначный универсум над полной алгеброй Гейтинга Н). Полный перечень работ занял бы не одну страницу и здесь приведены наиболее важные и интересные работы.

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

Степень разработанности проблемы Как уже упоминалось в предыдущем разделе, первые работы в области теории множеств с подлежащей интуиционистской логикой, появляются в конце 60-х и начале 70-х годов прошлого столетия. Здесь необходимо отметить исследования Дж. Майхилла и Г.Ф. Шварца по теории типов с интуиционистской логикой (эти исследования в определенной степени опираются на исследования по формализованному математическому анализу А. Трулстры (арифметика всех конечных типов), Дж. Московакис, А.Г. Драгалина, М. Д. Кроля, А. М. Левина, В.Г. Кановея, Е. Бишопа, школы исследователей-конструктивистов во главе с A.A. Марковым-младшим (Н.А.Шанин, Б.А. Кушнер, И.Д. Заславский, Г.С. Цейтин и ряд других), М. Бизона, Г. Крайзеля, И. Стаплса, С.К. Клини, Р. Весли, Б. Скарпеллини и др.). По теориям множеств полу бестиповым и полуинтуиционистским назовем уже упоминавшихся JI. Тарпа и JI. Позгея. По бестиповым теориям множеств с интуиционистской логикой типа Цермело-Френкеля (которые в основном и являются целью исследований автора диссертации) имеются исследования X. Фридмана (доказательство равнонепротиворечивости интуиционистского и классического вариантов теории множеств Цермело-Френкеля), А.Щедрова (интуиционистский вариант теории множеств, расширяющий систему формализованного анализа со схемой Крипке), В. Поуэлла (расширившего геделеву негативную интерпретацию на теорию множеств с принципом двойного дополнения множеств), Р. Грайсона (построившего для теории множеств со схемой собирания гейтингозначные модели) и ряда других авторов как в России, так и за рубежом. Все приведенные работы и ряд других, использованных в диссертации, цитируются в ней.

• усиление ряда результатов (Р. Грайсона, X. Фридмана) для рассматриваемой системы теории множеств;

Также стояла задача предложить интуиционистский вариант для теории множеств Куайна «New Foundations» и исследовать вопрос о возможности погружения (интерпретации) классической теории Куайна в ее интуиционистский вариант.

Перечисленные выше задачи оказались тесно связанными между собой с точки зрения построения необходимых моделей и их решение дало возможность положительно ответить на основной вопрос исследования. Теоретико-методологические основания исследования Исследование обсуждаемых в диссертации проблем основано на построении ряда моделей для теории множеств с интуиционистской логикой, которые имеют в целом и общем по своей структуре характер универсума, чьё построение осуществляется с помощью трансфинитной индукции по ординалам (напомним, что метатеорией является в большинстве случаев та же теория множеств с интуиционистской логикой и таким образом классические свойства ординалов не используются). Универсумы такого вида строились ранее в работах Х.Фридмана, Дж. Майхилла, Л. Тарпа и ряда других исследователей. Однако в диссертации предлагается единый метод построения таких моделей (и целых классов моделей), который однако формализованного обобщения не имеет. Модели этого вида (и первую очередь их разновидность реализуемостного типа) дали возможность получить ряд метаматематических результатов для бестипового варианта теории множеств с интуиционистской логикой типа Цермело-Френкеля, которые не удавалось до сих пор получить (в сферу приложимости моделей такого вида попал даже интуиционистский вариант теории множеств Куайна «Новые основания»). Отметим также, что в диссертации самым непосредственным образом используются результаты, полученные в области исследования теории множеств с интуиционистской логикой Х.Фридманом, Дж. Майхиллом, А. Щедровым, В. Поуэллом.

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

1. Исследованы свойства класса ординалов в теории множеств с интуиционистской логикой.

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

5. Исследован ограниченный вариант аксиомы выбора в форме АС на вопрос ее совместности и независимости с теорией множеств с интуиционистской логикой.

6. Предложен интуиционистский вариант для классической теории множеств Куайна и доказана непротиворечивость классической № относитель но этого варианта.

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

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

Апробация работы Все основные результаты диссертации были доложены на ряде международных Конгрессов по логике, методологии и философии науки (YII (1983), (только опубликованы тезисы),YIII (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 и др.), на научно-исследовательском семинаре им. А.А. Маркова кафедры математической логики и теории алгоритмов механико-математического факультета МГУ под руководством академика С.И. Адяна и профессора В.А. Успенского (2002), на заседании семинара сектора логики ИФРАН под руководством докторов философских наук В.А. Смирнова, Е.Д.

Смирновой и A.C. Карпенко (1990-2003), на семинаре кафедры логики философского факультета МГУ под руководством профессора Е.Д. Смирновой (2004), на заседании семинара кафедры алгебры УрГУ под руководством профессора Ю.М.Важенина (1997), на семинаре отдела алгебры Уральского отделения МИР АН (1997).

Структура диссертации Диссертация состоит из Введения, девяти Глав, Заключения и списка литературы.

Заключение научной работыдиссертация на тему "Интуиционистская логика и теория множеств"

В заключение сделаем некоторые выводы из рассмотренного выше материала. Открытие Г. Кантора [17] оформилось в отдельную ветвь математической науки во второй половине XIX века. К концу XIX и началу XX века теория множеств стала широко применяться сначала в анализе и геометрии, а затем и в отдельных разделах математики. Однако едва завершилось оформление учения о множествах Кантора, как оно натолкнулось на ряд противоречий (Бурали-Форти - 1895г., Рассел -1902г.). При этом сама логика оказалась в опасном положении и проблема обоснования логики и математики вновь стала поистине сверхактуальной. Многие математики резко изменили свою позицию по отношению к теории множеств (А. Пуанкаре). Наступил третий кризис в основаниях математики. Были предложены различные возможные варианты выхода из этого кризиса. Одним их таких выходов стало создание аксиоматической системы теории множеств, устраняющей неограниченную схему свёртки (аксиоматическая система теории множеств сначала Цермело [129], а затем - Цермело-Френкеля, см. [69]. Стандартной моделью такой аксиоматической системы теории множеств может служить кумулятивная иерархия.

С другой стороны, Л.Я. Брауэр предложил положить в основу математической деятельности интуитивную ясность математических конструкций и определений. А. Гейтинг дал соединённое начало этих двух направлений (формализма и интуитивной ясности) в 1930 году, что в итоге привело к созданию аксиоматической системы теории множеств, основанной на интуиционистской логике. Однако желаемого выхода так найдено и не было и ни одна из казавшихся наиболее оптимистичными программ (например, программа Д. Гильберта) в целом не привели к успеху

2-я теорема Гёделя и другие причины). В итоге ситуация так и не была выправлена. В [30] у крупнейших специалистов в области оснований математики мы читаем (стр. 416): "Во взглядах на то, каким образом можно было бы достигнуть удовлетворительного обоснования, все еще имеется большое расхождение и громадное количество возникающих в этой связи проблем еще далеко не решено. И все же подавляющее большинство математиков отказывается считать, что идеи Кантора были всего лишь болезненным бредом. Несмотря на то, что основания теории множеств все еще довольно шатки, эти математики продолжают с успехом применять понятия, методы и результаты теории множеств в большей части разделов анализа и геометрии, и даже отчасти в арифметике и алгебре, твердо веря, что работы по обоснованию теории множеств приведут в конце концов к реабилитации теории множеств в полном (или по крайней мере почти полном) ее классическом объеме. Эта позиция отнюдь не исключает готовности интерпретировать теорию множеств совсем не так, как это обычно делается, что соответствует, очевидно, существующей потребности в пересмотре интерпретации логики и математики вообще". Первая часть этого вывода ".к реабилитации теории множеств в полном (или по крайней мере почти полном) ее классическом объеме." кажется мне излишне оптимистичной, также как и возможность полного пересмотра интерпретации логики и математики, так как никаких удачных идей такого пересмотра (и направлений) пока даже не просматривается. Тем не менее уже нашло себе место направление, заключающееся в более или менее локальной формализации той или иной части (раздела) математики и изучении с определенной метаматематической и философской точки зрения этой части (раздела), причем последняя (метаматематика) является более или менее делом привычки и вкуса взглядов того или иного исследователя. Взаимоотношение различных метаматематических разделов также может изучаться с формальной точки зрения (то есть возникает метаматематика формализованных систем метаматематик). Именно такая ситуация имеет сейчас место в большинстве исследований по основаниям математики и именно с этой точки зрения и стояла задача создания такой системы теории множеств на базе интуиционистской логики, которая, напомним это кратко еще раз, была бы: а) достаточно мощной, не слабее классической теории множеств Цермело-Френкеля; б) достаточно эффективной, например, обладающей свойством полной экзистенциальности, и в которой были бы допустимы разные эффективные правила, например Черча, Маркова и другие.; в) эта система теории множеств должна была бы быть приемлемой с различных точек зрения, то есть допускать расширения до различных, может быть несовместных друг с другом, вариантов теории множеств (классическое расширение до теории ZF, конструктивное в стиле Майхилла до конструктивной теории множеств CST, интуиционистское до теорий множеств с различными оттенками понимания эффективности и т.д.).

Последний пункт говорит о базисности такой аксиоматической системы теории множеств, основанной на интуиционистской логике предикатов. Целью исследований в создании такой базисной системы теории множеств, основанной на интуиционистской логике, может служить описанная выше аксиоматическая система ZFIR + DCS, как обладающая всеми отмеченными свойствами. Это основной философский вывод моих исследований в области теории множеств с интуиционистской логикой, подкрепленный математическими результатами ряда работ последнего тридцатилетия. Отметим также, что наиболее трудной и нерешённой проблемой в исследованиях по аксиоматической системе теории множеств остается следующая, см. [73] (после, естественно, проблемы построения модели для аксиоматической системы теории множеств NF Куайна): возможна ли интерпретация системы ZFIR + DCS (или системы ZFIC или классической теории множеств ZF) в системе ZFIR? Выше было У'-"" обещано дать набросок решения этой проблемы и сейчас это будет сделано.

Система ZFIC является системой теории множеств, равнонепротиворечивой с системами ZFIR + DCS и ZF (так как вторая система легко интерпретируется в третьей, а третья в первой (упоминавшийся результат Фридмана)). Поэтому будем строить интерпретацию первой системы теории множеств ZFIC в ZFIR. Предположим, что в последней теории множеств нам удалось построить (т.е. выразить) систему функций на множествах (это самое тонкое место - вопрос о существовании системы функций со свойствами, описанными ниже), м.б. счётную, которая обладает следующими свойствами: а) система функций допускает кодировку множествами и существует универсальная функция для данной системы функций; >а. б) система функций содержит некоторые стандартные функции на множествах (например, тождественную функцию, функции-константы, гёделевы конструктивные функции и т.д.); в) при ограничении аргументов натуральными числами или ординалами получаются системы функций с теми же свойствами на натуральных числах (частично-рекурсивные) или на ординалах; г) для данной системы функций имеется некоторый аналог s-m-n-теоремы для частично-рекурсивных функций на натуральных числах.

Системы функций такого рода выразимы (т.е. теорию таких систем функций можно развить) в классической ZF (см. [86] и ссылки на работы из [86]). Однако в интуиционистской ZFIR будут ли выразимы системы функций на множествах со свойствами а) - г)?

Главная тонкость в том, что при построении такой системы функций и доказательстве свойств а) — г) не должен использоваться полный закон искючённого третьего (см. [86]). Такая система функций позволила бы интерпретировать все аксиомы и схемы аксиом системы теории множеств ZFIC как система «реализующих» функций при оценках (см. определение реализуемости формулы при оценках для системы теории множеств ZFI2). В этом случае схема аксиом собирания могла бы быть «реализуема» следующим образом с использованием внешним образом только схемы аксиом подстановки, т.е. стала бы возможной интепретация теории ZFIC в теории ZFIR: е(код функции), g: ю—»V (достаточно только одной оценнки), УхеаЗуф(х,у) -> ЗВ УхеаЗуеВф(х,у) - схема аксиом собирания). Такую конструкцию нужно получить. Предположим, что К(к^, УхеаЗуф(х,у)), то есть функция к «реализует» посылку схемы собирания. Имеем для всякого множества х из аеУ, !к(х) = < 1,у > так, что К(1^пу, ф(х,)) и тогда нужное В и «реализующая» заключение схемы функция могут быть получены с помощью схемы подстановки из функции к («реализация» посылки), что и доказывало бы «реализуемость» схемы и, следовательно, интерпретируемость ZFIC в ZFIR, т.е. доказывало бы непротиворечивость первой системы теории множеств относительно второй.

Список научной литературыХаханян, Валерий Христофорович, диссертация по теме "Логика"

1. Анисов A.M. Представление интенсиональных отношений в теориимножеств с атомами. Труды научно-исследовательского семинара логического центра ИФРАН 1997, М., 1998, С. 27-34.

2. Бирюков Б.В. Герман Вейль и методологические проблемы науки.

3. В кн.: Герман Вейль и симметрия. М., Наука, 1968, С. 174-191.

4. Бочаров В.А., Войшвилло Е.К., Драгалин А.Г., Смирнов В.А.

5. Некоторые проблемы развития логики. Вопросы философии, № 6, 1979, С. 102.

6. Васюков В.Л., Карпенко A.C. Связь импликации Лукасевича с импликацией Гейтинга.Семиотические аспекты формализации интеллектуальной деятельности. М., 1988, С. 79.

7. Войшвилло Е.К., Маркин В.И. Философское и методологическое значение логики. Вопросы философии, № 2, 1988, С. 89-94.

8. Гавриленко Ю. О допустимости правила Маркова в интуиционистской арифметике. В кн.: II Советско-финский коллоквиум, 1979, С. 12-15.

9. Гейтинг.А. Интуиционизм. М., Мир, 1965, 200 С.

10. Гудстейн Р. Рекурсивный математический анализ. М., Наука,1970,470 С.

11. Драгалин А.Г. Математический интуиционизм. Введение в теориюдоказательств. М., Мир, 1979, 256 С.

12. Драгалин А.Г. Новые виды реализуемости и правило Маркова.

13. ДАН СССР, т.251, № 3, С.534-537.

14. Драгалин А.Г. Функциональные алгебраические модели. В кн.:

15. Семиотика и информатика, XIII выпуск, М., ВИНИТИ, 1979, С. 184-195.

16. Драгалин А.Г. Алгебраический подход к анализу моделей нестандартных логик. В кн.: Семиотика и информатика, XII выпуск, М., ВИНИТИ, 1979, С. 53-56.

17. Драгалин А.Г. К обоснованию принципа конструктивного подбора

18. А.А.Маркова. ДАН СССР, т. 177, 1967, С. 13-16.

19. Драгалин А.Г. Конструктивные модели теорий интуиционистскихпоследовательностей выбора. В кн.: Исследования по формализованным языкам и неклассическим логикам. М., Наука, 1974, С.214-252.

20. Ивлев Ю.В. Место логики в методологии научного познания.

21. Методология развития научного знания. М., 1982, С.25-34.

22. Кановей В.Г. Аксиома выбора и аксиома детерминированности.1. М., Наука, 1984.

23. Кантор Г. Теория множеств. М., Наука, 1985, 432 С.

24. Клини С., Весли Р. Основания интуиционистской математики.1. М., Наука, 1978, 272 С.

25. Кроль М. К топологическим моделям интуиционистскогоанализа. Один контрпример. Матем. заметки, 1976, т.19, №6, С. 859-862.

26. Кроль М. Дизъюнктивное и экзистенциальное свойствоинтуиционистского анализа со схемой Крипке. ДАН СССР, 1977, т.234, № 4, С. 750-753.

27. Кроль М.Д. Различные формы принципа непрерывности. ДАН

28. СССР, т.271, № 1, 1983, С.33-36.

29. Кушнер Б.А. Лекции по конструктивному математическомуанализу. М., Наука, 1973, 448 С.

30. Маркин В.И. Семантическое доказательство погружаемости некоторых систем силлогистики в исчисление предикатов. В кн.: Логические исследования, М., 1983, С. 17-26.

31. Мартин-Лёф П. Очерки по конструктивной математике. М., Мир,1975, 136 С.

32. Новиков П.С. On the consistency of certain logical calculus.

33. Матем. сборник, № 12(54), 1943, С. 231-261.

34. Попов В.М. Погружение импликативного фрагмента классическойлогики в импликативный фрагмент интуиционистской. В кн.: Логические исследования. Выпуск 7. М., Наука, 2000, С. 80-83.

35. РЖ «Математика», №5, 1979, 5А59.

36. Смирнов В.А. Является ли классическая формальная логика универсальной? Тезисы докладов Первой научной конференции кафедр общественных наук Томского политехнического ин-та. Томск, 1958, С. 35-38.

37. Смирнова Е.Д. Философское значение теорем об ограниченности формализмов. Философские вопросы логического анализа научного знания. Ереван, 1974

38. Френкель А. Бар-Хиллел И. Основания теории множеств. М., Мир,1966, С. 416.

39. Хаханян В.Х. Модели интуиционистской теории множеств. Диссертация на соискание ученой степени кандидата физико-математических наук. М., 1982, 80 С.

40. Куайна NF. Математика и информатика в модернизации современного гуманитарного образования. Изд-во Урал. Гум.Ун-та, Екатеринбург, 2003, С.32-34.

41. Хаханян В.Х. Независимость аксиомы «collection» от принципа

42. DC» в интуиционистской теории множеств. Известия ВУЗов, сер. «Математика», № 2, 1993, С.81-83.

43. Хаханян В.Х. Теория множеств и тезис Чёрча. В кн.: Исследованияпо неклассическим логикам и формальным системам. М., Наука, 1983, С. 198-208.

44. Хаханян В.Х. Независимость принципа двойного дополнениямножеств от схемы собирания в теории множеств с интуиционистской логикой. В кн.: Логические исследования. Выпуск 5,М., Наука, 1998, С. 160-162.

45. Хаханян В.Х. Предикаты реализуемости для теории множеств.

46. В кн.: Логические исследования. Выпуск 8. М., Наука, 2001, С.217-222.

47. Хаханян В.Х. Функциональная алгебраическая модель, эквивалентная штрих-реализуемости Клини. Математические заметки, т.75, выпуск 1, январь 2004, С. 155- 157.

48. Хаханян В.Х. Функциональная алгебраическая модель,соответствующая штрих-реализуемости Клини. В кн.: Логические исследования. Выпуск 10. М., Наука, 2003, С.198-203.

49. Хаханян В.Х. Функциональные алгебраические модели для неклассической теории множеств. В кн.: Логические исследования, Выпуск 4. М., Наука, 1997, С. 192-195.

50. Хаханян В.Х. Непротиворечивость интуиционистской теориимножеств с принципами Чёрча и униформизации.

51. Вестник МГУ, серия «Математика.Механика», № 5, 1980, С. 3-7.

52. Хаханян В.Х. Сравнительная сила вариантов тезиса Чёрчана уровне теории множеств. ДАН СССР, т.252, № 5, 1980, С. 1070-1074.

53. Хаханян В.Х. Интуиционистская теория множеств: модели иметаматематика. М., МИИТ, 2003, 120 С.

54. Хаханян В.Х. Непротиворечивость интуиционистской теориимножеств с формальным математическим анализом. ДАН СССР, т.253, № 1, 1980, С. 48-52.

55. Хаханян В.Х. Невыводимость принципа униформизациииз тезиса Чёрча в интуиционитской теории множеств. Математические Заметки, т. 43, №5, май, 1988, С.685-691.

56. Шанин Н.А. Конструктивные вещественые числа и конструктивные функциональные пространства. Труды МИАН СССР, № 67, М.: Изд-во АН СССР, 1962, С. 15-294.

57. Шварц.Г.Ф. Некоторые применения метода рекурсивнойреализуемости к интуиционистской теории типов. В кн.: Вопросы кибернетики. Неклассические логики и их применение. М., 1982, АН СССР, С. 37-54.

58. Шестопал В.Е. Теория множеств с неограниченным свёртыванием,логика целостного и неклассическая вероятность. ИТЭФ-131, Москва 1983.

59. Beeson М. Problematic Principles in Constructive Mathematics

60. University Utrecht, Department of Mathematics, Preprint № 185, 1981, February.

61. Beeson M., Scedrov A. Church's Thesis, continuity and set theory.

62. Preprint N.l84, University Utrecht, Department of Math., 1981, February.

63. Bernini S. A very strong intuitionistic theory. Studia1.gica, 1976, v.35, n.4, P.377-385.

64. Bishop E. Foundations of constructive analysis. N.Y.:1. McGraw-Hill Co., 1967.

65. Brouwer L.E. Consciousness, philosophy and mathematics.

66. Proc. of X International Congress Philosophy, Amsterdam, 1948, P.1235-1249.

67. Brouwer L.E. An example of contradictory in classical theory offunctions. Proc. Akad. Amsterdam, Ser.A, 57, P.204-206; Indag.math., 1954, 16, P. 204-206.

68. Brouwer L.E.J. De onbetrouwbaarheid der logische principes. Tijdschriftvoor wijsbegeerte, 2, 1908, 152-158. (О недостоверности логических принципов).

69. Damnjanovic Z. Minimal realizability of intuitionistic arithmetic andelementary analysis. Journal of Symbolic Logic, 1995, 60, №4, P.1208-1241.

70. Diaconesku R. Axiom of choice and complementation. Proc.

71. Amer. Math. Society, v.51, 1975, P.176-178.

72. Dzierzgowski D. Intuitionistic typical ambiguity. Arch. Math.1.gic, 1992, № 31, P.171-182.

73. Dzierzgowski D. Models of intuitionistic TT and NF. Semin.

74. Math. / Institute Math. Pure et Appl., Univ. Cathol. Jouvain, 1994, № 1-2, P. 1-23.

75. Forti M., Honsell F. Choice principles in hyperuniverses. Annals

76. Pure and Applied Logic, v.77, № 1, 1996, P. 35-42.

77. Fraenkel A. Untersuchungen über die Grundlagen der Mengenlehre.70. Friedman H.71. Friedman H.72. Friedman H.73. Friedman H.74. Friedman H.75. Friedman H.

78. Friedman H., Scedrov A. The lack definable witnesses and provably recursive functions in intuitionistic set theories Advances in Mathematics, v.57, № 1,1985, P. 1-13.

79. Godel K. Zur intuitionistishen Arithmetik und Zahlentheorie

80. Hahanyan V.H. The consistency of intuitionistic set theory withformal mathematical analysis. Sov. Math. Dokl., v.22 (1980), № 1,P. 46-50.

81. Hahanyan V.H. The comparative strength of variants of Church's

82. Thesis at the level of set theory. Sov.Math. Dokl. v.21 (1980), № 3, P. 894-898.

83. Handbook of proof theory. Studies in Logic and the foundations of mathematics, v. 137, ed. Buss S., Elsevier, 1998, 458 P.

84. Heyting A. Die formalen Regeln der intuitionistichen. Mathematik.

85. Sitzangsber preuss Akad. Wiss., Berlin, 1930, S.57-71, 158-169.

86. Heyting A. Intuitionistic methods from a finite point of view.1.tuitionistic methods, Warsaw, P. 185-192.

87. Jensen R.B.,Karp C. Primitive recursive set functions. Proceedings

88. Symposium Pure Mathematics,

89. Amer. Math.Society 13, Part I, 1971, P.143-176.

90. Khakhanian V. Kh. ZFIR + CT is equiconsistent with ZFIR. SERDICA

91. Bulgaricae mathematicae publicationes. № 19 (1993), P. 8-11.

92. Khakhanian V.Kh. Markov's Rule is Admissible in the Set Theory with1.tuitionistic Logic. Lect. Notes in Comp.Science, v.1289, 1997, P.l67-171.

93. Khakhanian V.Kh. About admissibility of Markov's rule in set theory withintuitionistic logic. 10-th International Congress of LMPS, Augugt 19-25, 1995, Florence, Italy. Volume of abstracts, P.52.

94. Khakhanian V.Kh. The independence of a partial form of axiom ofchoice of intuitionistic set theory. Russian Mathematical Surveys, v.52, № 4, 1997. Communications of Moscow Mathematical Society.

95. Khakhanian V.Kh. Independence of the collection on the double complement and vice versa in set theory. The J. Symb. Logic v.57, № 1, 1992, P.378. Abstracts of VIII Latin American conference of mathematical logic.

96. Khakhanian V.Kh. Functional algebraic models for non-classicalset theory. Bulletin of the Section of Logic, v. 27, № 1/2 (march-june), 1998, P.53-54.

97. Kleene S.C. Constructive functions in FIM. In:Logic,Methodologyand Philosophy of Sciences III, Amsterdam, 1968, P.137-144.

98. Kleene S.C. Realizability: a retrospective survey. Lect. Notesin Math., v.337, 1973, P.96

99. Kreisel G. Lawless sequences of natural numbers.

100. Compositio math., 1968, v.20, P.222-248.

101. Kreisel G., Troelstra A.S. Formal systems for some branches ofintuitionistic analysis. Ann. Math. Ligic, 1970, v.l, P.229-387.

102. Krol M. A topological model for intuitionistic analysis with99. LifschitzV.100. Moschovakis101. Moschovakis102. Myhill J.103. Myhill J.104. Myhill J.105. Myhill J.106. Myhill J.107. Myhill J.108. Myhill J.109. Powell W.C.

103. Some properties of intuitionistic Zermelo-Fraenkel set theory. Lect. Notes in Math., n.337, 1973, P.206-231. Constructive set theory. Jour, of Symb. Logic, v.40, n.3, 1975, P. 347-382.

104. Metamathematical investigations of intuitionistic arithmetic and analysis. Lect. Notes in Math., v.344, 1973, chapter V.

105. The theory of choice sequences. In.: Proc. of

106. Congr. LMPS III, 1968, P. 201-233.

107. Beweis dass jede Menge wohlgeordnet werden kann.

108. Math. Annalen, v.59,1904, P. 514-516

109. Neuer Beweis fur die Wohlordnung. Math. Annalen,v.65, 1908, P. 107-128.