Жар холодных числ и пафос бесстрастной логики - [44]

В статье, в которой доказывалась теорема о неполноте формальной арифметики, Гёдель исследует систему формальной арифметики Principia Mathematica (он называет эту аксиоматически-дедуктивную теорию «системой PM»). Начинает он свою статью следующими словами: «Развитие математики в направлении все увеличивающейся строгости привело, как известно, к формализации многих ее частей, так что стало возможным доказывать теоремы, не пользуясь ничем, кроме нескольких механических правил. Наиболее широкие формальные системы, построенные к настоящему времени, это, с одной стороны, система Principia Mathematica (РМ) и, с другой стороны, система аксиом Цермело—Френкеля для теории множеств (развитая в дальнейшей Дж. фон Нейманом).

Обе эти системы настолько широки, что все методы доказательства, применяемые ныне в математике, в них формализованы, то есть сведены к небольшому числу аксиом и правил вывода. Поэтому можно предположить, что этих аксиом и правил вывода окажется достаточным, чтобы получить ответ на любой математический вопрос, который вообще может быть формально выражен в этих системах. Ниже будет показано, что это не так, что, наоборот, в обеих упомянутых системах имеются проблемы даже относительно простые, относящиеся к теории обычных целых чисел, которые нельзя решить, исходя из аксиом. Это обстоятельство не связано с какой-то специфической природой этих систем, напротив, оно имеет силу для очень широкого класса формальных систем, к которым, в частности, принадлежат все системы, получающиеся из упомянутых двух посредством присоединения к ним конечного числа аксиом, если только это присоединение не приводит к тому, что доказуемым становится какое-либо ложное предложение»[2].

Далее Гёдель излагает формальную систему, эквивалентную РМ, вводя только несущественные модификации, которые должны облегчить доказательство теоремы. Как и во всяком формальном исчислении, в основе этой системы лежат: перечень основных символов, определение комбинаций символов, называемой формулой, список постулатов — аксиом и правил вывода. С характером этих понятий читатель уже знаком, и нам остается рассказать о том, каким образом у Гёделя вводятся натуральные числа.

Это делается так: вводится символ для числа «нуль» (0), а также символ «следования за» f, который трактуется так, что f0 есть единица, ff0 — два и т. д.

Но для целей, которые преследует Гёдель, недостаточно иметь лишь символы для логических операций и чисел. Нужно выразить также основные арифметические предикаты, такие, как «простое число», «делится нацело» и т. п. В этом месте Гёдель, используя понятия системы РМ и известную в математике процедуру рекурсивного задания функции, то есть задания новых значений функции через предыдущие (рекурсивно, например, определяется функция «факториал» — произведение всех натуральных чисел от единицы до данного числа: (1)0! = 1; (2) (n+ 1)! = (n!) (n + 1)), вводит понятие рекурсивной функции, которое заведомо выразимо средствами формальной арифметики. Делается это так: задаются исходные рекурсивные функции — константа 0 и функция «следования за» — а затем устанавливается способ, с помощью которого из них можно получать более сложные рекурсивные функции. В самом начале этой части работы Гёдель показывает, что такие важные функции, как сложение, умножение и возведение в степень, рекурсивны. Он определяет также понятие рекурсивного арифметического предиката; n-местным арифметическим рекурсивным предикатом (отношением между n числами) называется такой предикат, который определяется уравнением φ (х1, х2,..., хn) = 0, где φ—рекурсивная функция, а х1, х2, ..., >Хn — переменные для чисел. Примером рекурсивного предиката является двуместный предикат «меньше». Рассмотрим этот случай подробнее, так как в дальнейшем нам понадобится представление о рекурсивных функциях и предикатах.

1. Функция δ, определяемая условиями

а) δ(0)=0, б) δ(у+1)= y,

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

2. Функция х ∸ у, определяемая условиями

а) х ∸ О = х, б) х ∸ (у+1)=δ(х ∸ у),

рекурсивна, как выраженная стандартной схемой рекурсии через рекурсивную функцию δ. Как нетрудно убедиться, смысл функции х ∸ у (она называется усеченным вычитанием) таков: функция эта равна х — у, если х >= у и равна нулю, если х < у.

В самом деле, посмотрим, каково значение функции х ∸ у для х, у = 0, 1, 2, 3 (над знаками равенств помечаем какой пункт определений 1, 2 применяется или какое из ранее полученных значений функции х — у используется):

Подобным же образом вычисляется 0∸3=0,0∸4=0 (вообще, легко усматривается, что при дальнейшем возрастании значения у выражение 0 ∸ у будет оставаться равным нулю).

При дальнейшем возрастании значения y выражение 2 ∸ у становится равным нулю. Аналогично вычисляется, что 3 ∸ 0 = 3, 3 ∸ 1 = 2, 3 ∸ 2 = 1, но при y > 2 выражение 3 ∸ y равно нулю.

3. Предикат, опередляемый уравнением х ∸ у = 0, рекурсивен; это очевидно, поскольку функция х ∸ у, как мы показали, рекурсивна. Но смысл этого предиката выражается в обычном языке утверждением x <= у.