Хавьер Фресан - Том. 22. Сон разума. Математическая логика и ее парадоксы

* * *

«ВСЁ, ЧТО НЕ В ВАШЕМ СПИСКЕ»

Рэндел Манро(род. в 1984 году) работал в NASA, пока в 2005 году не обнаружил в себе удивительный талант смешить людей шутками на околонаучные темы. Он начал рисовать комиксы xkcd— «веб-комикс о романтике, сарказме, математике и языке». В его схематичных комиксах часто упоминаются различные понятия физики, математики и информатики. Курт Гёдель становился героем множества историй, однако лучшая из них рассказана в комиксе «Фетиши», приведенном ниже. В нем вы можете видеть трех персонажей, а рисунки поясняет текст:

«Недавно писатель Катарина Гейтс попыталась составить таблицу всех сексуальных фетишей. Она понятия не имела, что ту же задумку уже однажды провалили Рассел и Уайтхед».

Один из героев комикса говорит:

— Привет, Гёдель. Мы тут собираем полный список всех фетишей. Скажи, что тебя возбуждает?

— Всё, что не в вашем списке, — отвечает Гёдель.

* * *

Существуют неполные системы, которые перестают быть таковыми, если добавить к ним несколько аксиом. Однако в случае с арифметикой это не так: Гёдель не только привел недоказуемое утверждение G s , но и доказал, что не имеет смысла включать его в качестве аксиомы, так как, применив аналогичный метод на множестве Т = S + G s — множестве аксиом, которое вновь будет непротиворечивым и рекурсивно перечислимым, — мы получим новое истинное, но недоказуемое высказывание G T . Если отрубить гидре с бесконечным числом голов одну, это не спасет нас от неполноты.

Мы обещали объяснить, как можно перевести на язык арифметики неразрешимое высказывание «я недоказуемо», однако вначале скажем несколько слов о второй теореме о неполноте. В главе 1 мы упомянули, что в противоречивой системе аксиом любое высказывание является теоремой. Следовательно, существование хотя бы одной формулы, которая не является теоремой, позволяет доказать, что рассматриваемая теория является непротиворечивой. Если можно найти всего одно недоказуемое высказывание, это автоматически доказывает непротиворечивость системы. Достаточно всего одного! Поэтому зачем рассматривать сложные высказывания, когда достаточно простейшего: 0 = 1? В начале книги мы указали, как теорема «единица отлична от нуля» выводится из аксиом Пеано. Нетрудно убедиться в том, что в любой разумной теории о числах, даже при выборе иных аксиом, ноль будет отличаться от единицы. Таким образом, заявление «арифметика является непротиворечивой» равносильно словам: формула 0 = 1 недоказуема.

И вновь мы столкнулись с высказыванием на метаязыке, однако благодаря «гёделизации» мы можем преобразовать ее в формулу о числах, которую обозначим Соn S (где S — система аксиом). В этой системе обозначений первая теорема о неполноте гласит, что из Соn S следует G s так как если арифметика является непротиворечивой (иными словами, Соn S истинна), то G s истинна. Здесь будет уместно напомнить, в чем заключается одно из важнейших правил дедукции, modus ponens , позволяющее выводить из логической формулы «если А , то В » и формулы А формулу В . Предположим на мгновение, что непротиворечивость арифметики можно доказать в рамках самой арифметики. Следовательно, формула Соn S является доказуемой, и, вкупе с доказательством первой теоремы о неполноте Соn S —> G s согласно modus ponens следует доказательство G s. Однако этот вывод абсурден, ведь G s недоказуема! Единственный возможный вывод таков: чтобы доказать непротиворечивость арифметики, нужно выйти за ее пределы — именно об этом говорится во второй теореме о неполноте, которую сам Гедель считал «неожиданным следствием» своих исследований.

Согласно программе Гильберта, для доказательства непротиворечивости математики следовало начать с арифметики. Тем не менее вторая теорема Гёделя указывает, что если доказательство непротиворечивости арифметики существует, то в нем обязательно должны использоваться более сложные методы, чем предложенные формалистами финитные. Читатель наверняка заметил, что название статьи Геделя «О формально неразрешимых предложениях Principia Mathematica и родственных систем I » наводит на мысли о возможном продолжении. И действительно, в этой статье содержались лишь наброски второй теоремы о неполноте. Хотя все указанное в ней было верно, Гедель так и не написал вторую часть статьи, что согласуется с его образом «исследователя, который оставляет работу над деталями остальным», созданным его биографами. На самом деле Гедель объяснил все подробности доказательства Давиду Гильберту и его коллеге Паулю Бернайсу(1888–1977) во время трансатлантического путешествия — они и опубликовали первое полное доказательство второй теоремы о неполноте в 1939 году. О духе тогдашней науки свидетельствует тот факт, что сам Гильберт завершил доказательство теоремы, которая сводила на нет все его труды в течение предыдущих 23 лет.

Однако теоремы о неполноте были приняты совершенно не так, как они того заслуживали. Некоторые математики считали, что неразрешимое высказывание «я недоказуемо» — лишь любопытный частный случай, никак не влияющий на их исследования. Были и те, кто не понимал тонкую разницу между истинным и доказуемым и обвинял Гёделя в том, что он воспроизвел парадокс лжеца. К их числу относился и шестидесятилетний Эрнст Цермело, хотя он как никто другой знал, сколь тяжело бороться за идею: его аксиома выбора в свое время вызвала огромное множество критических отзывов. Словом, математическое сообщество в то время не было готово понять работу, содержавшую принципиально новые методы и касавшуюся области, которая традиционно была уделом меньшинства. Томас Кун совершенно прав, указывая в своей книге «Структура научных революций», что «открытие всегда сопровождается трудностями, встречает сопротивление, утверждается вопреки основным принципам, на которых основано ожидание». К счастью, перевод статьи Гёделя на английский язык и популярное изложение его теорем способствовали тому, что начиная с 70-х годов теоремы о неполноте постепенно обрели статус важнейших открытий в логике со времен Аристотеля.

Курт Гёдельв Институте перспективных исследований в Принстоне, Нью-Джерси.

* * *

ГЁДЕЛЬ И АМЕРИКАНСКОЕ ГРАЖДАНСТВО

Покинув нацистскую Германию, Курт Гёдель в 1940 году был принят на работу в Принстонский университет. Когда семь лет спустя он получил американское гражданство, с ним произошел анекдотичный случай. Как и остальные кандидаты, Гёдель должен был продемонстрировать на экзамене знание американской конституции. И хотя экзамен был лишь формальностью, Гёдель решил серьезно подготовиться к нему, однако во время подготовки обнаружил в Конституции США несколько логических противоречий: