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

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 ∈ А, является истинным, но недоказуемым посредством этой машины.

15. Доказуемость и истина

Крупной вехой в истории математической логики стал 1931 г. Именно в этом году Гёдель опубликовал знаменитую теорему о неполноте. Свою эпохальную работу[8] он начинает следующими словами:

«Развитие математики в направлении все большей точности привело к формализации целых ее областей, в связи с чем стало возможно проводить доказательства, пользуясь небольшим числом чисто механических правил. В настоящий момент наиболее исчерпывающими системами являются, с одной стороны, система аксиом, предложенная Уайтхедом и Расселом в работе „Princlpia Mathematica“, а с другой — система Цермело — Френкеля в аксиоматической теории множеств. Обе эти системы настолько обширны, что в них оказывается возможным формализовать все методы доказательства, используемые сегодня в математике, — иначе говоря, все эти методы могут быть сведены к нескольким аксиомам и правилам вывода. Поэтому, казалось бы, разумно предположить, что указанных аксиом и правил вполне хватит для разрешения всех математических проблем, которые могут быть сформулированы в пределах данной системы. Ниже будет показано, что дело обстоит не так. В обеих упомянутых системах имеются сравнительно простые задачи из теории обычных целых чисел, которые не могут быть решены на базе этих аксиом».[9]

Далее Гёдель объясняет, что такая ситуация обусловлена отнюдь не какими-то специфическими особенностями двух упомянутых систем, но имеет место для обширного класса математических систем.

Что имеется в виду под «обширным классом» математических систем? Это выражение интерпретировалось по-разному, и соответственно по-разному обобщалась теорема Гёделя. Как ни странно, одно из самых простых и доступных для неспециалиста объяснений остается наименее известным. Это тем более удивительно, что на такое объяснение указывал и сам Гёдель во вводной части своей первой работы. К нему мы сейчас и обратимся.