Гл. 15-16.

Утверждения Гёделя и теорема Тарского

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

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

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

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

Стр. 180

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

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

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

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

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

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

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

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

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

Двойственная форма доказательства Гёдел

Те системы, которые, как доказал Гёдель, являются неполными, обладают также следующим свойством: с

Стр. 181

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

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

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

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

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

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

* Смальян Р. Теория формальных систем. Пер. с англ.— М.: Наука, 1981.

Стр. 182

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

.

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

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

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

Решени

1. Предположим, система действительно удовлетворяет условию G3. Пусть S—любое множество, именуемое в данной системе. Тогда, согласно условию G3, множество S* тоже именуемо в этой системе. Значит, существует такое число b, для которого Аb = 8*. Далее, число х принадлежит множеству S* только в том случае, если число х*х принадлежит множеству S.

Стр. 183

Поэтому х принадлежит множеству А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. Вообще для любого числа л, выбрав d=3n+1, мы получим, что утверждение bЄAb, является гёделевым для множества Ab в системе Фергюссона.

3. Да. Предположим, что данная система является гёделевой и что условия g1 и G2 выполняются; предположим также, что система правильна. Согласно условию gi, множество Р именуемо в этой системе; поэтому, согласно условию G1, именуемо также и множество Р—дополнение Р. Тогда, поскольку исходная система гёделева, то существует гёделево утверждение X для Р. Это означает, что X истинно в том и только том случае, если гёделев номер утверждения X принадлежит Р. Однако если гёделев номер утверждения X принадлежит Р, то тем самым он не принадлежит Р, а это значит, что утверждение X недоказуемо. Таким образом, гёделево утверждение для Р—это ни больше ни меньше как утверждение, которое истинно в

Стр. 184

том и только том случае, если оно недоказуемо в (данной системе, а такое утверждение (как мы уже видели) как раз и должно быть истинным, но недоказуемым в этой системе (если система правильна).

Итак, фактически суть доказательства Гёделя состоит в построении гёделева утверждения для множества Р.

4. Очевидно, что всякое утверждение X является гёделевым утверждением для множества Т, потому что если X истинно, то его гёделев номер принадлежит Т, а если оно ложно, то его гёделев номер не принадлежит Т. (cследовательно, ни одно утверждение не может оказаться гёделевым для Т, потому что не может существовать ни истинного утверждения Х, гёделев номер которого принадлежал бы множеству Т, ни ложного утверждения X, гёделев номер которого не принадлежал бы множеству Т.

Читателю будет поучительно убедиться, что для любого множества чисел А и для любого утверждения X это X может являться гёделевым утверждением либо для А, либо для А, но никак не для обоих множеств сразу.

5. Рассмотрим сначала произвольную систему, удовлетворяющую условию G3. В соответствии с решением задачи 1 для любого множества, именуемого в рамках данной системы, существует гёделево утверждение. Кроме того, согласно решению задачи 4 не существует гёделева утверждения для множества Т. Следовательно, если система удовлетворяет условию G3, то множество Т не допускает имени в этой системе. Если система удовлетворяет к тому же условию g3, то множество Т не именуемо в этой системе — потому что ли бы это было так, то тогда, согласно условию G3, допускало бы имя и его дополнение Т, что на самом деле не имеет места. Это доказывает, что в системе, удовлетворяющей условиям G2 и G3, множество Т не именуемо.

Окончательно: а) если выполняется условие G 3, то множество Т не именуемо в данной системе; б) если

Стр. 185

выполняются условия 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 есть гёделев номер

Стр.186

утверждения hЄAh, то h*h входит в R в том и только в том случае, если утверждение hЄAh опровержимо. Значит, утверждение hЄAh истинно в том и только в том случае, если оно опровержимо. Отсюда следует, что данное утверждение либо истинно и опровержимо, либо ложно и неопровержимо. Однако оно не может быть истинным и опровержимым, поскольку наша система правильна по условию задачи; следовательно, оно должно быть ложным и неопровержимым. Наконец, раз это утверждение ложно, оно не может быть и доказуемым (опять же потому, что система правильна). Таким образом, утверждение hЄAh, недоказуемо и неопровержимо (и, кроме того, оно ложно).

б. Пусть нам дано, что множество а10—это К и что А5n„ при любом числе n совпадает с множеством An*. Значит, A50 есть множество R*. Тогда, согласно решению «а», если принять h=50, то утверждение 50ЄA50 будет недоказуемым и неопровержимым. Кроме того, это утверждение будет ложным.

16 Машины, рассказывающие о себе

Рассмотрим теперь доказательство Гёделя с несколько иной точки зрения, которая позволяет увидеть основную идею особенно ярко.

Возьмем четыре символа Р, N, А, — и рассмотрим всевозможные комбинации этих символов. Произвольную комбинацию указанных символов мы будем называть выражением. Например, выражением является комбинация Р------NA—Р; точно так же выражением будет комбинация —PN------А—Р—. Некоторым выражениям мы будем приписывать определенный смысл — такие выражения в дальнейшем будут называться утверждениями.

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

Стр.187

выражение, которое может напечатать машина, рано или поздно обязательно будет ею напечатано. Если нам задано выражение 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 допускает распечат

Стр.188

ку. Поэтому чтобы сказать, что допускает распечатку выражение—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 не допускает распечатки

Стр.189

Удивительное дело! Машина печатает утверждения, которые представляют собой не что иное, как суждения о том, что она сама может и что не может напечатать! В этом смысле машина говорит о себе (или точнее, печатает утверждения о самой себе).

Пусть теперь нам известно, что машина на 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 говорило

Стр. 190

нам о том, что 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,

Стр. 191

NRA—X. Кроме того, пусть нам известно, что первая машина печатает только истинные утверждения, а вторая—только ложные. Условимся называть некоторое утверждение доказуемым в том и только том случае, если оно допускает распечатку первой машиной, и ложным — в том и только том случае, если оно: может быть напечатано второй машиной. Таким образом, символ Р означает «доказуемый» (от англ. provable), а символ R—«опровержимый» (от англ. refutable).

4. Найдите утверждение, которое было бы ложным, но неопровержимым.

5. Имеются такие два утверждения X и Y, что одно из них (правда, нам не известно, какое именно) должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (мы не знаем, каким именно). Такие пары можно строить двумя способами, и соответственно я предлагаю вашему вниманию две задачи:

а. Найдите такие высказывания X и Y, чтобы X утверждало доказуемость Y, a Y утверждало опровержимость X. Далее, покажите, что одно из них (мы не можем сказать, какое именно) либо истинно, но недоказуемо, либо ложно, но неопровержимо.

б. Найдите такие высказывания X и Y, чтобы Х утверждало недоказуемость Y, а Y утверждало неопровержимость X. Далее покажите, что одно из этих высказываний, X или Y (мы не можем сказать, какое именно), либо истинно, но недоказуемо, либо ложно, но неопровержимо.

6.А теперь рассмотрим задачу с четырьмя неизвестными! Пусть нам требуется найти такие высказывания X, Y, Z и W, чтобы X утверждало доказуемость Y, Y утверждало опровержимость Z. Z утверждало опровержимость W, a W утверждало бы неопровержимость X. Покажите, что одно из этих четырех высказываний должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (хотя, какое из этих четырех будет именно таким высказыванием, сказать невозможно).

Стр.192

Машина Мак-Каллоха и теоремы Гедел

Возможно, читатель уже отметил определенное сходство приведенных выше задач с некоторыми свойствами первой машины Мак-Каллоха. В самом деле, работа этой машины оказывается связанной с теоремой Гёделя, и вот каким образом.

7. Пусть у нас имеется некоторая математическая система, приводящая к набору утверждений, одни из которых называются истинными, а другие — доказуемыми. Мы предполагаем также, что эта система правильная, то есть каждое доказуемое в ней утверждение является истинным. Далее, пусть каждому числу N ставится в соответствие некоторое утверждение, которое мы будем называть утверждением N. Предположим наконец, что наша система удовлетворяет следующим двум условиям.

Условие Мс1. Для любых чисел X и Y, если число X порождает число Y в первой машине Мак-Каллоха, утверждение 8Х истинно тогда и только тогда, если утверждение Y доказуемо. (Напомним, что число 8Х это не 8, умноженное на X, а цифра 8, за которой стоит число X.)

Условие Мс2. Для любого числа X утверждение 9X истинно тогда и только тогда, если утверждение X не является истинным.

Найдите такое число N, при котором утверждение N истинно, но недоказуемо в данной системе.

8. Предположим, что в условии Mс1 говорится не о «первой машине Мак-Каллоха», а о «третьей машине Мак-Каллоха». Попробуем теперь найти такое утверждение, которое было бы истинным, но недоказуемым.

9. Парадокс ли это? Вернемся вновь к задаче 1, однако внесем в нее некоторые изменения. Вместо символа Р мы будем использовать символ В (в силу определенных психологических причин — каких именно, станет ясно из дальнейшего). Определение «утверждения» остается тем же, что и раньше, только на этот раз символ Р везде заменяется на символ В. Таким образом, наши

Стр. 193

утверждения принимают теперь вид: В—X, NB — X, ВА—X, NBA—X. Все утверждения, как и прежде, делятся на две группы — истинные и ложные, причем нам не известно, какие именно из утверждений истинны, а какие — ложны. Далее, вместо машины, печатающей различные утверждения, у нас теперь имеется ученый-логик, который верит одним утверждениям и не верит другим. Когда мы говорим, что наш логик не верит какому-то утверждению, мы вовсе не имеем в виду, что он обязательно сомневается в нем или отвергает его; просто неверно, что он верит в это утверждение. Другими словами, он либо считает его ложным, либо вообще не имеет о нем никакого мнения. Таким образом, символ В (от англ. believe — верить) означает «то, во что верит логик». Тогда для любого выражения X у нас есть четыре интерпретации выражений, содержащих X:

В1: утверждение В — X истинно тогда и только тогда когда логик верит в X;

В2: утверждение NB— X истинно тогда и только тогда когда логик не верит в X;

В3: утверждение ВА—X истинно тогда и только тогда когда логик верит в X—X;

В4: утверждение ВА—X истинно тогда и только тогда, когда логик не верит в X—X.

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

А дальше начинается нечто интересное. Предположим, нам известно об этом ученом-логике следующее. Обстоятельство 1. Наш ученый-логик знает логику не хуже нас с вами. Предположим, что он обладает абсолютными логическими способностями; это означает, что если ему заданы какие-нибудь логические посылки, то он может вывести из них все возможные суждения.

Обстоятельство 2. Логику известно, что выполняются условия В1, В2, В3 и В 4.

Стр.194

Обстоятельство 3. Логик всегда точен, то есть он не верит в ложные утверждения.

Далее, раз логику известно, что имеют место условия В1, В2, В3 и В4, и он может рассуждать так же логично, как мы с вами, ничто не мешает ему провести те же рассуждения, которые провели мы, прежде чем доказали, что утверждение NBA — NBA должно быть истинным. Ясно, что, как только он это проделает, он сразу поверит в утверждение NBA — NBA. Но как только он в него поверит, это утверждение становится опровергнутым, ибо смысл данного утверждения как раз и заключается в том, что наш логик в него не верит,— тем самым в конце концов окажется, что наш логик неточен!

Итак, не приходим ли мы к некоему парадоксу, если принимаем обстоятельства 1, 2 и 3? Конечно, нет, никакого парадокса здесь нет. Просто в последнем абзаце моего рассуждения допущена намеренная неточность! Не могли бы вы ее обнаружить?

Решени

1. Для любого выражения X утверждение NPA — X означает, что ассоциат выражения X не допускает распечатки. В частности, утверждение NPA — NPA означает, что ассоциат выражения NPA не допускает распечатки. Но ассоциатом NPA является само утверждение NPA — NPA! Следовательно, высказывание NPA — NPA утверждает невозможность собственной распечатки; другими словами, это высказывание истинно в том и только том случае, если оно не допускает распечатки. Отсюда следует, что оно либо истинно, но не допускает распечатки, либо ложно, но распечатку допускает. Последний случай исключается, поскольку машина является точной. Следовательно, нам остается лишь первая возможность: данное утверждение истинно, но не может быть напечатано машиной.

2. Выберем в качестве X утверждение Р—NPA — Р— NPA, а в качестве Y —NPA — Р—NPA. Утверждение X (которое имеет вид Р— Y) говорит нам о том, что утверждение Y допускает распечатку. Смысл самого Y

Стр.195

сводится к тому, что ассоциат утверждения Р—NPA не допускает распечатки. Но ассоциатом утверждения Р—NPA является X, значит, Y говорит нам о том, что X не допускает распечатки. (Между прочим, можно построить и другие X и Y, обладающие теми же свойствами: например, если взять в качестве X утверждение РА — NP—РА, а в качестве Y —утверждение NP— РА — NP— РА.)

Таким образом, у нас имеются два утверждения X и Y, причем X утверждает, что Y допускает распечатку, а Y утверждает, что X не допускает распечатки.

Предположим теперь, что X допускает распечатку. Тогда утверждение X окажется истинным, а это будет означать, что утверждение Y допускает распечатку. Но тогда Y окажется истинным, откуда будет следовать, что X распечатки не допускает. Тем самым мы приходим к противоречию, поскольку в данном случае X оказывается одновременно и допускающим, и не допускающим распечатку; следовательно, утверждение X не может быть напечатано. Далее, раз X не допускает распечатки, а Y как раз это и утверждает, то, стало быть, утверждение Y является истинным. Таким образом, мы имеем:

(1) X не допускает распечатки;

(2) Y истинно.

Наконец, утверждение X может быть либо истинным, либо ложным. Если X истинно, тогда, согласно (1), X истинно, но не допускает распечатки. Если же X ложно, тогда Y не допускает распечатки, поскольку само X говорит нам о том, что Y допускает распечатку. Значит, в данном случае Y истинно — согласно (2) — и не допускает распечатки. Итак, либо X, либо Y истинно и не допускает распечатки — однако определить, какое именно из этих двух выражений истинно и не допускает распечатки, оказывается невозможно.

Обсуждение. Описанная ситуация аналогична следующей ситуации, возникшей на острове рыцарей и плутов: пусть на острове имеются два обитателя X и Y, причем X утверждает, что Y —признанный рыцарь, а У утверждает, что X—непризнанный рыцарь. Единственное заключение, которое мы можем сделать—

Стр.196

это, что один из них является непризнанным рыцарем, но кто именно, сказать невозможно.

Подобная ситуация рассматривается в последней главе моей книги «Как же называется эта книга?» в разделе «Дважды гёделевы острова», к которому мы и отсылаем читателя.

3. Положим Z = PA — P—NP—РА.

Далее, положим Y = NP—Z (то есть Y=NP—РА — Р— NP— РА).

Положим, наконец, Х=Р— Y (то есть Х=Р—NP— PA — P—NP—PA).

Из этих выражений сразу ясно: X утверждает, что Y допускает распечатку, а Y говорит нам о том, что Z не допускает распечатки. Что же касается Z, то оно утверждает, что допускает распечатку ассоциат утверждения Р—NP—РА; но ассоциат Р—NP—РА есть утверждение Р—NP—РА — Р—NP—РА, которое в свою очередь и есть X! Итак, Z утверждает, что X допускает распечатку.

Таким образом, X утверждает, что Y допускает распечатку, Y утверждает, что Z не допускает распечатки, a Z утверждает, что распечатку допускает X. Посмотрим теперь, что же из этого следует.

Предположим, что Z допускает распечатку. Тогда Z истинно, откуда следует, что X допускает распечатку, а значит, является истинным; это в свою очередь означает, что Y допускает распечатку и, следовательно, является истинным. Если же Y истинно, то, стало быть, Z не должно допускать распечатки. Таким образом, мы приходим к противоречию: если Z допускает распечатку, то оно ее не допускает. Значит, Z не допускает распечатки, и поэтому Y является истинным. Итак, нам известно, что:

(1) Z не допускает распечатки;

(2) Y истинно.

Далее, X может быть либо истинным, либо ложным. Предположим, что X истинно. Если Z ложно, то тогда X не допускает распечатки, а это означает, что X истинно, но не допускает распечатки. Если же Z истинно, то тогда, поскольку, согласно (1), оно не допускает распечатки, Z истинно, но не допускает

Стр. 197

распечатки. Итак, если X истинно, то либо X, либо Z истинно, но не допускает распечатки. Если же X ложно, тогда Y не допускает распечатки и, следовательно, Y истинно — согласно (2) — и не допускает распечатки.

Итак: если X истинно, то по крайней мере одно из двух утверждений X и Z является истинным, но не допускающим распечатки. Если же X ложно, то истинным, но не допускающим распечатки, оказывается утверждение Y.

4. Пусть S есть утверждение вида RA—RA. Оно говорит нам о том, что ассоциат выражения RA (а ассоциат RA есть само S!) является опровержимым; следовательно, S истинно в том и только том случае, когда S опровержимо. Поскольку S не может быть одновременно и истинным и опровержимым, значит оно ложно, но неопровержимо.

5. а) Выберем в качестве X утверждение Р—RA — Р— RA, а в качестве Y —утверждение RA — Р—RA. Ясно, что X утверждает доказуемость Y, а Y утверждает опровержимость ассоциата выражения Р—RA (ассоциат Р—RA есть в данном случае просто само X). Итак, X утверждает, что Y доказуемо, а Y утверждает, что X опровержимо. (Другой вариант решения — принять за X утверждение РА—R — РА, а за Y —утверждение R — РА—R — РА.)

Далее, если Y доказуемо, то Y истинно, откуда следует, что X опровержимо и, следовательно, ложно, что в свою очередь означает, что Y недоказуемо. Таким образом, допущение о доказуемости Y приводит нас к противоречию; стало быть, оно неверно, и Y недоказуемо. Если же Y недоказуемо, то X ложно. Итак, мы имеем:

(1) X ложно;

(2) Y недоказуемо.

Теперь если Y истинно, то Y истинно и недоказуемо. Если же Y ложно, то X неопровержимо (поскольку Y утверждает опровержимость X), и поэтому в данном случае X ложно, но неопровержимо. Следова-

Стр.198

тельно, либо Y истинно, но недоказуемо, либо X ложно, но неопровержимо.

б) Возьмем в качестве X утверждение NP—NRA — NP—NRA, а в качестве Y —утверждение NRA — NP— NRA (или же за X можно принять NPA — NR — NPA, а за Y — NR — NPA — NR — NPA). Тогда, как читатель может убедиться сам, X утверждает недоказуемость Y, а Y утверждает неопровержимость X. Если X опровержимо, то X ложно; тогда Y доказуемо и, значит, Y истинно, откуда следует, что X неопровержимо. Следовательно, X неопровержимо и, кроме того, Y истинно. Если же X ложно, то X ложно и неопровержимо. Если, наконец, X истинно, то Y недоказуемо; поэтому в данном случае Y будет истинным и недоказуемым.

Обсуждение. По аналогии предположим, что на нашем острове, где живут рыцари и плуты, имеются еще два обитателя X и Y, причем X заявляет, будто Y —признанный рыцарь, а Y утверждает, что X—отъявленный плут. Единственный вывод, который можно сделать,— это что один из них (мы не знаем, кто именно) должен оказаться либо непризнанным рыцарем, либо неотъявленным плутом. Точно такая же ситуация будет иметь место, если X станет утверждать, что Y непризнанный рыцарь, а Y заявит, что X—неотъявленный плут

.

6. Положим

W=NPA—P—R — R—NPA.

Z=R—W, откуда Z=R—NPA—P—R — R — NPA,

Y-R—Z. откуда Y = R — R — NPA — Р— R — R — NPA.

Х = Р— Y. откуда Х = Р— R — R — NPA — Р— R — R-NPA.

Тогда X утверждает доказуемость Y, Y утверждает опровержимость Z, Z утверждает опровержимость W, a W утверждает недоказуемость X (действительно, W утверждает недоказуемость ассоциата выражения Р—R — R — NPA, которым является само высказывание X).

Если W опровержимо, то W ложно; поэтому X доказуемо и, значит, истинно; следовательно, Y доказуемо, а значит, истинно; стало быть, Z опровержимо, а потому ложно. Отсюда сразу следует, что W неопро-

Стр.199

вержимо. Итак, W не может быть опровержимым; значит, W является неопровержимым, и, следовательно, Z будет ложным.

Далее, если W ложно, то W ложно, но неопровержимо. Предположим, что W истинно; тогда X недоказуемо. Если X истинно, то X истинно и недоказуемо. Предположим теперь, что X ложно; тогда Y недоказуемо. Если Y истинно, то Y истинно, но недоказуемо. Предположим, наконец, что Y ложно; тогда Z неопровержимо. Итак, в данном случае Z ложно, но неопровержимо.

Приведенное рассуждение показывает, что либо W ложно и неопровержимо, либо X истинно и недоказуемо, либо Y истинно и недоказуемо, либо Z ложно и неопровержимо.

7. Эта задача фактически представляет собой просто записанный в других обозначениях вариант задачи 1 данной главы!

Мы знаем, что число 32983 в первой машине Мак-Каллоха порождает число 9832983. Следовательно, по условию Мс1 утверждение 832983 истинно в том и только том случае, если утверждение 9832983 доказуемо. Кроме того, по условию Мс2; утверждение 9832983 истинно в том и только том случае, если утверждение 832983 не является истинным. Итак, сопоставляя эти два факта, мы получаем, что утверждение 9832983 истинно в том и только том случае, если оно недоказуемо. Значит, решением является число 9832983.

Если мы сравним эту задачу с задачей 1, то увидим, что цифра 9 играет здесь роль N, цифра 8 соответствует символу Р, цифра 3 соответствует А, а цифра 2 играет роль тире. В самом деле, если мы заменим символы Р, N, А,— соответствующими цифрами 8, 9, 3, 2, то утверждение NPA — NPA (которое является решением задачи 1) трансформируется в число 9832983 (то есть в решение данной задачи!)

8. Прежде всего отметим, что третья машина Мак-Каллоха также подчиняется закону Мак-Каллоха, который гласит, что для любого числа А всегда найдется некое число X, которое порождает число АХ. Доказы-

Стр. 200

вается это следующим образом. Из гл.13 мы знаем, что существует число Н, а имении число 5464,такое что для любого X число Н2Н2 порождает число Х2Х2. (Вспомним также, что число Н2Н2 в данной ситуации порождает само себя; впрочем, к нашей задаче это никакого отношения не имеет.) И теперь произвольное число А и положим Х=Н2АН2), Тогда число X порождает число АН2АН2, которое и есть АХ. Таким образом, X порождает АХ. Итак, для любого числа А число X, порождающее число АХ,— это есть число 54642А54642.

Пусть нам требуется найти такое X, которое порождало бы 98Х. Предположим, что это X действительно порождает число 98Х. Тогда утверждение 8Х истинно в том и только том случае, если утверждение 98X доказуемо (согласно условию Мс1); поэтому утверждение 98Х истинно в том и только том случае, если утверждение 98Х недоказуемо (согласно условию Мс2). Значит, утверждение 98 X является истинным, но недоказуемым в данной системе (поскольку система правильна).

Теперь, если в качестве А мы возьмем число 98, то увидим, что числом X, порождающим 98Х, является число 546429854642, Поэтому утверждение

98546429854642 истинно, но недоказуемо в данной системе.

9. Я сообщил вам, что наш логик точен, но я вовсе не говорил, будто он знает, что он точен! Если бы логик знал, что он точен, тогда данная ситуация действительно привела бы нас к противоречию. Поэтому правильный вывод из обстоятельств 1, 2 и 3 вовсе не содержит противоречия: просто-напросто хотя логик и точен, но он не может знать, что он точен.

Эта ситуация определенным образом связана с еще одной теоремой Гёделя, называемой обычно второй теоремой Гёделя о неполноте. Эта теорема (с некоторыми упрощениями) утверждает, что для систем с достаточно богатой структурой (а таковы системы, рассмотренные Гёделем в его пионерской работе), если такая система непротиворечива, то она не может доказать

Стр. 201

собственную непротиворечивость. Однако это очень глубокий вопрос, и я собираюсь рассмотреть его более подробно в своих последующих книгах.