Рэймонд Смаллиан - Принцесса или тигр?

2. Прежде чем рассматривать другие решения, установим следующий факт весьма общего свойства. Пусть для всего дальнейшего ключевым является множество К — это множество всех чисел х, для которых утверждение x ∈ А x недоказуемо машиной, или, что то же самое, множество таких чисел х, для которых число х * х не может быть напечатано машиной. Далее, множество A 75как раз и есть такое множество К, потому что утверждение, что x принадлежит множеству A 75, равносильно утверждению, что x не принадлежит множеству A 25, что в свою очередь равносильно утверждению, что число х * х не принадлежит множеству A 8, где A 8— это множество тех чисел, которые машина может напечатать. Итак, A 75= К. Но при этом и A 73= К, потому что утверждение, что некое число x принадлежит множеству A n, равносильно утверждению, что число х * х принадлежит множеству A 8(согласно свойству 3, поскольку 73 = 3×24 + 1), что в свою очередь равносильно утверждению, что число х * х не принадлежит множеству A 8(согласно свойству 2). Таким образом, A 73— это множество всех тех чисел х, для которых число х * х не принадлежит множеству A 8или, что то же самое, множество всех чисел х, для которых утверждение x ∈ А x не может быть доказано машиной. Следовательно, A 73— это то же самое множество чисел, что и A 75, поскольку оба они тождественны множеству К. Более того, для любого заданного числа n , для которого А n = К, утверждение n ∈ А n должно быть истинным, но недоказуемым с помощью машины. Это можно показать буквально с помощью тех же самых рассуждений, что и в рассмотренном нами частном случае n = 75 (в еще более общей форме эти рассуждения приведены в следующей главе). Тем самым мы получаем, что утверждение 73 ∈ A 73— это еще один пример истинного утверждения, кодовый номер которого машина напечатать не может.

3. Для любого числа n множество A 9· n должно совпадать с множеством n. В самом деле, множество A 9· n есть дополнение множества A 3· n , а множество A 3· n в свою очередь есть дополнение множества A n ; следовательно, множество A 9· n совпадает с A n . Это означает, что множество A 675совпадает с множеством A 75, и, стало быть, утверждение 675 ∈ A 675— это есть еще одно решение задачи. Аналогично утверждение 2175 ∈ A 2175также является решением. Таким образом, мы получаем, что существует бесконечно много истинных утверждений, которые машина Фергюссона доказать не может: например, для любого n , которое равно произведению 75 на некоторое кратное числа 9 или произведению 73 на произвольное кратное числа 9, утверждение n ∈ А, является истинным, но недоказуемым посредством этой машины.

Крупной вехой в истории математической логики стал 1931 г. Именно в этом году Гёдель опубликовал знаменитую теорему о неполноте. Свою эпохальную работу [8] «Uber formal unentscheidbare Satze der „Principia Mathematica“ und verwandter Systeme'I» («О формально неразрешимых предложениях „Принципов математики“ и других родственных систем»), Моnatshefte fur Mathematik und Physik, 38, 173–198. он начинает следующими словами:

«Развитие математики в направлении все большей точности привело к формализации целых ее областей, в связи с чем стало возможно проводить доказательства, пользуясь небольшим числом чисто механических правил. В настоящий момент наиболее исчерпывающими системами являются, с одной стороны, система аксиом, предложенная Уайтхедом и Расселом в работе „Princlpia Mathematica“, а с другой — система Цермело — Френкеля в аксиоматической теории множеств. Обе эти системы настолько обширны, что в них оказывается возможным формализовать все методы доказательства, используемые сегодня в математике, — иначе говоря, все эти методы могут быть сведены к нескольким аксиомам и правилам вывода. Поэтому, казалось бы, разумно предположить, что указанных аксиом и правил вполне хватит для разрешения всех математических проблем, которые могут быть сформулированы в пределах данной системы. Ниже будет показано, что дело обстоит не так. В обеих упомянутых системах имеются сравнительно простые задачи из теории обычных целых чисел, которые не могут быть решены на базе этих аксиом». [9] Выборочный перевод автора.

Далее Гёдель объясняет, что такая ситуация обусловлена отнюдь не какими-то специфическими особенностями двух упомянутых систем, но имеет место для обширного класса математических систем.

Что имеется в виду под «обширным классом» математических систем? Это выражение интерпретировалось по-разному, и соответственно по-разному обобщалась теорема Гёделя. Как ни странно, одно из самых простых и доступных для неспециалиста объяснений остается наименее известным. Это тем более удивительно, что на такое объяснение указывал и сам Гёдель во вводной части своей первой работы. К нему мы сейчас и обратимся.

Рассмотрим систему аксиом со следующими свойствами. Прежде всего пусть у нас имеются имена для различных множеств положительных целых чисел, причем все эти «именуемые», или допускающие наименование, множества мы можем расположить в виде бесконечной последовательности A 1, A 2…, A n … (точно так же, как в системе Фергюссона, рассмотренной в предыдущей главе). Назовем число n индексом именуемого множества А, если А=n. (Таким образом, если, например, множества A 2, A 7и A 13совпадают между собой, то тогда числа 2, 7 и 13 — это все индексы одного и того же множества.) Как и для системы Фергюссона, с каждым числом x и с каждым числом у мы связываем утверждение, записываемое в виде x ∈ A y , которое называется истинным, если x принадлежит А у, и ложным, если x не принадлежит A y . Однако в дальнейшем мы не предполагаем, что утверждения типа x ∈ A y являются единственно возможными утверждениями в данной системе, поскольку могут существовать и другие. Предполагается также, что любое возможное утверждение обязательно классифицируется либо как истинное, либо как ложное.

Каждому утверждению в данной системе присваивается некий кодовый номер, который мы будем называть геделевым номером, причем гёделев номер утверждения x ∈ A y будем обозначать x * y . (Теперь уже нет нужды предполагать, что число x * y состоит из цепочки единиц длиной х, за которой следует цепочка нулей длиной у; сам Гёдель фактически использовал совсем другую кодовую нумерацию. Можно пользоваться самыми разными видами кодовой нумерации, и какой вид оказывался более удобным — это зависит от конкретного вида рассматриваемой нами системы. Так или иначе, для доказательства той общей теоремы, которую мы скоро докажем, нет необходимости вводить какую-то конкретную гёделеву нумерацию.)