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

Gustavo Ernesto Pineiro Наука. Величайшие теории: выпуск 17: У интуиции есть своя логика. Гёдель. Теоремы о неполноте.

Пер. с исп. — М: Де Агостини, 2015. — 168 с.

ISSN 2409-0069

© Gustavo Ernesto Pineiro, 2013 (текст)

© RBA Coliecionables S.A., 2012

© ООО «Де Агостини», 2014-2015

Наука. Величайшие теории Выпуск № 17, 2015 Еженедельное издание

Введение

В 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. И так далее, неважно, сколько эмпирических проверок мы сделаем, мы все равно не сможем проверить все четные числа, поскольку они никогда не заканчиваются и всегда есть бесконечное число новых четных чисел, среди которых может найтись контрпример.

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