Хотя это пока точно не известно, последняя теорема Ферма может быть примером истины, недоказуемой на основе аксиом Пеано. В этой теореме, впервые предложенной Пьером
Ферма в 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 году сделала его международной знаменитостью в мире математики. Его имя зазвучало на всех встречах и конгрессах, а его доказательство стало (и остается до сих пор) классикой математического рассуждения. Однако Гёдель не смог сразу же насладиться славой, поскольку по завершении этой работы пережил сильный нервный срыв и вынужден был отказаться от публичной деятельности на несколько месяцев. Почти наверняка это было результатом стресса, вызванного представлением его теоремы.
На самом деле в статье 1931 года Гёдель представил две теоремы. Одна из них — уже упомянутая первая теорема о неполноте, также известная как теорема Гёделя. Именно ее мы доказали в предыдущей главе и вернемся к ней еще. В теореме говорится, что если выбрать в качестве арифметических аксиом любое множество истинных высказываний и принимать только доказательства, проверяемые алгоритмически, то всегда найдется истинное высказывание, недоказуемое на основе этих аксиом.
Другая теорема, которую Гёдель представил в этой статье 1931 года, сегодня известна как вторая теорема о неполноте, или вторая теорема Гёделя. В ней говорится о невозможности алгоритмически проверить истинность множества арифметических аксиом. Мы обсудим эту теорему чуть позже. Следует сказать, что в статье не содержалось ее детального доказательства. Гёдель ограничился лишь тем, что в общих чертах изложил идею и отметил, что собирается написать вторую часть статьи с полным доказательством. Однако болезнь помешала ему сделать это в ближайшие месяцы, а после выздоровления выяснилось, что доказательства обеих теорем (даже второй, о которой ученый только намекнул) получили всеобщее признание. В этой ситуации Гёдель не счел нужным публиковать дополнительные пояснения, поэтому вторая часть статьи так и не была написана. (Оригинальное название статьи на немецком языке заканчивается римской цифрой I: это указывает на то, что речь идет только о первой части. В переводах на испанский, английский и другие языки ее обычно опускают.)