Нумерация Гёделя

Доказательство Гёделя занимает десятки страниц, однако идея, лежащая в его основе, поразительно проста. В любой формальной системе математические утверждения представляют собой просто последовательности символов. Гёдель нашел систематический способ превращать любую такую последовательность в уникальное целое число (так уж вышло, что в очень большое число, но эта подробность ни на что не влияет). Данная последовательность символов уникальным образом определяет это целое число (то есть последовательность может быть механически “зашифрована” в виде этого числа) и наоборот: если дано большое целое число, то его можно представить в виде последовательности символов, и тогда эта последовательность определяется уникальным образом (то есть большое целое число, если угодно, можно механически “расшифровать”). Впоследствии эти большие числа получили название “номера Гёделя” соответствующих последовательностей, а рецепт шифровки-расшифровки – “нумерация Гёделя”.

Следующая идея опирается на то, что доказательства в Principia Mathematica, как и в любой другой формальной системе, строятся регулярно, таким образом, что это можно отразить в мире чисел. Так, для любой теоремы существует “число-теорема”, с которым можно работать в терминах сложения, умножения и других математических понятий. Поэтому доказуемость последовательности в формальной системе соответствовала чисто математическому свойству очень большого числа, и об этом свойстве можно было говорить, применяя систему обозначений из Principia Mathematica. Иначе говоря, точно так же, как можно утверждать, что число N – квадрат, куб или простое число, и доказывать о подобных утверждениях всевозможные теоремы (например, “существует бесконечно много простых чисел”), можно утверждать, что число N – число-теорема, и существуют всевозможные теоремы об этом более сложном понятии “численности-теоремности” (например, “существует бесконечно много чисел-теорем”). Таким образом, система Principia Mathematica обретает способность говорить (в зашифрованном виде) о доказуемости или недоказуемости последовательностей в самой системе Principia Mathematica. Вот типичный пример, когда змея кусает свой хвост!

Решающий шаг Гёделя, его coup de grâce, состоял в конструировании особого математического утверждения G, согласно которому последовательность, обладающая номером Гёделя g, недоказуема, то есть ее нельзя формально вывести из системы аксиом Principia Mathematica. Что поразительно, Гёдель умудрился повернуть все так, что целое число g и есть номер Гёделя утверждения G (“несколько случайно”, как он лукаво заметил). Тогда утверждение G гласит, что оно – не теорема, то есть не может быть доказано в пределах Principia Mathematica. Можно выразить G словами: “Меня нельзя доказать в пределах Principia Mathematica”. А тогда ложно G или истинно? Доказуемо или недоказуемо? Выходит, если G доказано, это приводит к противоречию, и, наоборот, если доказано его отрицание не-G, это приводит к другому противоречию. Казалось бы, полная катастрофа, неизбежно ведущая к самопротиворечивой системе – но постойте! А вдруг недоказуемы и G, и не-G? В таком случае удается уберечь от противоречивости всю систему (Principia Mathematica), но лишь ценой полной невозможности решить, во что она “верит” – в G или в не-G.

Короче говоря, если система Principia Mathematica непротиворечива, то есть она никогда не докажет два утверждения, противоречащих друг другу, то с помощью ее аксиом и правил невозможно доказать ни G, ни не-G. А поскольку G утверждает, что его невозможно формально доказать, то, что́ оно утверждает, истинно. Однако доказательство истинности G по Гёделю опирается на смысл G. Это не доказательство с точки зрения формальной доказуемости, эта идея ограничена доказательствами, которые определяются по формальным правилам Principia Mathematica. Это Гёдель сумел показать, что это странное утверждение G истинно, поскольку мыслил вне правил системы.

Писатель Ганс Магнус Энценсбергер, родившийся в 1929 году, в одном из своих стихотворений сравнил доказательство Гёделя с курьезной историей об известном вруне бароне Мюнхгаузене, который утверждал, будто вытащил сам себя из болота за косичку. “Только Мюнхгаузен был лжец, а Гёдель оказался прав”.

Фраза “Меня нельзя доказать” вообще не похожа на нормальное математическое высказывание. Ведь математики обычно имеют дело с числами, фигурами, функциями, а не с абстрактными философскими на вид идеями вроде “доказуемости”. Но благодаря рецепту шифровки-расшифровки Гёделя на формальную доказуемость утверждения стали смотреть как на качество, в точности соответствующее арифметическому свойству номера Гёделя, присвоенного этому утверждению.

Вскоре было показано, что вдобавок к гёделевскому утверждению G, которое при помощи нумерации Гёделя истинно утверждает: “Меня нельзя доказать”, существует бесконечно много других истинных утверждений, которые нельзя доказать, зато они выглядят гораздо привычнее для математиков – например, существуют недоказуемые истинные утверждения, по форме схожие с гипотезой Гольдбаха, которую Гёдель упоминал на съезде в Кенигсберге. Это весьма поучительный пример.

Еще в 1742 году математик-любитель Кристиан Гольдбах предположил, что любое четное число больше 2 представляет собой сумму двух простых чисел. Отчасти это можно проверить. Так, 6 = 3 + 3, 12 = 5 + 7 и т. д. Самые быстрые компьютеры на Земле позволили проверить гипотезу Гольдбаха для всех четных чисел до 300 000 000 000 000 000 (17 нулей). Это виртуозное достижение, естественно, не доказывает гипотезу Гольдбаха и даже не приближает нас к доказательству: ведь по-прежнему остается бесконечно много четных чисел, до проверки которых еще не дошла очередь!

Компьютерная программа способна исследовать каждое четное число и проверять, представляют ли они собой сумму двух простых чисел. Если гипотеза Гольдбаха ошибочна, компьютер когда-нибудь это покажет, надо просто подождать, пока он доберется до четного числа, которое не будет представлять собой сумму двух простых чисел. Но если гипотеза верна, компьютер будет трудиться бесконечно, а нам придется до второго пришествия сидеть и ждать, не зная, найдется ли когда-нибудь исключение. Очевидно, гипотезу Гольдбаха так не докажешь. Компьютерная программа может подтвердить ложность гипотезы (если она и в самом деле ложна), поскольку это займет лишь конечное время, но не может подтвердить ее истинность (если она в действительности истинна), поскольку на это требуется бесконечное время.

Подобным же образом компьютер способен проинспектировать любую формальную математическую последовательность формул, ведь такая последовательность – всего лишь цепочка символов, и проверить, есть ли у нее формальное доказательство. Такая проверка – акт сугубо механический, и он не требует понимания, что означают те или иные символы. Компьютер может проинспектировать все возможные подобные тексты по одному, стоящие в бесконечном списке по возрастанию длины. Этот список никогда не исчерпать. Но если можно доказать либо утверждение А, либо его отрицание не-А, тогда компьютер обязательно найдет соответствующее доказательство: оно ведь есть где-то в этом списке.

Поначалу представляется, будто из всего этого следует, что все математические утверждения можно механически рассортировать. Запустите компьютер и поглядите, что он найдет первым – доказательство А или доказательство не-А. Пара пустяков!

Но тут есть загвоздка, которая в том и состоит, что благодаря теореме Гёделя о неполноте существуют истинные утверждения, для которых нет формального доказательства. Если А принадлежит к таким формулам, то компьютер будет продолжать процесс проверки бесконечно и так никогда и не определит, ложно или истинно А, ведь ни у А, ни у его отрицания нет доказательства!

Таким образом, теорема Гёделя о неполноте предвосхищает важнейшие идеи об абсолютных пределах возможностей компьютерных программ. Первым до них докопался английский математик Алан Тьюринг (1912–1954) в 1936 году. С годами Гёделю, Тьюрингу и другим гениальным логикам удалось установить, что процесс математического мышления невозможно полностью свести к чисто формальным аксиоматическим рассуждениям. В этом смысле математика – неисчерпаемый источник.

Через несколько десятков лет после прорывных статей Гёделя и Тьюринга в мире завоевала невероятную популярность логическая игра судоку – ей увлекались миллионы. Это показывает, что логика может быть очень интересной. Более того, головоломки судоку можно считать аналогичными формальным математическим теориям à la Гильберт, и сейчас мы в этом убедимся.

Цель игры в судоку – расставить цифры от 1 до 9 в 81 ячейке в квадрате 9 × 9 так, чтобы каждая цифра встречалась в каждом ряду, в каждом столбце и в каждом мини-квадрате 3 × 3 только один раз.

В нескольких ячейках цифры уже расставлены, что называется, бонусом. Так вот, в нашей аналогии с формальными системами заранее заданные цифры – это “аксиомы”. Мы ждем, что нормальная головоломка судоку, во-первых, имеет решение, во-вторых, это решение единственное. То есть предполагается, что для каждой из 81 ячейки найдется одна и только одна цифра, удовлетворяющая условиям. Если найдется какая-то ячейка, которую в принципе нельзя заполнить, значит, “аксиомы” ведут к противоречию. А если есть ячейка, которую можно заполнить двумя и более разными способами, значит, “аксиомы” неполны: задача о том, какие цифры подходят в какие ячейки, не имеет решения. Нужны дополнительные “аксиомы”, чтобы задать единственно верное расположение цифр. То есть идеальная головоломка судоку должна быть одновременно и полной, и непротиворечивой.

Однако ждать того же от формальной системы математики – значит неизбежно разочароваться. Именно это Гёдель и показал в 1931 году. Впоследствии Людвиг Витгенштейн подвел под этим черту следующим образом: “Теорема Гёделя вынуждает нас рассматривать математику под новым углом”. (Впрочем, большинство исследователей сходятся на том, что ни Витгенштейн, ни Рассел на самом деле не понимали идей Гёделя.) Теперь, когда мы прекрасно знаем, как все обстоит на самом деле, сама мысль, что все истинные утверждения математики (но не ложные) можно выявить по одному благодаря трудолюбивой компьютерной программе, выглядит так же диковинно, как надежды алхимиков обрести философский камень. Нельзя заменить живых математиков холодными строгими автоматами. Вероятно, так можно сказать и о других профессиях, но этого никто не доказал. (И в качестве реплики в сторону: в 2013 году математик Харальд Хельфготт доказал, что любое нечетное число представляет собой сумму трех простых чисел. Тем не менее мы ни на волосок не приблизились к доказательству гипотезы Гольдбаха.)

Примеры судоку: (а) неполное, (b) противоречивое, (c) “нормальное”

Гёделя иногда понимают неправильно. Разумеется, это практически неизбежно, и эту участь Гёдель разделяет с Дарвином и Эйнштейном и другими великими первопроходцами в науке. Кто-то утверждает, что Гёдель доказал, что математика противоречива. Это вовсе не так. Он доказал, что ее непротиворечивость невозможно формально доказать. Примерно так же вам, вероятно, не удастся обеспечить стопроцентно убедительное юридическое доказательство, что вы никогда в жизни не совершали убийства, – ни разу. Несмотря на это, мы, как правило, изначально не считаем никого убийцей. Так же и с математикой. Никто всерьез не верит, что математика внутренне противоречива. Перефразируя слова одного французского математика, изящно сформулировавшего девиз своей профессии, “Бог создал математику непротиворечивой, а дьявол сделал так, чтобы это нельзя было доказать”.