Идея кодирования и ее использование в математике

 

Исчисление высказываний представляет собой пример математической системы, по отношению к которой задачи, выдвигаемые гильбертовской теорией доказательства, оказались, как мы видели, полностью реализованными. Конечно, это исчисление формализует лишь некоторый фрагмент формальной логики, язык и дедуктивный аппарат которого недостаточны даже для формального построения элементарной арифметики. Но возможности гильбертовской программы отнюдь не ограничиваются доказательством непротиворечивости исчисления высказываний. Можно привести примеры гораздо более богатых теорий, для которых оказалось возможным дать строго метаматематические доказательства непротиворечивости и полноты. Примером может служить арифметическая система с операцией сложения (но без операции умножения) натуральных чисел, для которой также можно провести абсолютное доказательство непротиворечивости. Но достаточно ли сильны финитные методы Гильберта для установления непротиворечивости систем вроде Principia – систем, выразительные и логические средства которых позволяют построить всю арифметику, а не только отдельные ее фрагменты? Неоднократные попытки найти такое доказательство успехом не увенчались, а работа Гёделя 1931 г. показала, что они и не могли быть успешными, так как, строго придерживаясь границ, предначертанных в исходной формулировке гильбертовской программы, эту задачу вообще решить нельзя.

Что же, собственно, доказал Гёдель и как именно доказал? В работе Гёделя имеются два основных результата. Прежде всего (мы здесь не имеем в виду тот порядок, в каком эти результаты излагаются в самой работе Гёделя) он доказывает невозможность метаматематического доказательства непротиворечивости любой системы, достаточно обширной, чтобы включать в себя всю арифметику, которое (доказательство) не использовало бы каких‑либо существенно иных правил вывода, кроме тех, что используются для вывода теорем в самой рассматриваемой системе. Конечно, и такое (пользующееся более сильными в некотором смысле правилами вывода) доказательство может быть очень важным и полезным. Но все же если доказательство строится на основе правил вывода, значительно более мощных, нежели логические средства арифметического исчисления, так что уверенность в непротиворечивости используемых в доказательстве допущений будет ничуть не больше, чем расчеты на непротиворечивость арифметики, то ценность такого доказательства будет довольно‑таки специфической: мы убьем одно чудовище ценой рождения другого. Во всяком случае, если это доказательство будет не финитистским, то основной пункт гильбертовской программы останется, конечно, невыполненным. Гёделевское рассуждение как раз и показывает всю беспочвенность расчетов на нахождение финитистского доказательства непротиворечивости арифметики.

Второй основной результат работы Гёделя, пожалуй, еще более неожидан и поразителен; он указывает на некоторую принципиальную ограниченность возможностей аксиоматического метода. Гёдель показывает, что система Principia Mathematica, как и всякая иная система, средствами которой можно построить арифметику, – существенно неполна. Это значит, что для любой данной непротиворечивой системы арифметических аксиом имеются истинные арифметические предложения, не выводимые из аксиом этой системы.

Это обстоятельство играет решающую роль для оценки всей работы Гёделя, и на нем стоит остановиться несколько подробнее. Математикам хорошо известны примеры общих утверждений, для которых до сих пор не найдено никакого опровергающего примера, но не найдено и доказательства. Классическим примером такого рода может служить знаменитая «теорема Гольдбаха», утверждающая, что каждое четное число можно представить в виде суммы двух простых чисел. Мы не можем указать ни одного четного числа, которое не являлось бы суммой двух простых, но у нас нет и доказательства гипотезы Гольдбаха, пригодного для всех четных чисел. Таким образом, перед нами – арифметическое утверждение, которое вполне может быть истинным, но не выводимым из аксиом арифметики. Допустим, что это действительно так (утверждать подобное мы, разумеется, не можем). Представим себе, что мы изменили или пополнили исходную аксиоматику таким образом, чтобы все истинные, но не выводимые в исходной системе предложения (к их числу относится, по сделанному только что предположению, гипотеза Гольдбаха) станут в расширенной системе выводимыми[9]. Теорема Гёделя показывает, что никакое такое расширение арифметической системы не может сделать ее полной, т. е. что даже если пополнить ее бесконечным множеством аксиом, все равно в новой системе найдутся истинные, но не выводимые (хотя и выразимые!) ее средствами предложения.

 

^{Истинность таких предложений, как мы ниже увидим, можно установить посредством некоторого метаматематического рассуждения об арифметической системе. Но такое рассуждение не удовлетворяет требованию, согласно которому исчисление должно быть, так сказать, «замкнутой системой», т. е. все доказуемые в нем истинные предложения должны быть получены как формальные следствия из аксиом внутри самого исчисления. Таким образом, аксиоматический метод как средство построения всей содержательной арифметики оказывается принципиально ограниченным.}

 

Чтобы читателю было легче понять идею доказательства Гёделя, мы (следуя Гёделю) приведем вначале схему рассуждения, посредством которого получается логическая антиномия (противоречие), известная под названием «парадокса Ришара» (по имени описавшего ее в 1905 г. французского математика).

Возьмем какой‑нибудь язык (например, русский)[10], средствами которого можно описывать и определять все чисто арифметические свойства чисел. Рассмотрим определения, которые можно сформулировать на этом языке. Ясно, что некоторые термины, относящиеся к арифметическим свойствам, нам определить явным образом все равно не удастся (с чего‑то надо начать и в определениях во избежание ситуаций, известных под названиями «порочного круга» и «бесконечного спуска»), хотя, конечно, мы можем в принципе понимать смысл этих слов и без определений. Для нашей цели несущественно, какие именно термины принять в качестве исходных, неопределяемых; мы можем, например, считать, что мы понимаем смысл предложений «целое число делится на другое целое число», «целое число является произведением двух целых чисел» и т. п. Свойство быть простым числом тогда можно определить следующим образом: «не делиться ни на одно целое число, кроме самого себя и числа 1»; свойство быть точным квадратом: «быть произведением некоторого целого числа на то же число» и т. п.

Легко видеть, что каждое такое определение состоит лишь из конечного числа слов, а потому и из конечного числа букв алфавита. Поэтому мы можем ввести для таких словесных определений отношение порядка, считая одно определение предшествующим другому, если число букв, из которых состоит первое определение, меньше числа букв, составляющих второе определение; в тех же случаях, когда два определения состоят из одного и того же числа букв[11], одно из них считать предшествующим другому в обычном лексикографическом (алфавитном, словарном) порядке. Исходя из такого упорядочения можно теперь расположить все определения рассматриваемого вида в последовательность, сопоставив каждому из них единственное натуральное число – номер в этой же последовательности. Тогда самое короткое (и стоящее ранее других в алфавитном порядке) определение получит номер 1, следующее за ним в этом «словаре определений» – номер 2 и т. д.

Поскольку каждому определению теперь сопоставлено некоторое натуральное число, то может оказаться, что в некоторых случаях число, сопоставленное какому‑нибудь определению, само будет обладать определяемым свойством.

 

^{Ситуация здесь в точности такова же, как в том случае, когда все слова в обычном орфографическом словаре делятся на два класса: односложные и многосложные; при этом слово «многосложное» само оказывается многосложным.}

 

Пусть, например, определяющее выражение «не делиться ни на одно натуральное число, кроме самого себя и числа 1» оказалось в нашей последовательности на 17‑м месте; ясно, что сопоставленное ему число 17 само подпадает под это определение. Пусть, с другой стороны, определяющее выражение «быть произведением некоторого натурального числа на то же самое число» получило номер 15; само число 15, очевидно, не является точным квадратом и потому данным свойством не обладает. Назовем числа, не обладающие свойствами, определяемыми предложениями, которым они соответствуют в описанной нами нумерации, ришаровыми. Таким образом, «x – ришарово число» – это просто сокращение выражения «x не обладает свойством, определяемым предложением, имеющим номер x в данной словарной последовательности определяющих предложений». (Скажем, число 17 из нашего первого примера не является ришаровым, а число 15 из второго примера – ришарово.)

Теперь мы уже можем сформулировать парадокс Ришара. Определяющее выражение для свойства быть ришаровым числом описывает, очевидно, некоторое арифметическое свойство натуральных чисел. Значит, само определяющее выражение входит в описанную выше последовательность определяющих выражений. Но тогда оно имеет в этой последовательности некоторый номер, который мы обозначим через n. Зададим теперь вполне естественный вопрос (немедленно приводящий к антиномии Ришара): является ли число n ришаровым? Читатель, конечно, сразу увидит, что противоречие теперь неизбежно. В самом деле, число n является ришаровым в том и только в том случае, если оно не обладает свойством, описываемым предложением, имеющим номер n, т. е. не обладает свойством быть ришаровым! Короче говоря, n ришарово тогда и только тогда, когда оно не ришарово, т. е. утверждение «n – ришарово число» является одновременно истинным и ложным.

Следует заметить, что это противоречие в известном смысле есть трюк, который нам удался благодаря не вполне точному соблюдению правил игры. Дело в том, что мы фактически использовали одно допущение, которое, однако, предпочли в явном виде не формулировать. Мы согласились рассматривать определения чисто арифметических свойств натуральных чисел, т. е. свойств, формулируемых в терминах таких понятий, как арифметическое сложение, умножение и т. п. Затем, однако, без дополнительных оговорок мы включили в ту же последовательность определений предложение, сформулированное посредством упоминания о некотором способе записи арифметических свойств. Строго говоря, определение свойства быть ришаровым числом просто не принадлежит к той последовательности определений, которая вначале описывалась, так как это определение использует такие метаматематические понятия, как номер буквы (или вообще знака) в некоторой последовательности. Таким образом, если мы будем четко различать утверждения самой арифметики (относящиеся к числам, а отнюдь не к записям, в которые такие числа входят, т. е. к равенствам, неравенствам и вообще формулам) и утверждения относительно арифметики (т. е. как раз утверждения об арифметических формулах), то мы не получим никакого парадокса Ришара.

Значит, сам по себе парадокс Ришара совсем не страшен. Но сама схема приводящего к нему рассуждения чрезвычайно поучительна и плодотворна. Речь идет о возможности «отображения» (или «перевода») метаматематических высказываний, относящихся к некоторой достаточно богатой формальной системе, в саму систему. Сама по себе идея «перевода» хорошо известна и играет важнейшую роль во многих областях математики. Такая идея лежит, например, в основе всей аналитической геометрии, где геометрические понятия переводятся в алгебраические (арифметические), так что вместо геометрических соотношений мы, по существу, имеем дело с алгебраическими. (Вспомните хотя бы обсуждавшееся в разделе 2 отображение геометрии в алгебру, использованное Гильбертом для доказательства относительной непротиворечивости его системы геометрических аксиом). Такие отображения‑«переводы» играют большую роль и в физике, например, когда свойства электрического тока излагаются на языке гидродинамических явлений. Эта же идея перевода лежит в основе технического моделирования – идет ли речь об исследовании свойств модели самолета (или же самолета в натуральную величину) в аэродинамической трубе, или же об изучении в лабораторных условиях распределения каких‑либо материальных масс с помощью аналоговой модели, где роль этих масс играют электрические заряды.

На идее отображения[12] основан так называемый принцип двойственности в проективной геометрии, состоящий в возможности взаимной замены в аксиомах (а значит, и в теоремах) проективной геометрии терминов «точка» и «прямая», в результате чего аксиомы переходят в аксиомы (соответственно теоремы – в теоремы). При одном из таких «переводов» слово «точка» можно считать «образом», слово «прямая» – «прообразом»; при обратном переводе роли меняются.

Самым существенным в обсуждаемой здесь идее «моделирования» является то, что абстрактная структура отношений, выполняемых для «предметов» какой‑ либо области, может быть изучена с помощью рассмотрения отношений, имеющих место между «предметами» (как правило, другой природы, чем «предметы» исходной области), принадлежащими совсем другой области. Именно эта идея «кодирования» лежит в основе доказательства Гёделя. Если некоторые сложные метаматематические высказывания о формализованной системе арифметики можно, как рассчитывает Гёдель, перевести (или «отобразить») в некоторые арифметические высказывания, принадлежащие самой системе, то это уже само по себе явится большим достижением в деле развития теоретико‑доказательственной техники, так же, как исследовать алгебраические соотношения, представляющие (изображающие, кодирующие) некоторые геометрические соотношения между кривыми и поверхностями, гораздо удобнее, чем иметь дело с самими геометрическими соотношениями, – точно так же арифметические аналоги («образы») сложных логических соотношений оказываются в известном смысле более обозримыми и доступными для изучения, чем их логические «прообразы».

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

 

7

Теоремы Гёделя

 

Гёделевская нумерация

 

Гёдель прежде всего описал некоторое формализованное исчисление, средствами которого можно выразить все обычные арифметические понятия и установить известные арифметические соотношения.

 

^{Гёдель использовал несколько упрошенный вариант системы, описанной в Principia Mathematics. Но для его цели точно так же подходит любое исчисление, в котором можно построить систему натуральных чисел с определенными на ней арифметическими операциями.}

 

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

Гёдель показал, что каждому элементарному символу, каждой формуле (т. е. цепочке элементарных символов) и каждому доказательству (конечной последовательности формул) можно однозначным образом приписать некоторый номер (натуральное число). Такой номер, служащий своего рода значком, ярлыком, указывающим на отмечаемый им объект – символ, формулу или доказательство – формальной системы, мы будем называть «гёделевским номером» этого символа, формулы или доказательства[13].

Элементарные символы, составляющие алфавит системы, бывают двух сортов: константы и переменные. Мы будем считать, что у нас есть ровно десять символов‑констант, которым мы припишем в качестве гёделевских номеров числа от 1 до 10. Почти все эти символы читателю уже известны: «~» (сокращение для «не»), «˅» («или»), «ﬤ» («если…, то…»), «=» («равно»), «0» (цифровой знак, изображающий число «нуль»), а также три «знака препинания»: левая скобка «(», правая скобка «)» и запятая «,». Кроме того, нам понадобятся еще два символа: перевернутая буква «Ǝ» (читаемая как «существует» и называемая «квантором существования») и строчная латинская буква «s», обозначающая числовой оператор, сопоставляющий каждому натуральному числу непосредственно следующее за ним число. Пример: формулу «Ǝ x (x = s 0)» можно прочесть как «существует такое 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

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

2⁴ × 3¹¹ × 5⁸ × 7¹¹ × 11⁵ × 13⁷ × 17¹³ × 9⁹.

Обозначим это число, скажем, через m. Точно таким же образом мы можем приписать в качестве гёделевского номера единственное вполне определенное натуральное число каждой конечной последовательности элементарных символов, в частности каждой формуле, причем число простых сомножителей такого числа всегда будет равно числу вхождений элементарных символов в обозначаемой формуле.

 

^{В исчислении могут использоваться и символы, не входящие в его исходный («основной») алфавит; такие символы вводятся посредством определений, записанных в терминах исходных (и вообще ранее определенных) символов. Например, в наше исчисление можно ввести новый символ (константу) «·», обозначающий союз «и», определив его таким образом, чтобы запись «p · q» воспринималась как сокращение записи «~(~ p ˅~ q)». Какой гёделевский номер сопоставить введенному таким образом символу? Ответ станет совершенно очевидным, когда мы заметим, что из выражений, содержащих дополнительные (введенные определениями) символы, эти новые символы можно исключить, заменив их обозначаемыми ими выражениями, составленными исключительно из исходных символов (для этого мы просто читаем соответствующие определения «справа налево»); для последних же гёделевеcкие номера мы строить умеем. Поэтому нам достаточно условиться считать гёделевским номером формулы «p · q» гёделевский номер эквивалентной ей формулы «~(~ p ˅~ q)», гёделевским номером «формулы» «2 ≠ 3» – номер заменяемой ею «настоящей» формулы «~(ss 0= sss 0)» и т. п., условившись, конечно (что совсем нетрудно), об однозначном порядке таких «расшифровок».}

 

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

Ǝ x (x = sy),

Ǝ x (x = s 0).

Вторая формула последовательности, читаемая как «существует число, непосредственно следующее за нулем», – выводимая из первой формулы посредством подстановки цифры 0 вместо числовой переменной.

 

^{Читатель, конечно, помнит, что формальное доказательство мы определяли выше как конечную последовательность формул, каждая из которых есть либо аксиома, либо выводима из предыдущих формул этой последовательности по правилам вывода данного исчисления. Согласно этому определению приведенная пара формул доказательством не является (первая ее формула – не аксиома) – это лишь «кусок» доказательства, на примере которого мы столь же понятно (но далеко не так громоздко) поясним идею нумерации, как и на целом доказательстве.}

 

Выше мы уже определили гёделевский номер первой из этих формул – мы обозначили его тогда через m. Пусть гёделевским номером второй формулы является число n. Как и выше, мы хотим сопоставить нашей последовательности не пару чисел m и n, а некоторое единственным образом определенное натуральное число. Для этого нам достаточно взять в качестве такого гёделевского номера число, являющееся произведением степеней первых двух простых чисел (т. е. чисел 2 и 3), причем первый сомножитель будет входить в это произведение в степени, показатель которой равен гёделевскому номеру первой формулы, и аналогично для второго сомножителя (а также для третьего и других, если мы имеем дело с последовательностью, состоящей более чем из двух формул). Обозначим это число через k: k = 2^m × 3 ⁿ. Такой простой и компактный метод применим, очевидно, для получения гёделевского номера произвольной последовательности формул. Таким образом, любое выражение нашей системы – будь то элементарный символ, последовательность символов или последовательность таких последовательностей – может быть однозначно занумеровано посредством некоторого гёделевского номера.

Теперь уже полная «арифметизация» нашего формального исчисления не представит никакого труда. Такая «арифметизация» попросту сводится к устанорлению некоторого взаимно‑однозначного соответствия между выражениями, входящими в исчисление, и некоторым подмножеством натурального ряда.

 

^{Не всякое натуральное число есть гёделевский номер константы, переменной или формулы; предоставляем читателю придумать и разобрать примеры на различные возможные случаи.}

 

Если нам дано какое‑нибудь выражение, мы без труда напишем его гёделевский номер. Это, однако, лишь полдела. Важно то, что когда нам дано какое‑либо натуральное число, то мы можем установить, является ли это число гёделевским номером, а если да – то можем точно «восстановить» обозначаемое этим номером выражение. Если данное число не превосходит 10, то это, как мы знаем, просто номер некоторой константы. Если же данное число больше 10, то его можно разложить, причем единственным образом (в этом состоит так называемая основная теорема арифметики), на простые сомножители. Если оно оказалось простым, квадратом простого или кубом простого числа, то это – гёделевский номер переменной.

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

И в таком случае выражение, которому соответствует данный номер, может быть точно определено.

Следуя намеченной программе, мы можем для любого данного числа совершенно единообразным методом («как машина») проверить, является ли оно гёделевским номером, а если да – то какого выражения[14]. Пусть, например, нам дано число 243 000 000. Разложим его (оно, очевидно, составное) на простые сомножители: 243 000 000 = 64 × 243 × 15 625 = 2⁶ × 3⁵ × 5⁶. Вспомнив, что 6 есть гёделевский номер константы «0», а 5 – гёделевский номер знака «=», рисуем схему:

6 5 6

↓ ↓ ↓

0 = 0

Теперь видно, что число «243 миллиона» действительно есть гёделевский номер некоторой формулы, а именно, формулы «0 = 0» (т. е. «нуль равен нулю»).