У интуиции есть своя логика. Гёдель. Теоремы о неполноте. - Gustavo Pineiro

Тогда высказывание G формулируется как

"d(909) не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел".

Также предположим, что d(909) — это число 43. Следовательно, G примет вид

"43 не является простым числом, которое может быть записано как сумма или разность трех последовательных простых чисел".

Как уже было указано раньше, G имеет два уровня прочтения. На элементарном уровне это выражение арифметического свойства числа 43. Только когда мы смотрим на него через призму кодификации Гёделя, оно превращается в самореферентное и может читаться как говорящее о самом себе, что оно недоказуемо. Во второй главе мы увидим, что это замечание о различных уровнях прочтения позволяет преодолеть видимый парадокс, который возникает из анализа второй теоремы Гёделя.

В связи с первой теоремой о неполноте обычно возникает вопрос: если G — недоказуемая истина, как мы можем быть уверены в ее истинности?

Ответ заключается в том, что "доказуемый" — относительное понятие. Если задано множество аксиом Л, существует истинное высказывание 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 году сделала его международной знаменитостью в мире математики. Его имя зазвучало на всех встречах и конгрессах, а его доказательство стало (и остается до сих пор) классикой математического рассуждения. Однако Гёдель не смог сразу же насладиться славой, поскольку по завершении этой работы пережил сильный нервный срыв и вынужден был отказаться от публичной деятельности на несколько месяцев. Почти наверняка это было результатом стресса, вызванного представлением его теоремы.

На самом деле в статье 1931 года Гёдель представил две теоремы. Одна из них — уже упомянутая первая теорема о неполноте, также известная как теорема Гёделя. Именно ее мы доказали в предыдущей главе и вернемся к ней еще. В теореме говорится, что если выбрать в качестве арифметических аксиом любое множество истинных высказываний и принимать только доказательства, проверяемые алгоритмически, то всегда найдется истинное высказывание, недоказуемое на основе этих аксиом.

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

Преодолев нервный кризис, Гёдель в 1933 году начал работу в Венском университете в качестве приват-доцента. В то время в университетах Центральной Европы с должности приват-доцента обычно начинали карьеру преподавателя. Кроме того, как мы уже сказали, Гёдель превратился в международную знаменитость и в том же году был приглашен в США прочитать лекцию на ежегодном собрании Американского математического общества.

Во время этой первой поездки в США Гёдель познакомился с Альбертом Эйнштейном, который эмигрировал туда в 1933 году. Между ними сразу зародилась теплая дружба, которая длилась до самой смерти Эйнштейна в 1955 году.

В последующие два года, 1934 и 1935, Гёдель снова ездил в США, уже по приглашению Института перспективных исследований в Принстоне. В этом учреждении он прочитал несколько курсов и лекций, не только по своим теоремам о неполноте, но и по темам, затронутым в последующих исследованиях. Среди них, например, такая проблема: существует ли алгоритм, который при заданном множестве аксиом и высказывании Р позволит определить, доказуемо ли Р на основе этих аксиом? Гёдель получил несколько частичных решений, а полностью проблема была решена в 1936 году американским логиком Алонзо Чёрчем, который доказал, что алгоритма с такими

характеристиками не существует. Эта проблема, как и другие, поставленные самим Гёделем или другими логиками, вдохновленными его исследованиями, положила начало теории вычислимости, то есть изучению того, при каких условиях математическая проблема решаема алгоритмически.

Институт перспективных исследований в Принстоне (Нью-Джерси, США), основанный в 1930 году, имел целью собрать международную научно-исследовательскую элиту. И действительно, в нем трудились такие прославленные ученые, как Курт Гёдель, Альберт Эйнштейн, Джулиус Роберт Оппенгеймер (американский физик-теоретик, научный руководитель Манхэттенского проекта), Джон фон Нейман, Оскар Моргенштерн (последние двое — создатели теории игр) и Герман Вейль (выдающийся немецкий физик и математик).

Во время поездок в США Гёдель продемонстрировал свои методы, идеи и поставленные им проблемы, и это дало импульс развитию американской школы математической логики, где блистали Уиллард ван Орман Куайн, Стивен Коул Клини и уже упомянутый Алонзо Чёрч. Также работы Гёделя дали толчок развитию математической логики в целом; по сравнению с другими ученый публиковал очень мало научных работ, но каждая из них открывала новую отрасль в логике и вводила методы и идеи, актуальные до сих пор.

Алонзо Чёрч был одним из главных представителей американской школы математической логики, которая образовалась практически сразу после прочтения Гёделем курсов и лекций в США в 1930-х годах. Чёрч родился в Вашингтоне 14 июня 1903 года и изучал математику в Принстонском университете, где защитил докторскую диссертацию в 1927 году. Его научным руководителем был Освальд Веблен (который помогал в организации Института перспективных исследований в Принстоне и пригласил Гёделя прочитать там свои первые лекции). Чёрч внес вклад в логику первого порядка, теорию вычислимости (которая исследует, какие математические проблемы могут быть решены алгоритмически, а какие нет) и теоретическую информатику. Он также создал лямбда-исчисление, которое до сих пор является важным инструментом в изучении теории алгоритмов. Ученый скончался в США в 1995 году.