Решения

1. Одно из решений состоит в следующем: утверждение 75 ? A₇₅ является истинным, но не может быть доказано машиной. И вот почему.

Допустим, что утверждение 75 ? A₇₅ ложно. Тогда число 75 не принадлежит множеству A₇₅. Следовательно, это число должно принадлежать множеству A₂₅ (согласно свойству 2, множество А₇₅ является дополнением множества A₂₅). Это означает (согласно свойству 3), что число 75*75 принадлежит множеству A₈, поскольку 25 = 3?8 + 1, и, следовательно, машина может напечатать число 75*75. Иначе говоря, это означает, что утверждение 75 ? A₇₅ может быть доказано машиной. Таким образом, если бы утверждение 75 ? A₇₅ было ложным, то оно вполне могло бы быть доказано машиной. Однако нам известно по условию, что машина точна и никогда не доказывает ложные утверждения. Поэтому утверждение 75 ? A₇₅ не может оказаться ложным, и, стало быть, оно должно быть истинным.

Далее, поскольку утверждение 75 ? A₇₅ истинно, то число 75 действительно принадлежит множеству A₇₅. Поэтому оно не может принадлежать множеству А₂₅ (согласно свойству 2), и, следовательно, число 75*75 в свою очередь не может принадлежать множеству A₈, поскольку если бы это было так, то тогда, согласно свойству 3, число 75 принадлежало бы множеству А₂₅. Поскольку ясно, что число 75*75 не принадлежит множеству A₈, то утверждение 75 ? A₇₅ не может быть доказано машиной. Итак, утверждение 75 ? A₇₅ является истинным, но оно недоказуемо с помощью машины.

2. Прежде чем рассматривать другие решения, установим следующий факт весьма общего свойства. Пусть для всего дальнейшего ключевым является множество К — это множество всех чисел х, для которых утверждение x ? А_x недоказуемо машиной, или, что то же самое, множество таких чисел х, для которых число х*х не может быть напечатано машиной. Далее, множество A₇₅ как раз и есть такое множество К, потому что утверждение, что x принадлежит множеству A₇₅, равносильно утверждению, что x не принадлежит множеству A₂₅, что в свою очередь равносильно утверждению, что число х*х не принадлежит множеству A₈, где A₈ — это множество тех чисел, которые машина может напечатать. Итак, A₇₅ = К. Но при этом и A₇₃ = К, потому что утверждение, что некое число x принадлежит множеству A_n, равносильно утверждению, что число х*х принадлежит множеству A₈ (согласно свойству 3, поскольку 73 = 3?24 + 1), что в свою очередь равносильно утверждению, что число х*х не принадлежит множеству A₈ (согласно свойству 2). Таким образом, A₇₃ — это множество всех тех чисел х, для которых число х*х не принадлежит множеству A₈ или, что то же самое, множество всех чисел х, для которых утверждение x ? А_x не может быть доказано машиной. Следовательно, A₇₃ — это то же самое множество чисел, что и A₇₅, поскольку оба они тождественны множеству К. Более того, для любого заданного числа n, для которого А_n = К, утверждение n ? А_n должно быть истинным, но недоказуемым с помощью машины. Это можно показать буквально с помощью тех же самых рассуждений, что и в рассмотренном нами частном случае n = 75 (в еще более общей форме эти рассуждения приведены в следующей главе). Тем самым мы получаем, что утверждение 73 ? A₇₃ — это еще один пример истинного утверждения, кодовый номер которого машина напечатать не может.

3. Для любого числа n множество A_9·n должно совпадать с множеством n. В самом деле, множество A_9·n есть дополнение множества A_3·n, а множество A_3·n в свою очередь есть дополнение множества A_n; следовательно, множество A_9·n совпадает с A_n. Это означает, что множество A₆₇₅ совпадает с множеством A₇₅, и, стало быть, утверждение 675 ? A₆₇₅ — это есть еще одно решение задачи. Аналогично утверждение 2175 ? A₂₁₇₅ также является решением. Таким образом, мы получаем, что существует бесконечно много истинных утверждений, которые машина Фергюссона доказать не может: например, для любого n, которое равно произведению 75 на некоторое кратное числа 9 или произведению 73 на произвольное кратное числа 9, утверждение n ? А, является истинным, но недоказуемым посредством этой машины.