Вторая теорема Гёделя о неполноте

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

История

Предпосылки и контекст

На рубеже XIX—XX веков в математике возник кризис оснований, вызванный, в частности, открытием парадоксов в теории множеств (парадокс Рассела, парадокс Кантора). Это привело к попыткам построить формальные аксиоматические системы, которые были бы одновременно полными (любое истинное утверждение можно доказать) и непротиворечивыми (в системе нельзя вывести противоречие). Наиболее амбициозной программой стала программа Гильберта, сформулированная Давидом Гильбертом в 1920-х годах. Она предполагала, что вся математика может быть формализована в виде конечной системы аксиом, а затем можно доказать её непротиворечивость финитными (конечными, конструктивными) методами.

Открытие Гёделя

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

В 1931 году он опубликовал статью «О формально неразрешимых предложениях Principia Mathematica и родственных систем I», в которой, помимо первой теоремы, была сформулирована и вторая. Гёдель показал, что если система непротиворечива, то утверждение о её непротиворечивости как раз и является одним из тех истинных, но недоказуемых утверждений, о которых говорится в первой теореме. Таким образом, непротиворечивость системы не может быть доказана её собственными средствами.

Реакция и последствия

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

Формулировка и ключевые понятия

Формальная система

Для понимания теоремы необходимо определить, что такое формальная система. Это набор аксиом и правил вывода, записанных на формальном языке (например, языке логики первого порядка). Все утверждения в такой системе имеют строгую синтаксическую форму, а доказательства представляют собой конечные последовательности формул, каждая из которых либо является аксиомой, либо получена из предыдущих по правилам вывода. Примером формальной системы является арифметика Пеано (PA) или теория множеств Цермело — Френкеля (ZF).

Непротиворечивость

Формальная система называется непротиворечивой, если в ней нельзя вывести одновременно некоторое утверждение и его отрицание. Иными словами, в системе нет противоречия. Если система противоречива, то из неё можно вывести любое утверждение (принцип взрыва), что делает её тривиальной и бесполезной для математики.

Арифметизация

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

Формализованное утверждение о непротиворечивости

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

Содержание теоремы

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

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

Из этого вытекают несколько следствий:

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

Связь с первой теоремой

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

Доказательство (схема)

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

1. Арифметизация синтаксиса: С помощью гёделевой нумерации строится предикат Bew(x), который истинен тогда и только тогда, когда x является гёделевым номером доказуемой формулы. (Bew — от немецкого beweisbar, «доказуемый»).
2. Построение гёделева предложения: Строится формула G, которая утверждает: «Не существует доказательства G». Формально G ⇔ ¬Bew(⌜G⌝).
3. Доказательство недоказуемости G: Показывается, что если бы G была доказуема, то система была бы противоречива. Если бы ¬G была доказуема, то система также была бы противоречива. Следовательно, если система непротиворечива, G недоказуема и ¬G недоказуема.
4. Формализация доказательства: Далее Гёдель показывает, что само доказательство непротиворечивости системы (Con(S)) можно формализовать внутри системы. Затем он доказывает, что Con(S) влечёт G (Con(S) → G). Поскольку G недоказуема, то и Con(S) недоказуема. Если бы Con(S) была доказуема, то по правилу modus ponens была бы доказуема и G, что противоречит первой теореме.

Значение и влияние

В математике

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

В философии

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

В информатике

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

В популярной культуре

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

Критика и ограничения

• Требование непротиворечивости: Теорема применима только к непротиворечивым системам. Если система противоречива, то в ней доказуемо всё, включая Con(S), но это не имеет значения.
• Ограничение на мощность: Теорема справедлива только для систем, достаточно мощных, чтобы выразить арифметику. Существуют слабые формальные системы (например, логика высказываний), которые полны и непротиворечивы, но они не могут выразить арифметику.
• Необходимость метаматематики: Доказательство непротиворечивости возможно, но только в более сильной системе. Это создаёт бесконечную иерархию систем, где каждая следующая доказывает непротиворечивость предыдущей.

Источники

• Гёдель, К. «О формально неразрешимых предложениях Principia Mathematica и родственных систем I» (1931).
• Клини, С. К. «Введение в метаматематику» (1952).
• Нагель, Э., Ньюмен, Дж. Р. «Теорема Гёделя» (1958).
• Смирнов, В. А. «Логические системы и их непротиворечивость» (1983).
• Успенский, В. А. «Теорема Гёделя о неполноте» (1994).