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

Рассмотрим систему аксиом со следующими свойствами. Прежде всего пусть у нас имеются имена для различных множеств положительных целых чисел, причем все эти «именуемые», или допускающие наименование, множества мы можем расположить в виде бесконечной последовательности A₁, A₂…, A_n… (точно так же, как в системе Фергюссона, рассмотренной в предыдущей главе). Назовем число n индексом именуемого множества А, если А=n. (Таким образом, если, например, множества A₂, A₇ и A₁₃ совпадают между собой, то тогда числа 2, 7 и 13 — это все индексы одного и того же множества.) Как и для системы Фергюссона, с каждым числом x и с каждым числом у мы связываем утверждение, записываемое в виде x ∈ A_y, которое называется истинным, если x принадлежит А у, и ложным, если x не принадлежит A_y. Однако в дальнейшем мы не предполагаем, что утверждения типа x ∈ A_y являются единственно возможными утверждениями в данной системе, поскольку могут существовать и другие. Предполагается также, что любое возможное утверждение обязательно классифицируется либо как истинное, либо как ложное.

Каждому утверждению в данной системе присваивается некий кодовый номер, который мы будем называть геделевым номером, причем гёделев номер утверждения x ∈ A_y будем обозначать x*y. (Теперь уже нет нужды предполагать, что число x*y состоит из цепочки единиц длиной х, за которой следует цепочка нулей длиной у; сам Гёдель фактически использовал совсем другую кодовую нумерацию. Можно пользоваться самыми разными видами кодовой нумерации, и какой вид оказывался более удобным — это зависит от конкретного вида рассматриваемой нами системы. Так или иначе, для доказательства той общей теоремы, которую мы скоро докажем, нет необходимости вводить какую-то конкретную гёделеву нумерацию.)

Определенные утверждения в данной системе принимаются как аксиомы; кроме того, вводятся также некие специальные правила, по которым можно на основании этих аксиом доказывать различные другие утверждения. Таким образом, в данной системе имеется вполне определенное свойство утверждения, называемое его доказуемостью. Далее предполагается, что система правильна в том смысле, что каждое доказуемое в этой системе утверждение является истинным; отсюда, в частности, следует, что если утверждение x ∈ A_у доказуемо в данной системе, то число x действительно является элементом множества A_y.

Пусть P — это набор гёделевых номеров всех доказуемых в данной системе утверждений. Пусть опять же для любого множества чисел А его дополнение обозначается символом A̅ (это множество всех чисел, не принадлежащих А). Наконец, через А* мы будем обозначать множество всех чисел х, для которых число x*х принадлежит А. При этом нас будут интересовать системы, для которых выполняются следующие три условия G₁, G₂ и G₃:

Условие G₁. Множество P допускает наименование в данной системе. Иначе говоря, существует по крайней мере одно число р, для которого А_р представляет собой множество гёделевых номеров доказуемых утверждений. (Для системы Фергюссона таким р было число 8.)

Условие G₂. Дополнение любого множества, допускающего наименование в данной системе, также именуемо в этой системе. Иначе говоря, для любого числа x найдется такое число х', для которого множество А_x' является дополнением множества А_х. (Для системы Фергюссона таким x' было число 3·х.)

Условие G₃. Для любого именуемого множества А множество А* также именуемо в данной системе. Иначе говоря, для любого числа x всегда найдется такое число х*, что множество А_x, — представляет собой, множество всех чисел n, для которых n*n принадлежит А_x. (Для системы Фергюссона таким х* было число 3·x + 1.)

Очевидно, что условия F₁, F₂ и F₃, характеризующие машину Фергюссона, представляют собой не более чем частные случаи условий G₁, G₂ и G₃. Последние имеют большое значение потому, что они действительно выполняются для самых разнообразных математических систем, в том числе и для тех двух систем, которые рассмотрены в работе Гёделя. Другими словами, оказывается возможным расположить все допускающие наименование множества в виде бесконечной последовательности A₁, A₂…, A_n… и ввести для всех утверждений некоторую частную нумерацию Гёделя, причем так, что будут выполняться условия G₁, G₂ и G₃. В результате все то, что является доказуемым для систем, удовлетворяющих условиям G₁, G₂ и G₃, будет применимо ко многим другим важным системам. Теперь мы можем сформулировать и доказать теорему Гёделя в общей форме.

Теорема G.Для любой правильной системы, удовлетворяющей условиям G₁, G₂ и G₃, должно существовать утверждение, которое является истинным, но недоказуемым в данной системе.