Колмогоров А.Н.✫★★Ак, Драгалин А.Г. Математическая логика:
ВВЕДЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ. Изд. 6

Содержание

Предисловие к серии

Уважаемый читатель!

Вы открыли одну из замечательных книг, изданных в серии "Классический университетский учебник", посвященной 250-летию Московского университета. Серия включает свыше 150 учебников и учебных пособий, рекомендованных к изданию учеными советами факультетов, редакционным советом серии и издаваемых к юбилею по решению Ученого совета МГУ.

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

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

Издание серии "Классический университетский учебник" наглядно демонстрирует тот вклад, который вносит Московский университет в классическое университетское образование в нашей стране и, несомненно, служит его развитию.

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

Предисловие

Эта книга^* задумана как первоначальный курс математической логики. Она возникла в результате обработки конспектов лекций (читавшихся обоими авторами) семестрового курса математической логики для студентов первого курса механико-математического факультета Московского университета. Авторы стремились познакомить читателя с основными понятиями математической логики, полезными в работе математика любой специальности. Большое внимание уделено правильному использованию точных обозначений математической логики для записи математических суждений, логическим законам, началам теории множеств и теории алгорифмов.

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

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

[...]

Мы предприняли попытку концентрического изложения предмета, когда важнейшие темы обсуждаются в процессе обучения несколько раз, постепенно приобретая полную ясность. Учебник разбит на две книги. Во второй книге большее внимание уделяется фундаментальным результатам математической логики. Мы вновь вернемся к рассмотрению понятия множества, но уже на базе формальной аксиоматической теории Цермело–Френкеля. Таким образом, мы надеемся дать неспециалисту представление о классических результатах математической логики и подготовить будущего специалиста к изучению более подробных руководств.

^* Учебник А.Н.Колмогорова и А.Г.Драгалина "Введение в математическую логику" впервые опубликован издательством Московского университета
(М., 1982, 120 с.).

Введение

Логика – наука очень старая. Она возникла тогда, когда развитие специальных наук и вообще человеческого мышления сделало актуальным вопрос о том, как надо рассуждать, чтобы получить правильные выводы. Несомненен интерес к логике среди математиков и философов эпохи расцвета греческой культуры в VI–IV вв. до н.э. Но первое дошедшее до нас большое сочинение, посвященное специально логике ("Аналитики" Аристотеля, 384–322 гг. до н.э.), принадлежит уже позднегреческой эпохе. Независимо возникла буддистская логика, но дальнейшее развитие логики в Европе имеет своим исходным пунктом изучение Аристотеля.

Математическая логика с внешней стороны отличается от "обычной" тем, что она широко пользуется языком математических и логических знаков, исходя из того, что в принципе они могут совсем заменить слова обычного языка и принятые в обычных живых языках способы объединения слов в предложения. Довольно рано возникла идея о том, что, записав все исходные допущения на языке специальных знаков, похожих на математические, можно заменять рассуждение вычислением. Точно же сформулированные правила таких логических вычислений можно перевести на язык вычислительной машины, которая тогда будет способна автоматически выдавать интересующие нас следствия из введенных в нее исходных допущений. Своего рода "логическую машину" сконструировал еще в средние века Раймунд Луллий (1235–1315), дав ей, впрочем, лишь совершенно фантастические применения. Более определенный и близкий к реально осуществленному впоследствии замысел универсального логического исчисления развивал Лейбниц (1646–1716). Лейбниц надеялся даже, что в будущем философы вместо того, чтобы бесплодно спорить, будут брать бумагу и вычислять, кто из них прав.

Начало созданию того аппарата математической логики, который теперь мы называем логикой высказываний, положил Джордж Буль (1815–1864). Логико-математические языки и теория их смысла были затем значительно развиты в работах Фреге (1848–1925). Широко задуманное изложение больших разделов математики на языке математической логики было предпринято в работах Пеано (1858–1932) и особенно в фундаментальной трехтомной монографии Рассела и Уайтхеда, изданной в 1910–1913 гг.

В двадцатых годах XX века с программой обоснования математики на базе математической логики выступил знаменитый математик Гильберт (1862–1943). С этого времени и начинается современный этап развития математической логики, характеризующийся применением точных математических методов при изучении формальных аксиоматических теорий.

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

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

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

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

Какие же вопросы можно ставить относительно теории в целом?

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

Большое впечатление на современников произвело открытие в начале XX века Кантором и Расселом парадоксов в теории множеств. Это открытие свидетельствовало о том, что широко используемая и популярная (и в настоящее время) теория множеств в ее наивном изложении является противоречивой теорией. Изучение этого явления в значительной мере способствовало развитию современных методов математической логики. Была сформулирована аксиоматическая теория Цермело–Френкеля, в которой обычные способы вывода парадоксов уже не получаются. Программа Гильберта обоснования математики финитными средствами также в значительной степени связана с открытием парадоксов.

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

Можно сказать, что к настоящему времени непротиворечивость таких теорий, как элементарная геометрия, арифметика, анализ, хорошо изучена и достаточно надежно обоснована. Непротиворечивость мощных аксиоматических теорий множеств, таких как система Цермело–Френкеля или теория Куайна, гораздо более проблематична.

Большой интерес представляет изучение полноты той или иной теории. Во многих математических теориях время от времени возникают конкретные проблемы, которые не удается ни доказать, ни опровергнуть. Иногда это бывает в силу технической сложности самой проблемы, и, спустя определенное время, проблему все же удается разрешить. Однако в некоторых случаях ситуация совершенно иная: проблему просто невозможно ни доказать, ни опровергнуть в рамках исследуемой теории. Так, было показано, что подобными проблемами в теории множеств Цермело–Френкеля являются континуум-проблема Кантора и многие другие важные теоретико-множественные проблемы. Подчеркнем, что дано было точное доказательство того факта, что, например, аксиома выбора не может быть ни доказана, ни опровергнута в теории Цермело–Френкеля. Теорема Гёделя о неполноте утверждает, что всякая достаточно богатая теория необходимо содержит утверждения, которые нельзя ни доказать, ни опровергнуть в рамках теории.

Тем не менее некоторые важные теории оказываются полными. Таковы, например, элементарная геометрия, теория векторных пространств.

Существенно бывает исследовать разрешимость той или иной теории.

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

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

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

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

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

Об авторах

Колмогоров Андрей Николаевич

Выдающийся советский математик, академик АН СССР (1939). Родился в Тамбове. В 1925 г. окончил Московский университет, в котором с 1931 г. работал в должности профессора. Заведовал различными кафедрами, был деканом механико-математического факультета МГУ имени М. В. Ломоносова. Был одним из организаторов школьных математических кружков и олимпиад при МГУ, инициатором создания физико-математической школы-интерната при МГУ (1963).

А. Н. Колмогоров — автор классических работ по теории функций действительного переменного, теории множеств, топологии, конструктивной логике, функциональному анализу, механике, теории алгоритмов, теории информации. Основополагающее значение имеют его результаты в области теории вероятностей. Широко известна его деятельность по разработке методики и организации математического образования. А. Н. Колмогоров был председателем Московского математического общества, почетным доктором зарубежных университетов, иностранным членом многих академий и научных обществ, кавалером правительственных наград. Лауреат Государственной премии СССР (1941), Ленинской премии (1965) и многих международных премий.

Драгалин Альберт Григорьевич

Советский математик, яркий представитель российской школы математического конструктивизма. Окончил механико-математический факультет МГУ, где работал с 1966 года на кафедре математической логики. В 1968 году защитил диссертацию «Конструктивные трансфинитные числа и обоснование принципа конструктивного подбора» под руководством основателя советской конструктивистской школы А.А. Маркова С 1983 года жил в Венгрии, заведовал кафедрой вычислительной математики университета им. Л. Кошута (г. Дебрецен). В 1988 году Венгерской академией наук ему была присвоена степень доктора наук. Автор фундаментальных трудов по теоретико-модельным и теоретико-доказательственным основаниям интуиционистской логики, конструктивным методам нестандартного анализа. В 1970-е – начале 1980-х годов — доцент МГУ, в 1990-е — профессор Дебреценского университета.

Основные работы — по теории доказательств, интуиционизму, нестандартному анализу.