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