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

Читатель теперь легко убедится в том, что метаматематическое утверждение, гласящее, что некоторая последовательность формул есть доказательство данной формулы, является истинным в том и только в том случае, если гёделевский номер этой последовательности формул находится с гёделевским номером данной формулы как раз в том арифметическом отношении, которое мы обозначили здесь через «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». Впрочем, сама форма вопроса уже отчасти подсказывает ответ. Мы ведь уже упоминали о важном различии между понятиями «число» и «цифра». Цифра — это некоторый знак, т. е. выражение языка, которое можно записывать, стирать, зачеркивать, повторять и т. д. и т. п. Число же — это то, именем (или названием, обозначением) чего является обозначающая его цифра; само по себе число нельзя записать, стереть, зачеркнуть, повторить.