Теорема Гёделя

В 1931 году Курт Гёдель опубликовал в немецком журнале Monatshefte f?r Mathematik und Physik статью «О формально неразрешимых предложениях Principia Mathematica и родственных систем I» (?ber formal unentscheidbare S?tze der Principia Mathematica und verwandter Systeme I). Теорема VI этой статьи, прославившаяся впоследствии под названием первой теоремы Гёделя о неполноте, была сформулирована следующим образом:

Для каждого ?-непротиворечивого рекурсивного класса формул k существует такая рекурсивная классовая формула, что ни ? (?, r), ни ¬? (v, r) не принадлежат к Flg (k), где ? — свободная переменная r[26].

Гёдель исходно сформулировал это утверждение по-немецки, но я могу вас заверить, что для немецкоязычного читателя-неспециалиста оно было ничуть не более понятным, чем для нас в переводе. В переложении на обычный язык теорема утверждает приблизительно следующее:

Любая математическая система, которая 1) основана на конечном числе аксиом (утверждений, принимаемых без доказательства), 2) построена строго формальным образом, 3) содержит аксиому, предполагающую существование бесконечной последовательности натуральных чисел (причем ноль считается натуральным числом, и за каждым натуральным числом идет следующее), и 4) не содержит противоречий (в том смысле, что в рамках этой системы невозможно доказать как некоторое утверждение, так и утверждение, обратное ему), заведомо содержит такие утверждения, которые можно точно сформулировать в рамках этой системы, но нельзя ни доказать, ни опровергнуть.

Теорема Гёделя о неполноте чрезвычайно сильно потрясла математиков и логиков. В течение двух с половиной тысяч лет — с самого момента появления математики в современном смысле этого слова — математики твердо верили, что любое математическое утверждение, которое можно ясно и точно сформулировать, рано или поздно можно будет доказать либо опровергнуть, используя формальные методы математической дедукции. Нужно только быть достаточно умным — и доказательство найдется. Но Гёдель разбил эту мечту вдребезги. Он показал, что существуют такие математические утверждения, которые никто, как бы умен он ни был, никогда не сможет ни доказать, ни опровергнуть.

Четыре условия, которые я описал выше, нельзя назвать ни чрезмерно строгими, ни излишне заумными. Им соответствует бо?льшая часть той математики, которую мы используем повседневно. Таким образом, теорема Гёделя утверждает, что во всех математических системах, кроме самых простейших, непременно должны возникать задачи чисто математические, но не разрешимые методами самих этих систем. Отсюда и название «теорема о неполноте»[27].