Теорема Гёделя о неполноте

Формулы арифметики их номера <<	Оглавление	>> Что такое истина?

Как ни странно, но существование формул, которые невозможно ни доказать ни опровергнуть, на самом деле, достаточно естественно. В математике нет ограничения на длину доказательства. Мы можем записать сколь угодно длинную формулу. Её формальное доказательство также является формулой, которая будет ещё длиннее. Более того, весь опыт математики говорит о том, что минимально возможная длина доказательства данной формулы напрямую не связана с её длиной. Многие очень простые формулы имеют очень сложные (=длинные) доказательства (теорема Ферма, задача о 4-х красках, и т.п.).

Отсутствие ограничений на длину доказательства наводит на мысль, что некоторые теоремы (в том числе и достаточно простые в своей формулировке) никогда не будут доказаны или опровергнуты, хотя бы потому, что самое короткое из возможных их доказательств превышает все ресурсы памяти и времени жизни человека и даже всего человечества. Так как не существует "самого длинного доказательства", то не сложно сделать еще один шаг и допустить существование формул, которые требуют бесконечно длинных доказательств. Такие формулы не доказуемы принципиально.

Гёдель в 1931 г. предложил формальную демонстрацию этого факта. Введем логическую функцию " $\textstyle \mathbf {Proof} (A)$ ", обозначающую то, что существует доказательство формулы " $\textstyle A$ ". Если доказательство " $\textstyle A$ " существует, то " $\textstyle \mathbf {Proof} (A)$ =И=истина", а если нет то " $\textstyle \mathbf {Proof} (A)$ =Л=ложь". Теперь рассмотрим высказывание $\textstyle \mathbf {G}$ , определяемое как утверждение о том, что оно недоказуемо:

$\textstyle \mathbf {G} :\neg \mathbf {Proof} (\mathbf {G} )$ .

Сформулируем теорему Гёделя:

"Если теория непротиворечива, то формула $\textstyle \mathbf {G}$ истинна, но ее нельзя доказать: $\textstyle \mathbf {Proof} (\mathbf {G} )$ =Л".

Непротиворечивость означает, что ложную формулу нельзя доказать $\textstyle \mathbf {Proof}$ (Л)=Л, а если формула доказуема $\textstyle \mathbf {Proof} ({\mathcal {F}})$ =И, то она истинна: $\textstyle {\mathcal {F}}$ =И. Поэтому строится такое доказательство от противного:

$\textstyle \lozenge _{1}$ : пусть $\textstyle \mathbf {Proof} (\mathbf {G} )$ =И $\;\;=>\;\;\mathbf {G}$ =И, но $\mathbf {G} =\neg \mathbf {Proof} (\mathbf {G} )=\neg$ И=Л.

Мы получили противоречие, значит исходная посылка " $\textstyle \mathbf {Proof} (\mathbf {G} )$ =И" не верна, следовательно, доказательства утверждения G не существует. Но об этом и утверждает G, поэтому мы построили высказывание, которое не доказуемо, но при этом истинно по своему смыслу.

Конечно можно было построить и прямое доказательство теоремы:

$\textstyle \lozenge _{2}$ : пусть $\textstyle \mathbf {Proof} (\mathbf {G} )$ =Л => $\mathbf {G} =$ Л, но $\mathbf {G} =\neg \mathbf {Proof} (\mathbf {G} )=\neg$ Л=И

и опять получить противоречие. Однако, так не делают. Почему? Потому, что в первом случае вывод из " $\textstyle \mathbf {Proof} (\mathbf {G} )$ =И" того, что " $\textstyle \mathbf {G}$ =И" основывается на определении истинности (раз доказательство утверждения существует, то утверждение истинно). Во втором же случае, учитывая общие соображения, приведенные в начале этого раздела, можно усомниться в том, что из отсутствия доказательства утверждения $\textstyle \mathbf {G}$ , т.е. " $\textstyle \mathbf {Proof} (\mathbf {G} )$ =Л" следует его ложность " $\textstyle \mathbf {G}$ =Л" (как в прочем, и истинность). Поэтому, рассуждения $\textstyle \lozenge _{2}$ считаются неправомерными.

Формулировки и доказательство, приведенные выше, очень психологичны. Они используют никак не определённое понятие $\textstyle \mathbf {Proof}$ ("существует доказательство"), а также объект G, который, подобно парадоксу лжеца, вводится со ссылкой на самого себя. Поэтому, в такой форме теорема о неполноте убедительна только при изрядной харизме доказывающего. Заслуга Гёделя состоит в том, что он придал и $\textstyle \mathbf {Proof}$ и $\textstyle \mathbf {G}$ видимость конструктивных объектов в рамках арифметики натуральных чисел.

Введём предикат $\textstyle {D}(p,f)$ , обозначающий, что формула под номером $\textstyle f$ имеет доказательство под номером $\textstyle p$ , т.е. $\textstyle {\mathcal {P}}$ доказывает $\textstyle {\mathcal {F}}$ . Понятно, что когда доказательство $\textstyle {\mathcal {P}}$ уже построено, в силу его формальности, мы всегда можем проверить, что оно соответствует принятыми правилам, и в его конце находится доказываемая формула $\textstyle {\mathcal {F}}$ . Подобный алгоритм вполне реализуем, поэтому предикат $\textstyle {D}(p,f)$ можно также рассматривать как всюду определённую вычислимую на компьютере функцию, возвращающую 1, если $\textstyle {\mathcal {P}}$ доказывает $\textstyle {\mathcal {F}}$ или 0, если нет.

При помощи $\textstyle {D}(p,f)$ мы можем определить утверждение, которое себя не может доказать. Рассмотрим сначала следующий простой вариант:

Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \mathbf{G} : \neg \exists p \,D(p, g),\;\;\;\;\;\;\;где\;\;\;\;\;g=\gamma(\mathbf{G})=\gamma(''\neg \exists p \,D(p, g)'').}

В этом определении, символ $\textstyle g$ — это конкретное число (гёделевский номер формулы), получаемое из решения уравнения: $\textstyle g=\gamma (''\neg \exists p\,D(p,g)'')$ .

Теперь можно "смело" проводить доказательство теоремы о не полноте. Например, пусть $\textstyle \mathbf {G}$ доказуемо, тогда существует некоторый номер доказательства $\textstyle p_{0}$ , при котором $\textstyle D(p_{0},g)$ истинно. Следовательно, можно ввести квантор всеобщности и записать $\textstyle \exists p\,D(p,g)$ , а это не что иное, как $\textstyle \neg \mathbf {G}$ . Мы приходим к противоречию, следовательно $\textstyle \mathbf {G}$ не доказуемо. Аналогично проверяется недоказуемость $\textstyle \neg \mathbf {G}$ .

$\textstyle \bullet$ Вернёмся к уравнению $\textstyle g=\gamma (''\neg \exists p\,D(p,g)'')$ . Как оно должно решаться? В предикате $\textstyle D(p,x)$ (или в соответствующем алгоритме для компьютера) кодируются все символы, и в тех местах, где встречается $\textstyle x$ , ставится сначала " $\textstyle 0$ ", вычисляется гёделевский номер формулы, и проверяется не равен ли он 0. Если нет, подставляется $\textstyle \,0'\,$ (т.е. 1) и сравнивается результат с единицей, затем $\textstyle 0''$ , и т.д, пока решение найдено не будет. Увы, но, по крайней мере в гёделевской нумерации, это уравнение не имеет решения! Действительно, если код штриха равен числу $\textstyle m>0$ , то $\textstyle g$ штрихов в $\textstyle 0'''''$ вместо $\textstyle x$ на $\textstyle k$ -той позиции приведут в $\textstyle \gamma$ к произведению простых чисел в степени $\textstyle m$ : $\textstyle p_{k+1}^{m}\cdot ...\cdot p_{k+1+g}^{m}$ , что существенно больше чем число $\textstyle g$ (которому должно равняться $\textstyle \gamma$ ). Взять для штриха код $\textstyle m=0$ нельзя, так как тогда формулы $\textstyle \gamma (''0=0'')$ и $\textstyle \gamma (''\,0=0'''\,'')$ будут неотличимы. Таким образом, такой прямолинейный вариант построения $\textstyle \mathbf {G}$ не проходит, и необходимы дополнительные хитрости.

$\textstyle \bullet$ Предикат $\textstyle D(p,f)$ получает номер любой формулы $\textstyle f$ . Однако, её доказательство $\textstyle p$ может существовать только если $\textstyle f$ замкнута (без свободных переменных). Так, " $\textstyle x>2$ " не доказуема и не опровергаема. Рассмотрим, тем не менее, класс формул, которые содержат одну свободную переменную вида $\textstyle F(x)$ и будем их доказывать при данном $\textstyle x$ :

Q(x):\;\;x>2,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;F(x):\;\;\exists a\,\exists b\,\exists c\,(a^{x}+b^{x}=c^{x}),\;\;\;\;\;\;\;\;....

При любом конкретном $\textstyle x$ , первая формула имеет простое доказательство, и $\textstyle Q(3)$ , например, будет истинной. Вторая формула, для $\textstyle F(3)$ потребует уже достаточно нетривиальных рассуждений и будет ложной, и т.д. Все такие формулы имеют номер $\textstyle f=\gamma (''x>0'')$ . Если же на место $\textstyle x$ подставлено конкретное число, номер будет другой, так как это другая строка $\textstyle f_{1}=\gamma (''0'''>0'')$ .

Для подстановки "данного числа" введём функцию:

s(f)=\gamma \left(\,\{x/f\}\;\Gamma (f)\,\right).

Она вычисляется по следующему алгоритму. Берётся формула с произвольным номером $\textstyle f$ . По этому номеру "раскручивается" её строковое представление $\textstyle \Gamma (f)$ . В нём вместо всех свободных вхождений $\textstyle x$ подставляется число $\textstyle f$ [в форме $\textstyle 0''''''$ ], и снова вычисляется гёделевский номер. В принципе, может возникнуть несколько свободных переменных, поэтому будем считать, что $\textstyle \{x/f\}$ означает, что все они замещаются на $\textstyle f$ . Чтобы $\textstyle s(f)$ была всюду определена, необходимо модифицировать алгоритм нумерации так, чтобы для всех $\textstyle f=0,1,2,...$ при применении $\textstyle \Gamma (f)$ получались правильно построенные формулы, иначе нельзя будет идентифицировать свободна переменная или нет. Пусть это сделано.

Определим теперь высказывание (формулу):

G(x):\;\;\neg \exists p\,D(p,s(x)).

Здесь содержится утверждение о том, что не существует доказательства некоторой формулы под номером $\textstyle x$ , в которую вместо всех свободных переменных подставлен номер этой формулы, т.е. конкретное число $\textstyle x$ . Пусть гёделевский номер $\textstyle G(x)$ (формула зависящая от одной свободной переменной) равен $\textstyle g$ . Тогда определим:

Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \mathbf{G} :\;\;\neg \exists p\, D(p, s(g)),\;\;\;\;\;\;\;\;\;где\;g=\gamma(''\neg \exists p\, D(p, s(x))'').}

Подчеркнём, что $\textstyle g$ — это конкретное число, вычисленное при помощи гёделевской нумерологии по строке $\textstyle \gamma (''\neg \exists p\,D(p,s(x))'')$ , где $\textstyle x$ свободная переменная.

Не сложно видеть, что формула $\textstyle \mathbf {G}$ имеет номер равный $\textstyle s(g)$ :

\gamma (\mathbf {G} )=\gamma (''\neg \exists p\,D(p,s(g))'')=s(g).

Действительно, функция $\textstyle s(g)$ восстанавливает формулу $\textstyle G(x)$ и подставляет в неё число $\textstyle g$ . Таким образом, $\textstyle \mathbf {G}$ утверждает свою недоказуемость.

$\textstyle \bullet$ Подобное построение уже не содержит явных просчётов, но тем не менее предполагает доказанными ряд "очевидных" посылок. Так, мы считаем, что можно вычислять номер формул, содержащих "мета"- арифметическую функцию $\textstyle s(x)$ , которую не просто записать в рамках только арифметических операций, так как она использует поиск и замену свободных переменных. Поэтому, лучше $\textstyle D(p,f)$ и $\textstyle s(x)$ воспринимать как программы для идеального компьютера, например, на языке BASE. Правда, переходя к программированию, прийдётся выразить символы существования и единственности в виде бесконечных циклов, а не использовать их как самостоятельные математические объекты. Тем не менее, будем считать, что объект $\textstyle \mathbf {G}$ "сконструирован".

Получая противоречие при доказательстве $\textstyle \lozenge _{1}$ теоремы Гёделя, необходимо помнить, что возможны два варианта: (1) теорема верна; (2) объекты, участвующие в её доказательстве, не существуют, так как некорректно определены. Не всегда существование противоречия доказывает то, что мы хотим доказать!

Даже если при построении $\textstyle \mathbf {G}$ удаётся формально устранить все сомнения, есть ещё один вопрос, связанный с квантором существования $\textstyle \exists$ , и определением предиката $\textstyle \mathbf {Proof} (f)=\exists p\,D(p,f)$ . Вспомним, что при доказательстве теоремы Тьюринга, противоречие свидетельствовало об отсутствии универсальной функции контроля остановки $\textstyle T(p,i)$ . Не возникает ли той же проблемы с функцией $\textstyle \mathbf {Proof} (f)$ ?