Шрифт:
« Т n ( n ) останавливается»
— это утверждение — запишем его как S ( n ), — которое мы можем сформулировать в рамках нашей системы для любого n . Утверждение S ( n ) будет справедливым для одних значений n , и ложным — для остальных. Множество всех S ( n ), образованное перебором натуральных чисел 0,1, 2, 3…., будет представлено некоторым подмножеством N — скажем, S . Теперь учтем фундаментальный результат Тьюринга (глава 2, «Неразрешимость проблемы Гильберта»), который говорит о том, что не существует алгоритма, способного установить факт « Т n ( n ) не останавливается» как раз в тех случаях, когда она действительно не останавливается. Это означает, что множество, состоящее из отрицаний S ( n ), не является рекурсивно нумеруемым.
Мы видим, что часть S , принадлежащая Р , состоит только из истинных S ( n ). Почему это так? Понятно, что если любое конкретное S ( n ) доказуемо, то оно должно быть верным (ведь наша формальная система была выбрана так, чтобы иметь «смысл»!), и поэтому часть S , лежащая в Р , должна состоять исключительно из справедливыхутверждений S ( n ). Более того, ни одно верное утверждение S ( n ) не должно лежать вне Р , ибо, если Т n ( n ) останавливается, то мы можем отыскать доказательство этому в рамках нашей системы [82] .
82
''Доказательство могло бы, в действительности, состоять из последовательности шагов, которые отражали бы действие машины, продолжающееся до ее остановки. Доказательство завершалось бы, как только машина остановится.
Теперь предположим, что дополнение Р рекурсивно нумеруемо. Тогда у нас был бы алгоритм для построения элементов этого дополнительного множества. И мы смогли бы запустить его и пометить каждое утверждение S ( n ), которое попадает в поле его действия. Это все будут ложные утверждения S ( n ), так что наша процедура, по сути, обеспечит нам рекурсивную нумерацию множества таких утверждений. Но выше мы установили, что это множество не нумеруемотаким образом. Это противоречие показывает, что дополнение Р все-таки не может быть рекурсивно пронумеровано; а Р , следовательно, не является рекурсивным, что и требовалось доказать.
Эти свойства с очевидностью демонстрируют, что наша формальная система не может быть полной: то есть всегда будут существовать утверждения, чью справедливость (или ложность) невозможно доказать в рамках системы. Ведь если предположить, что такие «неразрешимые» утверждения не существуют, то дополнение множества Р с необходимостью было бы множеством опровергаемыхутверждений (все, что недоказуемо, обязано быть опровергаемо). Но мы уже знаем, что опровергаемые утверждения составляют рекурсивно нумеруемое множество, что делает Р рекурсивным. Однако, Р не рекурсивно — противоречие, которое доказывает требуемую неполноту. Это основное утверждение теоремы Геделя.
А как насчет подмножества T множества N , которое состоит из истинныхутверждений нашей формальной системы? Рекурсивно ли T ? Или оно только рекурсивно нумеруемо? А его дополнение? Оказывается, что ответ на все эти вопросы — отрицательный. Один из способов установить это — воспользоваться сделанным ранее выводом о невозможности алгоритмически сгенерировать ложные утверждения вида « Т n ( n ) останавливается». Как следствие, ложные утверждения в целомне могут быть получены с помощью алгоритма, поскольку такой алгоритм, в частности, пронумеровал бы все вышеупомянутые ложные « Т n ( n ) останавливается»-утверждения. Аналогично, и множество всех истинныхутверждений не может быть построено при помощи алгоритма (так как любой подобный алгоритм легко модифицируется для нахождения ложных утверждений путем отрицания каждого из генерируемых им утверждений).
Поскольку, тем самым, истинные утверждения не являются (равно как и ложные) рекурсивно нумеруемыми, то они образуют гораздо более глубокий и сложноорганизованный массив, чем утверждения, имеющие доказательство внутри системы. И это иллюстрирует еще один аспект теоремы Геделя: что понятие математической истинытолько частично досягаемо в рамках любой формальной системы.
Существуют некоторые простые классы истинных арифметических утверждений, которые все же образуют рекурсивно нумеруемые множества. Например, как это нетрудно видеть, истинные утверждения вида
E к.с. , x …, z [ f ( , x ,…, z ) = 0 ],
где f — некоторая функция, построенная из обычных арифметических операций сложения, вычитания, умножения и возведения в степень, составляют рекурсивно нумеруемые множества [83] (которые я обозначу через А ). Пример утверждения такого рода — хотя мы не знаем, верно ли оно — это отрицание последней теоремы Ферма [84] ., для которой мы можем взять за f функцию
83
Мы нумеруем множества { v , , x …., z ], где v представляет функцию f в согласии с некоторой лексикографической схемой. Мы (рекурсивно) проверяем на каждом этапе справедливость равенства f ( , x …, z ) = 0 и оставляем утверждение E к.с. , х …., z [( , х …., z ) = 0 ] только в том случае, если это равенство выполняется.
84
Последняя теорема Ферма доказана английским математиком Эндрю Уайлсом (Andrew J. Wiles). Доказательство опубликовано в 1995 году. — Прим. ред.
f ( , х , у , z ) = ( х + 1 ) + 3 + ( у + 1 ) + 3 – ( z + 1 ) + 3 .