У интуиции есть своя логика. Гёдель. Теоремы о неполноте.
Шрифт:
"1 не удовлетворяет свойству Р" доказуемо,
"2 не удовлетворяет свойству Р" доказуемо,
"3 не удовлетворяет свойству Р" доказуемо
...и так далее.
Верно ли, что "существует некоторое х, которое удовлетворяет свойству Р" недоказуемо? Поскольку в некоторых мирах это истинно, мы не можем точно утверждать, что это никогда не будет доказуемо. В доказательстве того, что не-G недоказуемо, имеется логический пробел, поскольку мы не можем утверждать, что это высказывание
К счастью, в 1936 году американский логик Джон Б. Россер в статье объемом всего две страницы изменил рассуждение Гёделя так, чтобы оно было справедливо и при гипотезе непротиворечивости. Благодаря Россеру в изложении теоремы Гёделя можно опустить упоминание омега-непротиворечивости, и она может быть записана в том виде, в каком мы привели ее в тексте. Изменение, внесенное Россером в рассуждение Гёделя, состояло в том, чтобы заменить самореферетное высказывание "это высказывание недоказуемо" другим: "если это высказывание доказуемо, то также доказуемо и его отрицание".
Это означает, что не существует доказательства G; следовательно, ни одно число не является кодом доказательства G: число 1 — не код доказательства G, так же как 2,3 и так далее.
Получается, что высказывания
"1 — не код доказательства высказывания с кодом m",
"2 — не код доказательства высказывания с кодом m", "k — не под доказательства высказывания с кодом т" и так далее являются финитными истинными высказываниями. Раз они финитные и истинные, они доказуемы. Следовательно,
"существует у, являющееся кодом доказательства высказывания с кодом m" недоказуемо. Но это высказывание — не-G, следовательно, не-G не будет доказуемым; однако это противоречит предположению того, что не-G доказуемо. От противного получили, что не-G в итоге недоказуемо (см. схему).
Итак, синтаксически доказано, что как G, так и не-G, ни одно из двух, недоказуемо. Таким образом, доказательство первой теоремы о неполноте может быть полностью переведено в синтаксические аргументы и понятия, как этого требует программа Гильберта. Этот способ представления доказательства, основанный исключительно на синтаксических аргументах, проверяемых механически, спас от любых споров.
В программе Гильберта требовалось, как мы уже сказали, найти непротиворечивое множество аксиом арифметики таким образом, чтобы каждое высказывание Р (либо его отрицание) было доказуемым. Но также требовалось, чтобы непротиворечивость этих аксиом проверялась алгоритмически, — это придавало уверенности, что аксиомы не приведут к парадоксу. В своей статье 1931 года Гёдель доказал вторую теорему, так называемую вторую теорему о неполноте. В ней доказывается, что эта цель также неосуществима.
Эта теорема часто формулируется следующим образом:
ни одно непротиворечивое множество аксиом не содержит арифметики, достаточной для того, чтобы доказать свою собственную
В выражении "содержит арифметики, достаточной..." речь идет об уже упомянутом условии того, что множество аксиом, о котором мы говорим, способно доказать все финитные истинные высказывания. Но как же может множество доказать или не доказать собственную непротиворечивость? Для начала арифметические аксиомы позволяют доказать только те высказывания, в которых говорится о числах, но не такие, в которых говорится о непротиворечивости множества аксиом. Мы уже сталкивались с подобной проблемой в предыдущей главе, когда хотели записать арифметическое высказывание, которое говорило бы о себе самом. Как добиться того, чтобы арифметическое высказывание, в котором говорится о числах, начало говорить о самом себе? Способом достижения этого была идентификация высказываний с помощью их кодов, так чтобы разговор о высказывании был равносилен разговору о его коде.
Для доказательства непротиворечивости аксиом арифметики необходим прямой метод.
Давид Гильберт на инаугурационном докладе на Втором Международном математическом конгрессе в Париже в 1900 году
В нашем случае, когда мы хотим записать арифметическое высказывание, в котором говорилось бы о непротиворечивости множества аксиом, нумерация Гёделя снова приходит нам на помощь.
Как уже говорилось, если множество аксиом противоречиво, то любое высказывание доказуемо на его основе. Наоборот, если множество непротиворечиво, всегда найдется высказывание, являющееся недоказуемым (поскольку для любого Р либо оно, либо его отрицание, по крайней мере одно из двух, недоказуемо). Следовательно, непротиворечивость множества аксиом равносильна тому, что есть по крайней мере одно высказывание, которое не является доказуемым на его основе. То, что система непротиворечива, равносильно следующему:
"существует некоторое высказывание, не являющееся доказуемым".
Вновь возьмем гипотетический пример из предыдущей главы, в котором мы предположили, что всем высказываниям соответствуют коды, являющиеся простыми числами, а доказуемым высказываниям, в частности, соответствуют простые числа, являющиеся суммой или разностью трех последовательных простых чисел. В данном контексте в предыдущем высказывании утверждалось бы, что "существует некоторое простое число, не являющееся суммой или разностью трех последовательных простых чисел", что на другом уровне прочтения означало бы: "существует код высказывания, не являющийся кодом доказуемого высказывания", то есть "существует недоказуемое высказывание" или "множество аксиом непротиворечиво".
У нас есть два уровня прочтения для "существует некоторое простое число, не являющееся суммой или разностью трех последовательных простых чисел": арифметический, где указывается только арифметическое свойство; и более высокий уровень прочтения, зависящий от нумерации Гёделя, на котором заявляется непротиворечивость множества аксиом. Теперь сформулируем вторую теорему о неполноте:
если система арифметических аксиом непротиворечива и может доказать все финитные истинные высказывания, то арифметическое высказывание, в котором утверждается непротиворечивость множества аксиом, недоказуемо на основе этих же аксиом.
Прокомментируем идею доказательства этой теоремы, как это сделал Гёдель в статье 1931 года. В своей первой теореме о неполноте Гёдель доказывает, что:
если множество аксиом непротиворечиво, то G недоказуемо.
Заметим, что высказывание, в котором говорится: "G недоказуемо", — это само G. То есть G = "G недоказуемо". Следовательно, в предыдущее утверждение, в котором говорится: "G недоказуемо", можно просто поставить G. Или, что то же самое, в своей первой теореме Гёдель доказал: