Teopeмa Гёделя - Нагель Эрнст. Страница 15

У читателя не раз мог возникнуть вопрос, почему, собственно, мы говорили сейчас не просто о «числе 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») является лишь схемой (формой) имени некоторого числа, но не формулой.

7.3. Изложение доказательств

Перейдем, наконец, к описанию идеи самого доказательства теоремы Гёделя. Вначале мы дадим совсем простой его набросок, разделив доказательство на пять основных шагов.

Прежде всего Гёдель показывает (1), как построить арифметическую формулу G, представляющую («кодирующую») метаматематическое высказывание «формула G недоказуема». Иначе говоря, формула G гласит о себе самой, что она недоказуема.

Идея построения такой формулы G по существу заимствована из рассуждения, приводящего к парадоксу Ришара. В этом парадоксе, как мы помним, выражению «ришарово число» сопоставляется некоторое число n, после чего рассматривается предложение «n есть ришарово число». В гёделевском же доказательстве формуле G сопоставляется некоторое число h, причем это делается так, чтобы оно соответствовало предложению «Формула, которой сопоставлено число h, недоказуема». Но затем Гёделю удается показать (2), что формула G доказуема тогда и только тогда, когда доказуемо ее формальное отрицание ~G. И этот шаг доказательства аналогичен соответствующему этому рассуждению в парадоксе Ришара, где доказывается, что п есть ришарово число в том и только в том случае, если п не есть ришарово число. Но если некоторая формула и ее отрицание доказуемы, то арифметическое исчисление, в котором возможны оба доказательства, противоречиво.

Значит, если это исчисление непротиворечиво, то как G, так и ~ G не выводимы из аксиом арифметики. Следовательно, если арифметика непротиворечива, то G является формально неразрешимой формулой. Далее Гёдель доказывает (3), что хотя формула G формально недоказуема, она является тем не менее истинной арифметической формулой. Она является истинной в том смысле, что утверждает про каждое натуральное число, что оно обладает некоторым арифметическим свойством, причем свойство это такого рода, что наличие его у каждого натурального числа можно действительно подтвердить посредством прямой проверки (4). Поскольку формула G, будучи истинной, является формально недоказуемой, система аксиом арифметики неполна. Иными словами, из аксиом арифметики нельзя вывести все истинные стремления арифметики. Более того, Гёдель доказал существенную неполноту [19] арифметики: даже если присоединить к ее аксиоматике новые аксиомы, обеспечивающие выводимость истинной формулы G, все равно и для такой пополненной (расширенной) системы можно всегда указать истинную, но формально недоказуемую формулу (5). В заключение Гёдель указал, как построить арифметическую формулу А, представляющую метаматематическое высказывание «Арифметика непротиворечива», и доказал, что формула «А ﬤ G» формально недоказуема. Из этого следует недоказуемость и самой формулы А. Окончательный вывод: непротиворечивость арифметики нельзя установить посредством рассуждения, представимого в формальном арифметическом исчислении.

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

1. Мы уже определили выше формулу «~ Dem(x, z)», представляющую в формальном арифметическом исчислении метаматематическое высказывание: «последовательность формул, имеющая гёделевский номер x, не является доказательством формулы, имеющей гёделевский номер z». Теперь мы доставив перед формулой приставку «∀x», являющуюся формальным аналогом языкового оборота «для всех x» (или «для любого x»), и получим в результате новую формулу «∀ x ~ Dem (x, z)», представляющую в формальной арифметике метаматематическое высказывание: «для любого x последовательность формул, имеющая гёделевский номер x, не является доказательством формулы, имеющей гёделевский номер z». Таким образом, эта новая формула является как раз той формулой формального арифметического исчисления, которая представляет в нем метаматематическое высказывание «формула, имеющая гёделевский номер z, недоказуема», или, что то же: «для формулы с гёделевским номером z нельзя построить доказательство».