|
Стр. 173 х*х не может быть напечатано машиной. Далее, множество А 75 как раз и есть такое множество К, потому что утверждение, что х принадлежит множеству Аn, равносильно утверждению, что х не принадлежит множеству A25, что в свою очередь равносильно утверждению, что число х*х не принадлежит множеству А8, где А8—это множество тех чисел, которые машина может напечатать. Итак, А 75=К. Но при этом и Аn=К, потому что утверждение, что некое число х принадлежит множеству An, равносильно утверждению, что число х*х принадлежит множеству А8 (согласно свойству 3, поскольку 73 = 3x24+1), что в свою очередь равносильно утверждению, что число х+х не принадлежит множеству А8 (согласно свойству 2). Таким образом, А7з— это множество всех тех чисел х, для которых число х*х не принадлежит множеству А8 или, что то же самое, множество всех чисел х, для которых утверждение хЄАx не может быть доказано машиной. Следовательно, А73 — это то же самое множество чисел, что и A75 поскольку оба они тождественны множеству К. Более того, для любого заданного числа n, для которого Аn=К, утверждение nЄА„ должно быть истинным, но недоказуемым с помощью машины. Это можно показать буквально с помощью тех же самых рассуждений, что и в рассмотренном нами частном случае n=75 (в еще более общей форме эти рассуждения приведены в следующей главе). Тем самым мы получаем, что утверждение 73ЄА73— это еще один пример истинного утверждения, кодовый номер которого машина напечатать не может. 3. Для любого числа n множество А9n должно совпадать с множеством n. В самом деле, множество А9.п есть дополнение множества A3n, а множество А3n в свою очередь есть дополнение множества n; следовательно, множество А9n„ совпадает с Аn, Это означает, что множество A 675 совпадает с множеством A75, и, стало быть, утверждение 675ЄА675 — это есть еще одно решение задачи. Аналогично утверждение 2175ЄA2175также является решением. Таким образом, мы получаем, что существует бесконечно много истинных утверждений, которые машина Фергюссона доказать не Стр. 174 может: например, для любого n, которое равно произведению 75 на некоторое кратное числа 9 или произведению 73 на произвольное кратное числа 9, утверждение nЄА,, является истинным, но недоказуемым посредством этой машины. 15 Доказуемость и истина Крупной вехой в истории математической логики стал 1931 г. Именно в этом году Гёдель опубликовал знаменитую теорему о неполноте. Свою эпохальную работу * он начинает следующими словами: «Развитие математики в направлении все большей точности привело к формализации целых ее областей, в связи с чем стало возможно проводить доказательства, пользуясь небольшим числом чисто механических правил. В настоящий момент наиболее исчерпывающими системами являются, с одной стороны, система аксиом, предложенная Уайтхедом и Расселом в работе «Princlpia Mathematica», а с другой — система Цермело — Френкеля в аксиоматической теории множеств. Обе эти системы настолько обширны, что в них оказывается возможным формализовать все методы доказательства, используемые сегодня в математике,— иначе говоря, все эти методы могут быть сведены к нескольким аксиомам и правилам вывода. Поэтому, казалось бы, разумно предположить, что указанных аксиом и правил вполне хватит для разрешения всех математических проблем, которые могут быть сформулированы в пределах данной системы. Ниже будет показано, что дело обстоит не так. В обеих упомянутых системах имеются сравнительно простые задачи — 107 —
|