Ю.Манин

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


Первый уровень.

Алфавит LAr включает: буквы русского и латинского шрифтов с индексами, цифры, скобки, знаки арифметических операций: + (сложение); ·, или × (умножение); ↑ (возвышение в степень); = (знак равенства). Типичный текст на LAr состоит из смеси обычных формул школьной арифметики и алгебры и минимума русской лексики, необходимого для выражения логических понятий (слов-связок «если…, то», «и», «или», «не»; слов-кванторов «для всех» и «существует»)

Второй уровень.

так называемый формальный язык арифметики по Шмульяну SAr: Алфавит SAr состоит из девяти знаков: x (переменная); ′ (штрих для формирования любого числа разных переменных x, x′, x′′, x′′′, … ); · (умножение); ↑ (возведение в степень); = (равенство); ↓ (логическая связка «конъюнкция отрицаний»); ( , ) (открывающая и закрывающая скобки); 1 (единица). Тексты на SAr являются последовательностями выражений; выражения – это некоторые последовательности знаков алфавита. Выражения бывают трех типов: числовые термы, классовые термы и формулы.

Высказывания на языке LAr (и формулы языка SAr) могут быть истинными, ложными или неопределенными (в отношении истинности). Неопределенными могут быть только те высказывания, в которых участвуют свободные символы переменных (x, y, z, … ), т. е. не связанные словами «для всех» или «существует». Высказывание «для всех x (x = 2)» ложно, ибо есть натуральные числа, отличные от 2; высказывание «существует x (x + 1000 = 2000)» истинно; высказывание «x = 3» не определенно: оно станет определенным – истинным или ложным, – если вместо «свободной» переменной x мы подставим в него то или иное (целое неотрицательное) число; высказывание «x = x» истинно, хотя переменная x в нем свободна.

Очень существенно, что все высказывания, не содержащие свободных переменных, мы считаем заведомо определенными в отношении истинности или ложности, даже если мы не в состоянии действительно решить, истинны они или ложны. Типичный пример – гипотеза Ферма:

    для всех x, y, z, n неверно, что
    (x + 1)↑(n+3)  +  ( y + 1)↑(n+3)  =  (z + 1)↑(n+3)
Согласно нашим представлениям, она либо истинна, либо ложна. Вера в это основана на абстрактной возможности произвести бесконечно много проверок числовых тождеств, которые получатся, если в уравнение Ферма подставлять всевозможные целые неотрицательные числа вместо x, y, z, n.

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

Кроме логических аксиом и правил вывода, в набор дедуктивных средств всякого языка, ориентированного на ту или иную область математики, входят «специальные» аксиомы. Они выражают те сведения об объектах теории, истинность которых мы постулируем, подкрепляя ее неформальными соображениями. В LAr к ним могут относиться обычные правила действия с целыми числами, коммутативность и ассоциативность умножения и сложения, дистрибутивность сложения относительно умножения, аксиомы индукции.

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

Теорема Гёделя: Полного финитно описываемого набора аксиом арифметики не существует.

Этот результат может быть строго доказан для SAr и проиллюстрирован для LAr. Принципы его доказательства применимы вообще к любому достаточно выразительному языку математики, на какой бы круг идей он ни был ориентирован. Требование достаточной выразительности здесь означает просто чтобы на языке можно было говорить также о целых числах и чтобы всякое их свойство, выразимое в LAr (или SAr), было выразимо и в этом языке. В остальном язык может быть любым.

Смысл теоремы Гёделя можно выразить иначе: для порождения всех истинных высказываний о целых числах нужно бесконечно много новых идей.

Принципы доказательства.

Чтобы доказать теорему Гёделя, нужно на время отказаться от рассмотрения отдельных высказываний, и обратиться к исследованию свойств истинности и выводимости в целом. С этой целью очень удобно перенумеровать все высказывания языка L целыми числами от 0 до ∞ и говорить затем просто об их номерах. На нашем неформальном уровне представим себе, что все высказывания расположены в словарном порядке и перенумерованы подряд целыми числами. Единственное существенное свойство нумерации, которым мы будем пользоваться, состоит в том, чтобы по каждому целому числу можно было чисто механически установить, является ли оно номером высказывания и если да, то какого; а по каждому высказыванию чисто механически установить его номер. Словарный порядок этому условию, очевидно, удовлетворяет, если правила образования высказываний сформулированы настолько точно, чтобы задачу их порождения и синтаксического анализа можно было поручить компьютеру (для LAr это не вполне так, что и будет главной причиной нестрогости последующих рассуждений)

Вот нумерация выражений в SAr, которой удобно пользоваться для доказательства теоремы Гёделя:

Перенумеруем как-нибудь все символы алфавита SAr цифрами от 1 до 9, так, чтобы лексически первый символ "1̄" получил номер 9. Чтобы получить номер конечной последовательности символов в SAr, заменим все эти символы соответствующими цифрами, прочтем результат как десятичную запись и увеличим его на единицу. Фиксируем такую нумерацию высказываний языка; ее принято называть нумерацией Гёделя.
Обозначим теперь буквой T множество номеров истинных высказываний, а D – множество номеров высказываний, выводимых из какой-нибудь финитно описываемой системы аксиом арифметики, или, более общо, выводимых с помощью данных дедуктивных средств.
Предполагается, что D содержится в T; мы хотим доказать, что D строго меньше, чем T. Это следует из двух фундаментальных принципов:
а) множество T невыразимо в языке LAr, если язык L достаточно богат
б) множество D всегда выразимо в языке LAr

Невыразимость истинности.

Это – теорема Тарского (1936), являющаяся вариантом одного промежуточного результата в первоначальном рассуждении Гёделя.

Ее доказательство основано на крайне остроумной модификации парадокса лжеца. Гёдель и Тарский показывают, что если в языке арифметики фиксировано некоторое высказывание P (x) с одной свободной переменной x, по нему можно построить высказывание Qp без свободных переменных, смысл которого в метаязыке можно выразить следующей фразой: Qp утверждает, что номер Qp не обладает свойством, выраженным P. Теперь предположим, что P выражает множество T номеров истинных высказываний, и придем к противоречию. Действительно, высказывание Qp определено и потому должно быть либо истинным, либо ложным. Если оно истинно, то истинно утверждение «номер Qp не обладает свойством, выраженным P», т. е. «номер Qp не принадлежит T», т. е. Qp не истинно – противоречие. Если же Qp ложно, то ложно утверждение «номер Qp не обладают свойством, выраженным P», т. е. номер Qp этим свойством обладает, тогда он лежит в T, и значит Qp истинно – снова противоречие! Значит, T не выразимо никакой из формул P и невыразимо вообще. Итак, вот содержательное разрешение старинного «парадокса лжеца»: истинность высказываний в языке средствами этого языка невыразима.

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

Фиксируем некоторый формальный язык математики L, семантику и средства дедукции в нем. Обозначим снова D множество номеров выводимых формул в некоторой фиксированной нумерации Гёделя. Построим явно формулу P, выражающую D. Для доказательства теоремы, что истинность T не выражается формулой P, мы пользовались следующей схемой рассуждений:

а) предположим, что истинность T выразима формулой P
б) тогда есть формула Qp, говорящая «я не истинна»
Не имея свободных переменных, она должна быть истинной или ложной
в) она не может быть ложной (по своей семантике)
г) она не может быть истинной (по своей семантике)
д) следовательно, истинность не выразима формулой P

Это рассуждение Тарского: пункты в) и г) в нем эксплуатируют в математическом контексте «парадокс лжеца», а пункт д) его объясняет. Но здесь никак не использовалось специфическое свойство P выражать D; теорема Тарского применима ко всем P. Гёдель рассуждал чуть-чуть иначе, и это маленькое отличие доставляет результат, замечательный для теории познания.

Доказательство Гёделя в параллельном изложении выглядит так:

а) выводимость D выразима формулой P
б) есть формула Qp , говорящая «я не выводима»
Не имея свободных переменных, она должна быть либо истинной, либо ложной
в) она не может быть ложной
(по своей семантике: иначе она должна была быть выводимой и, следовательно, истинной)
г) значит, она истинна
д) следовательно, она не выводима (по своей семантике)

Таким образом, Гёдель явно указывает формулу Qp , которая истинна, но не выводима с помощью данных дедуктивных средств! Иными словами, его рассуждение не только демонстрирует неполноту этого набора дедуктивных средств, но также дает эффективный способ пополнить этот набор новой аксиомой, истинность которой мы установили метаязыковыми разговорами. Расширив так множество D, мы получим большее множество D′, все еще не совпадающие с T; к нему можно снова применить конструкцию Гёделя и т.д. Таким образом, мы получаем рецепт для проведения целой серии творческих актов – пополнения арифметики новыми аксиомами, истинность которых мы не доказываем, но угадываем (формализация этого свойства T привела к математическому понятию «творческого множества»). Ясно, что как бы мы ни постарались финитно описать рецепт для бесконечного увеличения D таким способом, все T все равно окажется неисчерпанным – в силу той же теоремы о неполноте. Однако можно постараться исчерпать T формулами гёделевского типа, отказавшись от надежды описать этот набор формул финитно.

С.Феферман заметил, что есть много других способов добавлять к уже имеющимся аксиомам невыводимые, но истинные формулы. Истинность их устанавливается в метаязыке, как следствие нашей веры в истинность предыдущих аксиом (принятие которых, в свою очередь, было актом веры). Точнее, пусть P(x) – любая формула с одной свободной переменной. С.Феферман показывает, как написать формулу Ap без свободных переменных, смысл которой в метаязыке может быть выражен так: если для всех чисел n формулы P(n) выводимы из предыдущей системы аксиом, то ∀x P(x). После этого оказывается, что добавление формул Ap в бесконечном количестве и всех выводов из них исчерпывает T. Иными словами, начнем с принятия элементарных арифметических тождеств и аксиом индукции. Тогда для постижения полной истины в арифметике нам остается еще совершить трансфинитную последовательность актов веры в то, что предшествующие акты веры не были заблуждением.