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

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

* * *

ЧЕТВЕРТАЯ АКСИОМА ПЕАНО

Переведем в формальную систему арифметики четвертую аксиому Пеано, которая гласит: «за двумя различными натуральными числами следуют различные натуральные числа». Сначала определим переменные, используемые в высказывании: это два натуральных числа, х и у. Аксиома гласит, что не могут одновременно выполняться два следующих условия: х и у различны, следующие за ними числа совпадают. Иными словами, не существует чисел х и у таких, что:

1) х отличается от у;

2) число, следующее за х, равно числу, следующему за у.

Если бы символ конъюнкции был частью определенного нами языка, то эта аксиома записывалась бы так:

Так как использовать символ конъюнкции нельзя, нужно переписать это выражение, применяя функции отрицания и дизъюнкции. С учетом того, что отрицание отрицания высказывания равносильно исходному высказыванию, четвертая аксиома Пеано примет вид:

* * *

Благодаря описанному выше процессу арифметика была очищена от значений и сведена к формальному каркасу. Теперь ее аксиомы являются исключительно последовательностями абстрактных символов, а доказательства превратились в упражнения по комбинаторике. Однако мы по-прежнему можем сформулировать высказывания со смыслом: например, мы можем сказать «вторая аксиома Пеано длиннее третьей», «квантор существования упоминается во второй аксиоме Пеано два раза» или «формула ¬(0 = 1) является теоремой арифметики». Важно, что здесь речь идет уже не о формализованных высказываниях языка L, а о фразах на русском языке, которые относятся к формулам L. В этих фразах говорится уже не о числах, а о высказываниях о числах, таким образом, они выходят за пределы математики в область метаматематики. Этот переход подобен ситуации, когда один из героев романа начинает писать свой роман. Подобно тому, как литература порой превращается в металитературу, математика может превратиться в метаматематику.

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

Следовательно, при формализации арифметики все эти высказывания в рамках самой арифметики теряют смысл.

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

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

В этом метаматематическом доказательстве допускались не все методы: можно было использовать лишь два самых строгих, которые Гильберт назвал немецким словом finit, не слишком вдаваясь в объяснения, и которые позднее получили название финитных. Финитные методы должны были устранить все рассуждения, в которых можно было усомниться. Так, не допускались доказательства от противного, хотя этот метод использовал еще Евклид для доказательства того, что существует бесконечное множество простых чисел, а квадратный корень из двух нельзя представить в виде отношения двух натуральных чисел. Первый шаг доказательства от противного заключается в том, что мы отрицаем исходное высказывание, которое хотим доказать. Если, например, мы хотим доказать, что существует бесконечное множество простых чисел, то исходная гипотеза будет предполагать, что множество простых чисел является конечным. Затем на основе этой предпосылки нужно произвести корректные логические умозаключения, пока мы не получим абсурдное утверждение, которое будет гласить, например, что теорема арифметики, доказанная независимо от рассматриваемого утверждения, не выполняется. Все промежуточные рассуждения корректны, следовательно, единственным объяснением того, что мы пришли к абсурдному выводу, является ложность исходной гипотезы. Таким образом исходное утверждение оказывается доказанным. Часто, когда нам нужно доказать существование некоторого математического объекта, например решения некоторого уравнения, легче не найти его, а показать, что его отсутствие ведет к абсурдному заключению. Это же может произойти и в метаматематике: возможно, мы не сможем подтвердить истинность утверждения вида «формула Р доказуема», найдя явное доказательство этой формулы, однако можем предположить, что такого доказательства не существует, и в результате прийти к противоречию. Однако Гильберт не был достаточно уверен в этих методах, поэтому предпочел отказаться от них.