Сон разума. Математическая логика и ее парадоксы

* * *

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

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

Из обеих ситуаций понятно, что довольно часто «истинное» не означает «доказуемое». Именно это имеют в виду логики, когда говорят о неполноте системы аксиом. В идеале все истинные утверждения о некоторых объектах можно доказать на основе нескольких аксиом. Но, как правило, теория содержит высказывания, которые нельзя ни доказать, ни опровергнуть, — такие высказывания называются неразрешимыми. Опровергнуть высказывание означает доказать его отрицание: например, опровергнуть высказывание «все лебеди белые», которое мы уже упоминали, означает доказать, что «существует лебедь не белого цвета». Полные теории — это теории, которые не содержат неразрешимых высказываний, или, что аналогично, это системы аксиом, в которых для произвольного высказывания можно доказать или это высказывание, или обратное ему. Внимательный читатель уже заметил, что во втором определении полноты расплывчатое понятие «истина» заменено понятием «доказательство». Так удалось разрешить некоторые из парадоксов, которые издавна волновали философов.

С большинством математических теорий дело обстоит так же, как в нашем первом примере: никто не может однозначно ответить, виновны подозреваемые или нет. Но не удивляйтесь, когда мы скажем, что всегда можно выбрать аксиомы так, чтобы теория была полной: для этого система аксиом должна содержать все истинные высказывания. В этом случае все доказательства будут выполняться в одну строчку, так как всё, что мы захотим доказать, уже будет аксиомой. Почему бы нам не поступить именно так, ведь полные теории — это настоящий рай для логиков?

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

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

* * *

РАЗРЕШИМАЯ СИСТЕМА С БЕСКОНЕЧНЫМ ЧИСЛОМ АКСИОМ

Одну из возможных рекурсивно перечислимых систем с бесконечным числом аксиом можно получить, если развернуть одну из аксиом Пеано в бесконечное число утверждений. Аксиому «О не следует ни за каким натуральным числом»» можно считать сжатой формой множества высказываний: «О не следует за нулем», «О не следует за единицей», «О не следует за двойкой» и т. д. до бесконечности. Предположим, что мы хотим определить, является ли некоторое высказывание одной из этих аксиом. Разумеется, оно будет принадлежать приведенному выше списку, если будет начинаться со слов «О не следует за…», а далее будет указано некоторое число. Напомним, что «единица»» в действительности означает «число, следующее за нулем», «два» — «число, следующее за числом, следующим за нулем» и т. д. Нам останется только подсчитать, сколько раз в нашем высказывании встречается слово «следующее». Следовательно, рассматриваемая нами система аксиом является рекурсивно перечислимой.

* * *

Подведем итог. Аксиоматический метод появился примерно в 300 году до н. э., с написанием «Начал». Евклид считал, что аксиомы являются очевидными истинами, соответствующими нашим представлениям о предметах в физическом мире, однако открытие новых геометрий в середине XIX века покончило с этим реалистическим подходом. С того времени аксиомами называются всего лишь высказывания, выбранные из соображений удобства в качестве основы математической теории.

Когда мы применяем к аксиомам определенные правила вывода, например modus ponens или modus tollens, мы получаем новые истинные высказывания, которые в математике называются теоремами. Истинность теорем определяется доказательствами — конечными последовательностями высказываний, первым из которых является аксиома, следующими — либо аксиомы, либо утверждения, полученные из предыдущих по правилам вывода. Теория представляет собой множество аксиом, правил вывода и всех теорем, которые можно доказать с помощью этих правил на основе аксиом.

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

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

Глава 2 Парадоксы

Парадокс есть сама страсть мыслителя.

Сёрен Кьеркегор

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

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