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

Лекция 1. Аксиоматический метод в математике и фор-

мализация математических теорий

Логика — наука о построение правильных умозаключений. Матема-

тическая логика является разделом математики, посвященном изучению

математических доказательств и вопросов оснований математики.

Курс математической логики имеет своей целью изложить основы этой

науки, познакомить студентов с формализованным аксиоматическим ме-

тодом построения математических теорий, охватывающим также и логи-

ческие средства; его основными составными частями: языком, аксиома-

ми, правилами вывода; проблемами непротиворечивости, полноты, раз-

решимости теорий.

Аксиоматический метод в математике. Характерной чертой мате-

матики является использование доказательств, а не наблюдений. Физик

может выводить физические законы из других физических законов, но

окончательным подтверждение справедливости физического закона яв-

ляется его согласованность с данными эксперимента. Математик может

произвольное число раз подтвердить какую-либо формулу, но признать

ее как математический закон можно лишь с помощью доказательства. Та-

кое понимание математического факта возникло лишь на некотором эта-

пе развития математики. Истоки математики можно проследить в древних

цивилизациях Египта, Вавилона, Индии и Китая, где математика носила

эмпирический характер: имеется способ для решения какого-либо класса

задач, однако задача обоснования этого способа с помощью доказатель-

ства не рассматривается. Математика, признающая необходимость до-

казательства утверждений, возникла в древней Греции. В книгах Евклида

«Начала» (3 в. до н.э.) уже фигурируют аксиомы, теоремы, доказатель-

ства.

Опишем кратко построение аксиоматической теории. Если нам тре-

буется доказать утверждение A, то в процессе доказательства мы ссыла-

емся на ранее полученные утверждения A1, A2, . . .. Аналогично, для дока-

зательства утверждений A1, A2, . . . нужны ранее доказанные утверждения

B1, B2, . . . Чтобы процесс не был бесконечным, мы должны выбрать неко-

торые начальные законы, называемые аксиомами, которые принимаются

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

ваются, исходя из аксиом. На каком основании мы принимаем аксиомы?

Мы выбираем в качестве аксиом такие законы, которые, как мы полага-

ем, очевидны по самой природе рассматриваемых объектов. Например,

рассматривая N — множество натуральных чисел, мы приписываем ему

следующее свойство. Во множестве N существует элемент 1, который не

следует ни за каким элементом. При этом мы должны разъяснить, что

означает понятие «следовать за». Необходимо выразить это понятие, че-

рез другие, ранее разъясненные понятия. Снова, чтобы процесс не был

бесконечным, мы должны выбрать некоторые основные понятия, которые

остаются неопределяемыми. Остальные понятия, называемые производ-

ными понятиями, определяются в терминах основных. К основным поня-

тиям, так же как и к аксиомам, предъявляется требование: они должны

быть столь просты и ясны, что мы можем понимать их без точного опре-

деления.

Теперь можно описать процесс развертывания аксиоматической тео-

рии. Вначале мы вводим некоторые основные понятия и аксиомы об этих

понятиях. Далее переходим к определению производных понятий и дока-

зываем теоремы об основных и производных понятиях. Здание, которое

мы строим, состоящее из основных понятий, производных понятий, ак-

сиом и теорем, называется аксиоматической теорией. Это может быть,

например, аксиоматическим построением теории групп, планиметрии или

теории натуральных чисел.

Однако в понимании сущности аксиоматического метода есть принци-

пиально важный момент. До определенного этапа в развитии математики

неявно предполагалось, что мы описываем какие-то заранее подразуме-

ваемые, фиксированные объекты. Например, какое-то однозначно опре-

деленное множество точек, прямых плоскости. В этом случае мы гово-

рим о классическом аксиоматическом методе. Но и в этом случае можно

придумать другие объекты, для которых наши аксиомы истинными. Ито-

гда все доказанные теоремы будут истинными и для этих новых объектов.

Это приводит к пониманию, что все, что нами получено, справедливо и

для других объектов. Тем самым мы рассматриваем в аксиоматической

теории целый класс объектов и все теоремы применимы к этим объектам.

Мы называем такие аксиоматические системы современными, в противо-

положность классическим аксиоматическим системам. Типичным приме-

ром является теория групп.

До сих пор нами не затрагивались те логические правила, которые

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

ре к рассмотрению этих правил и более глубокому пониманию сущно-

сти аксиоматического метода подтолкнули некоторые парадоксы в тео-

рии множеств. На рубеже 19–20 веков аксиоматический метод проде-

монстрировал значительные достижения, например, Р.Дедекиндом (1888

г.) и Дж.Пеано (1891 г.) разработана аксиоматическая теория натураль-

ных чисел, Д.Гильбертом (1899 г.) получено аксиоматическое построение

евклидовой геометрии. Как основа большинства математических дисци-

плин в это время уже выступает теория множеств. Однако в это же время

в теории множеств были обнаружены парадоксы; приведем один из них.

Парадокс Рассела (1903 г.) Рассмотрим всевозможные множества

M и разделим их на два вида.

1) Множества, которые не являются элементом самого себя, т.е.M /∈ M.

2) Множества, которые являются элементом самого себя, т.е. M ∈ M.

Например, если M — множество жителей Екатеринбурга, тоM /∈ M;

если M — множество всех множеств, то M ∈ M. Ясно, что для любого

множестваM выполнено одно и только одно из условий 1) или 2).

Рассмотрим множество X, элементами которого являются все множе-

ства вида 2). Поэтому X состоит из всех множеств, не являющихся эле-

ментом самого себя

X = {M |M /∈ M}. (1)

Тогда множество X нельзя отнести к типу 2). Допустив, что X ти-

па 2), мы получим: X является элементом самого себя, т.е. X =

{A,B, . . .,X, . . .}. Это противоречит правилу (1) задания множества X.

Поэтому множество X типа 1). Тогда X не является элементом самого

себя,X /∈ X. Однако X состоит из всех множеств, не являющихся эле-

ментом самого себя и записьX /∈ X по правилу задания множества X

вынуждает включение X ∈ X. Получили одновременноX /∈ X и X ∈ X,

противоречие.

В итоге, не выполнено ни 1), ни 2) — парадокс _______в основаниях теории

множеств.

После ряда исследований этого парадокса выработано понимание, что

здесь нет противоречия с интуитивным понятием множества. Действи-

тельно, для образования множества X мы собираем вместе некоторые

объекты, которые в своей совокупности и составляют единственный объ-

ект, являющийся множеством X. Следовательно, перед тем, как множе-

ствоX образовано, мы должны иметь в распоряжении все объекты, кото-

рые являются элементами из X. Отсюда следует, что множество X все-

гда не является элементом для X и парадокс Рассела исчезает. Хотя и

данный парадокс получил разумное объяснение, среди математиков воз-

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

емых при построении аксиоматических теорий.

Формализация математических теорий. Любое предложение в ма-

тематике может обсуждаться с двух позиций: смысла этого утвержде-

ния и символической записи предложения. Рассмотрим, например, пред-

ложение «сумма углов треугольника равна 180◦» и обсудим смысл это-

го утверждения. Можно также объяснить смысл первой аксиомы Пеа-

но «имеется число без предшествующего элемента», но можно исследо-

вать символическую запись этого предложения. Проанализируем сред-

ства необходимые для выражения этого предложения в виде последова-

тельности символов. Символическая запись имеет вид:

∃ 1 ∀x S(x) _= 1 (2)

При этом переменная x предназначена обозначать произвольное нату-

ральное число, S есть знак для изображения функции, про которую мы

воображаем, что S(1) = 2, S(2) = 3, . . .. Знак S — унарный функцио-

нальный символ. Нам потребовались также логические знаки: ∃—кван-

тор существования и ∀—квантор всеобщности.

Если x — переменная, а S — унарный функциональный символ, то

конструкция S(x) называется термом. Знак 1 — знак для обозначения

конкретного предмета также является термом.

Выражение S(x) _= 1 можно записать с использованием знака отри-

цания ￢ в виде: ￢S(x) = 1. Сначала составляем формулу S(x) = 1. Она

отображает мысль «предмет S(x) равен предмету 1», Затем составля-

ем отрицание для предложения «предмет S(x) равен предмету 1» и спо-

мощью кванторов получим окончательную формулу. Таким образом мы

выразили в виде последовательности символов языка теории натураль-

ных чисел предложение «имеется число без предшествующего элемента».

Аналогичным образом можно записывать в виде формул произвольные

утверждения про объекты какой-либо теории.

Итак, для формализации некоторой математической теории нужно вы-

полнить следующие шаги:

1) Создать язык теории, т.е. ввести символы, которые необходимы для

записи предложений теории.

2) С помощью этих символов графически изобразить предложения

теории в виде строк символов (формул).При этом некоторые из этих фор-

мул—аксиомы теории.

Следующий шаг более трудный. Мы должны полностью описать те

средства логики (правила вывода), которые применяются для получения

теорем. Все теоремы должны выводится из аксиом, а аксиомы у нас про-

сто строки символов. Поэтому данные правила должны описывать дей-

ствия со строками и указывать, как из ранее полученных теорем получа-

ются новые теоремы.

Эти правилам вывода будут иметь следующий вид

A1, A2, . . ., An

B

(3)

При этом A1, A2, . . ., An —посылки, а B—заключение правила вывода.

Правило вывода утверждает: если A1, A2, . . .An —теоремы теории, то

B также является теоремой. После этого определение теоремы можно

сформулировать следующим образом.

1. Всякая аксиома является теоремой.

2. Если имеется некоторое правило вывода (3), и A1, A2, . . .An — тео-

ремы, то B также теорема.

3. То, что выражение является теоремой, устанавливается несколькими

применениями правил 1) и 2).

Если мы представим аксиомы теории и правила вывода в указанном

выше виде и перечислим правила вывода, то получим формализованную

аксиоматическую теорию.

Программа Гильберта Идею формализации математики предложил

немецкий математик Давид Гильберт. Его программа перестройки осно-

ваний математики включала следующие задачи.

а) Представить существующую математику, в частности теорию мно-

жеств, в виде формальной теории.

б) Доказать непротиворечивость полученной теории, т.е. доказать, что

в этой теории никакое утверждение не может быть доказано вместе со

своим отрицанием.

Одно из достоинств такого подхода — возможность доказывать

непротиворечивость аксиоматических теорий, не прибегая к методу на-

хождения модели теории. Другое важнейшее свойство — возможность

компьютерного доказательства теорем формализованных теорий. В на-

стоящее время имеется ряд компьютерных программ, предназначенных

для доказательства теорем.

Выдвинутая Гильбертом программа обоснования математики стимули-

ровала активные исследования в области оснований математики. В 30 го-

дах XX века австрийский математик Курт Гедель получил фундаменталь-

ные результаты, характеризующие сущность аксиоматического метода в

математике. Он показал, что первоначальный замысел Гильберта нельзя

реализовать в полном объеме. Эти результаты будут сформулированы в

заключительных разделах курса.