Принцесса или тигр

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

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

Для любого заданного утверждения X и любого множества положительных целых чисел А мы будем называть X гёделевым утверждением для A, если либо X истинно и его гёделев номер принадлежит A, либо X ложно и его гёделев номер не принадлежит A. (Подобное утверждение можно представлять себе как высказывание о том, что его собственный гёделев номер принадлежит A: если это утверждение истинно, то его гёделев номер действительно принадлежит A; если же оно ложно, то его гёделев номер не принадлежит A.) Далее, мы будем называть систему гёделевой в том случае, если для каждого множества Л, допускающего наименование в этой системе, существует хотя бы одно гёделево утверждение для A.

При этом самым существенным для нас пунктом является следующая теорема.

Теорема С. Если система удовлетворяет условию G3, то эта система является гёделевой.

1. Докажите теорему С.

2. В качестве частного случая рассмотрите систему Фергюссона. Найдите гёделево утверждение для множества А100

3. Предположим, что некоторая система является гёделевой (даже если она и не удовлетворяет условию G3). Если эта система правильна и удовлетворяет условиям G1, и G2, то обязательно ли она содержит утверждение, которое является истинным, но недоказуемым в данной системе?

4. Пусть Т—множество гёделевых номеров всех истинных утверждений. Существует ли гёделево утверждение для Т? Существует ли гёделево утверждение для множества Т, то есть дополнения Т?

Вот теперь мы наконец можем ответить и на вопрос, поставленный Тарским. В самой общей форме теорема Тарского формулируется следующим образом:

Теорема Т. Для любой заданной системы, удовлетворяющей условиям G 2 и G3, множество Т гёделевых номеров истинных утверждений не именуемо в данной системе.

Примечание. Иногда слово «именуемо» заменяется словом определимо», в результате чего теорему Т формулируют так: для достаточно богатой системы истинность в ее рамках не определима в пой системе.

5. Докажите теорему Т.

6. Следует отметить, что, доказав теорему Т, мы сразу и в качестве непосредственного следствия получаем теорему G. Может ли читатель сообразить, как это сделать?

Те системы, которые, как доказал Гёдель, являются неполными, обладают также следующим свойством: с каждым утверждением X связано утверждение X', о называется отрицанием X, которое истинно в том только том случае, если утверждение X ложно. Дале, если X' — отрицание некоего утверждения X — доказуемо в данной системе, то само утверждение X называется опровержимым в данной системе. Если предположить, что система правильна, то ни одно ложно, утверждение в этой системе не будет доказуемо и ни одно истинное утверждение не будет в ней опровержимо. Ранее мы убедились, что условия G1, G2 и G3 влекут за собой существование некоего гёделева утверждения, или высказывания, G для множества, также что такое утверждение G является истинным, не. недоказуемым в данной системе (предполагая, конечно, что система правильна). Но поскольку G истинно, оно не может быть опровержимым в этой системе (опять, же в предположении правильности системы). Значит утверждение G в данной системе и не доказуемо, и неопровержимо. (Такое утверждение называется неразрешимым в данной системе.)

В своей монографии «Теория формальных систем» [10] (1960 г.) я рассматривал «двойственную» форму доказательства Гёделя, а именно: что будет, если вместо высказывания, утверждающего свою недоказуемость, построить высказывание, утверждающее свою опровержимость? Более строго эту проблему можно сформулировать так.

Пусть R — множество гёделевых номеров опровержимых утверждений. Предположим, что X — гёделево утверждение для R. Что можно сказать о свойствах утверждения X?

Высказанная здесь идея развивается нами в следующей задаче.

7. Рассмотрим теперь правильную систему, которая удовлетворяет условию G3, а вместо условий G1 G2 потребуем выполнения следующего условия.

Условие G1. Множество R именуемо в данной системе. (Таким образом, мы предполагаем, что система правильна и удовлетворяет условиям G1 и G3.)

а. Показать, что существует такое утверждение, которое нельзя ни доказать, ни опровергнуть в данной системе.

б. Рассмотрим следующий частный случай: пусть нам дано, что а10 — это множество R и что для любого числа n множество А5n представляет собой множество (таких чисел х, для которых число х*х принадлежит Аn (здесь мы имеем частный случай условия G3). Задача теперь состоит в том, чтобы найти утверждение, которое было бы и недоказуемым, и неопровержимым и данной системе, а также определить, является ли это утверждение истинным или ложным.

Примечания.

1. Гёлелев метод получения неразрешимого утверждения сводится к построению гёделева утверждения для множества Р — дополнения R; такое утверждение (его можно рассматривать как высказывание, утверждающее собственную недоказуемость) должно быть истинным, но недоказуемым в данной системе. Двойственный метод сводится к построению гёделева утверждения не для множества Р, а для множества R; такое утверждение (его можно рассматривать как высказывание, утверждающее собственную опровержимость) должно быть ложным, но неопровержимым. (Поскольку оно ложно, оно так же недоказуемо и, следовательно, неразрешимо в данной системе.) Следует отметить, что те системы, которые рассматриваются в оригинальной работе Гёделя, удовлетворяют всем четырем условиям — G1, G2, G3 и G1, так что для построения неразрешимых утверждений можно использовать как тот, как и другой метод.

2. Высказывание, которое утверждает собственную недоказуемость, можно сравнить со словами того обитателя острова рыцарей и плутов, который заявляет, будто он непризнанный рыцарь, точно гак же высказывание, утверждающее свою собственную опровержимость, можно уподобить словам такого обитателя острова, который шявляет, что он отъявленный плут; этот человек и в самом деле мошенник, но неотъявленный. (Предоставляю читателю возможность доказать это самому.)