Сон разума. Математическая логика и ее парадоксы
Шрифт:
Вместо дурацкого ignorabimus провозгласим наш контрлозунг: мы должны знать — мы будем знать!» Эхо выступления Гильберта еще не стихло, когда он узнал, что его программа находится под угрозой.
До заявления Геделя программа Гильберта давала все основания рассчитывать на успех: ее первый этап, формализация математики, по всей видимости, был завершен Расселом и Уайтхедом в книге «Начала математики», а различные логики пытались доказать непротиворечивость классических формальных систем начиная с арифметики. Хотя еще во введении к своей докторской диссертации Гёдель предположил невозможность существования «истинных высказываний, которые нельзя вывести в рассматриваемой системе», он стремился не положить конец мечтам Гильберта, а доказать правильность его программы. Однако последние открытия того времени говорили об обратном: исследования Гаусса в области геометрии отрицали возможность создания идеально точной карты Земли; Эварист Галуа (1811–1832) доказал, что почти никакое алгебраическое уравнение нельзя решить простыми методами, а Вернер
Теоремы Гёделя сделали очевидными все ограничения, присущие аксиоматическому методу: если в первой главе мы объясняли, что обязательными свойствами любой формальной системы являются непротиворечивость (полное отсутствие противоречий), рекурсивная перечислимость (возможность отделить аксиомы от прочих высказываний) и полнота (истинное и доказуемое полностью совпадают), то Гёдель показал, что арифметика не может обладать всеми тремя этими свойствами одновременно. Согласно его трудам, никакая рекурсивно перечислимая и непротиворечивая система аксиом арифметики не может быть полной, то есть всегда будут существовать какие-либо истинные свойства чисел, которые нельзя будет доказать исходя из аксиом арифметики. В этом и заключается суть теоремы Гёделя о неполноте, которую специалисты называют первой теоремой Геделя, так как, помимо нее, он доказал и вторую теорему, в которой утверждается, что высказывание «арифметика является непротиворечивой» являет собой пример неразрешимого высказывания. К таким же выводам по результатам конференции в Кёнигсберге пришел и фон Нейман.
Для доказательства первой теоремы о неполноте Гедель видоизменил парадокс лжеца, превратив его в неразрешимое высказывание, которое тем не менее не содержало противоречий. Очарование этой теоремы отчасти заключается в том, что она находится всего в одном шаге от парадоксов, но никогда не делает этот шаг. Мы уже рассказывали в главе 2 об антиномии Эпименида, которая в одной из формулировок звучит как «эта фраза ложна». И действительно, если это высказывание истинно, то оно само утверждает свою ложность, а если считать его ложным, то оно должно быть истинным. Что произойдет, если вместо истинных утверждений мы будем рассматривать доказуемые? Обозначим буквой G (по первой букве фамилии Геделя) высказывание «это высказывание недоказуемо» и будем предполагать, что используемая нами система аксиом является непротиворечивой. Если G ложно, то, так как G гласит «я недоказуемо», то G является доказуемым, однако в непротиворечивой системе никакое ложное высказывание не может быть доказуемым, так как это немедленно приведет к противоречию. Если С не является ложным, оно истинное, следовательно, имеем истинное высказывание, гласящее «я недоказуемо». Таким образом, мы предположили, что исходная система непротиворечива, однако обнаружили истинное, но недоказуемое высказывание. Иными словами, непротиворечивость подразумевает неполноту.
Мы предположили, что исходная система непротиворечива… Но какая система?
Внимательный читатель, задавшись этим вопросом и прочитав предыдущий абзац, возможно, подумал, что автор запутался и не совсем четко представляет, о какой системе идет речь. С удовольствием сообщаем, что читатель самостоятельно пришел к важнейшему вопросу, на который до Гёделя никто не мог дать ответ. Наши рассуждения показывают, что утверждение «я недоказуемо» должно быть истинным, однако здесь речь идет не о математическом высказывании, как нам бы того ни хотелось, но о метаматематическом, так как в нем говорится не об объектах изучения какой-либо теории, а о самой теории. Гениальность Геделя заключалась в том, что он перевел некоторые высказывания с метаязыка на язык арифметики благодаря системе кодов, в основе которой лежали простые числа. После этой «гёделизации» метаматематики натуральные числа стали вести двойную жизнь: с одной стороны, они остались неизменными, с другой — стали играть роль формул, что позволило выразить высказывание вида «я недоказуемо», которое априори имело смысл в метаязыке, в виде отношения между числами.
Более подробное описание гёделевской нумерации будет приведено дальше, а пока мы укажем, что с ее помощью в арифметике можно найти утверждение, эквивалентное высказыванию «я недоказуемо». Если бы множество аксиом арифметики S было рекурсивно перечислимым и непротиворечивым, то существовала бы истинная, но недоказуемая формула Gs (мы использовали индекс S, чтобы указать, что эта формула зависит от выбранных нами аксиом и при смене системы аксиом эта формула также изменится). Гёдель поставил всех логиков перед необходимостью сделать выбор либо в пользу полноты, либо в пользу непротиворечивости. И, что было еще хуже, арифметика была не просто неполной — ее полнота была недостижимой. Когда в начале этой книги мы приводили пример с инспектором полиции, который недавно пришел на службу, читатель мог возразить, что его коллеги наверняка узнали бы, женат ли он, продлись разговор немного дольше.
* * *
«ВСЁ, ЧТО НЕ В ВАШЕМ СПИСКЕ»
Рэндел Манро (род. в 1984 году) работал в NASA, пока в 2005 году не обнаружил в себе удивительный талант смешить людей шутками на околонаучные темы. Он начал рисовать комиксы xkcd — «веб-комикс о романтике, сарказме, математике и языке». В его схематичных комиксах часто упоминаются различные понятия физики, математики и информатики. Курт Гёдель становился героем множества историй, однако лучшая из них рассказана в комиксе «Фетиши», приведенном ниже. В нем вы можете видеть трех персонажей, а рисунки поясняет текст:
«Недавно писатель Катарина Гейтс попыталась составить таблицу всех сексуальных фетишей. Она понятия не имела, что ту же задумку уже однажды провалили Рассел и Уайтхед».
Один из героев комикса говорит:
— Привет, Гёдель. Мы тут собираем полный список всех фетишей. Скажи, что тебя возбуждает?
— Всё, что не в вашем списке, — отвечает Гёдель.
* * *
Существуют неполные системы, которые перестают быть таковыми, если добавить к ним несколько аксиом. Однако в случае с арифметикой это не так: Гёдель не только привел недоказуемое утверждение Gs, но и доказал, что не имеет смысла включать его в качестве аксиомы, так как, применив аналогичный метод на множестве Т = S + Gs — множестве аксиом, которое вновь будет непротиворечивым и рекурсивно перечислимым, — мы получим новое истинное, но недоказуемое высказывание GT. Если отрубить гидре с бесконечным числом голов одну, это не спасет нас от неполноты.
Мы обещали объяснить, как можно перевести на язык арифметики неразрешимое высказывание «я недоказуемо», однако вначале скажем несколько слов о второй теореме о неполноте. В главе 1 мы упомянули, что в противоречивой системе аксиом любое высказывание является теоремой. Следовательно, существование хотя бы одной формулы, которая не является теоремой, позволяет доказать, что рассматриваемая теория является непротиворечивой. Если можно найти всего одно недоказуемое высказывание, это автоматически доказывает непротиворечивость системы. Достаточно всего одного! Поэтому зачем рассматривать сложные высказывания, когда достаточно простейшего: 0 = 1? В начале книги мы указали, как теорема «единица отлична от нуля» выводится из аксиом Пеано. Нетрудно убедиться в том, что в любой разумной теории о числах, даже при выборе иных аксиом, ноль будет отличаться от единицы. Таким образом, заявление «арифметика является непротиворечивой» равносильно словам: формула 0 = 1 недоказуема.
И вновь мы столкнулись с высказыванием на метаязыке, однако благодаря «гёделизации» мы можем преобразовать ее в формулу о числах, которую обозначим СоnS (где S — система аксиом). В этой системе обозначений первая теорема о неполноте гласит, что из СоnS следует Gs так как если арифметика является непротиворечивой (иными словами, СоnS истинна), то Gs истинна. Здесь будет уместно напомнить, в чем заключается одно из важнейших правил дедукции, modus ponens, позволяющее выводить из логической формулы «если А, то В» и формулы А формулу В. Предположим на мгновение, что непротиворечивость арифметики можно доказать в рамках самой арифметики. Следовательно, формула СоnS является доказуемой, и, вкупе с доказательством первой теоремы о неполноте СоnS —> Gs согласно modus ponens следует доказательство Gs. Однако этот вывод абсурден, ведь Gs недоказуема! Единственный возможный вывод таков: чтобы доказать непротиворечивость арифметики, нужно выйти за ее пределы — именно об этом говорится во второй теореме о неполноте, которую сам Гедель считал «неожиданным следствием» своих исследований.
Согласно программе Гильберта, для доказательства непротиворечивости математики следовало начать с арифметики. Тем не менее вторая теорема Гёделя указывает, что если доказательство непротиворечивости арифметики существует, то в нем обязательно должны использоваться более сложные методы, чем предложенные формалистами финитные. Читатель наверняка заметил, что название статьи Геделя «О формально неразрешимых предложениях Principia Mathematica и родственных систем I» наводит на мысли о возможном продолжении. И действительно, в этой статье содержались лишь наброски второй теоремы о неполноте. Хотя все указанное в ней было верно, Гедель так и не написал вторую часть статьи, что согласуется с его образом «исследователя, который оставляет работу над деталями остальным», созданным его биографами. На самом деле Гедель объяснил все подробности доказательства Давиду Гильберту и его коллеге Паулю Бернайсу (1888–1977) во время трансатлантического путешествия — они и опубликовали первое полное доказательство второй теоремы о неполноте в 1939 году. О духе тогдашней науки свидетельствует тот факт, что сам Гильберт завершил доказательство теоремы, которая сводила на нет все его труды в течение предыдущих 23 лет.
Однако теоремы о неполноте были приняты совершенно не так, как они того заслуживали. Некоторые математики считали, что неразрешимое высказывание «я недоказуемо» — лишь любопытный частный случай, никак не влияющий на их исследования. Были и те, кто не понимал тонкую разницу между истинным и доказуемым и обвинял Гёделя в том, что он воспроизвел парадокс лжеца. К их числу относился и шестидесятилетний Эрнст Цермело, хотя он как никто другой знал, сколь тяжело бороться за идею: его аксиома выбора в свое время вызвала огромное множество критических отзывов. Словом, математическое сообщество в то время не было готово понять работу, содержавшую принципиально новые методы и касавшуюся области, которая традиционно была уделом меньшинства. Томас Кун совершенно прав, указывая в своей книге «Структура научных революций», что «открытие всегда сопровождается трудностями, встречает сопротивление, утверждается вопреки основным принципам, на которых основано ожидание». К счастью, перевод статьи Гёделя на английский язык и популярное изложение его теорем способствовали тому, что начиная с 70-х годов теоремы о неполноте постепенно обрели статус важнейших открытий в логике со времен Аристотеля.