22. Неполны и неразрешимы Курт Гёдель
Курт Фридрих Гёдель
Родился: Брюнн, Австро-Венгрия, 28 апреля 1906 г. Умер: Принстон (штат Нью-Джерси), США, 14 января 1978 г.
Стереотипный образ математика – помимо того что все они пожилые мужчины – обязательно предусматривает их странность. Определенно, это люди не от мира сего. Как минимум они эксцентричны. А иногда и просто безумны.
Мы уже видели, что большинство математиков не укладывается в этот образ; правда, в основном это все же мужчины, но ситуация резко изменилась за последние несколько десятилетий. Согласен, к завершению карьеры математики, как правило, действительно становятся пожилыми, но кто из нас не стареет? Единственный способ избежать этого – умереть молодым, как Галуа. Известность и ответственность, как правило, появляются с возрастом, так что нет ничего удивительного в том, что среди лидеров этой науки преобладают именно пожилые.
Математик, с головой погруженный в исследования, может легко показаться человеком не от мира сего, но, как настойчиво уверяет один мой коллега-биолог, математики вовсе не рассеянны: они просто сосредоточены на чем-то. Если человек хочет решить сложную математическую задачу, он должен сосредоточиться. У некоторых математиков (математика ни в коем случае не единственная профессия, для которой это характерно) отвлеченность от сиюминутного мира переходит в эксцентричность. Возможно, самым очевидным примером чудака-математика может служить Пал Эрдёш, который никогда не занимал никакой академической должности и не имел собственного дома. Он путешествовал от одного коллеги к другому, проводя где ночь на диване в гостиной, а где и несколько месяцев в свободной комнате. При этом он написал невероятное количество (1500) исследовательских статей и сотрудничал с поразительным числом (500) разных математиков.
Что до безумия: некоторые математики на определенном этапе жизни страдают душевными болезнями. Кантор страдал сильными приступами депрессии. Джон Нэш, прототип героя книги и фильма «Игры разума», получил в 1994 г. Нобелевскую премию по экономике (или, точнее, премию памяти Альфреда Нобеля, которую в большинстве случаев приравнивают к любой из оригинальных Нобелевских премий). Тем не менее он много лет страдал заболеванием, которое диагностировали как параноидную шизофрению, и проходил лечение электрошоком. Но усилием воли он сумел излечиться – он признавал в себе психотические проявления и отказывался им поддаваться.
Курт Гёдель, безусловно, был эксцентричен, а временами даже выходил за рамки простой эксцентричности. Избранная им область математической логики на тот момент была не особенно популярна среди математиков, так что в этом отношении он был, пожалуй, еще более не от мира сего, чем большинство его коллег. Зато, словно в компенсацию, его открытия в этой области произвели настоящую революцию в наших представлениях об основах логики и математики и об их взаимодействии. Он был блестяще оригинален и потрясающе глубок.
Интерес к логике зародился у Гёделя в 1933 г., когда в Германии пришел к власти Адольф Гитлер. Этот интерес получил дополнительный толчок на семинарах, которые проводил Мориц Шлик – философ, основавший логический позитивизм и Венский кружок. В 1936 г. Шлика убил один из его бывших студентов, Иоганн Нельбёк. К тому моменту многие члены Венского кружка уже бежали из Германии, опасаясь антисемитского преследования, однако Шлик, живший в Австрии, продолжал работать в Венском университете. Он шел читать лекцию и поднимался по лестнице, когда Нельбёк выстрелил в него из пистолета. Нельбёк сознался в убийстве, но использовал публичные судебные слушания как платформу, с которой мог провозглашать свои политические убеждения. Он утверждал, что недостаток сдерживающих моральных факторов возник у него под влиянием философской позиции Шлика, которая была враждебна метафизике. Правда, многие подозревали, что подлинной причиной убийства была страстная влюбленность Нельбёка в студентку Сильвию Боровицку. Эта безответная страсть заставила беднягу решить, что Шлик является его соперником в борьбе за расположение девушки. Нельбёка приговорили к 10 годам тюрьмы, но его дело стало еще одним поленом на костре растущей антисемитской истерии в Вене, хотя Шлик, вообще говоря, не был евреем. Однако в псевдоправде нет ничего нового. Хуже того, после аннексии Австрии Германией Нельбёк был освобожден после всего лишь двух лет заключения.
Убийство наставника произвело на Гёделя ужасное впечатление. У него развились признаки паранойи – хотя здесь, пожалуй, уместна была бы старая шутка: «Если у меня паранойя, это не значит, что за мной не охотятся». Гёдель тоже не был евреем, но среди его друзей евреев было много. Жизнь под властью нацистов делала паранойю крайним проявлением душевного здоровья. Однако у Гёделя развилась серьезная фобия: он боялся, что его хотят отравить, так что ему пришлось несколько месяцев лечиться. Этот страх вернулся и преследовал Гёделя в последние годы его жизни, когда у него вновь появились симптомы душевной болезни и паранойи. Он отказывался есть любую пищу, кроме той, что приготовила его жена. В 1977 г. она перенесла два удара и вынуждена была надолго лечь в больницу, так что не могла для него готовить. Он перестал есть и довел себя до голодной смерти. Страшный и бессмысленный конец для одного из величайших мыслителей XX столетия.
* * *
Отец Гёделя Рудольф был управляющим текстильной фабрикой в австро-венгерском Брюнне (ныне это город Брно в Чешской Республике). С раннего детства и до достаточно зрелого возраста Курт был очень близок с матерью Марианной (урожденной Хандшух). Рудольф был протестантом, Марианна – католичкой; Курт был воспитан в протестантской вере. Он считал себя глубоко верующим человеком, но верил в личного Бога, вне рамок традиционной религии. Он писал, что «религии по большей части дурны, но религия – нет». Он регулярно читал Библию, но не бывал в церкви. Позже в его неопубликованных бумагах была обнаружена попытка математического доказательства Бытия Божия при помощи модальной логики. В детстве у него было семейное прозвище г-н Почему (Herr Warum), о причинах появления которого вы можете догадаться сами. В семь или восемь лет он перенес приступ ревматической лихорадки и, хотя полностью оправился, всю жизнь был уверен, что болезнь разрушающе подействовала на его сердце. Здоровье часто подводило его и оставалось достаточно хрупким до конца его жизни.
С 1916 г. Гёдель учился в Немецкой государственной гимназии, где получал высокие оценки по всем предметам, особенно по математике, языкам и религии. После распада Австро-Венгерской империи в конце Первой мировой войны он автоматически стал гражданином Чехословакии. В 1923 г. Гёдель поступил в Венский университет и поначалу не мог решить, изучать ему математику или физику. Книга Бертрана Рассела «Введение в математическую философию» побудила его остановиться на математике, а основным научным интересом стала математическая логика. Ключевой момент в его карьере наступил в 1928 г., когда он попал в Болонье на лекцию Давида Гильберта на 1-м Международном конгрессе математиков, проводившемся после окончания Первой мировой войны. Гильберт тогда рассказал о своих взглядах на аксиоматические системы, особенно на их непротиворечивость и полноту. В 1928 г. Гёдель прочел «Принципы математической логики» Гильберта и Вильгельма Аккермана, где излагалась техническая основа Гильбертовой программы разрешения этих вопросов. В 1929 г. он выбрал тему для своей докторской диссертации, которую готовил под руководством Ханса Хана. Он доказал то, что мы сегодня называем теоремой Гёделя о полноте: что исчисление предикатов (глава 14) является полным. То есть любая верная теорема может быть доказана, любая неверная теорема – опровергнута, и никаких других вариантов не существует. Однако исчисление предикатов – очень ограниченная область и не годится в качестве фундамента для всей математики. Программа Гильберта была сформулирована в рамках гораздо более богатой аксиоматической системы.
В том же году Гёдель стал гражданином Австрии. (В 1938 г., когда Германия аннексировала Австрию, его гражданство автоматически сменилось на германское.) В 1930 г. он получил степень доктора. В 1931 г. – разрушил программу Гильберта, опубликовав статью «О формально неразрешимых утверждениях Principia Mathematica и аналогичных систем», где доказывалось, что ни одна система аксиом, достаточно богатая, чтобы формализовать математику, не может быть логически полной, а непротиворечивость такой системы доказать невозможно. (О Principia Mathematica я расскажу вам чуть позже.) В 1932 г. он прошел хабилитацию, а в 1933 г. стал приват-доцентом Венского университета. Мучительные события, описанные выше, произошли именно в этот период его жизни. Чтобы отдохнуть от нацистской Австрии, он посетил Соединенные Штаты, где встретился и подружился с Эйнштейном.
В 1938 г. Гёдель женился на Адель Нимбурски (урожденной Поркерт), с которой познакомился в ночном клубе Der Nachtfalter в Вене одиннадцатью годами ранее. Она была на шесть лет старше и уже успела побывать замужем, к тому же его родители были против, но он поступил по-своему. Когда в 1939 г. началась Вторая мировая война, Гёдель испугался, что его могут призвать в германскую армию. По идее, слабое здоровье должно было ему помочь, но прежде его уже принимали за еврея, так кто даст гарантию, что в следующий раз его не примут за здорового человека? Он ухитрился получить американскую визу и вместе с женой отправился в США через Россию и Японию. Они благополучно прибыли туда в 1940 г. В том же году Гёдель доказал, что гипотеза о континууме Кантора вполне согласуется с обычными теоретико-множественными аксиомами для математики. Он получил работу в Институте высших исследований в Принстоне – сначала в качестве ординарного исследователя, затем на постоянной должности, а после, с 1953 г., профессора. Хотя в 1946 г. он прекратил публиковаться, исследования не оставил.
В 1948 г. Гёдель получил американское гражданство. Судя по всему, он был уверен, что обнаружил в конституции США логическую нестыковку, и пытался объяснить свою находку судье, который очень разумно не клюнул на эту наживку. Близкая дружба с Эйнштейном побудила его поработать над теорией относительности. В частности, он нашел пространство-время, в котором имеется замкнутая времениподобная кривая – математический эвфемизм для машины времени. Если нечто движется по такой кривой в пространстве и времени, его будущее плавно переходит в его прошлое. Это как находиться в Лондоне в 1900 г., затем переместиться на 20 лет в будущее – и обнаружить, что ты вновь в Лондоне в 1900 г. Позже замкнутые времениподобные кривые стали горячей темой не столько потому, что могли потенциально привести к созданию машины времени, но и потому, что помогли пролить свет на ограничения общей теории относительности и намекнули на возможную необходимость в новых законах физики.
В последние годы жизни здоровье Гёделя, никогда не отличавшееся крепостью, ухудшилось. Его брат Рудольф сообщал, что он
…имел обо всем очень личное и очень категоричное мнение… К несчастью, он всю жизнь был уверен, что всегда прав не только в математике, но и в медицине, так что для врачей он был очень сложным пациентом. После сильного кровотечения язвы двенадцатиперстной кишки… он придерживался чрезвычайно строгой (слишком строгой?) диеты, из-за которой постепенно терял вес.
Что произошло далее, вам уже известно. В свидетельстве о смерти причиной смерти названо «недоедание и истощение, вызванное расстройством личности». Истощение возникает в результате недостатка пищи. Он весил тогда всего 30 кг.
* * *
С древнейших времен математика считалась ярким примером того, что просто верно – абсолютная истина, без всяких «если» или «но». Два плюс два будет четыре: берите, что дают, и не жалуйтесь. Единственным конкурентом математики в притязаниях на абсолютную истину была религия (конфессия и секта на выбор верующего, разумеется), но даже здесь у математики имелось тайное преимущество. Религии, как сказал Терри Пратчетт, истинны «на заданную величину истинности». Математика могла доказать свою истинность.
Когда философы, логики и математики, интересы которых влекли их в этом направлении, начали глубже задумываться о том, что подразумевает такой тип абсолютной истины, они поняли, что он до некоторой степени иллюзорен. Два плюс два равно четырем для натуральных чисел, но что, собственно, представляет собой число? Ну и заодно, что такое «плюс» и «равно»? Математики ответили на этот вопрос тем, что определили континуум действительных чисел, но Кронекер считал их уже «делом рук человеческих», считая, что только целые числа даны человеку Богом. Трудно понять, как произвольное создание человеческого разума может представлять абсолютную истину. В лучшем случае это результат договоренности людей.
Представление о том, что математика состоит из непреложных истин, было оставлено в пользу концепции, по которой они представляют собой выводы из явных допущений, сделанные по некоторой определенной системе логики. В этом случае честность требует последовать примеру Евклида и сформулировать эти допущения и логические правила в виде системы явных аксиом. Это метаматематика – применение математических принципов к внутренней логической структуре самой математики. Бертран Рассел и Альфред Норт Уайтхед в своей книге 1910–1913 гг. Principia Mathematica – название представляло собой вполне сознательную отсылку к Ньютону – первыми проложили этот путь, и после нескольких сотен страниц сумели-таки определить число «один». После этого темп подрос и более продвинутые математические концепции появлялись все быстрее и быстрее, пока, наконец, не стало очевидно, что все остальное можно получить аналогичным образом; после этого авторы сдались. От одной из технических особенностей – теории «типов», введенной для того, чтобы избежать некоторых парадоксов, – позже пришлось отказаться в пользу других структур аксиом для теории множеств, самыми популярными из которых являются системы Эрнста Цермело и Абрахама Френкеля.
Именно на этом фоне Гильберт попытался завершить логический круг, доказав, что подобная аксиоматическая система логически непротиворечива (никакое доказательство не приводит к противоречию) и полна (любое осмысленное утверждение можно либо доказать, либо опровергнуть). Первый момент принципиально важен, поскольку в системе, которая не является непротиворечивой, утверждение «два плюс два равно пяти» можно доказать. В самом деле, любое утверждение может быть доказано. Второй шаг отождествляет понятия «верный» и «можно доказать» и «ложный» и «нельзя доказать». Гильберт сосредоточился на аксиоматической системе для арифметики, поскольку в Principia Mathematica все в математике выводилось из нее. Продолжив мысль Кронекера, после того как Бог дал нам целые числа, в остальном человек может разобраться сам. В программе Гильберта была прописана серия шагов, которая, по его мнению, должна была привести к цели, и основывалась она на логической сложности задействованных утверждений; ему даже удалось разобраться в некоторых не слишком сложных случаях. Все это выглядело перспективно.
* * *
Я подозреваю, что Гёдель углядел в этом мероприятии что-то сомнительное с философской точки зрения. По существу, от аксиоматической системы математической логики требовалось продемонстрировать свою собственную непротиворечивость. «Непротиворечивы ли вы?» – «Разумеется, да!» Пауза. «Ну да, ну да… Почему я должен вам верить?» Как бы то ни было, скепсис, из какого бы источника он ни проистекал, заставил его доказать два потрясающих результата, названные его именем: теорему о неполноте и теорему о непротиворечивости.
Вторая из них опирается на первую. Имея в виду, что противоречивая логическая система способна доказать что угодно, можно сделать вывод, что она, вероятно, способна доказать и утверждение «эта система непротиворечива». (Разумеется, она может с тем же успехом доказать утверждение «эта система противоречива», но забудем об этом.) Итак, какую гарантию истинности может предложить подобное доказательство? Никакой. Именно это интуитивное понимание отражено в ответе «ну да, ну да…». У программы Гильберта может быть единственный способ избежать этой ловушки: возможно, утверждение «эта система непротиворечива» не имеет смысла в пределах формальной аксиоматической системы. Безусловно, это утверждение не слишком похоже на арифметику.
Ответом Гёделя было превратить его в арифметику. Любая формальная математическая система построена из символов, и доказательство (или предполагаемое доказательство) некоторого утверждения представляет собой всего лишь строку символов. Символам могут быть присвоены кодовые номера, и строке символов тоже может быть присвоен уникальный численный код. Предложенный Гёделем способ нумерации состоит в том, чтобы превратить строку кодовых чисел abcdef… в единственное число, определяемое перемножением степеней простых чисел:
2a3b5c7d11e13f…
Чтобы расшифровать это число и превратить его обратно в строку, нужно воспользоваться единственностью разложения на простые множители.
Существуют и другие способы зашифровать символьную строку превращением ее в число: данный способ математически элегантен и притом совершенно непрактичен. Но Гёделю достаточно было того, что он существует.
В виде чисел он предлагал кодировать не только утверждения, но и доказательства, которые представляют собой некоторую последовательность утверждений. Логические правила вывода каждого утверждения из предыдущих накладывают ограничения на то, какие из этих чисел могут соответствовать логически верному доказательству. Так что утверждение «P есть верное доказательство утверждения S» само может рассматриваться как утверждение в арифметике: «Если расшифровать P в последовательность чисел, то последним из них будет число, соответствующее S». Гёделева система нумерации позволяет нам перейти от метаматематического утверждения о существовании некоторого доказательства к арифметическому утверждению о соответствующих числах.
Гёдель хотел проделать этот фокус с фразой «это утверждение ложно». Он не мог сделать это напрямую, поскольку это не арифметическое утверждение. Но его можно сделать арифметическим при помощи Гёделевых чисел, и тогда оно по существу превращается в утверждение «эта теорема не имеет доказательства». Есть еще кое-какие технические фокусы, которые придают всему этому смысл, но описанное выше – самая суть. Предположим, что Гильберт прав и аксиоматическая система арифметики полна. Тогда утверждение «эта теорема не имеет доказательства» либо имеет доказательство, либо нет. В том и другом случае у нас проблемы. Если у него есть доказательство, получаем противоречие. Если доказательства нет, утверждение ложно (мы ведь считаем, что Гильберт прав, помните?), так что доказательство все-таки имеется – еще одно противоречие. Значит, утверждение наше противоречит само себе… а в арифметике имеется теорема, которую невозможно ни доказать, ни опровергнуть.
Гёдель быстро превратил этот результат в свою теорему о непротиворечивости: если некоторое аксиоматическое описание арифметики непротиворечиво, то доказать его непротиворечивость невозможно. Это тот самый момент «ну да, ну да…» во всей его формальной красе: если бы в один прекрасный момент кто-нибудь нашел вдруг доказательство того, что арифметика непротиворечива, то мы могли бы сразу же сделать вывод о том, что на самом деле это не так.
Некоторое время Гильберт и его последователи надеялись, что теоремы Гёделя всего лишь указывают на техническую неполноценность конкретной аксиоматической системы, введенной в Principia Mathematica. Может быть, этой ловушки сможет избежать какая-нибудь альтернативная система. Но вскоре стало ясно, что та же цепочка рассуждений применима в любой аксиоматической системе, достаточно богатой, чтобы формализовать арифметику. Арифметика изначально неполна. И если она логически непротиворечива, в чем убеждено большинство математиков и что все мы принимаем за рабочую гипотезу, то доказать это невозможно. Одним ударом Гёдель умудрился целиком изменить философские взгляды человечества на математику. Ее истины не могут быть абсолютными, потому что существуют утверждения, истинность или ложность которых лежит вообще вне логической системы.
Мы в общем случае считаем, что неразрешенная гипотеза, как гипотеза Римана, к примеру, является либо верной, либо ошибочной, то есть у нее либо имеется доказательство, либо нет. После Гёделя мы вынуждены добавлять к этому третий вариант. Может быть, не существует ни логической цепочки, которая вела бы от аксиом теории множеств к гипотезе Римана, ни логической цепочки, которая вела бы от аксиом теории множеств к отрицанию гипотезы Римана. Если так, то для этой гипотезы не существует ни доказательства, ни опровержения. Большинство математиков готовы держать пари за то, что гипотеза Римана разрешима. Более того, большинство считает, что она верна и что в один прекрасный день доказательство этого будет найдено. Но если нет, то наверняка будет найден контрпример – нуль, лежащий вне критической линии. Смысл в том, что мы этого не знаем. Мы полагаем, что «разумные» теоремы могут быть либо доказаны, либо опровергнуты, а неразрешимые теоремы кажутся нам слегка надуманными и искусственными. Однако в следующей главе мы увидим, как разумный естественный вопрос в области теоретической информатики оказывается неразрешимым.
Классическая логика с ее четким разграничением истинного и ложного, без промежуточных вариантов, всегда двузначна. Открытие Гёделя позволяет предположить, что для математики лучше подошла бы трехзначная логика: истинно, ложно или неразрешимо.