Это можно показать буквально с помощью тех же самых рассуждений, что и в рассмотренном нами частном случае n = 75 (в еще более общей форме эти рассуждения приведены в следующей главе). Тем самым мы получаем, что утверждение 73 Є А73 — это еще один пример истинного утверждения, кодовый номер которого машина напечатать не может.
3. Для любого числа n множество А9n должно совпадать с множеством n. В самом деле, множество А9n есть дополнение множества A3n, а множество А3n в свою очередь есть дополнение множества n; следовательно, множество А9n совпадает с Аn, Это означает, что множество A675 совпадает с множеством A75, и, стало быть, утверждение 675 Є А675 — это есть еще одно решение задачи. Аналогично утверждение 2175 Є A2175также является решением. Таким образом, мы получаем, что существует бесконечно много истинных утверждений, которые машина Фергюссона доказать не может: например, для любого n, которое равно произведению 75 на некоторое кратное числа 9 или произведению 73 на произвольное кратное числа 9, утверждение n Є А, является истинным, но недоказуемым посредством этой машины.


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

Крупной вехой в истории математической логики стал 1931 г. Именно в этом году Гёдель опубликовал знаменитую теорему о неполноте. Свою эпохальную работу «Uber formal unentscheidbare Satze der «Principia Mathematica» und verwandter Systeme'I» («О формально неразрешимых предложениях «Принципов математики» и других родственных систем»), Моnatshefte fur Mathematik und Physik, 38, 173–198.

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


Далее Гёдель объясняет, что такая ситуация обусловлена отнюдь не какими-то специфическими особенностями двух упомянутых систем, но имеет место для обширного класса математических систем.
Что имеется в виду под «обширным классом» математических систем? Это выражение интерпретировалось по-разному, и соответственно по-разному обобщалась теорема Гёделя. Как ни странно, одно из самых простых и доступных для неспециалиста объяснений остается наименее известным. Это тем более удивительно, что на такое объяснение указывал и сам Гёдель во вводной части своей первой работы. К нему мы сейчас и обратимся.
Рассмотрим систему аксиом со следующими свойствами. Прежде всего пусть у нас имеются имена для различных множеств положительных целых чисел, причем все эти «именуемые», или допускающие наименование, множества мы можем расположить в виде бесконечной последовательности А1, А2…, An… (точно так же, как в системе Фергюссона, рассмотренной в предыдущей главе). Назовем число n индексом именуемого множества А, если А=n. (Таким образом, если, например, множества А2, А7 и A13 совпадают между собой, то тогда числа 2, 7 и 13 — это все индексы одного и того же множества.) Как и для системы Фергюссона, с каждым числом х и с каждым числом у мы связываем утверждение, записываемое в виде х Є Ау, которое называется истинным, если х принадлежит А у, и ложным, если х не принадлежит Ау. Однако в дальнейшем мы не предполагаем, что утверждения типа х Є Ау являются единственно возможными утверждениями в данной системе, поскольку могут существовать и другие. Предполагается также, что любое возможное утверждение обязательно классифицируется либо как истинное, либо как ложное.
Каждому утверждению в данной системе присваивается некий кодовый номер, который мы будем называть геделевым номером, причем гёделев номер утверждения x Є АУ будем обозначать х*у. (Теперь уже нет нужды предполагать, что число х*у состоит из цепочки единиц миной х, за которой следует цепочка нулей длиной у; cам Гёдель фактически использовал совсем другую кодовую нумерацию. Можно пользоваться самыми разными видами кодовой нумерации, и какой вид оказывался более удобным — это зависит от конкретного вида рассматриваемой нами системы. Так или иначе, для доказательства той общей теоремы, которую мы скоро докажем, нет необходимости вводить какую-то конкретную гёделеву нумерацию.)
Определенные утверждения в данной системе принимаются как аксиомы; кроме того, вводятся также некие специальные правила, по которым можно на основании этих аксиом доказывать различные другие утверждения. Таким образом, в данной системе имеется иполне определенное свойство утверждения, называемое его доказуемостью.
Далее предполагается, что система правильна в том смысле, что каждое доказуемое в этой системе утверждение является истинным; отсюда, в частности, следует, что если утверждение x Є
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69