Том 22. Сон разума. Математическая логика и ее парадоксы - страница 29
Более подробное описание гёделевской нумерации будет приведено дальше, а пока мы укажем, что с ее помощью в арифметике можно найти утверждение, эквивалентное высказыванию «я недоказуемо». Если бы множество аксиом арифметики S было рекурсивно перечислимым и непротиворечивым, то существовала бы истинная, но недоказуемая формула G>s (мы использовали индекс S, чтобы указать, что эта формула зависит от выбранных нами аксиом и при смене системы аксиом эта формула также изменится). Гёдель поставил всех логиков перед необходимостью сделать выбор либо в пользу полноты, либо в пользу непротиворечивости. И, что было еще хуже, арифметика была не просто неполной — ее полнота была недостижимой. Когда в начале этой книги мы приводили пример с инспектором полиции, который недавно пришел на службу, читатель мог возразить, что его коллеги наверняка узнали бы, женат ли он, продлись разговор немного дольше.
* * *
«ВСЁ, ЧТО НЕ В ВАШЕМ СПИСКЕ»
Рэндел Манро (род. в 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 является доказуемой, и, вкупе с доказательством первой теоремы о неполноте
