Теорема Гёделя впервые увидела свет как «теорема VI» в его статье 1931 года «О формально неразрешимых суждениях в „Principia Mathematica“ и родственных системах, I». Теорема утверждает следующее:
Каждому ω-непротиворечивому рекурсивному классу формул k соответствует рекурсивный символ классов r такой, что ни v Gen r ни Neg (v Gen r) не принадлежат к Flg (к), где v - свободная переменная r.
В оригинале это было написано по-немецки; читатель, возможно, думает, что с тем же успехом можно было бы это на немецком и оставить. Постараемся привести перевод на более понятный язык.
Все непротиворечивые аксиоматические формулировки теории чисел содержат неразрешимые суждения.
Это наша жемчужина.
В ней трудно увидеть Странную Петлю, потому что эта Петля спрятана в «устрице» — в доказательстве. Доказательство теоремы Гёделя о неполноте вращается вокруг автореферентного (описывающего самого себя) математического суждения, так же как парадокс Эпименида — вокруг такого суждения в языке. Говорить о языке, используя для этого сам язык, несложно; гораздо труднее вообразить, как может говорить само о себе математическое суждение о числах. На самом деле, уже для того, чтобы связать идею автореферентного суждения с теорией чисел, понадобился гениальный ум. Интуитивно придя к мысли о возможности такого суждения, Гёдель преодолел одну из основных трудностей. Само же создание автореферентного суждения было делом техники, раздуванием костра из блистательной искры мгновенного прозрения.
Мы остановимся на теореме Гёделя в последующих главах; но чтобы покуда не оставить читателя в полной тьме, я несколькими штрихами обрисую суть идеи в надежде на то, что это заставит вас задуматься. Для начала уясним, в чем здесь основная трудность. Математические суждения описывают свойства целых чисел (мы будем говорить здесь о суждениях теории чисел). Ни целые числа, ни их свойства не являются сами по себе суждениями. Суждения теории чисел не говорят ничего про суждения теории чисел; они не более как суждения теории чисел. В этом и заключается проблема; однако Гёдель сумел увидеть глубже того, что лежит на поверхности.
Гёдель предположил, что суждение теории чисел могло бы быть о суждении теории чисел (возможно даже о себе самом), если бы сами числа могли обозначать суждения. Иными словами, в центре его построения находится идея кода. В этом коде, обычно именуемом «Гёделевой нумерацией», символы и последовательности символов обозначаются числами. Таким образом, любое суждение теории чисел, будучи последовательностью специальных символов, получает Гёделев номер, что-то вроде телефонного номера или номерного знака машины. В дальнейшем, для ссылки на данное суждение используется соответствующий Гёделев номер. С помощью этого кодирующего трюка суждения теории чисел приобретают двоякое значение: они могут быть поняты как суждения теории чисел, а так же как суждения о суждениях теории чисел.
После того, как Гёдель изобрел эту кодирующую схему, ему пришлось разработать в деталях способ перевода парадокса Эпименида на формальный язык теории чисел. Конечный результат «пересадки» Эпименида на формальную почву звучит так: «Это суждение теории чисел не имеет доказательства» (вместо «Это суждение теории чисел ложно»). Эта формулировка может создать немалую путаницу. так как «доказательство» для многих является весьма приблизительным понятием. В действительности, труды Геделя были лишь частью долгих поисков, предпринятых математиками в надежде выяснить, что же такое доказательства. Необходимо помнить тот факт, что доказательства являются таковыми только внутри жестких систем теорем. В Гёделевской работе такой жесткой системой, к которой относится слово «доказательство», является огромный труд Бертрана Рассела и Альфреда Норта Уайтхеда «Principia Mathematical» («Основания математики»), опубликованный между 1910 и 1913 годами. Следовательно, Гёделево высказывание Г должно бы звучать более правильно как: