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

• Название: Принцесса или тигр
• Автор: Рэймонд Смаллиан
• Жанр: Математика

Задачи по логике

---

Доказуемость и истина

Крупной вехой в истории математической логики стал 1931 г. Именно в этом году Гёдель опубликовал знаменитую теорему о неполноте. Свою эпохальную работу[8] он начинает следующими словами:

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

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

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

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

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

Определенные утверждения в данной системе принимаются как аксиомы; кроме того, вводятся также некие специальные правила, по которым можно на основании этих аксиом доказывать различные другие утверждения. Таким образом, в данной системе имеется иполне определенное свойство утверждения, называемое его доказуемостью.

Далее предполагается, что система правильна в том смысле, что каждое доказуемое в этой системе утверждение является истинным; отсюда, в частности, следует, что если утверждение x Є Aу доказуемо в данной системе, то число х действительно является элементом множества Ау.

Пусть Р — это набор гёделевых номеров всех доказуемых в данной системе утверждений. Пусть опять же для любого множества чисел А его дополнение обозначается символом А (это множество всех чисел, не принадлежащих А). Наконец, через А* мы будем обозначать множество всех чисел х, для которых число x*х принадлежит А. При этом нас будут интересовать системы, для которых выполняются следующие три условия Gi, G2 и G3:

Условие G1. Множество Р допускает наименование в данной системе. Иначе говоря, существует по крайней мере одно число р, для которого Ар представляет собой множество гёделевых номеров доказуемых утверждений. (Для системы Фергюссона таким р было число 8.)

Условие G2. Дополнение любого множества, допускающего наименование в данной системе, также именуемо в этой системе. Иначе говоря, для любого числа х найдется такое число х, для которого множество А* является дополнением множества Ах. (Для системы Фергюссона таким х было число 3х.)

Условие G3. Для любого именуемого множества А множество А* также именуемо в данной системе. Иначе говоря, для любого числа x всегда найдется такое число х*, что множество А, — представляет собой, множество всех чисел n, для которых n*n принадлежит А, (Для системы Фергюссона таким х* было число 3x+1.)

Очевидно, что условия F1, F2 и Fз, характеризующие машину Фергюссона, представляют собой не более чем частные случаи условий G1, G2 и G3. Последние имеют большое значение потому, что они действительно выполняются для самых разнообразных математических систем, в том числе и для тех двух систем, которые рассмотрены в работе Гёделя. Другими словами, оказывается возможным расположить все допускающие наименование множества в виде бесконечной последовательности A1, A2…, An… и ввести для всех утверждений некоторую частную нумерацию Гёделя, причем так, что будут выполняться условия G 1, G2 и G3. В результате все то, что является доказуемым для систем, удовлетворяющих условиям G1, G2 и G3, будет применимо ко многим другим важным системам. Теперь мы можем сформулировать и доказать теорему Гёделя в общей форме.

Теорема G. Для любой правильной системы, удовлетворяющей условиям G1, G2 и G3, должно существовать утверждение, которое является истинным, но недоказуемым в данной системе.

Доказательство теоремы G представляет собой простое обобщение доказательства, которое уже известно читателю для системы Фергюссона. Обозначим через К множество таких чисел х, для которых элемент х*х не принадлежит множеству Р. Поскольку множество Р (согласно условию G1) именуемо в данной системе, то же можно сказать и о его дополнении Р (согласно условию G2), а следовательно, и о множестве Р* (согласно условию G3). Но множество Р* совпадает с множеством К (поскольку Р* — это множество таких чисел х, для которых х* х принадлежит Р, или, другими словами, множество таких чисел х, для которых элемент х*х не принадлежит Р). Таким образом, множество К допускает наименование в данной системе, откуда следует, что К = А* по крайней мере для одного числа k. (Для системы Фергюссона одним из таких чначений k было число 73, другим — число 75.) Таким образом, для любого числа х истинность утверждения x Є Ak равносильна утверждению, что число х*х не принадлежит Р, а это в свою очередь означает, что утверждение x Є Ax недоказуемо (в данной системе). В частности, если мы возьмем в качестве х число k то истинность утверждения k Є A* будет равносильна его недоказуемости в данной системе, что означает либо истинность, но недоказуемость этого утверждения, либо его ложность, но доказуемость в той же системе. Но последняя возможность исключена, поскольку мы предположили, что наша система является правильной; следовательно, указанное утверждение истинно, но недоказуемо в данной системе.

Обсуждение. В своей предыдущей книжке «Как же называется эта книга?» я рассматривал аналогичную ситуацию — остров, все жители которого делятся на рыцарей, которые всегда говорят только правду, и плутов, которые всегда лгут. При этом некоторых рыцарей мы называли признанными рыцарями, а некоторых плутов — отъявленными плутами. (Все рыцари высказывают истинные суждения, а признанные рыцари высказывают утверждения, которые не только истинны, но и доказуемы.) Далее, ни один из жителей острова не может сказать: «Я не рыцарь» — ведь рыцари никогда не лгут и, стало быть, рыцарь не станет говорить, будто он не рыцарь; плут же никогда не скажет о себе правдиво, что он не рыцарь. Именно поэтому ни один из обитателей острова никак не может заявить, что он не рыцарь. Вместе с тем некий островитянин вполне может сказать: «Я непризнанный рыцарь». Противоречия в таком заявлении нет, однако вот что интересно: сказавший это наверняка должен быть рыцарем, но непризнанным рыцарем. Дело в том, что плут никак не может сделать правдивого заявления, что он непризнанный рыцарь (поскольку он и в самом деле им не является); стало быть, говорящий должен быть рыцарем. Но раз он рыцарь, то, значит, должен говорить правду; стало быть, он рыцарь, но, как он сам утверждает, — непризнанный рыцарь. (Точно так же высказывание k Є Ak выдающее свою недоказуемость в данной системе, должно быть истинным, но недоказуемым в этой системе.)