7.2. Арифметизация метаматематики

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

Рассмотрим такой популярный пример. При входе в большие универсальные магазины покупателям иногда выдают билетики с номерами, определяющими порядок дальнейшего обслуживания покупателей. Достаточно бывает посмотреть на эти номера, чтобы ответить на вопросы, сколько покупателей уже обслужено, сколько ожидает своей очереди, кто за кем стоит, сколько всего покупателей было с утра в магазине и т. п. Если, скажем, миссис Смит имеет номер 37, а миссис Браун — номер 53, то вместо того чтобы объяснить миссис Браун, что она должна пропустить вперед миссис Смит, достаточно обратить ее внимание на то, что 37 меньше, чем 53.

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

Проиллюстрируем все эти общие замечания одним элементарным примером. Возьмем первую аксиому исчисления высказываний, являющуюся, кстати, аксиомой и рассматриваемого сейчас логико-арифметического исчисления: «(p ? p) ? p». Ее гёделевский номер, равный, как легко убедиться, числу 2⁸ ? 3¹¹ ? 5² ? 7¹¹^{^}² ? 11⁹ ? 13⁸ ? 17¹¹ мы обозначим буквой а. Рассмотрим теперь формулу «(p ? p)», гёделевский номер которой, равный числу 2⁸ ? 3^{11^2} ? 5² ? 7^{11^2} ? 11⁹, обозначим через b. Сформулируем теперь метаматематическое утверждение, гласящее, что формула «(p ? p)» есть начальная «подформула» (т. е. часть формулы, сама также являющаяся формулой) выбранной аксиомы. Какой арифметической формуле рассматриваемой формальной системы соответствует это утверждение? Очевидно, что более короткая формула «(p ? p)» является начальной подформулой более длинной формулы «(p ? p) ? p» в том и только в том случае, если (гёделевский) номер b, соответствующий первой из этих формул, есть делитель (гёделевского) номера a, соответствующего второй формуле. В предположении, что термин «делитель» определен некоторым подходящим образом в формализованной арифметической системе арифметической формулой, однозначным образом соответствующей упомянутому выше метаматематическому утверждению о том, что первая аксиома начинается с подформулы «(p ? p)», является формула «b есть делитель a». Более того, если эта последняя формула истинна, т. е. если b действительно является делителем a, то верно и то, что «(p ? p)» есть начальная подформула формулы «(p ? p) ? p».

Рассмотрим теперь повнимательнее следующее метаматематическое высказывание: «Последовательность формул, имеющая гёделевский номер x, является доказательством формулы, имеющей гёделевский номер z». Высказывание кодируется (изображается) посредством некоторой вполне определенной формулы арифметического исчисления, выражающей некоторое чисто арифметическое отношение между числами x и z. (Некоторое представление о том, насколько сложным является такое отношение, читатель получит, вспомнив приводившийся выше пример, в котором конец доказательства (а не все доказательство!) некоторой формулы, имеющей гёделевский номер, n, получал гёделевский номер k = 2^m ? 3ⁿ. Самый беглый анализ приводит нас к выводу, что здесь вводится вполне определенное, хотя и далеко не простое, арифметическое отношение между k (будем для простоты считать его номером всего доказательства) и n — гёделевским номером заключения этого доказательства.) Мы будем записывать отношение между числами x и z посредством формулы «Dem(x, z)»[15] напоминающей нам самим своим обликом о том метаматематическом утверждении, которому она соответствует (а именно, об утверждении «Последовательность формул, имеющая гёделевский номер x, является доказательством формулы, имеющей гёделевский номер z»).

^{Читатель должен твердо уяснить себе, что хотя «Dem(x, z)» кодирует некоторое метаматематическое утверждение, сама эта запись является формулой арифметического исчисления. Формула эта в более привычных обозначениях может быть записана в виде f(x, z) = 0, где буква f обозначает некоторый довольно-таки сложный комплекс арифметических операций над числами. Однако эта более привычная запись не «подсказывает» сразу своей метаматематической интерпретации, почему мы и предпочли запись, приведенную в тексте.}

Читатель теперь легко убедится в том, что метаматематическое утверждение, гласящее, что некоторая последовательность формул есть доказательство данной формулы, является истинным в том и только в том случае, если гёделевский номер этой последовательности формул находится с гёделевским номером данной формулы как раз в том арифметическом отношении, которое мы обозначили здесь через «Dem». Вообще, чтобы утверждать истинность или ложность какого-либо интересующего нас метаматематического утверждения, нам достаточно решить вопрос о том, находятся ли некоторые два числа в отношении, обозначаемом через «Dem». Но и обратно: чтобы убедиться, что два числа находятся в названном отношении, достаточно установить истинность метаматематического утверждения, «кодируемого» этим арифметическим отношением. Аналогично, метаматематическое высказывание «Последовательность формул, имеющая гёделевский номер x, не является доказательством формулы, имеющей гёделевский номер z», кодируется некоторой вполне определенной формулой формализованной арифметической системы, являющейся формальным отрицанием формулы «Dem(x, z)», т. е. формулой «~ Dem(x, z)».

Еще несколько слов об обозначениях, используемых в доказательстве теоремы Гёделя. Начнем с примера. Формула «? x (x = sy)» имеет гёделевский номер m (см. выше, с. 81), а переменная «y» — гёделевский номер 13. Подставив в эту формулу вместо переменной, имеющей гёделевский номер 13 (т. е. вместо «y») цифру[16], обозначающую число m, мы получим в результате формулу «? x (x = sm)», выражающую утверждение, согласно которому существует такое число x, что это ж непосредственно следует за числом m.

Последняя формула также имеет некоторый гёделевский номер, который совсем нетрудно вычислить. Но вместо того чтобы фактически производить это вычисление, мы можем совершенно однозначно охарактеризовать этот номер чисто метаматематическим образом, говоря, что это гёделевский номер формулы, получаемый из формулы, имеющей гёделевский номер m, подстановкой вместо входящей в эту формулу переменной с гёделевским номером 13 цифры «m». Такая метаматематическая характеристика однозначно определяет некоторое число, являющееся некоторой определенной функцией от чисел m и 13, причем сама эта функция может быть выражена средствами нашей формализованной арифметической системы. Значит, и само число можно выразить внутри нашего исчисления. Обозначим его через «sub(m, 13, m)», напоминая тем самым, что речь идет о гёделевском номере формулы, полученной из формулы, имеющей гёделевский номер m, подстановкой[17] вместо входящей в нее переменной с гёделевским номером 13 цифры, обозначающей число m. Вообще, через «sub(y, 13, y)» мы будем обозначать теперь арифметическую формулу, выражающую внутри арифметического исчисления метаматематическую характеристику: «гёделевский номер формулы, получаемой из формулы, имеющей гёделевский номер y, подстановкой вместо входящей в нее переменной, имеющей гёделевский номер 13, цифры, обозначающей число „y“». Если в выражение «sub(y, 13, y)» мы подставим теперь вместо «y» какую-нибудь определенную цифру, скажем, цифру, обозначающую число m, или выражение 243 000 000, то получающееся в результате выражение также будет обозначать некоторое определенное натуральное число, являющееся притом гёделевским номером некоторой определенной формулы.

У читателя не раз мог возникнуть вопрос, почему, собственно, мы говорили сейчас не просто о «числе y», а — столь вычурно и длинно! — о «цифре, обозначающей y». Впрочем, сама форма вопроса уже отчасти подсказывает ответ. Мы ведь уже упоминали о важном различии между понятиями «число» и «цифра». Цифра — это некоторый знак, т. е. выражение языка, которое можно записывать, стирать, зачеркивать, повторять и т. д. и т. п. Число же — это то, именем (или названием, обозначением) чего является обозначающая его цифра; само по себе число нельзя записать, стереть, зачеркнуть, повторить.

Скажем, когда мы говорим, что 10 — число пальцев на обеих руках, то мы характеризуем этой фразой некоторое «свойство» множества наших пальцев — свойство, которое, разумеется, «цифрой» никак не назовешь. Но число 10 может записываться как арабскими цифрами: «10», так и римскими цифрами (т. е. прописными латинскими буквами) «X»; эти имена сами по себе, конечно, различны, хотя обозначают они одно и то же число. Так вот, когда мы производим подстановку вместо числовой переменной (которая сама есть просто знак, буква), то мы ставим вместо одного знака другой знак. Мы не можем подставить вместо знака число — ведь число, являющееся некоторым свойством (или, как иногда говорят, понятием), вообще не есть что-то такое, что можно непосредственно нанести на бумагу. Итак, вместо числовой — а лучше сказать, цифровой! — переменной мы подставляем именно цифру (или цифровое выражение, скажем «s0» или «7 + 5»), а не число. Именно поэтому мы выше говорили о подстановке цифры (обозначающей число) y, а не самого числа у в интересующее нас метаматематическое выражение.

Читатель может далее поинтересоваться, какое же число обозначается выражением «sub(y, 13, y)», если формула, имеющая гёделевский номер у, не содержит переменной, имеющей гёделевский номер 13, т. е. попросту, если формула не содержит переменной «y». Скажем, sub(243 000 000, 13, 243 000 000) есть гёделевский номер формулы, полученной из формулы, имеющей гёделевский номер 243 000 000, подстановкой вместо переменной «y» цифры[18] 243 000 000. Выше (с. 85) мы уже выяснили, что 243 000 000 — гёделевский номер формулы «0 = 0», не содержащей переменной «y». Но какая же формула получится из формулы «0 = 0» в результате подстановки вместо не входящей в нее переменной «y» цифры, обозначающей число 243 000 000? Ответ очень простой: раз формула не содержит этой переменной, то и подстановка чисто фиктивная, т. е. такая «подстановка» не меняет формулы, иначе говоря, число, обозначаемое записью «sub(243 000 000, 13, 243 000 000)», есть само число 243 000 000.

Заметим, наконец, что выражение «sub(y, 13, y)» не является формулой нашей арифметической системы в том смысле, в каком, например являются формулами выражения «? x (x = sy)» или «Dem(x, z)», и вот почему. Выражение «0 = 0» мы называем формулой; такая запись утверждает наличие некоторого отношения между двумя числами, так что имеет смысл ставить вопрос, истинно или ложно это утверждение. Аналогично, когда вместо переменных, входящих в выражение «Dem(x, z)», подставляются некоторые цифры, то получающееся выражение оказывается записью некоторого утверждения (о том, что два числа находятся в некотором отношении), о котором опять-таки имеет смысл ставить вопрос, истинно оно или ложно. То же самое можно сказать и о выражении «? x (x = sy)».

Что же касается выражения «sub(y, 13, y)», даже если переставить в него вместо «y» какую-нибудь конкретную цифру, то оно все равно не будет ничего утверждать и по этой причине не будет ни истинным, ни ложным. Выражение это лишь обозначает (или называет) некоторое число, характеризующее его как некоторую функцию от других чисел. Итак, выражение «Dem(x, z)» (подобно, например, записям «у = f(x)» или «3² + 4² = 5²») есть формула и является схемой (или формой) некоторого утверждения; в отличие от него запись «sub(y, 13, y)» (подобно «f(x)» или «(7 ? 5) + 8») является лишь схемой (формой) имени некоторого числа, но не формулой.