Хавьер Фресан - Том. 22. Сон разума. Математическая логика и ее парадоксы

• Название: Том. 22. Сон разума. Математическая логика и ее парадоксы
• Автор: Хавьер Фресан
• Издательство: «Де Агостини»
• Жанр: Математика
• Год: 2014
• ISBN: 978-5-9774-0717-5

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

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

---

Цель Гильберта понятна из его переписки, в которой он, например, объясняет, что геометрия не изменится, если вместо терминов «точка», «прямая» и «плоскость» мы напишем «любовь», «закон» и «трубочист». Как следствие, для формалиста выражения «глава третья» и «глава 3» — это два разных высказывания, единственная связь между которыми заключается в особенностях синтаксиса: оба выражения начинаются с одного и того же слова.

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

Чтобы определить формальную систему, помимо алфавита, необходимы аксиомы и правила вывода. Аксиомы отличаются от всех остальных формул только тем, что занимают привилегированное положение. Как мы указывали в главе 1, выбор аксиом — одна из сложнейших задач при определении формальной системы: если мы выберем слишком много аксиом, то они могут смешаться с остальными формулами, а если мы выберем слишком мало аксиом, то некоторые формулы нельзя будет ни доказать, ни опровергнуть. Правила вывода, в свою очередь, это процедуры, позволяющие получить новые формулы на основе уже известных. Аксиомы и правила вывода объединяются в формальные доказательства — последовательности формул, каждая из которых является либо аксиомой, либо получена из предыдущих формул с помощью правил вывода. Традиционно последняя формула доказательства называется теоремой.

Следовательно, первое требование программы Гильберта заключалось в том, чтобы описать алфавит, определить аксиомы и формальные правила вывода для арифметики. Этой задаче Бертран Рассел и Альфред Норт Уайтхед посвятили три объемных тома «Начал математики», опубликованных в 1910–1913 годах. В действительности теория, предложенная Расселом и Уайтхедом и названная вскоре логицизмом, выходила далеко за рамки формалистской программы: оба ее автора не ограничивались формализацией арифметики и хотели свести ее к логике, то есть определить все понятия теории натуральных чисел исходя из чисто логических обозначений, а также вывести из этих понятий все теоремы арифметики. Одним из величайших успехов математики XIX века было построение любого класса чисел на основе натуральных, таким образом, если бы Рассел и Уайтхед достигли своей цели, математика и логика пошли бы рука об руку по дороге, свободной от противоречий (по крайней мере, основоположники логицизма на это надеялись).

* * *

НЕПРИБЫЛЬНАЯ МАТЕМАТИКА

Ключевой труд Рассела и Уайтхеда был опубликован издательством Cambridge University Press. Издательство смогло выделить на публикацию всего 300 фунтов, что составляло половину необходимой суммы. Недостающие 300 фунтов обязалось внести Лондонское королевское общество, членом которого был Рассел, однако в итоге было внесено лишь 200, а остаток Расселу и Уайтхеду пришлось заплатить из своего кармана. «Неплохой баланс, — шутил Рассел впоследствии, — за десять лет работы мы заработали минус пятьдесят фунтов на каждого».

* * *

В упрощенной версии формальная система арифметики, предложенная Расселом и Уайтхедом в «Началах математики», состояла из следующих основных символов: 0 (число ноль), s (функция следования), ¬ (отрицание), V (дизъюнкция «или»),  (существование), = (равенство) и открывающая и закрывающая скобки. Позднее к этим символам были добавлены переменные х, у, z типа 0, которые обозначали натуральные числа, а также переменные А, В, С типа 1, то есть множества натуральных чисел, и т. д. по мере того, как требовались элементы все новых и новых типов. Возможно, внимательный читатель заметил отсутствие других символов, которые должны быть частью языка: например, наряду с квантором существования, благодаря которому можно формализовать высказывания вида «существует натуральное число, обладающее свойством Р», можно было бы добавить еще один символ, который означал бы «для всех», как в высказывании «для всех натуральных чисел выполняется утверждение Р». По сути, этот универсальный квантор очень широко используется в математике: «для всех» обозначается символом . Мы действительно можем добавить к языку символ , однако этого на самом деле не требуется, так как выражение «для всех натуральных чисел выполняется высказывание Р» равносильно выражению «не существует такого натурального числа, для которого не выполнялось бы высказывание Р». Следовательно, символ  можно выразить с помощью символов отрицания и существования.

Это же справедливо и для конъюнкции «и»: для ее обозначения существует символ , однако он является избыточным, так как его можно заменить символами V и ¬. Чтобы доказать это, рассмотрим три операции теории множеств: дополнение, объединение и пересечение.

Для данного множества А, которое содержится в другом множестве В, дополнением множества А до В называют множество, состоящее из элементов, принадлежащих В, но не А. Например, дополнением множества гласных {а, е, i, о, и} английского алфавита является множество согласных. Рассмотрим операции объединения и пересечения. Для данных множеств X и Y их пересечение X  Y определяется как множество элементов, одновременно принадлежащих X и Y. Например, если X — множество четных чисел 0, 2, 4, 6, 8, 10…, а Y — множество чисел, кратных трем, 0, 3, 6, 9, 12, 15 …, то чтобы найти их пересечение, нужно определить их общие элементы: ими будут 0, 6, 12, 18…, то есть числа, кратные шести. Объединением множеств X U Y называется множество, которому принадлежат все элементы X и все элементы Y. В предыдущем примере первыми элементами объединения X и Y будут 0, 2, 3, 4, 6, 8, 9…

Похожесть символов, обозначающих пересечение двух множеств () и конъюнкцию двух высказываний (), а также символов, обозначающих объединение двух множеств (U) и дизъюнкцию двух высказываний (V), вовсе не случайна. Если сопоставить свойствам Р и Q множества чисел, обладающих этими свойствами, например X и Y, то числа, обладающие свойствами Р и Q одновременно, будут элементами пересечения множеств X  Y, а числа, обладающие свойством Р или Q, то есть как минимум одним из этих двух свойств, будут принадлежать объединению множеств X U Y. Дополнение множества, в свою очередь, соответствует отрицанию высказывания. Для представления дополнений, объединений и пересечений множеств очень удобно использовать диаграммы, созданные британским математиком и философом Джоном Венном в 1880 году. С их помощью можно доказать, что конъюнкция свойств Р и Q равносильна отрицанию дизъюнкции отрицаний Р и Q, иными словами, Р  Q = ¬(¬Р V ¬Q). Это свойство позволяет выразить  через V и ¬.

Рис. 1. Пересечение двух множеств, соответствующее конъюнкции P  Q.

Рис. 2. Объединение двух множеств, соответствующее дизъюнкции Р V Q.

Рис. 3. Дополнение множества, соответствующее отрицанию ¬Р.

Диаграммы Венна, на которых представлены операции пересечения (рис. 1), объединения (рис. 2) и дополнения (рис. 3) множеств.

Сделав замечание о том, как представляются выражение «для всех» и конъюнкция высказываний (логическое «и»), рассмотрим, как переводятся в формальную систему арифметики некоторые аксиомы Пеано. Первая аксиома Пеано звучит так: «Ноль есть натуральное число». Эта аксиома не требует перевода, так как мы включили символ 0 в созданный нами язык. Перейдем ко второй аксиоме: «Каждое натуральное число имеет число, следующее за ним». В этой аксиоме фигурируют две переменные: рассматриваемое натуральное число, которое мы будем обозначать через х, и следующее за ним, которое будем обозначать через у. Вспомним, что число, следующее за данным, записывается с помощью буквы s, которая ставится перед этим числом, и выражается формулой у = sx, то есть «у равно числу, следующему за х». Следующий шаг заключается в том, что высказывание «каждое натуральное число» равносильно высказыванию «для всех натуральных чисел», и в этом контексте слово «имеет» означает «существует». Таким образом, аксиома принимает вид: «Для всякого натурального числа х существует натуральное число у такое, что у = sx». Если бы мы могли использовать символ , то на этом можно было бы остановиться: аксиома записывалась бы как xy(y = sx) — скобки мы использовали, чтобы выделить свойство, которым обладают числа х и у. Так как этот символ применить нельзя, нужно выполнить еще одно действие: так как «для всякого натурального числа х существует натуральное число у такое, что у = sx» равносильно «не существует натурального числа х такого, что для него не существует натурального числа у такого, что у = sx», и вторая аксиома Пеано будет записываться так: ¬ху (у = sx). После столь подробных объяснений читатель может самостоятельно убедиться в том, что третья аксиома Пеано, «0 не следует ни за каким натуральным числом», соответствует выражению ¬х (sx = 0).