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

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

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

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

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

* * *

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

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

* * *

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

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

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

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