Gustavo Pineiro - У интуиции есть своя логика. Гёдель. Теоремы о неполноте.
Обзор книги Gustavo Pineiro - У интуиции есть своя логика. Гёдель. Теоремы о неполноте.
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 оказалось вне списка. Если бы нашелся хотя бы один пример, для которого гипотеза не выполнялась бы, то есть контрпример — четное число, которое нельзя записать в виде суммы двух простых чисел,— то гипотеза оказалась бы ложной. Такого контрпримера еще не нашли. На момент написания этих строк с помощью компьютеров было выяснено, что все четные числа до 1018 (единица с 18 нулями) могут быть записаны в виде суммы двух простых чисел.
Но как можно подтвердить, что гипотеза истинна? Достаточно ли того, что она проверена для четных чисел, меньших 1018, для признания ее истинности? Нет, потому что это может быть неверно для числа, непосредственно следующего за 1018 (то есть 1018 + 2). А если мы проверим это для 1018 + 2, достаточно ли этого? Нет, потому что это может быть неверно для 1018 + 4. И так далее, неважно, сколько эмпирических проверок мы сделаем, мы все равно не сможем проверить все четные числа, поскольку они никогда не заканчиваются и всегда есть бесконечное число новых четных чисел, среди которых может найтись контрпример.
Единственный способ проверить истинность гипотезы — это найти доказательство, то есть такие рассуждения, которые демонстрируют справедливость утверждения сразу для всех возможных случаев. Рассмотрим пример такого доказательства (естественно, мы не можем привести доказательство гипотезы Гольдбаха, поскольку оно до сих пор не найдено). Докажем утверждение: «Все простые числа, большие двух, являются нечетными». Это утверждение затрагивает бесконечное число чисел; однако мы можем охватить их все одним и тем же рассуждением.
Все простые числа, большие двух, являются нечетными. Доказательство: если простое число, большее двух, четно, то оно делится на 2. Но это невозможно, поскольку оно простое, то есть может делиться только на единицу и само на себя. Оно не может быть кратным двум, то есть четным; следовательно, оно нечетное.
Мы можем понимать доказательство как рассуждение, которое потенциально включает в себя бесконечное число частных случаев. Все сложные математические проблемы потенциально включают в себя бесконечное количество объектов, будь то числа, уравнения или другие объекты. По этой причине вычисление суммы всех чисел от единицы до миллиона, при всей своей трудоемкости, не является сложной проблемой в том смысле, который придают этому слову математики, поскольку вычисление предполагает вполне определенное количество операций, и их можно совершить за некоторый промежуток времени, имеющий начало и конец.
Решение проблемы, сформулированной в гипотезе Гольдбаха (или любой другой гипотезе), состоит в том, чтобы найти опровергающий контрпример или доказательство, подтверждающее ее истинность.
Если предложено рассуждение, предположительно доказывающее гипотезу, как мы убедимся в том, что оно верно? Если кто-то не убежден в справедливости рассуждения, каковы критерии, позволяющие устранить его сомнения? Прежде чем ответить на эти вопросы, рассмотрим еще один исторический пример.
В 1909 году французский математик Эмиль Борель дал определение понятию нормального числа. Нет необходимости вникать во все сложности этого определения, достаточно сказать, что число нормальное, когда после запятой его знаки ведут себя так, как если бы выбирались наугад, и это происходит при записи в десятичном (как это принято), двоичном, шестнадцатеричном или любом другом виде. Например, ясно, что 0, 101010101... не является нормальным числом (его знаки после запятой ведут себя слишком закономерно для того, чтобы быть похожими на случайные). И напротив, считается, что π = 3,1415926... и √2 = 1,4142135... являются нормальными числами, хотя эта гипотеза еще не доказана и не опровергнута.
Борель, помимо того что дал определение нормальным числам, доказал: их количество бесконечно, то есть ряд нормальных чисел никогда не заканчивается. Однако в его доказательстве были использованы очень косвенные методы; можно сказать, он также доказал, что этого бесконечного количества чисел не может не существовать. Главное в этой истории то, что Борель, как и никто другой, не был способен в 1909 году привести ни одного примера нормального числа. Некоторые числа (включая приведенные выше) подходили под определение нормальных, но нельзя было утверждать это точно. То есть Борель доказал, что существует бесконечное количество чисел определенного типа, но не смог привести ни одного из них. Допустима ли такая ситуация? Можем ли мы вести разговор о числах, ни имея ни одного их примера? В начале XX века многие математики начали выказывать недоверие доказательствам, включавшим ряды, образованные бесконечным количеством чисел (такими как ряд нормальных чисел). Они сомневались, допустимо ли работать с ними, пользуясь теми же правилами, что и для конечных рядов (то есть не расширяющихся до неопределенности). Это недоверие было подкреплено тем, что в 1902 году британский философ и математик Бертран Рассел нашел логические противоречия, связанные с рассуждениями такого типа.
В начале XX века вопрос о том, как определить справедливость математического рассуждения, был совершенно неясен. Среди математиков бурлили споры и дискуссии. И только почти через четверть века, в 1930 году, ученые пришли к соглашению о четких и конкретных критериях, которым должно соответствовать доказательство, чтобы его приняли как верное. Эти критерии, установленные объективно, состояли в том, чтобы рассуждения были проверены компьютером — беспристрастным судьей, который ограничивается вычислениями, не оперируя лингвистическими конструкциями. Естественно, это современный вариант соглашения, раньше он формулировался по-другому, поскольку в 1930 году еще не было компьютеров.
