истинно, то
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, то увидим, что числом