Математическая логика

Колмогоров А. Н., Драгалин А. Г.

Издательство УРСС Серия "Классический университетский учебник". 2003. Твердый переплет. 240 с.

М.: МГУ, 1984, 119 с. - Библиогр. (19 назв.)

Аннотация

А. Н. Колмогоров (1903-1987) и А. Г. Драгалин (1941-1998) - выдающиеся отечественные логики и математики, оказавшие глубокое воздействие на стиль и направление мировых исследований по логике и философии математики.

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

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

Оглавление

Введение в математическую логику
Предисловие
Введение
I Начальные понятия математической логики и теории множеств
 § 1. Синтаксис языка математических и логических знаков
 § 2. О классификации суждений и теории силлогизмов по Аристотелю
 § 3. О понятии множества
 § 4. Отношения и функции
 § 5. Математические структуры
 § 6. Булева алгебра
 § 7. Логика высказываний
 § 8. Исчисление высказываний
 § 9. О логике предикатов
II Логико-математические языки. Логические законы
 § 1. Язык первого порядка. Формулы и термы
 § 2. О правильной подстановке термов в формулы
 § 3. Семантика языка. Истинность в модели
 § 4. Примеры языков и моделей
 § 5. Логические законы
 § 6. Приложения теории логико-математических языков. Предваренная форма. Дизъюнктивная и конъюнктивная нормальная форма. Язык логики высказываний и логики предикатов
III Формальные аксиоматические теории
 § 1. Исчисление предикатов
 § 2. Теорема о дедукции. Техника естественного вывода
 § 3. Формальные аксиоматические теории. Примеры формальных аксиоматических теорий
Приложение 1. Кодирование с исправлением ошибок
Приложение 2. Применения к контактным схемам
Литература

Математическая логика. Дополнительные главы
Предисловие
Введение
I Теория множеств
 § 1. Язык наивной теории множеств, парадоксы наивной теории множеств
 § 2. Язык теории множеств Цермело-Френкеля
 § 3. Отношения и функция в языке теории множеств
 § 4. Натуральные числа в теории множеств. Запись математических утверждений в языке теории множеств
 § 5. О континуум-гипотезе и аксиоме выбора
 § 6. Аксиоматическая теория множеств Цермело-Френкеля
II Элементы теории алгорифмов
 § 1. Машины Тьюринга
 § 2. Тезис Черча
 § 3. Рекурсивные и рекурсивно-перечислимые множества и предикаты
 § 4. Примитивно-рекурсивные функции, геделева нумерация, арифметика с примитивно-рекурсивными термами
 § 5. Некоторые теоремы общей теории алгорифмов
   1. Универсальная функция
   2. Невычислимые множества и функции
   3. Проблема остановки
   4. Рекурсивно-неотделимые множества
   5. Теорема о рекурсии
III Элементы теории доказательств
 § 1. Неполнота и неразрешимость аксиоматических теорий
   1. Теорема о неподвижной точке
   2. Теорема Геделя о неполноте
   3. Вторая теорема Геделя
   4. Теорема о неполноте в форме Россера
   5. Теорема Леба
   6. Неразрешимость
   7. Распространение результатов на другие теории
 § 2. Теорема Геделя о полноте исчисления предикатов
 § 3. Теорема об устранении сечения
 § 4. О программе Гильберта обоснования математики
Литература
Именной указатель
Предметный указатель

Предисловие

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

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

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

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

Авторы

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предисловие к Дополнительным главам

Книга представляет собой вторую часть первоначального курса математической логики [1], но может читаться и независимо, если читатель имеет некоторое предварительное знакомство с логико-математическими языками и теорией логического вывода. Необходимые предварительные сведения можно получить как в нашей книге [1], так и в первых главах любого из более подробных курсов математической логики, например [2-4]. Необходимый минимум сведений и терминологию мы напоминаем также во введении.

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

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

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

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

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

Авторы

Об авторах

Андрей Николаевич Колмогоров (1903-1987)

Выдающийся российский математик, академик. Родился в 1903 году в Тамбове. В 1925 году окончил Московский университет, профессором которого работал с 1931 года. Заведовал различными кафедрами, был деканом механико-математического факультета МГУ. Автор фундаментальных работ по теории функций действительного переменного, теории множеств, топологии, конструктивной логике, функциональному анализу, механике, теории алгоритмов, теории информации. Основополагающее значение имеют результаты А.Н.Колмогорова в области теории вероятности. Широко известна его деятельность по разработке методики и организации математического образования. А.Н.Колмогоров был председателем Московского математического общества, почетным доктором зарубежных университетов, иностранным членом многих академий и научных обществ, лауреатом международных премий и кавалером правительственных наград. Умер в Москве в 1987 году.

Альберт Григорьевич Драгалин (1941-1998)

Видный представитель российской школы математического конструктивизма. Родился 10 апреля 1941 года на острове Моржевец Архангельской области. Окончил механико-математический факультет МГУ им.М.В.Ломоносова, где работал с 1966 года. С 1983 года жил в Венгрии, заведовал кафедрой вычислительной математики университета им.Л.Кошута (г.Дебрецен). В 1988 году Венгерской Академией наук ему была присвоена степень доктора наук. Умер 18 декабря 1998 года в г.Дебрецен.

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

Источник: Едиториал УРСС