У интуиции есть своя логика. Гёдель. Теоремы о неполноте.
Шрифт:
Мы уже сказали, что "быть кодом доказуемого высказывания" — это свойство, которое можно выразить в терминах сумм, произведений и логических операций. Очевидно, что то же самое происходит и с его отрицанием. Следовательно, мы можем записать пропозициональную функцию:
"x: не является кодом доказуемого высказывания", что, как говорится в методе самореференции, превращается в: "d(x) не является кодом доказуемого высказывания". Если его код — число т, то:
G: "d(m) не является кодом доказуемого высказывания"
имеет в качестве кода число d(m) и может рассматриваться как самореферентное высказывание, говорящее о своем коде следующее: "мой собственный код не соответствует доказуемому высказыванию". Другими словами,
"G недоказуемо".
Как мы видели в начале доказательства, это высказывание является истинным и одновременно недоказуемым (вспомним, что "доказуемый" всегда означает "доказуемый на основе предложенных аксиом"). Мы доказали, что существует высказывание G, являющееся истинным и недоказуемым, и описали шаги, необходимые для того, чтобы записать его. Этим завершается доказательство первой теоремы Гёделя о неполноте.
Один из самых древних известных парадоксов — это так называемый парадокс лжеца. Он возникает, если поставить вопрос, является ли утверждение "это предложение ложное" истинным или ложным. Если утверждение истинно, то, судя по его смыслу, оно оказывается ложным. Но если оно ложно, то оно получается истинным. Так мы сталкиваемся с бессмыслицей, порочным кругом, который снова и снова приводит нас от истинности к ложности и от ложности к истинности. В своей статье 1931 года Гёдель объяснил, что его доказательство найдено под влиянием парадокса лжеца, только вместо того чтобы написать высказывание, говорящее о собственной ложности, Гёдель написал высказывание, говорящее о собственной недоказуемости. Высказывание "это предложение ложно" — парадоксальная бессмыслица. Но высказывание "это предложение недоказуемо на основе предложенных аксиом" — недоказуемая истина.
Важное пояснение: рассуждение, которое мы провели, на самом деле не является формальным доказательством первой теоремы Гёделя о неполноте. Это только введение, полезное для понимания основных идей, но не объясняющее специфических деталей того, как эти идеи применяются на практике. Если читателя заинтересовали детали, он может углубиться в технические работы по математической логике.
Как выглядело бы высказывание G в нашем гипотетическом примере? Вспомним, что в этом примере свойство, характеризующее коды доказуемых высказываний, — это "быть простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел". Возьмем пропозициональную функцию "х не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел" и трансформируем ее в "d(x) не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел". Предположим, что последнему выражению соответствует число 909.
Тогда высказывание G формулируется как
"d(909) не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел".
Также предположим, что d(909) — это число 43. Следовательно, G примет вид
"43 не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел".
Как уже было указано раньше, G имеет два уровня прочтения. На элементарном уровне это выражение арифметического свойства числа 43. Только когда мы смотрим на него через призму кодификации Гёделя, оно превращается в самореферентное и может читаться как говорящее о самом себе, что оно недоказуемо. Во второй главе мы увидим, что это замечание о различных уровнях прочтения позволяет преодолеть видимый парадокс, который возникает из анализа второй теоремы Гёделя.
В
Ответ заключается в том, что "доказуемый" — относительное понятие. Если задано множество аксиом Л, существует истинное высказывание G, которое недоказуемо на основе этих аксиом (с использованием методов доказательства, принятых в программе Гильберта). Но ничто не мешает G быть доказуемым на основе других аксиом или с помощью других методов.
Хотя это пока точно не известно, последняя теорема Ферма может быть примером истины, недоказуемой на основе аксиом Пеано. В этой теореме, впервые предложенной Пьером
Ферма в 1637 году, утверждается, что если n > 2, то хn + уn + zn не имеет решений среди натуральных чисел. После многочисленных попыток теорема наконец была доказана Эндрю Уайлсом в 1996 году.
Однако доказательство Уайлса во многом выходит за пределы обычных методов или аксиом арифметики. Последняя теорема Ферма истинна (Уайлс доказал это), но доказуема ли она, например, на основе аксиом Пеано с помощью методов программы Гильберта? Сегодня ответ на этот вопрос неизвестен, но наиболее разумное предположение заключается в том, что последняя теорема Ферма недоказуема на основе аксиом Пеано посредством рассуждений, проверяемых алгоритмически.
Однако если G недоказуемо на основе множества A аксиом, вполне возможно добавить во множество А новую аксиому, так что G станет доказуемым на основе этой расширенной системы, которую обозначим А'. Конечно, для А также справедлива теорема Гёделя, и, следовательно, будет существовать арифметическое утверждение G', которое является недоказуемым на ее основе.
Мы можем добавить в А новую аксиому, которая позволит доказать G\ и так получим множество A", где G будет доказуемым. Но для А' существует новое недоказуемое высказывание G". Мы можем добавить новую аксиому в А", но тогда существует недоказуемое G""... И так до бесконечности...
A —> G недоказуемо.
А' = А + другая аксиома —> G доказуемо, но G' — нет.
А" = А' + другая аксиома —> G и G" доказуемы, но G" — нет.
А"' + другая аксиома —> G, G и G" доказуемы, но G'" — нет.
Добавляя аксиомы по одной, никогда не удастся достигнуть полноты (то есть возможности доказать все истины). Но можно ли добиться этого другими средствами? Обратимся к этому вопросу в следующей главе.
ГЛАВА 3
Вторая теорема Гёделя
Гильберт потратил десять лет на разработку своей программы, и этот период был полон борьбы. После всех усилий, когда первая теорема Гёделя о неполноте показала, что программа неосуществима, сдался ли Гильберт? Не искал ли он неточности в доказательстве Гёделя? Неужели даже не протестовал? В этой главе мы проанализируем, как Гёделю удалось представить доказательство своей теоремы о неполноте таким образом, чтобы никто — даже Гильберт — не мог усомниться в ее справедливости.
Публикация первой теоремы Гёделя о неполноте в 1931 году сделала его международной знаменитостью в мире математики. Его имя зазвучало на всех встречах и конгрессах, а его доказательство стало (и остается до сих пор) классикой математического рассуждения. Однако Гёдель не смог сразу же насладиться славой, поскольку по завершении этой работы пережил сильный нервный срыв и вынужден был отказаться от публичной деятельности на несколько месяцев. Почти наверняка это было результатом стресса, вызванного представлением его теоремы.