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

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

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

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

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

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. Парадокс ли это?