Гёдель. Теоремы о неполноте

Введение

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

До того как Гёдель доказал свою теорему, математики безгранично верили в то, что при достаточном количестве времени, терпения и усилий любая поставленная проблема может быть решена. Например, немецкий математик Давид Гильберт, представивший на Втором Международном математическом конгрессе в Париже в 1900 году знаменитый список из 23 проблем, в своем выдающемся докладе предположил, что эти проблемы определят значительную часть математических исследований в течение XX века.

Проблемы Гильберта очень сложны, и было ясно, что для нахождения решений потребуются десятки лет, что в будущем и подтвердилось. Например, ответ на десятую проблему (в современных терминах: может ли определенный тип уравнений, называемых диофантовыми, всегда быть решен с помощью компьютера?) был найден только в 1970 году. Восьмая про-

блема, известная как гипотеза Римана, не решена и сегодня. Однако ни Гильберт, ни кто-либо из его коллег в далеком 1900 году не сомневались, что рано или поздно будут найдены решения всех проблем. Сам Гильберт выразил эту мысль такими словами: «Мы хотим знать, мы будем знать» ( Wirmiissen wissen, wir werden wissen). Их он распорядился написать и в своей эпитафии — возможно, в качестве послания будущим поколениям или как посмертный вызов Гёделю (Гильберт скончался в 1943 году, через 13 лет после того, как Гёдель сформулировал свою теорему).

Итак, что именно представляет собой математическая проблема? Что мы хотим сказать, когда утверждаем, что проблемы Гильберта были сложными? Может ли считаться сложной задача: «сосчитайте сумму всех чисел от единицы до миллиона»?

Большинство проблем, которые изучает математическая наука, сформулированы как гипотезы. Гипотеза — это утверждение, которое кажется истинным, но его истинность еще не доказана. Знаменитый пример — так называемая гипотеза Гольдбаха, сформулированная прусским математиком Кристианом Гольдбахом в 1742 году:

«Любое четное число, большее двух, может быть выражено в виде суммы двух простых чисел».

Простые числа — это те, которые делятся только на единицу и на само себя; число 1 по техническим причинам не считается простым. Проверим, например, что эта гипотеза справедлива для четных чисел, меньших 12:

4 = 2 + 2

6 = 3 + 3

8 = 3 + 5

10 = 3 + 7

12 = 5 + 7

В гипотезе говорится о четных числах больше двух, поэтому само число 2 оказалось вне списка. Если бы нашелся хотя бы один пример, для которого гипотеза не выполнялась бы, то есть контрпример — четное число, которое нельзя записать в виде суммы двух простых чисел,— то гипотеза оказалась бы ложной. Такого контрпримера еще не нашли. На момент написания этих строк с помощью компьютеров было выяснено, что все четные числа до 10¹⁸ (единица с 18 нулями) могут быть записаны в виде суммы двух простых чисел.

Но как можно подтвердить, что гипотеза истинна? Достаточно ли того, что она проверена для четных чисел, меньших 10¹⁸, для признания ее истинности? Нет, потому что это может быть неверно для числа, непосредственно следующего за 10¹⁸ (то есть 10¹⁸ + 2). А если мы проверим это для 10¹⁸ + 2, достаточно ли этого? Нет, потому что это может быть неверно для 10¹⁸ + 4. И так далее, неважно, сколько эмпирических проверок мы сделаем, мы все равно не сможем проверить все четные числа, поскольку они никогда не заканчиваются и всегда есть бесконечное число новых четных чисел, среди которых может найтись контрпример.

Единственный способ проверить истинность гипотезы — это найти доказательство, то есть такие рассуждения, которые демонстрируют справедливость утверждения сразу для всех возможных случаев. Рассмотрим пример такого доказательства (естественно, мы не можем привести доказательство гипотезы Гольдбаха, поскольку оно до сих пор не найдено). Докажем утверждение: «Все простые числа, большие двух, являются нечетными». Это утверждение затрагивает бесконечное число чисел; однако мы можем охватить их все одним и тем же рассуждением.

Все простые числа, большие двух, являются нечетными. Доказательство: если простое число, большее двух, четно, то оно делится на 2. Но это невозможно, поскольку оно простое, то есть может делиться только на единицу и само на себя. Оно не может быть кратным двум, то есть четным; следовательно, оно нечетное.

Мы можем понимать доказательство как рассуждение, которое потенциально включает в себя бесконечное число частных случаев. Все сложные математические проблемы потенциально включают в себя бесконечное количество объектов, будь то числа, уравнения или другие объекты. По этой причине вычисление суммы всех чисел от единицы до миллиона, при всей своей трудоемкости, не является сложной проблемой в том смысле, который придают этому слову математики, поскольку вычисление предполагает вполне определенное количество операций, и их можно совершить за некоторый промежуток времени, имеющий начало и конец.

Решение проблемы, сформулированной в гипотезе Гольдбаха (или любой другой гипотезе), состоит в том, чтобы найти опровергающий контрпример или доказательство, подтверждающее ее истинность.

Если предложено рассуждение, предположительно доказывающее гипотезу, как мы убедимся в том, что оно верно? Если кто-то не убежден в справедливости рассуждения, каковы критерии, позволяющие устранить его сомнения? Прежде чем ответить на эти вопросы, рассмотрим еще один исторический пример.

В 1909 году французский математик Эмиль Борель дал определение понятию нормального числа. Нет необходимости вникать во все сложности этого определения, достаточно сказать, что число нормальное, когда после запятой его знаки ведут себя так, как если бы выбирались наугад, и это происходит при записи в десятичном (как это принято), двоичном, шестнадцатеричном или любом другом виде. Например, ясно, что 0, 101010101... не является нормальным числом (его знаки после запятой ведут себя слишком закономерно для того, чтобы быть похожими на случайные). И напротив, считается, что π = 3,1415926... и √2 = 1,4142135... являются нормальными числами, хотя эта гипотеза еще не доказана и не опровергнута.

Борель, помимо того что дал определение нормальным числам, доказал: их количество бесконечно, то есть ряд нормальных чисел никогда не заканчивается. Однако в его доказательстве были использованы очень косвенные методы; можно сказать, он также доказал, что этого бесконечного количества чисел не может не существовать. Главное в этой истории то, что Борель, как и никто другой, не был способен в 1909 году привести ни одного примера нормального числа. Некоторые числа (включая приведенные выше) подходили под определение нормальных, но нельзя было утверждать это точно. То есть Борель доказал, что существует бесконечное количество чисел определенного типа, но не смог привести ни одного из них. Допустима ли такая ситуация? Можем ли мы вести разговор о числах, ни имея ни одного их примера? В начале XX века многие математики начали выказывать недоверие доказательствам, включавшим ряды, образованные бесконечным количеством чисел (такими как ряд нормальных чисел). Они сомневались, допустимо ли работать с ними, пользуясь теми же правилами, что и для конечных рядов (то есть не расширяющихся до неопределенности). Это недоверие было подкреплено тем, что в 1902 году британский философ и математик Бертран Рассел нашел логические противоречия, связанные с рассуждениями такого типа.

В начале XX века вопрос о том, как определить справедливость математического рассуждения, был совершенно неясен. Среди математиков бурлили споры и дискуссии. И только почти через четверть века, в 1930 году, ученые пришли к соглашению о четких и конкретных критериях, которым должно соответствовать доказательство, чтобы его приняли как верное. Эти критерии, установленные объективно, состояли в том, чтобы рассуждения были проверены компьютером — беспристрастным судьей, который ограничивается вычислениями, не оперируя лингвистическими конструкциями. Естественно, это современный вариант соглашения, раньше он формулировался по-другому, поскольку в 1930 году еще не было компьютеров.

Но именно в том месте и в то время, когда математики собрались, чтобы прийти к согласию о надежных методах рассуждений, Курт Гёдель поднял руку и попросил слова, чтобы рассказать о своей теореме о неполноте: если даже придерживаться методов, исключающих ошибку, всегда будут существовать истинные гипотезы, которые нельзя доказать, и математические проблемы, которые невозможно решить с помощью самых надежных методов. Мы можем иметь потенциальную способность решать проблемы (без уверенности в том, что решение правильное), но никогда не сможем одновременно иметь уверенность в своих методах и возможность решить все проблемы.

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

Эта книга — об истории открытия Гёделя и его следствиях для философии математики. В главе 1 описаны исторический процесс, приведший к полемике о методах доказательства в математике, и роль, которую сыграла в этой полемике теорема Гёделя. В главе 2 приведены сама теорема и объяснение ее доказательства. Но как на том историческом этапе, когда почти все методы математического доказательства были поставлены под сомнение, Гёделю удалось убедить всех в своей правоте? Ответ на этот вопрос проанализирован в главе 3, в то время как глава 4 посвящена другим работам математика, среди которых — исследования в теории относительности. В последней главе обсуждаются некоторые философские следствия теорем Гёделя, связанные с природой математической истины.

1906 Курт Гёдель родился 28 апреля в Брно, в Австро-Венгерской империи (современная Чешская Республика), в семье Рудольфа Гёделя и Марианны Хандшу. У него был только один старший брат, которого, как и отца, звали Рудольфом.

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

1923 Поступил в Венский университет, чтобы изучать теоретическую физику, однако, благодаря влиянию профессора Филиппа Фуртвенглера, занялся математикой.

1926 Приглашен в Венский кружок — группу интеллектуалов, основанную в 1922 году немецким философом Морицем Шликом для обсуждения науки и эпистемологии. Здесь Гёдель познакомился с дебатами вокруг теории доказательства и решил посвятить себя математической логике.

1929 Завершил докторскую диссертацию, которую представил в следующем году в Венском университете.

1930 С 5 по 7 сентября в Кёнигсберге проходил конгресс, посвященный теории доказательства и связанным с ней темам. На пленарном заседании 7 сентября Гёдель впервые провозгласил свою теорему о неполноте.

1931 Опубликована статья ученого «О формально неразрешимых предложениях Principia Mathematica у родственных систем», содержащая формулировку и доказательство его теоремы о неполноте.

1933 Назначен приват-доцентом Венского университета. Совершил серию поездок в США, где читал различные курсы и лекции.

1938 Женился на Адель Поркерт, разведенной танцовщице, на шесть лет старше его.

1939 Под давлением нацистов, пришедших к власти в Австрии, бежал с супругой США. В Европу они так больше и не вернулись.

1940 Присоединился к Институту перспективных исследований в Принстоне, где началась его дружба с Альбертом Эйнштейном.

1951 Прочитал Гиббсовскую лекцию, в которой проанализировал некоторые возможные философские следствия из своей теоремы о неполноте.

1978 Курт Гёдель скончался в Принстонской больнице вечером 14 января.