Принцесса или тигр   ::   Смаллиан Рэймонд

Пусть для всего дальнейшего ключевым является множество К — это множество всех чисел х, для которых утверждение х Є Аx недоказуемо машиной, или, что то же самое, множество таких чисел х,для которых число х*х не может быть напечатано машиной. Далее, множество А75 как раз и есть такое множество К, потому что утверждение, что х принадлежит множеству Аn, равносильно утверждению, что х не принадлежит множеству A25, что в свою очередь равносильно утверждению, что число х*х не принадлежит множеству А8, где А8 — это множество тех чисел, которые машина может напечатать. Итак, А75 = К. Но при этом и Аn = К, потому что утверждение, что некое число х принадлежит множеству An, равносильно утверждению, что число х*х принадлежит множеству А8 (согласно свойству 3, поскольку 73 = 3x24+1), что в свою очередь равносильно утверждению, что число х+х не принадлежит множеству А8 (согласно свойству 2). Таким образом, А75 — это множество всех тех чисел х, для которых число х*х не принадлежит множеству А8 или, что то же самое, множество всех чисел х, для которых утверждение х Є Аx не может быть доказано машиной. Следовательно, А73 — это то же самое множество чисел, что и A75 поскольку оба они тождественны множеству К. Более того, для любого заданного числа n, для которого Аn = К, утверждение n Є А* должно быть истинным, но недоказуемым с помощью машины. Это можно показать буквально с помощью тех же самых рассуждений, что и в рассмотренном нами частном случае n = 75 (в еще более общей форме эти рассуждения приведены в следующей главе). Тем самым мы получаем, что утверждение 73 Є А73 — это еще один пример истинного утверждения, кодовый номер которого машина напечатать не может.

3.