Прежде чем перейти к самой теореме Гёделя, нам придется преодолеть еще два препятствия. Прежде всего нам надо разобраться, зачем, собственно, ему понадобилась Principia Mathematica Уайтхеда и Рассела и в чем суть этой системы; далее, нам понадобится рассмотреть в качестве примера формализации дедуктивной системы один небольшой фрагмент системы Principia,и показать, как можно получить абсолютное доказательство непротиворечивости этого фрагмента.
Обычно, даже если математические доказательства проводятся с соблюдением общепринятых норм профессиональной строгости, эта строгость существенно умаляется в результате некоторого упрощения весьма принципиального характера. Дело в том, что принципы (правила) вывода, употребляемые в доказательствах, в явной форме не формулируются, так что математики применяют их не вполне осознанно. Возьмем, например, евклидовское доказательство того факта, что не существует наибольшего простого числа (целое число, как известно, называется простым, если оно не делится без остатка ни на одно число, кроме единицы и самого себя). Доказательство, проводимое методом reductio ad absurdum (от противного), выглядит следующим образом.
Пусть, в противоречии с доказываемым утверждением, имеется наибольшее простое число. Обозначим его через «x». Тогда:
1. x есть наибольшее простое число.
2. Образуем произведение всех простых чисел, меньших или равных x, и прибавим к этому произведению число 1. В результате получим некоторое число y:
y = (2 × З × 5 × 7 × … × x) + 1.
3. Если у само есть простое число, то x не есть наибольшее простое число, так как у, очевидно, больше x.
4. Если y — составное число (т. е. не является простым), то и тогда х не есть наибольшее простое число; в самом деле, если у — составное, то оно должно иметь некоторый простой делитель z; но z непременно должно быть отличным от всех простых чисел 2, 3, 5, 7, …, x, меньших или равных x, так что z должно в этом случае быть простым числом, превосходящим x.
5. Но у есть либо простое, либо составное число.
6. Следовательно, x не есть наибольшее простое число.
7. Наибольшего простого числа не существует.
Мы выписали здесь только основные шаги доказательства. Можно, однако, показать, что для восполнения всей цепочки рассуждений так или иначе пришлось бы использовать некоторые неявно подразумеваемые правила вывода и законы (теоремы) логики. Некоторые из этих правил и законов принадлежат самой элементарной части формальной логики, другие — более высоким ее разделам, например правила и законы, составляющие так называемую «теорию квалификаций». В этой теории формулируются правила употребления «кванторных» оборотов речи, вроде «все», «некоторые» и их синонимов. Приведем здесь примеры элементарной логической теоремы и правила вывода, используемые, хотя и неявно, в приведенном выше доказательстве теоремы Евклида.
Обратите внимание на 5-й шаг этого доказательства. Откуда он, собственно, получен? — Из логической теоремы («необходимой истины»), согласно которой «либо p, либо не p», где через «p» обозначена переменная («пропозициональная переменная»). Но как же именно 5-й шаг доказательства получается из этой теоремы? Посредством правила вывода, называемого «правилом подстановки вместо пропозициональных переменных», согласно которому из любого высказывания можно вывести другое высказывание, подставляя вместо каждого вхождения в исходное высказывание некоторой пропозициональной переменной (в нашем примере переменной «p») любого (одного и того же) высказывания (в рассматриваемом случае высказывания «y — простое число»). Применение такого рода правил и логических теорем, как мы уже отмечали, происходит на каждом шагу, но часто совершенно неосознанным образом. Явная же формулировка правил (даже для столь простого случая, как теорема Евклида) есть достижение лишь последнего столетия в истории логики.
Подобно мольеровскому господину Журдену, всю жизнь говорившему прозой, но не подозревавшему об этом обстоятельстве, математики в течение по крайней мере двух тысячелетий обходились без точной формулировки принципов, лежащих в основе всех их рассуждений. Понимание подлинной природы таких принципов — достижение самого недавнего времени.
Почти две тысячи лет аристотелевская теория правильных форм логического вывода безоговорочно считалась исчерпывающей и не нуждающейся в дальнейшей разработке. Еще в 1787 г. Иммануил Кант говорил, что формальную логику Аристотеля «не продвинешь дальше ни на один шаг — это наиболее завершенная и полная из всех наук». На самом же деле традиционная логика существеннейшим образом не полна, и средств ее недостаточно для обоснования многих принципов вывода, используемых даже во вполне элементарных математических рассуждениях.
Простым примером могут служить принципы, используемые при следующем выводе: 5 > 3, следовательно, 52 > 32.
Возрождение логических исследований в новое время началось с опубликования «Математического анализа логики» Джорджа Буля (1847). Буль и его последователи занимались прежде всего разработкой так называемой алгебры логики, посвященной выяснению и уточнению более общих и более разнообразных типов логической дедукции, нежели подпадающие под традиционные логические принципы. С помощью булевой техники легко выражаются, конечно, и традиционные умозаключения.
Другое направление исследований, тесно связанное с разработкой математиками XIX столетия проблематики оснований анализа, также оказалось близким программе Буля. Целью нового направления было представить всю чистую математику как часть формальной логики. Классическое выражение эта линия развития логики и математики получила в Principia Mathematica Уайтхеда и Рассела (1910–1913). Математикам XIX-го столетия удалось «арифметизировать» алгебру и так называемое «исчисление бесконечно малых», показав, что различные понятия, используемые в математическом анализе, определимы исключительно в арифметических терминах (т. е. в терминах целых чисел и арифметических операций над ними). Например, вместо того чтобы допускать мнимое число √-1 в качестве некоей мистической «сущности», его стали определять как упорядоченную пару целых чисел (0,1), причем над такими парами разрешено было производить определенного рода операции «сложения» и «умножения». Аналогично, иррациональное число √2 теперь стали определять как некоторый класс рациональных чисел, а именно, как класс рациональных чисел, квадраты которых меньше 2. Рассел же (а еще ранее немецкий математик Готтлоб Фреге) поставил своей целью показать, что все арифметические понятия можно определить в чисто логических терминах, а все аксиомы арифметики вывести из небольшого числа предложений, которые можно было бы квалифицировать как чисто логические истины.
Приведем пример. В логике имеется понятие класса. Два класса, по определению, «подобны», если между их членами можно установить взаимно-однозначное соответствие (причем понятие взаимно-однозначного соответствия само может быть определено в терминах других логических понятий). Класс, имеющий единственный член, называется «единичным классом» (таков, например, класс естественных спутников Земли); кардинальное (количественное) число 1 определяется как класс всех классов, подобных какому-либо единичному классу. Аналогично можно определить и другие кардинальные числа; различные арифметические операции (сложение, умножение и т. д.) также можно определить через понятия формальной логики. Произвольное арифметическое утверждение (скажем, «1 + 1 = 2») можно теперь представить как сокращенную запись некоторого утверждения, составленного исключительно из выражений, принадлежащих обычной логике, и все такие чисто логические утверждения, как можно показать, выводимы из некоторой системы логических аксиом.
Таким образом, Principia Mathematica явилась существенным продвижением в решении проблемы непротиворечивости математических систем, в частности арифметики, в том смысле, что посредством этой системы P. M. было достигнуто некоторое сведение упомянутой проблемы к проблеме непротиворечивости самой формальной логики. В самом деле, если аксиомы арифметики суть просто-напросто сокращенные записи некоторых теорем логики, то вопрос о том, совместимы ли арифметические аксиомы, эквивалентен вопросу о совместимости основных логических аксиом.
Далеко не все математики (по разным причинам) согласились с тезисом Фреге-Рассела, согласно которому математика есть не что иное, как часть логики. Кроме того, как мы уже отмечали, антиномии канторовской теории бесконечных множеств, если не принять специальных мер предосторожности, легко воспроизводятся и в рамках чистой логики. Но независимо от степени приемлемости самого по себе тезиса Фреге-Рассела два достоинства системы P. M. позволяют считать ее неоценимым достижением на пути к дальнейшему изучению проблемы непротиворечивости. В Principia разработана замечательная своей краткостью система обозначений, при помощи которой все предложения чистой математики (в частности, арифметики) могут быть записаны некоторым стандартным образом. Кроме того, в этой книге явным образом сформулировано большинство правил вывода, используемых в математических доказательствах (быть может, известных и ранее, но не в столь точном и полном виде). Резюмируя, можно сказать, что в Principia создан весьма совершенный инструмент для исследования всей системы арифметики как неинтерпретированного исчисления, т. е. как системы бессмысленных значков, из которых посредством точно сформулированных правил образуются и преобразуются «строчки» знаков — формулы.