Теорема о компактности

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

История

Истоки теоремы о компактности восходят к работам Леопольда Лёвенгейма (1915) и Альфреда Тарского (1920-е годы) по теории моделей. В 1930 году Курт Гёдель в своей диссертации доказал теорему о полноте для исчисления предикатов первого порядка, из которой теорема о компактности следовала как прямое следствие. Однако в явном виде она была сформулирована и доказана Анатолием Мальцевым в 1936 году для случая счетных языков. Мальцев применил её для доказательства существования неархимедовых упорядоченных полей и других алгебраических структур.

В 1950-х годах Леон Хенкин и Абрахам Робинсон обобщили теорему на произвольные (в том числе несчетные) языки, используя ультрапроизведения и теорему об ультрафильтрах. В современной теории моделей теорема о компактности рассматривается как одно из центральных свойств логики первого порядка, отличающее её от логик высших порядков.

Формулировка

Пусть L — язык первого порядка, а S — произвольное (возможно, бесконечное) множество формул этого языка. Теорема о компактности утверждает:

S имеет модель тогда и только тогда, когда каждое конечное подмножество S₀ ⊆ S имеет модель.

В терминах выполнимости: если любое конечное подмножество формул из S одновременно выполнимо, то и всё множество S выполнимо.

Эквивалентные формулировки

• Свойство конечного пересечения: Если для любого конечного набора формул существует интерпретация, в которой все они истинны, то существует интерпретация, в которой истинны все формулы из S.
• Компактность пространства типов: Пространство полных типов над данной теорией компактно в топологии, порождённой формулами (как замкнутыми множествами).
• Секвенциальная компактность: Из любой последовательности моделей теории T можно выделить подпоследовательность, сходящуюся к некоторой модели T (в смысле ультрапроизведений).

Доказательство

Через теорему Гёделя о полноте

Наиболее прямое доказательство использует теорему Гёделя о полноте: если каждое конечное подмножество S имеет модель, то каждое такое подмножество непротиворечиво в исчислении предикатов. Следовательно, всё множество S непротиворечиво, и по теореме о полноте оно имеет модель.

Через ультрапроизведения

Другой подход — конструктивный, с использованием ультрафильтров. Пусть I — множество всех конечных подмножеств S. Для каждого i ∈ I выберем модель Mᵢ, удовлетворяющую всем формулам из i. Рассмотрим ультрафильтр U на I, содержащий все множества вида { j ∈ I | j ⊇ i₀ } для каждого i₀. Тогда ультрапроизведение ∏ Mᵢ / U является моделью всего множества S.

Следствия и применения

В теории моделей

• Теорема Лёвенгейма — Скулема: Из теоремы о компактности следует, что если теория имеет бесконечную модель, то она имеет модели любой бесконечной мощности (при условии, что язык не более чем счётный).
• Нестандартные модели: Теорема позволяет доказывать существование нестандартных моделей арифметики (например, модели Пеано с бесконечно большими числами) и неархимедовых упорядоченных полей.
• Топология пространства типов: Компактность пространства типов — прямое следствие теоремы о компактности.

В алгебре

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

В анализе

• Нестандартный анализ: Абрахам Робинсон в 1960-х годах использовал теорему о компактности для построения нестандартных моделей вещественных чисел, содержащих бесконечно малые и бесконечно большие величины.

Ограничения

• Теорема о компактности не выполняется для логик высших порядков (второго порядка, логики с кванторами по предикатам). Например, множество аксиом конечности (все конечные подмножества выполнимы, но всё множество — нет) не имеет модели в логике второго порядка.
• Для логики первого порядка с бесконечными кванторами (например, L_{ω₁,ω}) теорема также не верна.
• В конструктивной математике и интуиционистской логике теорема о компактности может не выполняться, так как её доказательство существенно опирается на закон исключённого третьего и аксиому выбора.

Связь с другими теоремами

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

Примеры

Пример 1: Нестандартная модель арифметики

Рассмотрим теорию PA (арифметика Пеано) и добавим к ней бесконечно много констант c₁, c₂, … с аксиомами: c₁ > 0, c₂ > 1, c₃ > 2, …. Любое конечное подмножество этих аксиом имеет модель (например, стандартную модель ℕ с достаточно большим значением константы). По теореме о компактности существует модель, в которой все константы больше всех натуральных чисел — то есть модель с бесконечно большими числами.

Пример 2: Графы с произвольно большими кликами

Пусть T — теория графов (неориентированных, без петель). Добавим аксиомы, утверждающие, что для каждого n существует клика размера n (то есть подграф, изоморфный полному графу Kₙ). Любое конечное подмножество этих аксиом выполнимо (например, в графе, состоящем из одной большой клики). По теореме о компактности существует граф, содержащий клики всех конечных размеров, но не обязательно бесконечную клику.

Интересные факты

• Теорема о компактности является одним из немногих утверждений математической логики, которое нашло применение в «обычной» математике (алгебре, анализе, топологии) без явного использования логической терминологии.
• В 1970-х годах советский математик Юрий Матиясевич доказал, что для диофантовых уравнений (10-я проблема Гильберта) теорема о компактности не работает: существует бесконечное множество диофантовых уравнений, каждое конечное подмножество которых имеет решение, но всё множество — нет.
• Теорема о компактности эквивалентна аксиоме выбора (над ZF) для несчётных языков; для счётных языков она доказуема в ZF без аксиомы выбора.

Источники

• Ч. Ч. Чен, Р. Л. Ли. Символическая логика и её применения. — М.: Мир, 1981.
• Дж. Барвайс (ред.). Справочная книга по математической логике. Часть I. Теория моделей. — М.: Наука, 1982.
• А. И. Мальцев. Алгебраические системы. — М.: Наука, 1970.
• Э. Мендельсон. Введение в математическую логику. — М.: Наука, 1976.
• К. Гёдель. О полноте исчисления предикатов (1930) // Сборник трудов. — М.: Наука, 1980.