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

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

Пусть P — это набор гёделевых номеров всех доказуемых в данной системе утверждений. Пусть опять же для любого множества чисел А его дополнение обозначается символом A̅ (это множество всех чисел, не принадлежащих А ). Наконец, через А * мы будем обозначать множество всех чисел х, для которых число x * х принадлежит А. При этом нас будут интересовать системы, для которых выполняются следующие три условия G 1, G 2и G 3:

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

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

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

Очевидно, что условия F 1, F 2и F 3, характеризующие машину Фергюссона, представляют собой не более чем частные случаи условий G 1, G 2и G 3. Последние имеют большое значение потому, что они действительно выполняются для самых разнообразных математических систем, в том числе и для тех двух систем, которые рассмотрены в работе Гёделя. Другими словами, оказывается возможным расположить все допускающие наименование множества в виде бесконечной последовательности A 1, A 2…, A n … и ввести для всех утверждений некоторую частную нумерацию Гёделя, причем так, что будут выполняться условия G 1, G 2и G 3. В результате все то, что является доказуемым для систем, удовлетворяющих условиям G 1, G 2и G 3, будет применимо ко многим другим важным системам. Теперь мы можем сформулировать и доказать теорему Гёделя в общей форме.

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

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

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

Рассмотрим теперь систему, удовлетворяющую условиям G 2; и G 3(условие G 1пока несущественно). Ранее мы определили P как множество гёделевых номеров всех утверждений, доказуемых в данной системе; пусть теперь Т будет множеством гёделевых номеров всех истинных утверждений в этой системе. В 1933 г. логик Альфред Тарский поставил вопрос: «Именуемо ли множество Т в данной системе или нет?» — и ответил на него. Ответ может быть получен на основе лишь условий G 2и G 3. Однако, прежде чем говорить об этом, обратимся сначала к вопросу не меньшей важности — о системах, которые удовлетворяют по крайней мере условию G 3.