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

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

История

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

Независимо от Гёделя, в 1936 году советский математик Анатолий Иванович Мальцев опубликовал работу, в которой применил компактность к алгебраическим задачам, в частности к теории групп. Именно Мальцев впервые осознал важность теоремы для построения моделей с заданными свойствами, и в русскоязычной литературе теорему часто называют теоремой Мальцева. В 1941 году Мальцев доказал обобщение для логики первого порядка с равенством, а в 1950-х годах теорема была окончательно формализована в рамках теории моделей.

Формулировка и доказательство

Классическая формулировка

Пусть \( \Phi \) — множество предложений (замкнутых формул) логики первого порядка. Говорят, что \( \Phi \) компактно, если из того, что каждое конечное подмножество \( \Phi_0 \subseteq \Phi \) имеет модель, следует, что и всё \( \Phi \) имеет модель. Эквивалентная формулировка: если \( \Phi \) не имеет модели, то существует конечное подмножество \( \Phi_0 \subseteq \Phi \), которое также не имеет модели.

Доказательство (через теорему о полноте)

Наиболее распространённое доказательство использует теорему Гёделя о полноте. Если \( \Phi \) не имеет модели, то оно противоречиво, то есть из \( \Phi \) выводится противоречие (например, формула \( \bot \)). По определению выводимости, любое доказательство использует лишь конечное число аксиом из \( \Phi \). Следовательно, существует конечное подмножество \( \Phi_0 \subseteq \Phi \), из которого выводится противоречие, а значит, \( \Phi_0 \) не имеет модели. Обратное утверждение (если все конечные подмножества имеют модель, то и всё множество имеет модель) вытекает из контрапозиции.

Доказательство через ультрапроизведения

Альтернативное доказательство использует конструкцию ультрапроизведения. Пусть для каждого конечного подмножества \( \Phi_0 \subseteq \Phi \) существует модель \( \mathcal{M}_{\Phi_0} \). Рассмотрим множество индексов \( I = \{ \Phi_0 \subseteq \Phi \mid \Phi_0 \text{ конечно} \} \). На \( I \) можно задать ультрафильтр, состоящий из множеств вида \( \{ \Phi_0 \mid a \in \Phi_0 \} \) для каждого предложения \( a \in \Phi \). Тогда ультрапроизведение моделей \( \mathcal{M}_{\Phi_0} \) по этому ультрафильтру является моделью всего \( \Phi \). Этот подход особенно полезен в теории моделей для построения нестандартных моделей.

Применения

В алгебре

Одно из первых приложений теоремы компактности — доказательство существования алгебраических структур с заданными свойствами. Например, Мальцев доказал, что если каждая конечная подгруппа некоторой группы вложима в группу с данным свойством (например, в разрешимую группу), то и вся группа вложима. Аналогично, теорема позволяет строить поля произвольной характеристики, содержащие заданное поле, или доказывать, что любое локально нильпотентное кольцо является нильпотентным (при определённых ограничениях).

В нестандартном анализе

Теорема компактности лежит в основе нестандартного анализа Абрахама Робинсона (1960-е годы). Рассмотрим теорию действительных чисел \( \mathbb{R} \) в сигнатуре \( \{ +, \cdot, 0, 1, < \} \). Добавим к ней константу \( c \) и аксиомы: \( c > 0 \), \( c < 1/n \) для каждого натурального \( n \). Любое конечное подмножество этих аксиом имеет модель (например, в \( \mathbb{R} \) можно взять \( c = 1/(N+1) \) для достаточно большого \( N \)). По теореме компактности, существует модель, содержащая бесконечно малый элемент \( c \), то есть нестандартную модель действительных чисел.

В теории графов

Теорема компактности позволяет переносить свойства с конечных графов на бесконечные. Например, теорема де Брёйна — Эрдёша: если в конечном графе хроматическое число не превосходит \( k \), то и в любом его подграфе оно не превосходит \( k \). С помощью компактности доказывается, что граф \( k \)-раскрашиваем тогда и только тогда, когда каждый его конечный подграф \( k \)-раскрашиваем. Это следует из того, что свойство «граф \( k \)-раскрашиваем» выразимо в логике первого порядка.

В теории меры и топологии

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

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

Теорема Лёвенгейма — Сколема

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

Теорема о полноте

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

Ограничения и обобщения

Для логик высших порядков

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

Для бесконечных языков

Существуют обобщения теоремы для логик с бесконечными дизъюнкциями и конъюнкциями (так называемые \( L_{\omega_1, \omega} \)), но там компактность, как правило, не выполняется. Исключением являются некоторые фрагменты, такие как логика \( L_{\kappa, \kappa} \) для слабо компактных кардиналов \( \kappa \).

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

• Теорема компактности иногда парадоксальна для интуиции: она утверждает, что если каждое конечное подмножество аксиом имеет модель, то и всё бесконечное множество имеет модель. Однако построенная модель может быть нестандартной (содержать нестандартные элементы), что не всегда очевидно.
• В 1960-х годах Абрахам Робинсон использовал теорему компактности для доказательства существования бесконечно малых и бесконечно больших чисел, что возродило интерес к нестандартному анализу, предложенному Лейбницем.
• Теорема компактности эквивалентна принципу ультрафильтра (аксиоме выбора) в теории множеств Цермело — Френкеля. Без аксиомы выбора она может не выполняться для некоторых множеств предложений.

Источники

• Гёдель, К. «О полноте аксиом логического исчисления». 1930.
• Мальцев, А. И. «Об одном общем методе получения локальных теорем теории групп». 1936.
• Чен, Ч., Кейслер, Г. «Теория моделей». 1973.
• Робинсон, А. «Нестандартный анализ». 1966.
• Ершов, Ю. Л., Палютин, Е. А. «Математическая логика». 1987.