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

Материал из synset
Версия от 14:17, 11 февраля 2010; WikiSysop (обсуждение | вклад) (Защищена страница «Теорема Гёделя о неполноте» ([edit=sysop] (бессрочно) [move=sysop] (бессрочно)))
Перейти к: навигация, поиск
Формулы арифметики их номера << Оглавление >> Что такое истина?

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

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

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

.

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

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

Непротиворечивость означает, что ложную формулу нельзя доказать Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle \mathbf{Proof}(Л)=Л} , а если формула доказуема Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle \mathbf{Proof}(\mathcal F)=И} , то она истинна: Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle \mathcal F=И} . Поэтому строится такое доказательство от противного: : пусть Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle \mathbf{Proof}(\mathbf{G})=И \;\;=>\;\; \mathbf{G}=И,\;но\;\mathbf{G}=\neg \mathbf{Proof}(\mathbf{G})=\neg И=Л} . Мы получили противоречие, значит исходная посылка "Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle \mathbf{Proof}(\mathbf{G})=И} " не верна, следовательно, доказательства утверждения G не существует. Но об этом и утверждает G, поэтому мы построили высказывание, которое не доказуемо, но при этом истинно по своему смыслу.

Конечно можно было построить и прямое доказательство теоремы: : пусть Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{Proof}(\mathbf{G})=Л \;\;=>\;\; \mathbf{G}=Л,\;но\;\mathbf{G}=\neg \mathbf{Proof}(\mathbf{G})=\neg Л=И} и опять получить противоречие. Однако, так не делают. Почему? Потому, что в первом случае вывод из "Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle \mathbf{Proof}(\mathbf{G})=И} " того, что "Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle \mathbf{G}=И} " основывается на определении истинности (раз доказательство утверждения существует, то утверждение истинно). Во втором же случае, учитывая общие соображения, приведенные в начале этого раздела, можно усомниться в том, что из отсутствия доказательства утверждения , т.е. "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{Proof}(\mathbf{G})=Л} " следует его ложность "Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle \mathbf{G}=Л} " (как в прочем, и истинность). Поэтому, рассуждения считаются неправомерными.

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

Введём предикат , обозначающий, что формула под номером имеет доказательство под номером , т.е. доказывает . Понятно, что когда доказательство уже построено, в силу его формальности, мы всегда можем проверить, что оно соответствует принятыми правилам, и в его конце находится доказываемая формула . Подобный алгоритм вполне реализуем, поэтому предикат можно также рассматривать как всюду определённую вычислимую на компьютере функцию, возвращающую 1, если доказывает или 0, если нет.

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

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

В этом определении, символ — это конкретное число (гёделевский номер формулы), получаемое из решения уравнения: .

Теперь можно "смело" проводить доказательство теоремы о не полноте. Например, пусть доказуемо, тогда существует некоторый номер доказательства , при котором истинно. Следовательно, можно ввести квантор всеобщности и записать , а это не что иное, как . Мы приходим к противоречию, следовательно не доказуемо. Аналогично проверяется недоказуемость .

Вернёмся к уравнению . Как оно должно решаться? В предикате (или в соответствующем алгоритме для компьютера) кодируются все символы, и в тех местах, где встречается , ставится сначала "", вычисляется гёделевский номер формулы, и проверяется не равен ли он 0. Если нет, подставляется (т.е. 1) и сравнивается результат с единицей, затем , и т.д, пока решение найдено не будет. Увы, но, по крайней мере в гёделевской нумерации, это уравнение не имеет решения! Действительно, если код штриха равен числу , то штрихов в вместо на -той позиции приведут в к произведению простых чисел в степени : , что существенно больше чем число (которому должно равняться ). Взять для штриха код нельзя, так как тогда формулы и будут неотличимы. Таким образом, такой прямолинейный вариант построения не проходит, и необходимы дополнительные хитрости.

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

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

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

Она вычисляется по следующему алгоритму. Берётся формула с произвольным номером . По этому номеру "раскручивается" её строковое представление . В нём вместо всех свободных вхождений подставляется число [в форме ], и снова вычисляется гёделевский номер. В принципе, может возникнуть несколько свободных переменных, поэтому будем считать, что означает, что все они замещаются на . Чтобы была всюду определена, необходимо модифицировать алгоритм нумерации так, чтобы для всех при применении получались правильно построенные формулы, иначе нельзя будет идентифицировать свободна переменная или нет. Пусть это сделано.

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

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

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

Подчеркнём, что — это конкретное число, вычисленное при помощи гёделевской нумерологии по строке , где свободная переменная.

Не сложно видеть, что формула имеет номер равный :

Действительно, функция восстанавливает формулу и подставляет в неё число . Таким образом, утверждает свою недоказуемость.

Подобное построение уже не содержит явных просчётов, но тем не менее предполагает доказанными ряд "очевидных" посылок. Так, мы считаем, что можно вычислять номер формул, содержащих "мета"- арифметическую функцию , которую не просто записать в рамках только арифметических операций, так как она использует поиск и замену свободных переменных. Поэтому, лучше и воспринимать как программы для идеального компьютера, например, на языке BASE. Правда, переходя к программированию, прийдётся выразить символы существования и единственности в виде бесконечных циклов, а не использовать их как самостоятельные математические объекты. Тем не менее, будем считать, что объект "сконструирован".

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

Даже если при построении удаётся формально устранить все сомнения, есть ещё один вопрос, связанный с квантором существования , и определением предиката . Вспомним, что при доказательстве теоремы Тьюринга, противоречие свидетельствовало об отсутствии универсальной функции контроля остановки . Не возникает ли той же проблемы с функцией ?


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

Истинность и доказуемость - о конструктивной математике, Канторе и Гёделе