самой арифметики (относящиеся к числам, а отнюдь не к записям, в которые такие числа входят, т. е. к равенствам, неравенствам и вообще формулам) и утверждения относительно арифметики (т. е. как раз утверждения об арифметических формулах), то мы не получим никакого парадокса Ришара.
Значит, сам по себе парадокс Ришара совсем не страшен. Но сама схема приводящего к нему рассуждения чрезвычайно поучительна и плодотворна. Речь идет о возможности «отображения» (или «перевода») метаматематических высказываний, относящихся к некоторой достаточно богатой формальной системе, в саму систему. Сама по себе идея «перевода» хорошо известна и играет важнейшую роль во многих областях математики. Такая идея лежит, например, в основе всей аналитической геометрии, где геометрические понятия переводятся в алгебраические (арифметические), так что вместо геометрических соотношений мы, по существу, имеем дело с алгебраическими. (Вспомните хотя бы обсуждавшееся в разделе 2 отображение геометрии в алгебру, использованное Гильбертом для доказательства относительной непротиворечивости его системы геометрических аксиом). Такие отображения-«переводы» играют большую роль и в физике, например, когда свойства электрического тока излагаются на языке гидродинамических явлений. Эта же идея перевода лежит в основе технического моделирования — идет ли речь об исследовании свойств модели самолета (или же самолета в натуральную величину) в аэродинамической трубе, или же об изучении в лабораторных условиях распределения каких-либо материальных масс с помощью аналоговой модели, где роль этих масс играют электрические заряды.
На идее отображения[12] основан так называемый принцип двойственности в проективной геометрии, состоящий в возможности взаимной замены в аксиомах (а значит, и в теоремах) проективной геометрии терминов «точка» и «прямая», в результате чего аксиомы переходят в аксиомы (соответственно теоремы — в теоремы). При одном из таких «переводов» слово «точка» можно считать «образом», слово «прямая» — «прообразом»; при обратном переводе роли меняются.
Самым существенным в обсуждаемой здесь идее «моделирования» является то, что абстрактная структура отношений, выполняемых для «предметов» какой- либо области, может быть изучена с помощью рассмотрения отношений, имеющих место между «предметами» (как правило, другой природы, чем «предметы» исходной области), принадлежащими совсем другой области. Именно эта идея «кодирования» лежит в основе доказательства Гёделя. Если некоторые сложные метаматематические высказывания о формализованной системе арифметики можно, как рассчитывает Гёдель, перевести (или «отобразить») в некоторые арифметические высказывания, принадлежащие самой системе, то это уже само по себе явится большим достижением в деле развития теоретико-доказательственной техники, так же, как исследовать алгебраические соотношения, представляющие (изображающие, кодирующие) некоторые геометрические соотношения между кривыми и поверхностями, гораздо удобнее, чем иметь дело с самими геометрическими соотношениями, — точно так же арифметические аналоги («образы») сложных логических соотношений оказываются в известном смысле более обозримыми и доступными для изучения, чем их логические «прообразы».
Использование идеи кодирования, как мы уже отмечали, лежит в основе знаменитой работы Гёделя. Следуя схеме рассуждения, очень близкой к той, что проводится в парадоксе Ришара (но усовершенствуя ее при этом таким образом, что она становится неуязвимой по отношению к сформулированным выше критическим заключениям), Гёдель показывает, что метаматематические высказывания об арифметическом формализованном исчислении можно представить посредством некоторых арифметических формул внутри исчисления. Как мы покажем подробнее в следующем разделе, ему удалось найти такой метод арифметического кодирования метаматематических высказываний, что для некоторой формулы, выражающей истинное метаматематическое утверждение о формулах арифметики, ни она сама, ни ее отрицание не доказуемы в формальной арифметике. Поскольку одна из этих формул, выражающая истинное арифметическое высказывание, не выводима из арифметических аксиом, то аксиомы образуют неполную систему. Предложенный Гёделем метод кодирования позволил ему также построить арифметическую формулу, соответствующую метаматематическому высказыванию «арифметическое исчисление непротиворечиво», и показать, что эта формула недоказуема в (этом же!) арифметическом исчислении. Отсюда следует, что упомянутое метаматематическое высказывание не может быть установлено без привлечения некоторых дополнительных дедуктивных средств, не представимых (т. е. не кодируемых, не переводимых) в самом арифметическом исчислении, так что если это высказывание и можно доказать, то уж заведомо с привлечением средств, непротиворечивость которых не менее сомнительна, нежели сама по себе непротиворечивость арифметики. Все важнейшие выводы были получены Гёделем с использованием придуманной им чрезвычайно остроумной системы числового кодирования, или, как мы будем далее говорить, нумерации.
7Теоремы Гёделя
7.1. Гёделевская нумерация
Гёдель прежде всего описал некоторое формализованное исчисление, средствами которого можно выразить все обычные арифметические понятия и установить известные арифметические соотношения.
Гёдель использовал несколько упрошенный вариант системы, описанной в Principia Mathematics. Но для его цели точно так же подходит любое исчисление, в котором можно построить систему натуральных чисел с определенными на ней арифметическими операциями.
Формулы этого исчисления строятся исходя из некоторого запаса элементарных символов, образующих алфавит системы. В этом исчислении, как обычно, выделено некоторое множество исходных формул (аксиом) и точно перечислены правила преобразования (правила вывода), посредством которых из аксиом выводятся теоремы.
Гёдель показал, что каждому элементарному символу, каждой формуле (т. е. цепочке элементарных символов) и каждому доказательству (конечной последовательности формул) можно однозначным образом приписать некоторый номер (натуральное число). Такой номер, служащий своего рода значком, ярлыком, указывающим на отмечаемый им объект — символ, формулу или доказательство — формальной системы, мы будем называть «гёделевским номером» этого символа, формулы или доказательства[13].
Элементарные символы, составляющие алфавит системы, бывают двух сортов: константы и переменные. Мы будем считать, что у нас есть ровно десять символов-констант, которым мы припишем в качестве гёделевских номеров числа от 1 до 10. Почти все эти символы читателю уже известны: «~» (сокращение для «не»), «˅» («или»), «ﬤ» («если…, то…»), «=» («равно»), «0» (цифровой знак, изображающий число «нуль»), а также три «знака препинания»: левая скобка «(», правая скобка «)» и запятая «,». Кроме того, нам понадобятся еще два символа: перевернутая буква «Ǝ» (читаемая как «существует» и называемая «квантором существования») и строчная латинская буква «s», обозначающая числовой оператор, сопоставляющий каждому натуральному числу непосредственно следующее за ним число. Пример: формулу «Ǝ x (x = s0)» можно прочесть как «существует такое x, что x непосредственно следует за числом 0». Выпишем все используемые нами символы-константы (под ними указаны соответствующие гёделевские номера):
~ ˅ﬤƎ = 0 s ( ) ,
1 2 3 4 5 6 7 8 9 10
Кроме элементарных символов-констант, в алфавит нашего исчисления входят еще переменные, причем переменные трех сортов: числовые переменные «x», «y», «z» и т. д. (вместо них можно подставлять «цифры» и составленные из них (и числовых переменных) «арифметические выражения», выражающие натуральные числа); пропозициональные переменные «p», «q», «r» и т. д. (вместо них можно подставлять «формулы», выражающие высказывания); и, наконец, предикатные переменные «P», «Q», «R» и т. д. (вместо них можно подставлять арифметические «предикаты», выражающие такие свойства и отношения, как «больше чем», «простое (число)» и т. п.). Переменным также сопоставляются гёделевские номера, причем делается это в соответствии со следующими соглашениями:
1) различным числовым переменным приписываются различные простые числа, большие 10;
2) различным пропозициональным переменным приписываются квадраты различных простых чисел, больших 10;
3) различным предикатным переменным приписываются кубы различных простых чисел, бОльших 10.
* Кавычки (добавленные при переводе) означают здесь, что подставить можно не само написанное в правом столбце слово, а его формальную запись на языке нашего исчисления. — Прим. перев.
Возьмем какую-нибудь формулу нашей системы, например
Ǝx (x = sy)
(которую можно прочесть как «существует такое x, что x непосредственно следует за y» и которая выражает то обстоятельство, что для каждого числа есть непосредственно следующее за ним число). Выпишем под каждым из входящих в нее символов его (символа) гёделевский номер:
Ǝx ( x = s у )
↓↓↓↓↓↓↓↓
4 11 8 11 5 7 13 9
Конечно, нам бы хотелось сопоставить каждой формуле не набор номеров (как пока получилось), а один-единственный определенный номер. Но это очень легко сделать. А именно: сопоставим этой формуле произведение первых восьми простых чисел в порядке их величины, причем каждое из них в степени, показатель которой равен гёделевскому номеру соответствующего элементарного символа:
24× 311× 58× 711× 115× 137× 1713× 99.
Обозначим это число, скажем, через