У интуиции есть своя логика. Гёдель. Теоремы о неполноте. - Коллектив авторов (серии книг читать бесплатно .TXT) 📗
Однако если 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 году.
В то время как Гёдель наслаждался плодами растущего академического престижа, политическая ситуация в Вене становилась всё более сложной. После того как Адольф Гитлер пришел к власти, он объявил о своем намерении сделать Австрию частью Германии. С этой целью он начал политическое и военное давление на соседнюю страну. В 1931 году он потребовал, чтобы нацистская партия, которая в Австрии была запрещена, получила признание и вошла в состав правительства. Однако на выборах в Австрии в апреле 1932 года нацисты не одержали ожидаемой победы, так что перешли в оппозицию и прибегли к террористическим методам. Произошла серия терактов, убийств высокопоставленных лиц и попыток государственного переворота, которые к 1937 году привели Австрию к угрозе гражданской войны.
