Теоремы Гёделя о неполноте

Теоремы Гёделя о неполноте — в математической логике две теоремы, доказанные в 1931 году Куртом Гёделем, констатирующие некоторые ограничения, которые присущи всем «достаточно сложным» формальным системам, достаточным для описания арифметики. Эти теоремы также имеют значимость в философии математики.

Эти теоремы показывают, что программа Гильберта по поиску полного и непротиворечивого множества аксиом для всей математики несостоятельна и невозможна, а потому теоремы дают отрицательный ответ на вторую проблему Гильберта. Некоторые авторы (например, Д. Р. Лукас) утверждают, что теоремы Гёделя о неполноте имеют более широкое применение в различных областях философии и даже когнитологии, но эти утверждения в общем виде не принимаются научным сообществом.

Первая теорема о неполноте

Первая теорема Гёделя о неполноте, по всей видимости, является наиболее знаменательным результатом в математической логике. Она звучит следующим образом:

Для произвольной непротиворечивой формальной и вычислимой теории, в которой можно доказать базовые арифметические высказывания, может быть построено истинное арифметическое высказывание, истинность которого не может быть доказана в рамках теории. Другими словами, любая вполне полезная теория, достаточная для представления арифметики, не может быть одновременно непротиворечивой и полной.

Здесь слово «теория» обозначает «бесконечное множество» высказываний, некоторые из которых полагаются истинными без доказательств (такие высказывания называются аксиомами), а другие (теоремы) могут быть выведены из аксиом, а потому полагаются (доказываются) истинными. Словосочетание «доказуемый в теории» обозначает «выводимый из аксиом и примитивов теории (константных символов алфавита) при помощи стандартной логики (первого порядка)». Теория является непротиворечивой (согласованной), если в ней невозможно доказать противоречивое высказывание. Словосочетание «может быть построено» обозначает, что существует некоторая механическая процедура (алгоритм), которая может построить высказывание на основе аксиом, примитивов и логики первого порядка. «Элементарная арифметика» заключается в наличии операций сложения и умножения над натуральными числами. Результирующее истинное, но недоказуемое высказывание часто обозначается для заданной теории как «последовательность Гёделя», однако существует бесконечно количество других высказываний в теории, которые имеют такое же свойство: недоказуемая в рамках теории истинность.

Предположение о том, что теория вычислима, обозначает, что в принципе возможно реализовать компьютерный алгоритм (компьютерную программу), которая (если ей разрешено вычислять произвольно долгое время, вплоть до бесконечности) вычислит список всех теорем теории. Фактически, достаточно вычислить только список аксиом, и все теоремы могут быть эффективно получены из такого списка.

Первая теорема о неполноте была озаглавлена как «Теорема VI» в статье Гёделя от 1931 года On Formally Undecidable Propositions in Principia Mathematica and Related Systems I. В оригинальной записи Гёделя она звучала как:

«Общий вывод о существовании неразрешимых пропозиций заключается в следующем:

Теорема VI. Для каждого \(\omega\)-согласованного рекурсивного класса \(k\) ФОРМУЛ существуют рекурсивные ЗНАКИ \(r\) такие, что ни \((v \, \mathrm{Gen} \, r)\), ни \(\neg (v \, \mathrm{Gen} \, r)\) не принадлежат \(Flg(k)\) (где \(v\) есть СВОБОДНАЯ ПЕРЕМЕННАЯ \(r\))».

Обозначение \(Flg\) происходит от нем. Folgerungsmenge — множество последовательностей, \(Gen\) происходит от нем. Generalisation — обобщение.

Грубо говоря, высказывание Гёделя \(G\) утверждает: «истинность \(G\) не может быть доказана». Если бы \(G\) можно было доказать в рамках теории, то в таком случае теория содержала бы теорему, которая противоречит сама себе, а потому теория была бы противоречива. Но если \(G\) недоказуемо, то оно истинно, а потому теория неполна (высказывание \(G\) невыводимо в ней).

Это пояснение на обычном естественном языке, а потому не совсем математически строго. Для предоставления строгого доказательства, Гёдель пронумеровал высказывания при помощи натуральных чисел. В этом случае теория, описывающая числа, также принадлежит множеству высказываний. Вопросы о доказуемости высказываний представимы в данном случае в виде вопросов о свойствах натуральных чисел, которые должны быть вычислимы, если теория полна. В этих терминах высказывание Гёделя гласит, что не существует числа с некоторым определённым свойством. Число с этим свойством будет являться доказательством противоречивости теории. Если такое число существует, теория противоречива вопреки первоначальному предположению. Так что предполагая, что теория непротиворечива (как предполагается в посылке теоремы), получается, что такого числа не существует, и высказывание Гёделя истинно, но в рамках теории этого доказать невозможно (следовательно, теория неполна). Важное концептуальное замечание состоит в том, что необходимо предположить, что теория непротиворечива, для того чтобы объявить высказывание Гёделя истинным.

Расширения оригинального вывода Гёделя

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

Оригинальное утверждение Гёделя в формулировке теоремы о неполноте требовало предположения, что теория не просто непротиворечива, но \(\omega\)-непротиворечива. Теория \(\omega\)-непротиворечива, если она не \(\omega\)-противоречива. И теория \(\omega\)-противоречива, если существует предикат \(P\) такой, что для каждого специфического натурального числа \(n\) теория доказывает высказывание \(\neg P(n)\), а кроме того, теория также доказывает существование некоторого натурального числа \(n\), для которого \(P(n)\). Так что теория говорит о том, что число со свойством \(P\) существует в то время, когда утверждается, что у этого числа нет произвольного свойства. Свойство \(\omega\)-непротиворечивости теории подразумевает её непротиворечивость, но не наоборот (непротиворечивость не подразумевает \(\omega\)-непротиворечивости). Позднее Д. Б. Россер усилил теорему о неполноте при помощи создания доказательства, которое не требует того, чтобы теория была \(\omega\)-непротиворечива. Это больше относится к узкому интересу учёных, поскольку все теории в рамках арифметики, то есть с аксиомами об истинности высказываний с натуральными числами, являются \(\omega\)-непротиворечивыми, так что оригинальная теорема Гёделя относится ко всем таким теориям. Но именно более сильная версия теоремы о неполноте, которая не требует наличия свойства \(\omega\)-непротиворечивости, сегодня известна как первая теорема Гёделя о неполноте.

Вторая теорема о неполноте

Вторая теорема Гёделя о неполноте звучит следующим образом:

Для любой формально рекурсивно перечислимой (то есть эффективно генерируемой) теории \(T\), включая базовые арифметические истинностные высказывания и определённые высказывания о формальной доказуемости, данная теория \(T\) включает в себя утверждение о своей непротиворечивости тогда и только тогда, когда теория \(T\) противоречива.

Доказательство необходимости (части «тогда»): Если \(T\) противоречива, то в её рамках можно доказать произвольное высказывание, в том числе и о том, что \(T\) непротиворечива.

Доказательство достаточности (части «и только тогда»): Если \(T\) непротиворечива, то \(T\) не включает в себя высказывания о своей собственной противоречивости. Это следует из первой теоремы Гёделя о неполноте.

В формулировке второй теоремы Гёделя существует определённая техническая тонкость, а именно то, как точно выражается непротиворечивость \(T\) в терминах самой \(T\). Существует много способов это сделать, и не все они ведут к одному и тому же результату. В частности, различные формализации утверждения о том, что \(T\) непротиворечива, могут быть неэквивалентны в рамках \(T\), а некоторые вообще могут быть доказуемы. Например, в рамках арифметики первого порядка (арифметика Пеано или АП для краткости) можно доказать, что наибольшее непротиворечивое подмножество АП является непротиворечивым. Но раз АП является непротиворечивой теорией, наибольшим непротиворечивым подмножеством её является сама АП, так что в этом смысле в рамках АП доказывается, что она сама по себе непротиворечива. То, что невозможно доказать в рамках АП, заключается в том, что наибольшее непротиворечивое подмножество АП есть само АП (при этом термин «наибольшее непротиворечивое подмножество АП» является неясным, но здесь говорится о том, что наибольший непротиворечивый сегмент набора аксиом АП пронумерован по некоторому критерию, например, при помощи «чисел Гёделя», то есть способом, который Гёдель использовал для доказательства своей первой теоремы о неполноте).

В случае арифметики Пеано или любой иной схожей явно аксиоматизируемой теории \(T\) возможно определить непротиворечивость «\(Con(T)\)» в терминах несуществования числа с определённым свойством. Например: не существует целого числа, кодирующего высказывания о высказываниях таких, что каждое высказывание является либо одной из (канонических) аксиом \(T\), либо логической аксиомой, либо непосредственной последовательностью предыдущих высказываний в соответствии с правилами вывода логики первого порядка, и таких, что последнее высказывание противоречиво. Однако, для произвольной \(T\) не существует канонического выбора для \(Con(T)\).

Формализация \(Con(T)\) зависит от двух факторов: формализации нотации для описания высказывания, выводимого из набора высказываний, а также формализации нотации для записи аксиом теории \(T\). Формализация выводимости может быть выполнена в каноническом виде так, что заданная арифметическая формула \(A(x)\)определяет набор аксиом, и можно создать предикат \(Prov_A(P)\), который определяет, является ли \(P\) доказуемым при помощи набора аксиом, полученных из формулы \(A(x)\). При помощи этого предиката можно выразить \(Con(T)\) как «\(\neg Prov_A(P \and \neg P)\)». С. Феферман показал, что вторая теорема Гёделя о неполноте применима в случаях, когда формула \(A(x)\) выбрана так, что она имеет форму «существует число \(n\), удовлетворяющее разрешимый предикат \(P\)» для некоторого \(P\). В дополнение \(Prov_A(P)\) должен удовлетворять так называемым условиям доказуемости Гильберта-Бернайза:

1. Если \(T\) доказывает \(P\), то \(T\) доказывает и \(Prov_A(P)\).
2. \(T\) доказывает пункт 1, то есть \(T\) доказывает, что если \(T\) доказывает \(P\), то \(T\) доказывает и \(Prov_A(P)\).
3. \(T\) доказывает, что если \(T\) доказывает \((P \Rightarrow Q)\), то \(T\) доказывает, что из доказуемости \(P\) следует доказуемость \(Q\).

Из второй теоремы Гёделя о неполноте также следует, что теория \(T_1\), удовлетворяющая перечисленные выше технические условия, не может доказать непротиворечивость произвольной теории \(T_2\), которая доказывает непротиворечивость теории \(T_1\). Это следует из того, что если \(T_1\) может доказать, что \(T_2\) доказывает непротиворечивость \(T_1\), то сама по себе теория \(T_1\) фактически становится непротиворечивой. Утверждение о том, что \(T_1\) является непротиворечивой, имеет форму «для всех чисел \(n\), \(n\) имеет вычислимое свойство, которое заставляет это число не быть кодом для доказательства противоречивого утверждения в \(T_1\)». Если \(T_1\) фактически противоречива, тогда \(T_2\) докажет для некоторых \(n\) то, что эти числа являются кодом доказательства противоречивых высказываний в рамках \(T_1\). Но если теория \(T_2\) также доказывает, что \(T_1\) непротиворечива, то есть не существует указанного \(n\), она сама по себе противоречива. Это доказательство можно вывести в рамках \(T_1\) и заключить, что \(T_2\) непротиворечива, и в этом случае \(T_1\) непротиворечива. По второй теореме Гёделя о неполноте в рамках \(T_1\) невозможно доказать её непротиворечивость, так что в ней невозможно доказать и непротиворечивость \(T_2\).

Это простое заключение второй теоремы о неполноте показывает, что не существует надежды доказать, например, непротиворечивость арифметики первого порядка при помощи использования предоставленных ею конечных механизмов, и понимается, что конечные механизмы корректно формализованы в теории, непротиворечивость которой доказывается в рамках АП (арифмметика Пеано). Обычно принимается, что теория примитивной рекурсивной арифметики (ПРА) является аккуратной формализацией конечной математики, и в свою очередь ПРА доказуемо непротиворечива в АП. Это значит, что в рамках ПРА невозможно доказать непротиворечивость АП. Это рассуждение показывает обречённость программы Гильберта по валидации использования «идеальных» математических принципов для доказательства «реальных» (конечных) математических утверждений, поскольку «идеальные» принципы попросту не могут быть выведены.

Это заключение является тем, что делает вторую теорему о неполноте эпистемологически значимой. Как заметил Г. Крейзель, она не даёт никакой интересной информации в случаях, если в рамках теории \(T\) можно доказать её непротиворечивость. Это происходит потому, что в рамках противоречивых теорий можно доказать всё, что угодно, включая их непротиворечивость. Это значит, что доказательство непротиворечивости теории \(T\) в рамках самой \(T\) не может дать исследователю никакой информации о том, является ли теория \(T\) непротиворечивой. Никакого заключения невозможно получить при помощи доказательства непротиворечивости теории в рамках самой теории. Интерес в доказательстве непротиворечивости заключается в возможности доказать непротиворечивость теории \(T\) в рамках некоторой теории \(T'\), которая в некотором смысле является менее «глупой» (менее слабой), чем первоначальная теория \(T\). Например, если \(T'\) — теория множеств с аксиоматикой Цермело-Френкеля, а \(T\) — примитивная рекурсивная арифметика, то в рамках \(T'\) можно доказать непротиворечивость \(T\), а потому непротиворечивость \(T'\) невозможно доказать в рамках \(T\). Это — главное следствие второй теоремы Гёделя о неполноте.

Оригинальная формулировка теоремы Гёделя XI

Несмотря на то, что сегодня данная теорема называется второй теоремой Гёделя о неполноте, в оригинальном исследовании Курта Гёделя она носила наименование «Теорема XI». Она гласила (в нижеследующем тексте «Раздел 2» является разделом, где была приведена «Теорема VI» — первая теорема о неполноте, а сокращение «P» является сокращением Гёделя для арифметики Пеано):

Результаты Раздела 2 имеют неожиданное следствие относительно доказательства непротиворечивости системы P (и её расширений), которые могут быт сформулированы следующим образом:

Теорема XI. Пусть \(k\) — произвольный рекурсивный непротиворечивый⁶³ класс ФОРМУЛ, тогда ПРОПОЗИЦИОНАЛЬНАЯ ФОРМУЛА о том, что \(k\) — непротиворечив, не может быть доказана в рамках \(k\). В частности, непротиворечивость P не может быть доказана в рамках P⁶⁴, принимая во внимание, что P — непротиворечива (если P противоречива, в ней доказывается всё, что угодно).

⁶³ \(k\) является непротиворечивым (обозначается как \(Wid(k)\)), если \((Ex)(Form(x) \and \overline{Bew_k(x)})\).

Примечание:

• Wid, от нем. Widerspruchfreiheit — непротиворечивость;
• Form, от нем. Formel — формула;
• Bew, от нем. Beweisbar — доказуемый.

Так что выражение «система \(k\) непротиворечива» определяется следующим образом: «существует по крайней мере одно значение \(x\) в формуле \(F\) такое, что эта формула \(F(x)\) является истинной, но её истинность не выводима в рамках \(k\).»

⁶⁴ Это утверждение следует из того, если подставить в \(k\) класс пустых ФОРМУЛ.

Смысл теорем Гёделя

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

Для того, чтобы провести этот механический процесс, необходимо понимание природы аксиом. Можно начать с конечного набора аксиом, как, например, в евклидовой геометрии, хотя можно использовать и бесконечный список аксиом, но в этом случае необходимо иметь механизм для понимания того, является ли произвольное утверждение аксиомой или нет. В информатике такое множество называется рекурсивным, так что необходимо рекурсивное множество аксиом. Хотя бесконечный список аксиом может выглядеть странным, это обычное дело для многих формальных систем. Например, в арифметике Пеано используется именно бесконечный список аксиом, а шаг индуктивной аксиомы по своей сути является всего лишь схемой построения аксиом — она утверждает, что 0 имеет некоторое свойство, а также если некоторое натуральное число имеет это свойство (как у 0), то и следующее за ним число также имеет это же свойство. В этом случае все натуральные числа имеют это свойство — не указывается, какое именно свойство, а потому в логике первого порядка для вывода истинности для всех свойств для всех натуральных числе необходим бесконечный набор аксиом.

Первая теорема Гёделя о неполноте показывает, что любая формальная система, в рамках которой можно определить натуральные числа, по необходимости неполна — она содержит высказывания, значения истинности которых не могут быть вычислены. Говоря иначе, не существует замкнутой формальной системы, которая может определить натуральные числа, поскольку в ней будут содержаться истинные утверждения, истинность которых невозможно доказать в рамках формальной системы. Это опровергает попытки Г. Фреге и Б. Рассела определить натуральные числа в терминах формальной логики.

Существование неполных формальных систем не является чем-то необычным. Например, если рассмотреть евклидову геометрию и выкинуть из системы аксиом аксиому о параллельных прямых, то получится неполная система (в том смысле, что эта система содержит неполный набор истинных высказываний о свойствах евклидова пространства). Формальная система может быть неполной просто по причине отсутствия всех необходимых аксиом.

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

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

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

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

Современное доказательство

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

1. Лемма куина: любая компьютерная программа может включать в себя подпрограмму, которая возвращает исходный код всей программы. Эта подпрограмма может записывать свой результат в строку или кодировать его в большое число.

   Доказательство: пусть подпрограммой будет стандартный куин с дополнительными данными, описывающими оставшуюся часть исходного кода программы.

2. Лемма останова: не существует компьютерной программы PREDICT(P), которая по исходному коду программы P может сказать, остановится программа P или нет.

   Доказательство: пусть имеется программа SPITE, которая заносит свой исходный код в некоторую переменную R, после чего вычисляет значение PREDICT(R). Если ответом является «R останавливается», программа SPITE уходит в бесконечный цикл (не останавливается). Если ответом является «R не останавливается», то программа SPITE останавливается. Поскольку R является исходным кодом программы SPITE, не имеет значения, какой результат выдала программа PREDICT, он в любом случае ложен.

Теорема о неполноте: пусть система аксиом описывает натуральные числа (или любую иную дискретную структуру), а также существует достаточное количество операций (сложения и умножения достаточно), чтобы описать работающий компьютер. Тогда эта система либо противоречива, либо неполна.

Доказательство: пусть имеется программа DEDUCE, которая позволяет вычислить все следствия из системы аксиом. Пусть DEDUCE выводит свой собственный исходный код в некоторую переменную R и пытается вывести теорему «R никогда не останавливается». Если DEDUCE выводит эту теорему, она останавливается.

Если система аксиом доказывает, что DEDUCE не останавливается, она противоречива. Если система аксиом не доказывает, что DEDUCE не останавливается, она неполна.

Этот аргумент явно не демонстрирует неполноту, поскольку непротиворечивая система аксиом всё же может без противоречий доказать \(\omega\)-противоречивую теорему о том, что DEDUCE останавливается (даже в случае, если она не останавливается).

Так что пусть имеется программа ROSSER, которая выводит свой исходный код в переменную R, после чего ищет доказательство либо: 1) R возвращает что-либо или 2) R ничего не возвращает. Если она находит доказательство 1), она останавливается без возвращения чего-либо. Если она находит доказательство 2), она возвращает некоторую строку и останавливается.

Если система аксиом непротиворечива, в её рамках невозможно доказать ни утверждение «ROSSER возвращает что-либо», ни его отрицание «ROSSER не возвращает ничего». Так что независимо от заключений относительно программы DEDUCE, система аксиом неполна.

Для доказательства второй теоремы Гёделя о неполноте необходимо отметить, что непротиворечивость аксиом доказывает, что программа DEDUCE не останавливается, так что система не может доказать свою собственную непротиворечивость.

Примеры неразрешимых утверждений

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

Из-за такого двойного смысла слова «неразрешимый» иногда используется термин «независимый» для обозначения «утверждений, которые не могут быть ни доказаны, ни опровергнуты». Однако термин «независимый» также двусмысленнен. Некоторые используют его для обозначения «недоказуемых» утверждений, так что в этом смысле независимые утверждения могут быть опровергаемы.

Неразрешимость высказывания в определённой дедуктивной системе сама по себе не ставит вопроса о том, определена ли истинность высказывани, либо высказывание может быть определено в каком-то ином смысле. Неразрешимость только лишь влечёт то, что в рамказ заданной дедуктивной системы невозможно доказать истинность или ложность высказывания. В любом случае, существуют так называемые «абсолютно неразрешимые» высказывания, значение истинности которых никогда не может быть получено. Такие высказывания являются спорным вопросом многих философских школ.

Одна из первых первых проблем, которая, как ожидается, неразрешима во втором смысле этого слова, — это проблема слов для групп, впервые описанная М. Деном в 1911 году. Данная проблема спрашивает о существовании конечной группы, для которой не существует алгоритма для определения того, являются ли два слова эквивалентными. То, что это неразрешимая проблема, было показано в 1952 году.

В совместной работе Гёделя и П. Кохена были даны два конкретных примера неразрешимых утверждений (в первом смысле этого слова): континуум-гипотеза не может быть ни доказана, ни опровергнута в рамках ZFC (стандартной аксиоматики теории множеств), и аксиома выбора не может быть ни доказана, ни опровергнута в рамках ZF (аксиоматика Цермело-Френкеля, которая включает все аксиомы ZFC, кроме аксиомы выбора). Доказательство этих утверждений не требует привлечения теорем о неполноте. Сам Гёдель доказал в 1940 году, что ни одно из этих утверждений не может быть опровергнуто ни в ZF, ни в ZFC. В 1960-ых годах П. Кохен доказал, что оба утверждения недоказуемы в ZF, и континуум-гипотеза недоказуемы в ZFC.

В 1936 году Алан Тьюринг доказал, что проблема останова — вопрос о том, остановится ли машина Тьюринга на заданной программе или нет, — неразрешим во втором смысле этого термина. Этот вывод позже был обобщён в теореме Райса.

Сегодня в математике можно найти достаточное количество примеров неразрешимых (в обоих смыслах) утверждений.

Ограничения на применимость теорем Гёделя

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

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

Дискуссии

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

А вот такое перефразирование второй теоремы является ещё более тревожным для основ математики:

Если возможно доказать непротиворечивость системы, включающей арифметику, в рамках неё самой, то эта система противоречива.

Следовательно, для установления факта непротиворечивости некоторой системы \(S\) необходимо использовать более мощную систему \(T\), но доказательство в рамках \(T\) не может быть полностью законченным, пока не доказана непротиворечивость самой \(T\) (причём без использования системы \(S\)).

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

Некоторые исследователи предполагают, что утверждение, которое недоказуемо в рамках дедуктивной системы, может быть совершенно доказуемо на некотором метаязыке. А то, что не может быть доказано на этом метаязыке, может, в свою очередь, быть доказано на мета-метаязыке, и так до бесконечности. Применяя такие системы типизированных метаязыков совместно с аксиомой редуцируемости, которая по индуктивному предположению применяется ко всему набору языков, можно для любых областей знаний обходить проблему неполноты.

Необходимо также отметить, что теоремы Гёделя применимы только к достаточно сильным системам аксиом. «Достаточно сильный» в данном контексте обозначает, что теория содержит достаточно средств для представления данных, необходимых для доказательства первой теоремы о неполноте. Существенно то, что для этого нужны базовые аксиомы, представляющие операции сложения и умножения, как, к примеру, в арифметике Робинсона Q. Существуют более слабые системы аксиом, которые полны и непротиворечивы, например, арифметика Пресбургера, которая доказывает истинность утверждений первого порядка только относительно сложения.

Система аксиом может содержать бесконечное количество аксиом (как, к примеру, арифметика Пеано первого порядка), но для применимости к такой системе теоремы Гёделя. должен быть эффективный алгоритм, который позволяет проверять корректность. Например, можно рассмотреть множество всех высказываний первого порядка, который истинны в стандартной модели натуральных чисел. Эта система полна, но теорема Гёделя неприменима в данном случае, поскольку не существует эффективной процедуры, которая определяет, является ли заданная последовательность аксиомой. Фактически, это так по следствию из первой теоремы Гёделя о неполноте.

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

Сам Гёдель доказал технически более слабые версии теорем. Первое доказательство теорем в приведённых в статье формулировках впервые было приведено Д. Б. Россером в 1936 году.

По существу, доказательство первой теоремы содержит процесс конструирования утверждения \(p\) в рамках формальной системы, которое можно описать на метаязыке следующим образом: $$p = $$«Это утверждение не может быть доказано в рассматриваемой формальной системе»

Как видно, это, всего лишь, современный вариант парадокса лжеца, который в отличие от классической формулировки, не совсем парадоксальный.

Если система аксиом непротиворечива, доказательство теоремы Гёделя показывает, что \(p\) (и его отрицание) не могут быть доказаны в рамках системы. Следовательно утверждение \(p\) истинно (это утверждение о том, что оно само недоказуемо, и оно действительно недоказуемо). Если система аксиом \(\omega\)-непротиворечива, то отрицание \(p\) также не может быть доказано, и таким образом \(p\) невычислимо. В системах, которые \(\omega\)-противоречивы (но непротиворечивы), либо имеется такая же ситуация, либо утверждение \(\neg p\) может быть доказано.

Добавление утверждения \(p\) в качестве аксиомы не решает проблемы, поскольку для такой расширенной системы будет существовать иное утверждение Гёделя. Такие теории, как арифметика Пеано, для которых не может быть построено перечислимого расширения, называются существенно неполными.

Разум и машины

Некоторые авторы, включая Д. Р. Лукаса, обсуждают вопрос о том, что теоремы Гёделя о неполноте касаются в том числе и некоторых аспектов человеческого разума. Бо́льшая часть обсуждений лежит в плоскости того, эквивалентен ли человеческий разум машине Тьюринга и по тезису Чёрча-Тьюринга вообще конечному автомату. Если это так, и конечный автомат непротиворечив, то в этом случае теоремы Гёделя применимы.

Х. Патнэм (1960) навел на мысль, что теоремы Гёделя не могут применяться к разуму человека, поскольку люди делают ошибки и потому противоречивы, но теоремы вполне можно применять к определённым областям знаний, таких как математика или наука в целом. Если верить, что эти области знания непротиворечивы, то либо в них нельзя доказать их непротиворечивость, либо их нельзя представить в виде машины Тьюринга.

Постмодернизм и европейская философия

Время от времени раздаются призывы расширить (по аналогии) область применимости теорем о неполноте за пределы логики и математики. Например, Р. Дебрэй применяет её в политике («Секрет имеет форму логического закона, расширяющий теорему Гёделя: Не может существовать организованной системы без замыкания, и ни одна система не может быть замкнута внутренними для этой системы элементами»). Некоторые авторы в большинстве своём негативно прокомментировали подобные расширения и интерпретации. Основная причина негативных реакций заключается в том, что нельзя применять теорему Гёделя из мира идей Платона в нереалистичных использованиях гуманитарными интеллигентами.

Теории всего и физика

С. Хокинг и другие убеждают, что (аналогично) из теоремы Гёделя следует, что даже очень сложная формулировка физических принципов будет неполной, а потому не может быть создано всеобщей теории, основанной на конечном числе физических принципов. На самом же деле все просто. Брадобрея побреет другой брадобрей который придет к нему в гости, либо сам брадобрей первый, придет в гости ко второму, и они при этом друг друга спокойно побреют, либо при необходимости они побреют и других таким же образом ьрадобреев. А все от того, что градоначальник живущий в каждом из их городов, распостранил действие своего приказа, только на территории его отдельного от других, города, и этот приказ не может иметь отношение при этом к другим городам, а не его городу! Так же и в другой формулировке этого парадокса, Мэр города мэров, может жить в кажом из городов, в том числе и в городе мэров при этом, раз он поставлен над всеми другими мэрами их над ними командует, то его "своим" городом, является и город мэров, для него, и все остальные города, находящиеся в его распоряжении, но при этом, он одновременно, не является исходя из этого, жителем какого-либо только лишь одного определенного города, в том числе и города меров, а раз, он местным жителем всех этих городов может не являться, и не является, то формулировка "свой город" для него звучит неопределенно, и не имеет к нему непосредственного при этом отношения, из-за непонятной, невнятной, размытой, в его понимании, и несформулированной для него формулировки, в отношении того, жителем какого города он вообще может, и должен, являться, потому как даже если ему указать насильно при этом, сказав ему, что он является лишь мэром города мэров, и не может быть мэром других всех остальных этих городов, то это будет неправильно, ведь он как ему не указывай ложно, какого города он при этом мэром является, он все равно останется к тому же по факту мэром всех остальных этих городов. И это словно бы напоминало ситуацию, когда президенту страны было тсказано, что он якобы должен быть президентом не всей страны, а только лишь быть при этом президентом столицы этой страны, а не ее всей, но он по факту является президентом всей страны, а иначе к нему бы неприменимо было бы само понятие, президент страны!

Наброски к доказательству первой теоремы

Главной проблемой в показанной выше идее доказательства первой теоремы о неполноте заключается в следующем: для того чтобы сконструировать утверждение \(p\), которое эквивалентно «\(p\) не может быть доказано», само утверждение \(p\) должно содержать некую ссылку на само себя, которая может с лёгкостью привести к нескончаемой рекурсии рассмотрения. Изобретательный трюк Гёделя, который впоследствии был использован Аланом Тьюрингом для указания на то, что проблема останова не может быть решена, описан ниже.

Для того чтобы начать доказательство, каждая формула или утверждение, какие могут быть сформулированы в рамках системы, должны получить уникальный номер, называемый «число Гёделя». Это должно быть сделано таким образом, чтобы имелась простая механическая процедура перевода числа Гёделя в утверждения и обратно. Например, можно использовать такую же схему, которая используется для кодирования символов в системе ASCII. Поскольку рассматриваемая система по предположению теоремы достаточно сильная, чтобы рассматривать числа, после кодирования она может рассматривать и закодированные формулы и утверждения.

Формула \(F(x)\), которая содержит ровно одну свободную переменную \(x\), называется «формой утверждения» или «знаком класса». Поскольку \(x\) заменяется определённым числом, форма утверждения преобразуется в «добросовестное утверждение», и оно, либо доказываемо в системе, либо нет. Для определённых формул можно показать, что для каждого натурального числа \(n\) выражение \(F(n)\) истинно тогда и только тогда, когда оно доказуемо, (точное требование оригинального доказательства несколько слабее, но для набросков доказательства приведённого рассуждения достаточно). В частности, это истинно для каждой специфицированной арифметической операции над конечными натуральными числами, как например «\(2 \times 3 = 6\)».

Формы утверждения сами по себе не являются утверждениями, а потому не могут быть доказаны или опровергнуты. Но каждая форма утверждения \(F(x)\) может быть ассоциирована с числом Гёделя, которое обозначается как \(G(F)\). Выбор свободной переменной не влияет на выбор числа Гёделя \(G(F)\).

Теперь необходимо применить трюк: описания доказательств могут быть сами записаны при помощи чисел Гёделя. Это происходит следующим образом. Поскольку доказательство — это список утверждений, подчиняющихся некоторым правилам, можно определить число Гёделя для доказательства. Теперь для каждого утверждения \(S\) можно спросить, является ли число \(x\) числом Гёделя для его доказательства. Отношение между числом Гёделя утверждения \(S\) и \(x\) (число Гёделя доказательства \(S\)) является арифметическим отношением между двумя числами.

Форма утверждения \(F\) называется само-недоказуемым, если \(F(G(F))\) (форма \(F\), применённая к своему собственному числу Гёделя) недоказуема. Эта концепция может быть определена формально, и можно сконструировать форму утверждения \(SU(z)\), чья интерпретация заключается в том, что число \(z\) является числом Гёделя для само-недоказуемой формы. Формально \(SU(z)\) определяется как: если \(z = G(F)\) для некоторой формы \(F(x)\), тогда для каждого числа \(x\) это число не является числом Гёделя для доказательства \(F(G(F))\).

Важное свойство \(SU\) заключается в том, что она может быть (грубо) определена таким образом, что в непротиворечивой системе для каждого заданного числа \(z\), применение \(SU(z)\) доказуемо тогда и только тогда, когда оно истинно (потому, что имеется ровно одно число \(x\), которое является числом Гёделя для доказательства утверждения \(S\), и при \(y = G(S)\) имеется прямое арифметическое отношение между \(x\) и \(y\), которое может быть просто проверено). Это предположение не совсем аккуратно, но вполне достаточно для наброска к доказательству.

Теперь желаемое утверждение \(p\), упомянутое ранее, может быть построено как \(p = SU(G(SU))\). Это эквивалентно утверждению того, что \(SU(G(SU))\) не может быть доказано, то есть \(p\) не может быть доказано.

Интуитивно понятно, что вопрос о том, является ли \(p\) истинным, является вопросом «Правда ли, что свойство само-недоказуемости само по себе само-недоказуемо?» Такая формулировка очень похожа на парадокс брадобрея о брадобрее, который бреет тех и только тех, кто не бреется сам. Бреется ли брадобрей сам?

Теперь можно предположить, что взятая система аксиом \(\omega\)-непротиворечива. В этом случае если \(p\) было бы доказуемым, оно было бы истинным. Но в этом случае \(p\) эквивалентно утверждению, что \(p\) недоказуемо. Это противоречие показывает, что \(p\) не может быть доказано.

Если бы отрицание \(p\) было доказуемым, тогда по определению \(SU\) это значило бы, что можно доказать существование числа Гёделя доказательства \(SU(G(SU))\). Однако для каждого заданного числа \(x\), оно не может быть числом Гёделя доказательства утверждения \(SU(G(SU))\), поскольку \(p = SU(G(SU))\) недоказуемо, как уже показано. Так что с одной стороны невозможно доказать, что существует число с заданным свойством (число Гёделя доказательства \(p\)), но с другой стороны для каждого заданного числа невозможно доказать, что оно не имеет этого свойства. Это невозможно в \(\omega\)-непротиворечивой системе. А потому отрицание \(p\) недоказуемо.

Таким образом, утверждение \(p\) невычислимо, так как оно не может быть ни доказанным, ни опровергнутым в рамках выбранной системы.

Наброски к доказательству второй теоремы

Пусть \(p\) — невычислимое утверждение, созданное выше. Пусть непротиворечивость системы может быть доказана в рамках самой системы. В предыдущем разделе показано, что если система непротиворечива, то утверждение \(p\) недоказуемо.

Доказательство этой импликации может быть формализовано в рамках самой системы, а потому либо утверждение «\(p\) недоказуемо», либо утверждение «\(\neg P(p)\)» доказуемо в системе.

Но это последнее утверждение само по себе эквивалентно \(p\) (и эта эквивалентность может быть доказана в рамках системы), так что \(p\) может быть доказано в системе. Данное противоречие показывает, что система должна быть противоречивой.

См. также

• Теорема Гёделя о полноте
• Доказательство непротиворечивости
• Диагональный процесс Кантора
• Недоказуемость
• Формальная логика

Литература

Работы Гёделя

• 1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38: 173-98.
  • Hirzel, Martin, 2000, On formally undecidable propositions of Principia Mathematica and related systems I.. Современный перевод.
• 1951, Some basic theorems on the foundations of mathematics and their implications в Solomon Feferman, ed., 1995. Collected works / Kurt Gödel, Vol. III. Oxford University Press: 304-23.

Работы иных авторов

• Успенский В. А. Теорема Гёделя о неполноте. «Популярные лекции по математике» М.: «Наука», 1982 г., 114 стр.

Ссылки

• Академик Ю. Л. Ершов «Доказательность в математике», программа А. Гордона от 16 июня 2003 года
• А. Б. Сосинский «Теорема Геделя», летняя школа «Современная математика», Дубна, 2006
• П. Дж. Коэн «Об основаниях теории множеств»
• М. Кордонский «Конец истины»