Синтаксическая полнота

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

Определение и формализация

Формально, формальная система \( S \) называется синтаксически полной (или просто полной), если для любой замкнутой формулы \( \phi \) (то есть формулы без свободных переменных), выраженной на языке системы, выполняется: либо \( S \vdash \phi \), либо \( S \vdash \neg \phi \). Здесь \( \vdash \) обозначает отношение выводимости: формула является теоремой системы.

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

История и контекст

Понятие синтаксической полноты возникло в рамках программы Гильберта по обоснованию математики. Давид Гильберт в начале XX века поставил задачу доказать непротиворечивость и полноту формальных систем, лежащих в основе арифметики и анализа. Однако в 1931 году Курт Гёдель доказал свою первую теорему о неполноте, которая показала, что любая непротиворечивая формальная система, достаточно мощная, чтобы выразить арифметику натуральных чисел, не может быть синтаксически полной. Это стало одним из самых значительных результатов в математической логике.

Виды синтаксической полноты

В зависимости от контекста выделяют несколько разновидностей синтаксической полноты:

Полнота по Гёделю (дедуктивная полнота)

Это классическое определение, данное выше. Система полна по Гёделю, если она может доказать или опровергнуть любое утверждение своего языка. Как показал Гёдель, арифметика Пеано (PA) и теория множеств Цермело — Френкеля (ZFC) не являются полными в этом смысле.

Полнота по Посту (консистентная полнота)

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

Логическая полнота

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

Полнота теории

Теория (множество формул, замкнутое относительно выводимости) называется полной, если для любой формулы \( \phi \) либо \( \phi \in T \), либо \( \neg \phi \in T \). Примеры полных теорий: теория плотных линейных порядков без концов, теория алгебраически замкнутых полей фиксированной характеристики.

Примеры полных и неполных систем

Полные системы

• Исчисление высказываний (классическое) — синтаксически полно. Любая тавтология выводима, любая не-тавтология опровержима.
• Теория вещественно замкнутых полей (RCF) — полна. Это следует из результата Альфреда Тарского об элиминации кванторов.
• Арифметика Пресбургера (арифметика натуральных чисел без умножения) — полна и разрешима.
• Теория плотных линейных порядков без концов (например, рациональные числа с отношением <) — полна.

Неполные системы

• Арифметика Пеано (PA) — неполна (первая теорема Гёделя). Существуют неразрешимые утверждения, такие как «предложение Гёделя» или утверждение о непротиворечивости PA.
• Теория множеств Цермело — Френкеля (ZFC) — неполна. Например, континуум-гипотеза не может быть ни доказана, ни опровергнута в ZFC (при условии её непротиворечивости).
• Логика первого порядка — неполна как теория (множество общезначимых формул не является рекурсивно перечислимым), хотя она семантически полна (теорема Гёделя о полноте).

Связь с непротиворечивостью и разрешимостью

Синтаксическая полнота тесно связана с непротиворечивостью. Непротиворечивая система не может одновременно доказывать и \( \phi \), и \( \neg \phi \). Полная система, напротив, для каждой формулы выбирает одну из сторон. Если система полна и непротиворечива, то она является максимально непротиворечивой. Такие системы часто называют полными теориями.

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

Значение и приложения

Понятие синтаксической полноты имеет фундаментальное значение для:

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

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

Концепция синтаксической полноты подверглась критике с позиций интуиционизма и конструктивизма. Л. Э. Я. Брауэр и его последователи отрицают закон исключённого третьего, поэтому для них классическое определение полноты теряет смысл. В интуиционистской логике система может быть полной в другом смысле — например, если любая доказуемая формула имеет конструктивное доказательство.

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

Источники

• Гёдель, К. «О формально неразрешимых предложениях Principia Mathematica и родственных систем I». Monatshefte für Mathematik und Physik, 1931.
• Мендельсон, Э. «Введение в математическую логику». — М.: Наука, 1976.
• Тарский, А. «Понятие истины в формализованных языках». Studia Logica, 1933.
• Шенфилд, Дж. «Математическая логика». — М.: Мир, 1975.
• Клини, С. К. «Введение в метаматематику». — М.: Иностранная литература, 1957.