Рассмотрим теперь доказательство Гёделя с несколько иной точки зрения, которая позволяет увидеть основную идею особенно ярко.
Возьмем четыре символа P, N, А, ‒ и рассмотрим всевозможные комбинации этих символов. Произвольную комбинацию указанных символов мы будем называть выражением. Например, выражением является комбинация P‒‒NA‒P; точно так же выражением будет комбинация ‒PN‒‒А‒P‒. Некоторым выражениям мы будем приписывать определенный смысл — такие выражения в дальнейшем будут называться утверждениями.
Предположим, что у нас имеется машина, которая может выдавать нам (распечатывать) одни выражения и не может выдавать другие. При этом те выражения, которые машина может напечатать, мы будем называть допускающими распечатку. Предполагается, что любое выражение, которое может напечатать машина, рано или поздно обязательно будет ею напечатано. Если нам задано выражение X и мы хотим высказать суждение, что X допускает распечатку, то будем записывать это как P‒X. Так, например, запись P‒ANN означает, что выражение ANN допускает распечатку (при этом неважно, является ли это утверждение истинным или ложным). Если же мы хотим сказать, что выражение X не допускает распечатки, то будем писать NP‒X. (Символ N — от англ. not — отрицание «не», а символ P — от англ. printable — допускающий распечатку.) Таким образом, запись вида NP‒X следует читать как «не допускающее распечатки X», или, что по существу то же самое, «выражение X не допускает распечатки».
Ассоциатом выражения X мы будем называть выражение X‒X; при этом вместо слова «ассоциат» нами будет использоваться символ А (от англ. associate). Таким образом, если нам задано некоторое выражение X и мы хотим сказать, что ассоциат выражения X допускает распечатку, то будем записывать это как РА‒X. Если мы теперь хотим сказать, что ассоциат утверждения X не допускает распечатки, то это будет записываться как NPA‒X.
Читателя, быть может, удивляет, что мы используем тире в качестве своеобразного символа. В самом деле, почему, когда нам нужно высказать суждение о том, что выражение X допускает распечатку, вместо записи P‒X не писать просто РХ? Это делается для того, чтобы избежать определенной двусмысленности. В самом деле, что, например, может означать запись PAN, если мы откажемся от тире? Она может означать либо что ассоциат выражения N допускает распечатку, либо что допускает распечатку выражение AN. Если же мы пользуемся тире, то подобной двусмысленности не возникает. Так, если мы хотим сказать, что ассоциат выражения N допускает распечатку, то записываем этот факт как РА‒N; если же хотим сказать, что допускает распечатку выражение AN, то пишем P‒AN. Предположим теперь, нам нужно сказать, что выражение ‒X допускает распечатку. Правильно ли будет записать эту фразу как P‒X? Нет, ведь запись P‒X означает, что выражение X допускает распечатку. Поэтому чтобы сказать, что допускает распечатку выражение ‒X, нужно написать P‒X.
Рассмотрим еще несколько примеров: запись P‒‒ означает, что ‒ допускает распечатку, запись PA‒‒ означает, что выражение ‒‒‒ (ассоциат выражения ‒) допускает распечатку; запись P‒‒‒‒ также означает, что ‒‒‒ допускает распечатку; запись NPA‒‒P‒A означает, что ассоциат выражения ‒P‒A не допускает распечатки, или, другими словами, что не допускает распечатки выражение ‒P‒A‒‒P‒A. То же самое означает и запись вида NP‒‒P‒A‒‒P‒A.
Утверждением будем называть любое выражение одного из следующих четырех типов: P‒X, NP‒X, РА‒X или NPA‒X, где X — любое выражение. Утверждение P‒X мы будем называть истинным, если X допускает распечатку, и ложным, если X с допускает распечатки. Утверждение NP‒X мы будем называть истинным, если X не допускает распечатки, и ложным, если X эту распечатку допускает, утверждение РА‒X будет называться истинным, если ассоциат выражения X допускает распечатку, и ложным, если ассоциат этого X распечатки не допускает. Наконец, утверждение NA‒X мы будем называть истинным, если ассоциат выражения X не допускает распечатки, и ложным, если ассоциат этого X распечатку допускает. Итак, мы дали точное определение истинности и ложности для утверждений всех четырех видов. Отсюда следует, что для любого выражения X справедливы:
Правило 1. Утверждение P‒X истинно тогда и только тогда, когда выражение X допускает распечатку (на машине).
Правило 2. Утверждение РА‒X истинно тогда и только тогда, когда выражение X‒X допускает распечатку.
Правило 3. Утверждение NP‒X истинно тогда и только тогда, когда выражение X не допускает распечатки.
Правило 4. Утверждение NPA‒X истинно тогда и только тогда, когда выражение X‒X не допускает распечатки
Удивительное дело! Машина печатает утверждения, которые представляют собой не что иное, как суждения о том, что она сама может и что не может напечатать! В этом смысле машина говорит о себе (или точнее, печатает утверждения о самой себе).
Пусть теперь нам известно, что машина на 100 % точна, то есть она не может выдать нам ложное утверждение, печатая только истинные утверждения. Отсюда вытекает ряд следствий. Например, если машина в один прекрасный день напечатает утверждение P‒X, то, значит, она должна напечатать и выражение X, потому что раз она может напечатать утверждение P‒X, то, стало быть, это утверждение истинно, а это означает, что выражение X допускает распечатку. Значит, действительно, машина рано или поздно должна распечатать выражение X.
Аналогично, если машина выдаст нам утверждение РА‒X, тогда (поскольку утверждение РА‒X должно быть истинным) она должна напечатать нам также и выражение X‒X. Помимо этого, если машина напечатает утверждение NP‒X, тогда она не сможет напечатать утверждение P‒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. Таким образом, теперь у нас пять символов: P, R, N, А, ‒. Пусть нам даны две машины, М1 и М2, каждая из которых может печатать различные выражения, составленные из этих пяти символов. При этом под символом P в данном случае мы будем подразумевать «допускающий распечатку первой машиной», а под символом R — «допускающий распечатку второй машиной». Таким образом, запись P‒X означает, что выражение X допускает распечатку первой машиной, а запись R‒X — что выражение X допускает распечатку второй машиной. Запись РА‒X означает, что ассоциат выражения X допускает распечатку первой машиной, а запись RA‒X показывает, что ассоциат выражения X допускает распечатку второй машиной. Наконец, «фразы» NP‒X, NR‒X, NPA‒X, NRA‒X говорят соответственно о следующем: выражение X не допускает распечатки первой машиной; выражение X не допускает распечатки второй машиной; выражение X‒X не допускает распечатки первой машиной; выражение X‒X не допускает распечатки второй машиной. Под утверждением мы будем теперь понимать любое выражение одного из следующих восьми типов: P‒X, R‒X, NP‒X, NR‒X, РА‒X, RA‒X, NPA‒X, NRA‒X. Кроме того, пусть нам известно, что первая машина печатает только истинные утверждения, а вторая — только ложные. Условимся называть некоторое утверждение доказуемым в том и только том случае, если оно допускает распечатку первой машиной, и ложным — в том и только том случае, если оно: может быть напечатано второй машиной. Таким образом, символ P означает «доказуемый» (от англ. provable), а символ R — «опровержимый» (от англ. refutable).
4. Найдите утверждение, которое было бы ложным, но неопровержимым.
5. Имеются такие два утверждения X и Y, что одно из них (правда, нам не известно, какое именно) должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (мы не знаем, каким именно). Такие пары можно строить двумя способами, и соответственно я предлагаю вашему вниманию две задачи:
а. Найдите такие высказывания X и Y, чтобы X утверждало доказуемость Y, a Y утверждало опровержимость X. Далее, покажите, что одно из них (мы не можем сказать, какое именно) либо истинно, но недоказуемо, либо ложно, но неопровержимо.
б. Найдите такие высказывания X и Y, чтобы X утверждало недоказуемость Y, а Y утверждало неопровержимость X. Далее покажите, что одно из этих высказываний, X или Y (мы не можем сказать, какое именно), либо истинно, но недоказуемо, либо ложно, но неопровержимо.
6. А теперь рассмотрим задачу с четырьмя неизвестными! Пусть нам требуется найти такие высказывания X, Y, Z и W, чтобы X утверждало доказуемость Y, Y утверждало опровержимость Z, Z утверждало опровержимость W, a W утверждало бы неопровержимость X. Покажите, что одно из этих четырех высказываний должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (хотя, какое из этих четырех будет именно таким высказыванием, сказать невозможно).
Возможно, читатель уже отметил определенное сходство приведенных выше задач с некоторыми свойствами первой машины Мак-Каллоха. В самом деле, работа этой машины оказывается связанной с теоремой Гёделя, и вот каким образом.
7. Пусть у нас имеется некоторая математическая система, приводящая к набору утверждений, одни из которых называются истинными, а другие — доказуемыми. Мы предполагаем также, что эта система правильная, то есть каждое доказуемое в ней утверждение является истинным. Далее, пусть каждому числу N ставится в соответствие некоторое утверждение, которое мы будем называть утверждением N. Предположим наконец, что наша система удовлетворяет следующим двум условиям.
Условие Мс1. Для любых чисел X и Y, если число X порождает число Y в первой машине Мак-Каллоха, утверждение 8X истинно тогда и только тогда, если утверждение Y доказуемо. (Напомним, что число 8X это не 8, умноженное на X, а цифра 8, за которой стоит число X.)
Условие Мс2. Для любого числа X утверждение 9X истинно тогда и только тогда, если утверждение X не является истинным.
Найдите такое число N, при котором утверждение N истинно, но недоказуемо в данной системе.
8. Предположим, что в условии Mс1 говорится не о «первой машине Мак-Каллоха», а о «третьей машине Мак-Каллоха». Попробуем теперь найти такое утверждение, которое было бы истинным, но недоказуемым.
9. Парадокс ли это? Вернемся вновь к задаче 1, однако внесем в нее некоторые изменения. Вместо символа P мы будем использовать символ В (в силу определенных психологических причин — каких именно, станет ясно из дальнейшего). Определение «утверждения» остается тем же, что и раньше, только на этот раз символ P везде заменяется на символ В. Таким образом, наши утверждения принимают теперь вид: В‒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.
Обстоятельство 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 утверждение P‒NPA‒P‒NPA, а в качестве Y — NPA‒P‒NPA. Утверждение X (которое имеет вид P‒Y) говорит нам о том, что утверждение Y допускает распечатку. Смысл самого Y сводится к тому, что ассоциат утверждения P‒NPA не допускает распечатки. Но ассоциатом утверждения P‒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 — признанный рыцарь, а Y утверждает, что X — непризнанный рыцарь. Единственное заключение, которое мы можем сделать — это, что один из них является непризнанным рыцарем, но кто именно, сказать невозможно.
Подобная ситуация рассматривается в последней главе моей книги «Как же называется эта книга?» в разделе «Дважды гёделевы острова», к которому мы и отсылаем читателя.
3. Положим Z = PA‒P‒NP‒РА.
Далее, положим Y = NP‒Z (то есть Y = NP‒РА‒P‒NP‒РА).
Положим, наконец, X = P‒Y (то есть X = P‒NP‒PA‒P‒NP‒PA).
Из этих выражений сразу ясно: X утверждает, что Y допускает распечатку, а Y говорит нам о том, что Z не допускает распечатки. Что же касается Z, то оно утверждает, что допускает распечатку ассоциат утверждения P‒NP‒РА; но ассоциат P‒NP‒РА есть утверждение P‒NP‒РА‒P‒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 истинно, но не допускает распечатки. Итак, если X истинно, то либо X, либо Z истинно, но не допускает распечатки. Если же X ложно, тогда Y не допускает распечатки и, следовательно, Y истинно — согласно (2) — и не допускает распечатки.
Итак: если X истинно, то по крайней мере одно из двух утверждений X и Z является истинным, но не допускающим распечатки. Если же X ложно, то истинным, но не допускающим распечатки, оказывается утверждение Y.
4. Пусть S есть утверждение вида RA‒RA. Оно говорит нам о том, что ассоциат выражения RA (а ассоциат RA есть само S!) является опровержимым; следовательно, S истинно в том и только том случае, когда S опровержимо. Поскольку S не может быть одновременно и истинным и опровержимым, значит оно ложно, но неопровержимо.
5. а) Выберем в качестве X утверждение P‒RA‒P‒RA, а в качестве Y — утверждение RA‒P‒RA. Ясно, что X утверждает доказуемость Y, а Y утверждает опровержимость ассоциата выражения P‒RA (ассоциат P‒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 ложно, но неопровержимо. Следовательно, либо 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‒P‒R‒R‒NPA,
X = P‒Y, откуда X = P‒R‒R‒NPA‒P‒R‒R‒NPA.
Тогда X утверждает доказуемость Y, Y утверждает опровержимость Z, Z утверждает опровержимость W, a W утверждает недоказуемость X (действительно, W утверждает недоказуемость ассоциата выражения P‒R‒R‒NPA, которым является само высказывание X).
Если W опровержимо, то W ложно; поэтому X доказуемо и, значит, истинно; следовательно, Y доказуемо, а значит, истинно; стало быть, Z опровержимо, а потому ложно. Отсюда сразу следует, что W неопровержимо. Итак, 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 соответствует символу P, цифра 3 соответствует А, а цифра 2 играет роль тире. В самом деле, если мы заменим символы P, N, А, — соответствующими цифрами 8, 9, 3, 2, то утверждение NPA‒NPA (которое является решением задачи 1) трансформируется в число 9832983 (то есть в решение данной задачи!)
8. Прежде всего отметим, что третья машина Мак-Каллоха также подчиняется закону Мак-Каллоха, который гласит, что для любого числа А всегда найдется некое число X, которое порождает число АХ. Доказывается это следующим образом. Из гл. 13 мы знаем, что существует число Н, а имении число 5464, такое что для любого X число Н2Н2 порождает число Х2X2. (Вспомним также, что число Н2Н2 в данной ситуации порождает само себя; впрочем, к нашей задаче это никакого отношения не имеет.) И теперь произвольное число А и положим X = Н2АН2), Тогда число X порождает число АН2АН2, которое и есть АХ. Таким образом, X порождает АХ. Итак, для любого числа А число X, порождающее число АХ, — это есть число 54642A54642.
Пусть нам требуется найти такое X, которое порождало бы 98X. Предположим, что это X действительно порождает число 98X. Тогда утверждение 8X истинно в том и только том случае, если утверждение 98X доказуемо (согласно условию Мс1); поэтому утверждение 98X истинно в том и только том случае, если утверждение 98X недоказуемо (согласно условию Мс2). Значит, утверждение 98X является истинным, но недоказуемым в данной системе (поскольку система правильна).
Теперь, если в качестве А мы возьмем число 98, то увидим, что числом X, порождающим 98X, является число 546429854642, Поэтому утверждение 98546429854642 истинно, но недоказуемо в данной системе.
9. Я сообщил вам, что наш логик точен, но я вовсе не говорил, будто он знает, что он точен! Если бы логик знал, что он точен, тогда данная ситуация действительно привела бы нас к противоречию. Поэтому правильный вывод из обстоятельств 1, 2 и 3 вовсе не содержит противоречия: просто-напросто хотя логик и точен, но он не может знать, что он точен.
Эта ситуация определенным образом связана с еще одной теоремой Гёделя, называемой обычно второй теоремой Гёделя о неполноте. Эта теорема (с некоторыми упрощениями) утверждает, что для систем с достаточно богатой структурой (а таковы системы, рассмотренные Гёделем в его пионерской работе), если такая система непротиворечива, то она не может доказать собственную непротиворечивость. Однако это очень глубокий вопрос, и я собираюсь рассмотреть его более подробно в своих последующих книгах.