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

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

Что утверждает теорема о полноте

Формально теорема о полноте звучит так: для любой формулы $\varphi$ логики первого порядка

$$\vDash \varphi \quad\Longleftrightarrow\quad \vdash \varphi.$$

Слева - семантическое следование: $\vDash \varphi$ означает, что $\varphi$ общезначима, то есть истинна в любой интерпретации (модели) на любом непустом множестве. Справа - синтаксическое выведение: $\vdash \varphi$ означает, что $\varphi$ можно формально вывести из аксиом исчисления предикатов по правилам вывода за конечное число шагов.

Содержательная часть теоремы - стрелка справа налево: если формула истинна везде, она доказуема. Обратная стрелка ($\vdash \varphi \Rightarrow \vDash \varphi$) - это корректность (soundness) исчисления, она проверяется почти механически и обычно доказывается отдельно и легко.

Рассчитать для своей задачи

В более общей форме теорема говорит о выводимости из множества посылок $\Gamma$:

$$\Gamma \vDash \varphi \quad\Longleftrightarrow\quad \Gamma \vdash \varphi.$$

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

Полнота против неполноты: не путать

Это место, где спотыкаются почти все. Гёдель доказал две разные теоремы:

• Теорема о полноте (1929) - про исчисление предикатов как систему вывода: формальный аппарат логики первого порядка достаточно силён, чтобы доказать каждую общезначимую формулу.
• Теорема о неполноте (1931) - про конкретные содержательные теории вроде арифметики Пеано: в любой непротиворечивой и достаточно богатой теории найдётся истинное утверждение, которое в ней недоказуемо.

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

Ключевые понятия: модель, общезначимость, выводимость

Чтобы строго понять формулировку, нужны три кирпича.

Модель (интерпретация). Это непустое множество $M$ (носитель) плюс назначение смысла каждому символу языка: предикатам - отношения на $M$, функциям - операции, константам - элементы. В модели каждая замкнутая формула получает истинностное значение.

Общезначимость. Формула $\varphi$ общезначима, если она истинна в каждой модели при любой интерпретации переменных. Пример: $\forall x\, (P(x) \to P(x))$ истинна всегда, независимо от того, что значит $P$.

Выводимость. Существует фиксированный список логических аксиом и правил (например, modus ponens и правило обобщения). Формула выводима, если есть конечная цепочка формул, каждая из которых - аксиома или получена из предыдущих по правилу, заканчивающаяся на $\varphi$.

Теорема о полноте связывает «истинно во всех мыслимых мирах» (семантика, потенциально про бесконечное число моделей) с «доказуемо за конечное число шагов» (синтаксис). Именно эта связь делает логику первого порядка такой удобной рабочей системой.

Идея доказательства (метод Хенкина)

Самое прозрачное современное доказательство принадлежит Леону Хенкину (1949). Его удобно формулировать через контрапозицию: вместо «общезначимая ⇒ доказуема» доказывают «непротиворечивое множество имеет модель».

Рассчитать для своей задачи

Ключевые шаги построения модели для непротиворечивого множества $\Gamma$:

1. Пополнение до максимального. $\Gamma$ расширяют до максимального непротиворечивого множества $\Gamma^*$ - такого, что для каждой формулы $\psi$ либо $\psi \in \Gamma^*$, либо $\neg\psi \in \Gamma^*$.
2. Свидетели Хенкина. Для каждой формулы вида $\exists x\, \psi(x)$ в язык добавляют новую константу-«свидетеля» $c$ и аксиому $\exists x\,\psi(x) \to \psi(c)$, гарантируя, что существование подтверждается конкретным объектом.
3. Каноническая модель. Носителем берут сами замкнутые термы языка (с точностью до доказуемого равенства). Предикаты интерпретируют так: $P(t_1,\dots,t_n)$ истинно тогда и только тогда, когда $P(t_1,\dots,t_n) \in \Gamma^*$.
4. Лемма об истинности. Доказывают индукцией по структуре формулы, что в этой модели истинны ровно формулы из $\Gamma^*$, а значит и все формулы из $\Gamma$.

Получается: раз у непротиворечивого $\Gamma$ есть модель, то недоказуемая формула $\varphi$ (для которой $\Gamma \cup \{\neg\varphi\}$ непротиворечиво) не может быть общезначимой - найдётся модель, где она ложна. Контрапозиция и даёт полноту.

Следствие: теорема компактности

Из теоремы о полноте почти даром выводится теорема компактности - один из самых мощных инструментов теории моделей.

Доказательство в одну строку: доказательство любой формулы - конечный объект, в нём задействовано лишь конечное число посылок из $\Gamma$. Поэтому если $\Gamma$ противоречиво (из него выводимо $\bot$), то противоречиво уже какое-то конечное подмножество. Через полноту «противоречиво» переводится в «не имеет модели» - и компактность готова.

Компактность лежит в основе нестандартного анализа: добавив к аксиомам вещественных чисел утверждения $c > 0$, $c > 1$, $c > 2$, $\dots$, получаем согласованное (каждое конечное подмножество выполнимо) множество, у которого есть модель с бесконечно большим элементом. Это формальное оправдание бесконечно малых; тонкости же непрерывности на бесконечных множествах разбираются в теореме Кантора о равномерной непрерывности.

Почему теорема не работает для логики второго порядка

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

Это объясняет, почему логика первого порядка стала стандартным языком оснований математики: она достаточно выразительна для аксиоматики теории множеств и при этом обладает полным, корректным и эффективно проверяемым исчислением вывода.

Частые ошибки

• Путают полноту с неполнотой. Теорема о полноте говорит, что логика доказывает все валидные формулы; теорема о неполноте - что арифметика не доказывает все истины о числах. Это разные теоремы про разные объекты.
• Считают, что полнота даёт алгоритм решения. Полнота гарантирует существование доказательства для валидной формулы, но не быстрый способ его найти; общая проблема разрешимости логики первого порядка алгоритмически неразрешима (теорема Чёрча).
• Забывают про корректность. Без отдельно доказанной корректности ($\vdash \Rightarrow \vDash$) равенство $\vdash$ и $\vDash$ не замыкается - это две половины утверждения.
• Думают, что модель всегда конечна. Каноническая модель Хенкина обычно бесконечна (счётна), и в общем случае конечной модели может не существовать.
• Применяют теорему ко второму порядку. Для логики второго порядка теорема о полноте ложна - путать порядки нельзя.

FAQ

Чем теорема о полноте отличается от теоремы о неполноте? Полнота - про логическое исчисление: каждая общезначимая формула первого порядка доказуема. Неполнота - про содержательные теории: в арифметике Пеано есть истинные, но недоказуемые утверждения. Первая хвалит логику, вторая ограничивает теории. Объекты разные, противоречия нет.

Кто и когда доказал теорему о полноте? Курт Гёдель в своей докторской диссертации 1929 года (опубликована в 1930). Наиболее популярное сегодня доказательство дал Леон Хенкин в 1949 году методом построения канонической модели из свидетелей.

Зачем нужна теорема о полноте на практике? Она оправдывает работу с формальными доказательствами: если что-то истинно во всех моделях, доказательство существует. Из неё следует теорема компактности, на которой стоит вся теория моделей и нестандартный анализ.

Коротко

Теорема Гёделя о полноте устанавливает совпадение синтаксиса и семантики в логике первого порядка: доказуемость равна общезначимости ($\vdash \varphi \Leftrightarrow \vDash \varphi$). Содержательная часть - каждая истинная во всех моделях формула выводима из аксиом; доказывается методом Хенкина через построение модели из непротиворечивого множества. Из неё следует теорема компактности, а сам результат не нужно путать с теоремой о неполноте, которая ограничивает уже содержательные теории, а не логическое исчисление.