Обсуждение. В своей предыдущей книжке «Как же называется эта книга?» я рассматривал аналогичную ситуацию — остров, все жители которого делятся на рыцарей, которые всегда говорят только правду, и плутов, которые всегда лгут. При этом некоторых рыцарей мы называли признанными рыцарями, а некоторых плутов — отъявленными плутами. (Все рыцари высказывают истинные суждения, а признанные рыцари высказывают утверждения, которые не только истинны, но и доказуемы.) Далее, ни один из жителей острова не может сказать: «Я не рыцарь» — ведь рыцари никогда не лгут и, стало быть, рыцарь не станет говорить, будто он не рыцарь; плут же никогда не скажет о себе правдиво, что он не рыцарь. Именно поэтому ни один из обитателей острова никак не может заявить, что он не рыцарь. Вместе с тем некий островитянин вполне может сказать: «Я непризнанный рыцарь». Противоречия в таком заявлении нет, однако вот что интересно: сказавший это наверняка должен быть рыцарем, но непризнанным рыцарем. Дело в том, что плут никак не может сделать правдивого заявления, что он непризнанный рыцарь (поскольку он и в самом деле им не является); стало быть, говорящий должен быть рыцарем. Но раз он рыцарь, то, значит, должен говорить правду; стало быть, он рыцарь, но, как он сам утверждает, — непризнанный рыцарь. (Точно так же высказывание k Є Ak выдающее свою недоказуемость в данной системе, должно быть истинным, но недоказуемым в этой системе.)
Для любого заданного утверждения 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. Может ли читатель сообразить, как это сделать?
В своей монографии «Теория формальных систем»[! Смальян Р. Теория формальных систем. Пер. с англ. — М.: Наука, 1981.!] (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. Высказывание, которое утверждает собственную недоказуемость, можно сравнить со словами того обитателя острова рыцарей и плутов, который заявляет, будто он непризнанный рыцарь, точно гак же высказывание, утверждающее свою собственную опровержимость, можно уподобить словам такого обитателя острова, который шявляет, что он отъявленный плут; этот человек и в самом деле мошенник, но неотъявленный. (Предоставляю читателю возможность доказать это самому.)
Решения
Машины, рассказывающие о себе
Утверждения Гёделя и теорема Тарского
Рассмотрим теперь систему, удовлетворяющую условиям 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 в данной системе и не доказуемо, и неопровержимо. (Такое утверждение называется неразрешимым в данной системе.)В своей монографии «Теория формальных систем»[! Смальян Р. Теория формальных систем. Пер. с англ. — М.: Наука, 1981.!] (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. Высказывание, которое утверждает собственную недоказуемость, можно сравнить со словами того обитателя острова рыцарей и плутов, который заявляет, будто он непризнанный рыцарь, точно гак же высказывание, утверждающее свою собственную опровержимость, можно уподобить словам такого обитателя острова, который шявляет, что он отъявленный плут; этот человек и в самом деле мошенник, но неотъявленный. (Предоставляю читателю возможность доказать это самому.)
Решения
1. Предположим, система действительно удовлетворяет условию G3. Пусть S—любое множество, именуемое в данной системе. Тогда, согласно условию G3, множество S* тоже именуемо в этой системе. Значит, существует такое число b, для которого Аb = 8*. Далее, число х принадлежит множеству S* только в том случае, если число х*х принадлежит множеству S.
Поэтому х принадлежит множеству Аb только в том случае, если х*х принадлежит S. В частности, если в качестве х выбрать число b, то это число принадлежит; множеству Ab, только в том случае, если число b* принадлежит множеству S. Кроме того, число b принадлежит Ab в том и только том случае, если утверждение b Є Аb истинно. Поэтому утверждение b Є Аb истинно тогда и только тогда, когда b*b принадлежит множеству S. Но число b*b есть гёделев номер утверждения b Є Ab. Следовательно, мы имеем, что утверждение b Є Ab будет истинным тогда и только тогда, когда гёделев номер этого утверждения принадлежит множеству S. Итак, если утверждение b Є A истинно, то его гёделев номер принадлежит S; если ж это утверждение ложно, то его гёделев номер принадлежит S. Таким образом, утверждение b Є A является гёделевым утверждением для S.
2. В системе Фергюссона при любом заданном числе n множество а3n+i представляет собой множество An*. Поэтому множество A301 — это есть множество A Воспользуемся теперь результатом предыдущей задачи, положив b равным 301. Тогда утверждение 301 Є А301 будет гёделевым утверждением для множества Аb. Вообще для любого числа n, выбрав d = 3n+1, мы получим, что утверждение b Є Ab, является гёделевым для множества Ab в системе Фергюссона.
3. Да. Предположим, что данная система является гёделевой и что условия G1 и G2 выполняются; предположим также, что система правильна. Согласно условию G1, множество R именуемо в этой системе; поэтому, согласно условию G1, именуемо также и множество Р — дополнение R. Тогда, поскольку исходная система гёделева, то существует гёделево утверждение X для Р. Это означает, что X истинно в том и только том случае, если гёделев номер утверждения X принадлежит Р. Однако если гёделев номер утверждения X принадлежит Р, то тем самым он не принадлежит R, а это значит, что утверждение X недоказуемо. Таким образом, гёделево утверждение для R — это ни больше ни меньше как утверждение, которое истинно в том и только том случае, если оно недоказуемо в (данной системе, а такое утверждение (как мы уже видели) как раз и должно быть истинным, но недоказуемым в этой системе (если система правильна).
Итак, фактически суть доказательства Гёделя состоит в построении гёделева утверждения для множества Р.
4. Очевидно, что всякое утверждение X является гёделевым утверждением для множества Т, потому что если X истинно, то его гёделев номер принадлежит Т, а если оно ложно, то его гёделев номер не принадлежит Т. (cследовательно, ни одно утверждение не может оказаться гёделевым для Т, потому что не может существовать ни истинного утверждения Х, гёделев номер которого принадлежал бы множеству Т, ни ложного утверждения X, гёделев номер которого не принадлежал бы множеству Т.
Читателю будет поучительно убедиться, что для любого множества чисел А и для любого утверждения X это X может являться гёделевым утверждением либо для А, либо для А, но никак не для обоих множеств сразу.
5. Рассмотрим сначала произвольную систему, удовлетворяющую условию G3. В соответствии с решением задачи 1 для любого множества, именуемого в рамках данной системы, существует гёделево утверждение. Кроме того, согласно решению задачи 4 не существует гёделева утверждения для множества Т. Следовательно, если система удовлетворяет условию G3, то множество Т не допускает имени в этой системе. Если система удовлетворяет к тому же условию G3, то множество Т не именуемо в этой системе — потому что ли бы это было так, то тогда, согласно условию G3, допускало бы имя и его дополнение Т, что на самом деле не имеет места. Это доказывает, что в системе, удовлетворяющей условиям G2 и G3, множество Т не именуемо.
Окончательно:
а) если выполняется условие G 3, то множество Т не именуемо в данной системе;
б) если выполняются условия G1 и G3, то ни множество Т, ни его дополнение Т в этой системе не именуемы.
6. Как только теорема Т доказана, теорему G можно получить следующим образом.
Предположим, что мы имеем правильную систему, удовлетворяющую условиям G1; G2 и G3 — Из условий G2 и G3, согласно теореме Т, следует, что множество Т не допускает имени в данной системе. Но, согласно условию G1, множество Р допускает имя в данной системе. Поэтому раз Р допускает имя в рамка системы, а Т нет, то, значит, это должны быть разные множества. Однако каждое число, принадлежащее множеству Р, входит также и в множество Т, поскольку нам дано, что система является правильной в том смысле, что каждое доказуемое утверждение в ней истинно. Стало быть, поскольку множество Т не совпадает с множеством Р, в множестве Т должно существовать хотя бы одно число n, которое не принадлежит Р. Вместе с тем, поскольку это n принадлежит Т, оно должно быть гёделевым номером некоего истинного утверждения X. Но поскольку это число n не принадлежит Р, то утверждение X должно быть недоказуемым в данной системе. Значит, утверждение X истинно, но недоказуемо в данной системе. Итак, теорема G действительно имеет место.
7. Пусть теперь нам даны условия G1 и G3.
а. Согласно условию G1, множество R именуемо в данной системе. Тогда, согласно условию G5, множество R* также допускает имя в рамках этой системы. Следовательно, существует такое число Н, при котором Ah = R*. Далее, по определению множества R* число х принадлежит R* в том и только том случае, если число х*х принадлежит множеству R. Поэтому для любого а это х принадлежит Ah в том и только том случае, если число х*х входит в множество R. В частности, если к качестве x выбратьh, то число h будет принадлежать, Ah, в том и только том случае, если число h*h входит в R. Далее, h принадлежит Ah в том и только том случае, если утверждение h Є Ah, истинно. С другой стороны, поскольку число h*h есть гёделев номер утверждения h Є Ah, то h*h входит в R в том и только в том случае, если утверждение h Є Ah опровержимо. Значит, утверждение h Є Ah истинно в том и только в том случае, если оно опровержимо. Отсюда следует, что данное утверждение либо истинно и опровержимо, либо ложно и неопровержимо. Однако оно не может быть истинным и опровержимым, поскольку наша система правильна по условию задачи; следовательно, оно должно быть ложным и неопровержимым. Наконец, раз это утверждение ложно, оно не может быть и доказуемым (опять же потому, что система правильна). Таким образом, утверждение h Є Ah, недоказуемо и неопровержимо (и, кроме того, оно ложно).
б. Пусть нам дано, что множество а10 — это К и что А5n при любом числе n совпадает с множеством An*. Значит, A50 есть множество R*. Тогда, согласно решению «а», если принять h = 50, то утверждение 50 Є A50 будет недоказуемым и неопровержимым. Кроме того, это утверждение будет ложным.
Поэтому х принадлежит множеству Аb только в том случае, если х*х принадлежит S. В частности, если в качестве х выбрать число b, то это число принадлежит; множеству Ab, только в том случае, если число b* принадлежит множеству S. Кроме того, число b принадлежит Ab в том и только том случае, если утверждение b Є Аb истинно. Поэтому утверждение b Є Аb истинно тогда и только тогда, когда b*b принадлежит множеству S. Но число b*b есть гёделев номер утверждения b Є Ab. Следовательно, мы имеем, что утверждение b Є Ab будет истинным тогда и только тогда, когда гёделев номер этого утверждения принадлежит множеству S. Итак, если утверждение b Є A истинно, то его гёделев номер принадлежит S; если ж это утверждение ложно, то его гёделев номер принадлежит S. Таким образом, утверждение b Є A является гёделевым утверждением для S.
2. В системе Фергюссона при любом заданном числе n множество а3n+i представляет собой множество An*. Поэтому множество A301 — это есть множество A Воспользуемся теперь результатом предыдущей задачи, положив b равным 301. Тогда утверждение 301 Є А301 будет гёделевым утверждением для множества Аb. Вообще для любого числа n, выбрав d = 3n+1, мы получим, что утверждение b Є Ab, является гёделевым для множества Ab в системе Фергюссона.
3. Да. Предположим, что данная система является гёделевой и что условия G1 и G2 выполняются; предположим также, что система правильна. Согласно условию G1, множество R именуемо в этой системе; поэтому, согласно условию G1, именуемо также и множество Р — дополнение R. Тогда, поскольку исходная система гёделева, то существует гёделево утверждение X для Р. Это означает, что X истинно в том и только том случае, если гёделев номер утверждения X принадлежит Р. Однако если гёделев номер утверждения X принадлежит Р, то тем самым он не принадлежит R, а это значит, что утверждение X недоказуемо. Таким образом, гёделево утверждение для R — это ни больше ни меньше как утверждение, которое истинно в том и только том случае, если оно недоказуемо в (данной системе, а такое утверждение (как мы уже видели) как раз и должно быть истинным, но недоказуемым в этой системе (если система правильна).
Итак, фактически суть доказательства Гёделя состоит в построении гёделева утверждения для множества Р.
4. Очевидно, что всякое утверждение X является гёделевым утверждением для множества Т, потому что если X истинно, то его гёделев номер принадлежит Т, а если оно ложно, то его гёделев номер не принадлежит Т. (cследовательно, ни одно утверждение не может оказаться гёделевым для Т, потому что не может существовать ни истинного утверждения Х, гёделев номер которого принадлежал бы множеству Т, ни ложного утверждения X, гёделев номер которого не принадлежал бы множеству Т.
Читателю будет поучительно убедиться, что для любого множества чисел А и для любого утверждения X это X может являться гёделевым утверждением либо для А, либо для А, но никак не для обоих множеств сразу.
5. Рассмотрим сначала произвольную систему, удовлетворяющую условию G3. В соответствии с решением задачи 1 для любого множества, именуемого в рамках данной системы, существует гёделево утверждение. Кроме того, согласно решению задачи 4 не существует гёделева утверждения для множества Т. Следовательно, если система удовлетворяет условию G3, то множество Т не допускает имени в этой системе. Если система удовлетворяет к тому же условию G3, то множество Т не именуемо в этой системе — потому что ли бы это было так, то тогда, согласно условию G3, допускало бы имя и его дополнение Т, что на самом деле не имеет места. Это доказывает, что в системе, удовлетворяющей условиям G2 и G3, множество Т не именуемо.
Окончательно:
а) если выполняется условие G 3, то множество Т не именуемо в данной системе;
б) если выполняются условия G1 и G3, то ни множество Т, ни его дополнение Т в этой системе не именуемы.
6. Как только теорема Т доказана, теорему G можно получить следующим образом.
Предположим, что мы имеем правильную систему, удовлетворяющую условиям G1; G2 и G3 — Из условий G2 и G3, согласно теореме Т, следует, что множество Т не допускает имени в данной системе. Но, согласно условию G1, множество Р допускает имя в данной системе. Поэтому раз Р допускает имя в рамка системы, а Т нет, то, значит, это должны быть разные множества. Однако каждое число, принадлежащее множеству Р, входит также и в множество Т, поскольку нам дано, что система является правильной в том смысле, что каждое доказуемое утверждение в ней истинно. Стало быть, поскольку множество Т не совпадает с множеством Р, в множестве Т должно существовать хотя бы одно число n, которое не принадлежит Р. Вместе с тем, поскольку это n принадлежит Т, оно должно быть гёделевым номером некоего истинного утверждения X. Но поскольку это число n не принадлежит Р, то утверждение X должно быть недоказуемым в данной системе. Значит, утверждение X истинно, но недоказуемо в данной системе. Итак, теорема G действительно имеет место.
7. Пусть теперь нам даны условия G1 и G3.
а. Согласно условию G1, множество R именуемо в данной системе. Тогда, согласно условию G5, множество R* также допускает имя в рамках этой системы. Следовательно, существует такое число Н, при котором Ah = R*. Далее, по определению множества R* число х принадлежит R* в том и только том случае, если число х*х принадлежит множеству R. Поэтому для любого а это х принадлежит Ah в том и только том случае, если число х*х входит в множество R. В частности, если к качестве x выбратьh, то число h будет принадлежать, Ah, в том и только том случае, если число h*h входит в R. Далее, h принадлежит Ah в том и только том случае, если утверждение h Є Ah, истинно. С другой стороны, поскольку число h*h есть гёделев номер утверждения h Є Ah, то h*h входит в R в том и только в том случае, если утверждение h Є Ah опровержимо. Значит, утверждение h Є Ah истинно в том и только в том случае, если оно опровержимо. Отсюда следует, что данное утверждение либо истинно и опровержимо, либо ложно и неопровержимо. Однако оно не может быть истинным и опровержимым, поскольку наша система правильна по условию задачи; следовательно, оно должно быть ложным и неопровержимым. Наконец, раз это утверждение ложно, оно не может быть и доказуемым (опять же потому, что система правильна). Таким образом, утверждение h Є Ah, недоказуемо и неопровержимо (и, кроме того, оно ложно).
б. Пусть нам дано, что множество а10 — это К и что А5n при любом числе n совпадает с множеством An*. Значит, A50 есть множество R*. Тогда, согласно решению «а», если принять h = 50, то утверждение 50 Є A50 будет недоказуемым и неопровержимым. Кроме того, это утверждение будет ложным.
Машины, рассказывающие о себе
Рассмотрим теперь доказательство Гёделя с несколько иной точки зрения, которая позволяет увидеть основную идею особенно ярко.
Возьмем четыре символа Р, N, А, — , и рассмотрим всевозможные комбинации этих символов. Произвольную комбинацию указанных символов мы будем называть выражением. Например, выражением является комбинация Р-NA-Р; точно так же выражением будет комбинация — PN-А-Р-. Некоторым выражениям мы будем приписывать определенный смысл — такие выражения в дальнейшем будут называться утверждениями.
Предположим, что у нас имеется машина, которая может выдавать нам (распечатывать) одни выражения и не может выдавать другие. При этом те выражения, которые машина может напечатать, мы будем называть Допускающими распечатку. Предполагается, что любое выражение, которое может напечатать машина, рано или поздно обязательно будет ею напечатано. Если нам задано выражение X и мы хотим высказать суждение, что X допускает распечатку, то будем записывать это как Р-X. Так, например, запись Р-ANN означает, что выражение ANN допускает распечатку (при этом неважно, является ли это утверждение истинным или ложным). Если же мы хотим сказать, что выражение X не допускает распечатки, то будем писать NP-X. (Символ N — от англ. not — отрицание «не», а символ Р — от англ. printable — допускающий распечатку.) Таким образом, запись вида NP-X следует читать как «не допускающее распечатки X», или, что по существу то же самое, «выражение X не допускает распечатки».
Ассоциатом выражения X мы будем называть выражение X–X; при этом вместо слова «ассоциат» нами будет использоваться символ А (от англ. associate). Таким образом, если нам задано некоторое выражение X и мы хотим сказать, что ассоциат выражения X допускает распечатку, то будем записывать это как РА-X. Если мы теперь хотим сказать, что ассоциат утверждения X не допускает распечатки, то это будет записываться как NPA-X.
Читателя, быть может, удивляет, что мы используем тире в качестве своеобразного символа. В самом деле, почему, когда нам нужно высказать суждение о том, что выражение X допускает распечатку, вместо записи Р-X не писать просто РХ? Это делается для того, чтобы избежать определенной двусмысленности. В самом деле, что, например, может означать запись PAN, если мы откажемся от тире? Она может означать либо что ассоциат выражения N допускает распечатку, либо что допускает распечатку выражение AN. Если же мы пользуемся тире, то подобной двусмысленности не возникает. Так, если мы хотим сказать, что ассоциат выражения N допускает распечатку, то записываем этот факт как РА-N; если же хотим сказать, что допускает распечатку выражение AN, то пишем Р-AN. Предположим теперь, нам нужно сказать, что выражение — X допускает распечатку. Правильно ли будет записать эту фразу как Р-Х? Нет, ведь запись Р-X означает, что выражение X допускает распечатку. Поэтому чтобы сказать, что допускает распечатку выражение — X, нужно написать Р-X.
Рассмотрим еще несколько примеров: запись Р- означает, что «-» допускает распечатку, запись РА- означает, что выражение (ассоциат выражения-) допускает распечатку; запись Р- также означает, что «-» допускает распечатку; запись NРА-Р-А означает, что ассоциат выражения — Р-А не допускает распечатки, или, другими словами, что не допускает распечатки выражение — Р-А-Р-А. То же самое означает и запись вида NP-Р-А-Р-А.
Утверждением будем называть любое выражение одного из следующих четырех типов: Р-X, NP-X, РА-X или NPA-X, где X — любое выражение. Утверждение Р-X мы будем называть истинным, если X допускает распечатку, и ложным, если X с допускает распечатки. Утверждение NP-X мы будем называть истинным, если X не допускает распечатки, и ложным, если X эту распечатку допускает, утверждение РА-X будет называться истинным, если ассоциат выражения X допускает распечатку, и ложным, если ассоциат этого X распечатки не допускает. Наконец, утверждение NA-X мы будем называть истинным, если ассоциат выражения X не допускает распечатки, и ложным, если ассоциат этого X распечатку допускает. Итак, мы дали точное определение истинности и ложности для утверждений всех четырех видов. Отсюда следует, что для любого выражения X справедливы:
Правило 1. Утверждение Р-X истинно тогда и только тогда, когда выражение X допускает распечатку (на машине).
Правило 2. Утверждение РА-X истинно тогда и только тогда, когда выражение X–X допускает распечатку.
Правило 3. Утверждение NP-X истинно тогда и только тогда, когда выражение X не допускает распечатки.
Правило 4. Утверждение NPA-X истинно тогда и только тогда, когда выражение X–X не допускает распечатки
Удивительное дело! Машина печатает утверждения, которые представляют собой не что иное, как суждения о том, что она сама может и что не может напечатать! В этом смысле машина говорит о себе (или точнее, печатает утверждения о самой себе).
Пусть теперь нам известно, что машина на 100 % точна, то есть она не может выдать нам ложное утверждение, печатая только истинные утверждения. Отсюда вытекает ряд следствий. Например, если машина в один прекрасный день напечатает утверждение Р-X, то, значит, она должна напечатать и выражение X, потому что раз она может напечатать утверждение Р-X, то, стало быть, это утверждение истинно, а это означает, что выражение X допускает распечатку. Значит, действительно, машина рано или поздно должна распечатать выражение X.
Аналогично, если машина выдаст нам утверждение РА-X, тогда (поскольку утверждение РА-X должно быть истинным) она должна напечатать нам также и выражение X–X. Помимо этого, если машина напечатает утверждение NP-X, тогда она не сможет напечатать утверждение Р-X, поскольку эти два высказывания не могут одновременно являться истинными: ведь первое из них утверждает, что машина не может напечатать выражение X, а второе — что машина может его напечатать.
Следующая задача высвечивает идею Гёделя так хорошо, что лучше трудно себе представить.
1. На редкость гёделева задача.
Найдите истинное утверждение, которое машина не может напечатать!
2. Дважды гёделева головоломка.
Все исходные условия остаются прежними — и, в частности, то, что машина абсолютно точна. Пусть у нас имеются утверждение X и утверждение Y; одно из них является истинным, но не допускающим распечатки; однако, пользуясь лишь условиями, вытекающими из правил 1–4, мы не можем сказать, какое именно это утверждение, X или Y. Можете ли вы найти такие утверждения X и Y? (Подсказка: найти такие утверждения X и Y, чтобы утверждение X говорило нам о том, что Y допускает распечатку, а в утверждении Y говорилось бы о том, что X не допускает распечатки. Существуют два способа построения таких утверждений, причем оба они связаны с законами Фергюссона!)
3. Трижды гёделева проблема.
Построить такие утверждения X, Y и Z, чтобы X говорило о том, что Y допускает распечатку, Y говорило бы о том, что не допускает распечатки, a Z — о том, что X в свою очередь вновь допускает распечатку, и показать, что по крайней мере одно из этих утверждений (правда, нельзя сказать, какое именно) должно быть истинным, но не допускающим распечатки на машине.
4. Найдите утверждение, которое было бы ложным, но неопровержимым.
5. Имеются такие два утверждения X и Y, что одно из них (правда, нам не известно, какое именно) должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (мы не знаем, каким именно). Такие пары можно строить двумя способами, и соответственно я предлагаю вашему вниманию две задачи:
а. Найдите такие высказывания X и Y, чтобы X утверждало доказуемость Y, a Y утверждало опровержимость X. Далее, покажите, что одно из них (мы не можем сказать, какое именно) либо истинно, но недоказуемо, либо ложно, но неопровержимо.
б. Найдите такие высказывания X и Y, чтобы Х утверждало недоказуемость Y, а Y утверждало неопровержимость X. Далее покажите, что одно из этих высказываний, X или Y (мы не можем сказать, какое именно), либо истинно, но недоказуемо, либо ложно, но неопровержимо.
Возьмем четыре символа Р, N, А, — , и рассмотрим всевозможные комбинации этих символов. Произвольную комбинацию указанных символов мы будем называть выражением. Например, выражением является комбинация Р-NA-Р; точно так же выражением будет комбинация — PN-А-Р-. Некоторым выражениям мы будем приписывать определенный смысл — такие выражения в дальнейшем будут называться утверждениями.
Предположим, что у нас имеется машина, которая может выдавать нам (распечатывать) одни выражения и не может выдавать другие. При этом те выражения, которые машина может напечатать, мы будем называть Допускающими распечатку. Предполагается, что любое выражение, которое может напечатать машина, рано или поздно обязательно будет ею напечатано. Если нам задано выражение X и мы хотим высказать суждение, что X допускает распечатку, то будем записывать это как Р-X. Так, например, запись Р-ANN означает, что выражение ANN допускает распечатку (при этом неважно, является ли это утверждение истинным или ложным). Если же мы хотим сказать, что выражение X не допускает распечатки, то будем писать NP-X. (Символ N — от англ. not — отрицание «не», а символ Р — от англ. printable — допускающий распечатку.) Таким образом, запись вида NP-X следует читать как «не допускающее распечатки X», или, что по существу то же самое, «выражение X не допускает распечатки».
Ассоциатом выражения X мы будем называть выражение X–X; при этом вместо слова «ассоциат» нами будет использоваться символ А (от англ. associate). Таким образом, если нам задано некоторое выражение X и мы хотим сказать, что ассоциат выражения X допускает распечатку, то будем записывать это как РА-X. Если мы теперь хотим сказать, что ассоциат утверждения X не допускает распечатки, то это будет записываться как NPA-X.
Читателя, быть может, удивляет, что мы используем тире в качестве своеобразного символа. В самом деле, почему, когда нам нужно высказать суждение о том, что выражение X допускает распечатку, вместо записи Р-X не писать просто РХ? Это делается для того, чтобы избежать определенной двусмысленности. В самом деле, что, например, может означать запись PAN, если мы откажемся от тире? Она может означать либо что ассоциат выражения N допускает распечатку, либо что допускает распечатку выражение AN. Если же мы пользуемся тире, то подобной двусмысленности не возникает. Так, если мы хотим сказать, что ассоциат выражения N допускает распечатку, то записываем этот факт как РА-N; если же хотим сказать, что допускает распечатку выражение AN, то пишем Р-AN. Предположим теперь, нам нужно сказать, что выражение — X допускает распечатку. Правильно ли будет записать эту фразу как Р-Х? Нет, ведь запись Р-X означает, что выражение X допускает распечатку. Поэтому чтобы сказать, что допускает распечатку выражение — X, нужно написать Р-X.
Рассмотрим еще несколько примеров: запись Р- означает, что «-» допускает распечатку, запись РА- означает, что выражение (ассоциат выражения-) допускает распечатку; запись Р- также означает, что «-» допускает распечатку; запись NРА-Р-А означает, что ассоциат выражения — Р-А не допускает распечатки, или, другими словами, что не допускает распечатки выражение — Р-А-Р-А. То же самое означает и запись вида NP-Р-А-Р-А.
Утверждением будем называть любое выражение одного из следующих четырех типов: Р-X, NP-X, РА-X или NPA-X, где X — любое выражение. Утверждение Р-X мы будем называть истинным, если X допускает распечатку, и ложным, если X с допускает распечатки. Утверждение NP-X мы будем называть истинным, если X не допускает распечатки, и ложным, если X эту распечатку допускает, утверждение РА-X будет называться истинным, если ассоциат выражения X допускает распечатку, и ложным, если ассоциат этого X распечатки не допускает. Наконец, утверждение NA-X мы будем называть истинным, если ассоциат выражения X не допускает распечатки, и ложным, если ассоциат этого X распечатку допускает. Итак, мы дали точное определение истинности и ложности для утверждений всех четырех видов. Отсюда следует, что для любого выражения X справедливы:
Правило 1. Утверждение Р-X истинно тогда и только тогда, когда выражение X допускает распечатку (на машине).
Правило 2. Утверждение РА-X истинно тогда и только тогда, когда выражение X–X допускает распечатку.
Правило 3. Утверждение NP-X истинно тогда и только тогда, когда выражение X не допускает распечатки.
Правило 4. Утверждение NPA-X истинно тогда и только тогда, когда выражение X–X не допускает распечатки
Удивительное дело! Машина печатает утверждения, которые представляют собой не что иное, как суждения о том, что она сама может и что не может напечатать! В этом смысле машина говорит о себе (или точнее, печатает утверждения о самой себе).
Пусть теперь нам известно, что машина на 100 % точна, то есть она не может выдать нам ложное утверждение, печатая только истинные утверждения. Отсюда вытекает ряд следствий. Например, если машина в один прекрасный день напечатает утверждение Р-X, то, значит, она должна напечатать и выражение X, потому что раз она может напечатать утверждение Р-X, то, стало быть, это утверждение истинно, а это означает, что выражение X допускает распечатку. Значит, действительно, машина рано или поздно должна распечатать выражение X.
Аналогично, если машина выдаст нам утверждение РА-X, тогда (поскольку утверждение РА-X должно быть истинным) она должна напечатать нам также и выражение X–X. Помимо этого, если машина напечатает утверждение NP-X, тогда она не сможет напечатать утверждение Р-X, поскольку эти два высказывания не могут одновременно являться истинными: ведь первое из них утверждает, что машина не может напечатать выражение X, а второе — что машина может его напечатать.
Следующая задача высвечивает идею Гёделя так хорошо, что лучше трудно себе представить.
1. На редкость гёделева задача.
Найдите истинное утверждение, которое машина не может напечатать!
2. Дважды гёделева головоломка.
Все исходные условия остаются прежними — и, в частности, то, что машина абсолютно точна. Пусть у нас имеются утверждение X и утверждение Y; одно из них является истинным, но не допускающим распечатки; однако, пользуясь лишь условиями, вытекающими из правил 1–4, мы не можем сказать, какое именно это утверждение, X или Y. Можете ли вы найти такие утверждения X и Y? (Подсказка: найти такие утверждения X и Y, чтобы утверждение X говорило нам о том, что Y допускает распечатку, а в утверждении Y говорилось бы о том, что X не допускает распечатки. Существуют два способа построения таких утверждений, причем оба они связаны с законами Фергюссона!)
3. Трижды гёделева проблема.
Построить такие утверждения X, Y и Z, чтобы X говорило о том, что Y допускает распечатку, Y говорило бы о том, что не допускает распечатки, a Z — о том, что X в свою очередь вновь допускает распечатку, и показать, что по крайней мере одно из этих утверждений (правда, нельзя сказать, какое именно) должно быть истинным, но не допускающим распечатки на машине.
Две машины, толкующие о себе, а также друг о друге
Добавим к четырем нашим символам еще один — символ R. Таким образом, теперь у нас пять символов: Р, R, N, А, — . Пусть нам даны две машины, М1 и М2, каждая из которых может печатать различные выражения, составленные из этих пяти символов. При этом под символом Р в данном случае мы будем подразумевать «допускающий распечатку первой машиной», а под символом R — «допускающий распечатку второй машиной». Таким образом, запись Р-X означает, что выражение X допускает распечатку первой машиной, а запись R-X — что выражение X допускает распечатку второй машиной. Запись РА-X означает, что ассоциат выражения X допускает распечатку первой машиной, а запись RA-X показывает, что ассоциат выражения X допускает распечатку второй машиной. Наконец, «фразы» NP-X, NR-X, NPA-X, NRA-X говорят соответственно о следующем: выражение X не допускает распечатки первой машиной; выражение X не допускает распечатки второй машиной; выражение X–X не допускает распечатки первой машиной; выражение X–X не допускает распечатки второй машиной. Под утверждением мы будем теперь понимать любое выражение одного из следующих восьми типов: Р-X, R-X, NP-X, NR-X, РА-Х, RA-X, NPA-X, NRA-X. Кроме того, пусть нам известно, что первая машина печатает только истинные утверждения, а вторая — только ложные. Условимся называть некоторое утверждение доказуемым в том и только том случае, если оно допускает распечатку первой машиной, и ложным — в том и только том случае, если оно: может быть напечатано второй машиной. Таким образом, символ Р означает «доказуемый» (от англ. provable), а символ R — «опровержимый» (от англ. refutable).4. Найдите утверждение, которое было бы ложным, но неопровержимым.
5. Имеются такие два утверждения X и Y, что одно из них (правда, нам не известно, какое именно) должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (мы не знаем, каким именно). Такие пары можно строить двумя способами, и соответственно я предлагаю вашему вниманию две задачи:
а. Найдите такие высказывания X и Y, чтобы X утверждало доказуемость Y, a Y утверждало опровержимость X. Далее, покажите, что одно из них (мы не можем сказать, какое именно) либо истинно, но недоказуемо, либо ложно, но неопровержимо.
б. Найдите такие высказывания X и Y, чтобы Х утверждало недоказуемость Y, а Y утверждало неопровержимость X. Далее покажите, что одно из этих высказываний, X или Y (мы не можем сказать, какое именно), либо истинно, но недоказуемо, либо ложно, но неопровержимо.