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

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

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

Теорема о компактности — одно из двух ключевых свойств, наряду с нисходящей теоремой Левенхайма-Скулема , которая используется в теореме Линдстрема для характеристики логики первого порядка. Хотя существуют некоторые обобщения теоремы о компактности на логики не первого порядка, сама теорема о компактности в них не выполняется, за исключением очень ограниченного числа примеров.

История

Курт Гёдель доказал счетную теорему о компактности в 1930 году. Анатолий Мальцев доказал несчетный случай в 1936 году.

Приложения

Теорема о компактности имеет множество приложений в теории моделей; Здесь представлены несколько типичных результатов.

Принцип Робинсона

Из теоремы компактности следует следующий результат, сформулированный Абрахамом Робинсоном в его диссертации 1949 года .

Принцип Робинсона : Если предложение первого порядка справедливо в каждом поле , нулевой характеристики то существует константа $p$ так что это предложение справедливо для любого поля характеристики, превышающего $p.$ Это можно увидеть следующим образом: предположим, $\varphi$ — это предложение, которое справедливо в каждом поле нулевой характеристики. Тогда его отрицание $\lnot \varphi ,$ вместе с аксиомами поля и бесконечной последовательностью предложений $$1+1\neq 0,\;\;1+1+1\neq 0,\;\ldots$$невыполнима котором (поскольку не существует поля характеристики 0, в $\lnot \varphi$ выполняется, а бесконечная последовательность предложений гарантирует, что любая модель будет полем с характеристикой 0). Следовательно, существует конечное подмножество $A$ из этих предложений, что невыполнимо. $A$ должен содержать $\lnot \varphi$ потому что в противном случае это было бы выполнимо. Потому что добавление большего количества предложений к $A$ не меняет невыполнимости, можно считать, что $A$ содержит аксиомы поля и для некоторых $k,$ первый $k$ предложения формы $1+1+\cdots +1\neq 0.$ Позволять $B$ содержать все предложения $A$ кроме $\lnot \varphi .$ Тогда любое поле с характеристикой большей, чем $k$ является моделью $B,$ и $\lnot \varphi$ вместе с $B$ не является выполнимым. Это означает, что $\varphi$ должно присутствовать в каждой модели $B,$ что означает именно это $\varphi$ имеет место в каждом поле характеристики, большей, чем $k.$ Это завершает доказательство.

Принцип Лефшеца , один из первых примеров принципа переноса , расширяет этот результат. Предложение первого порядка $\varphi$ на языке колец верно в некотором (или, что то же самое, в каждом ) алгебраически замкнутом поле характеристики 0 (например, в комплексных числах ) тогда и только тогда, когда существует бесконечно много простых чисел. $p$ для чего $\varphi$ верно в некотором алгебраически замкнутом поле характеристики $p,$ в этом случае $\varphi$ верно во всех алгебраически замкнутых полях достаточно большой ненулевой характеристики $p.$ Одним из следствий является следующий частный случай теоремы Аха – Гротендика : все инъективные комплексные многочлены $\mathbb {C} ^{n}\to \mathbb {C} ^{n}$ сюръективны ​ (более того, можно даже показать, что его обратный тоже будет полиномом). Фактически вывод о сюръективности остается верным для любого инъективного многочлена $F^{n}\to F^{n}$ где $F$ — конечное поле или алгебраическое замыкание такого поля.

Восходящая теорема Левенхайма – Скулема

Второе применение теоремы о компактности показывает, что любая теория, имеющая сколь угодно большие конечные модели или одну бесконечную модель, имеет модели сколь угодно большой мощности (это теорема Левенхайма–Скулема вверх ). Так, например, существуют нестандартные модели арифметики Пеано с бесчисленным количеством «натуральных чисел». Чтобы добиться этого, позвольте $T$ — исходная теория и пусть $\kappa$ быть любым кардинальным числом . Добавьте к языку $T$ один постоянный символ для каждого элемента $\kappa .$ Затем добавьте в $T$ совокупность предложений, в которых говорится, что объекты, обозначаемые любыми двумя различными постоянными символами из новой коллекции, различны (это совокупность $\kappa ^{2}$ предложения). Поскольку каждое конечное подмножество этой новой теории выполнимо с помощью достаточно большой конечной модели $T,$ или по любой бесконечной модели вся расширенная теория выполнима. Но любая модель расширенной теории имеет мощность не менее $\kappa$.

Нестандартный анализ

Третье применение теоремы о компактности — построение нестандартных моделей действительных чисел, то есть непротиворечивых расширений теории действительных чисел, содержащих «бесконечно малые» числа. Чтобы увидеть это, позвольте $\Sigma$ быть аксиоматизацией первого порядка теории действительных чисел. Рассмотрим теорию, полученную добавлением нового постоянного символа $\varepsilon$ к языку и прилегающие к нему $\Sigma$ аксиома $\varepsilon >0$ и аксиомы $\varepsilon <{\tfrac {1}{n}}$ для всех положительных целых чисел $n.$ Очевидно, что стандартные действительные числа $\mathbb {R}$ являются моделью для каждого конечного подмножества этих аксиом, потому что действительные числа удовлетворяют всему в $\Sigma$ и, при соответствующем выборе $\varepsilon ,$ можно заставить удовлетворить любое конечное подмножество аксиом о $\varepsilon .$ По теореме компактности существует модель ${}^{*}\mathbb {R}$ это удовлетворяет $\Sigma$ а также содержит бесконечно малый элемент $\varepsilon .$

Аналогичное рассуждение, на этот раз примыкающее к аксиомам $\omega >0,\;\omega >1,\ldots ,$ и т. д., показывает, что существование чисел бесконечно больших величин не может быть исключено никакой аксиоматизацией. $\Sigma$ из реальных.

Можно показать, что гипердействительные числа ${}^{*}\mathbb {R}$ удовлетворить принципу передачи : предложение первого порядка верно для $\mathbb {R}$ тогда и только тогда, когда это верно для ${}^{*}\mathbb {R} .$

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

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

Первоначально Гёдель доказал теорему о компактности именно таким способом, но позднее были найдены некоторые «чисто семантические» доказательства теоремы о компактности; то есть доказательства, которые относятся к истине , а не к доказуемости . Одно из этих доказательств опирается на ультрапроизведения, зависящие от следующей аксиомы выбора:

Доказательство : Исправьте язык первого порядка $L,$ и пусть $\Sigma$ быть коллекцией $L$-предложения такие, что каждое конечное подмножество $L$-предложения, $i\subseteq \Sigma$ у него есть модель ${\mathcal {M}}_{i}.$ Также пусть ${\textstyle \prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}}$ быть прямым продуктом структур и $I$ быть совокупностью конечных подмножеств $\Sigma .$ Для каждого $i\in I,$ позволять $A_{i}=\{j\in I:j\supseteq i\}.$ Семейство всех этих наборов $A_{i}$ генерирует правильный фильтр , поэтому существует ультрафильтр $U$ содержащий все множества вида $A_{i}.$

Теперь для любого предложения $\varphi$ в $\Sigma :$

• набор $A_{\{\varphi \}}$ находится в $U$
• в любое время $j\in A_{\{\varphi \}},$ затем $\varphi \in j,$ следовательно $\varphi$ держится ${\mathcal {M}}_{j}$
• набор всего $j$ с имуществом, которое $\varphi$ держится ${\mathcal {M}}_{j}$ представляет собой надмножество $A_{\{\varphi \}},$ следовательно, и в $U$

Из теоремы Лоша теперь следует, что $\varphi$ содержится в ультрапродукте ${\textstyle \prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}/U.}$ Итак, это ультрапроизведение удовлетворяет всем формулам $\Sigma .$

См. также

• Теорема Барвайса о компактности
• Теорема Эрбрана - сведение математической логики первого порядка к логике высказываний. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Список тем по булевой алгебре
• Теорема Левенхайма – Скулема - Существование и мощность моделей логических теорий.

Ссылки

• Булос, Джордж; Джеффри, Ричард; Берджесс, Джон (2004). Вычислимость и логика (четвертое изд.). Издательство Кембриджского университета.
• Чанг, CC; Кейслер, Х. Джером (1989). Теория моделей (третье изд.). Эльзевир. ISBN  0-7204-0692-7 .
• Доусон, Джон В. младший (1993). «Компактность логики первого порядка: от Гёделя до Линдстрема». История и философия логики . 14 :15–37. дои : 10.1080/01445349308837208 .
• Ходжес, Уилфрид (1993). Модельная теория . Издательство Кембриджского университета. ISBN  0-521-30442-3 .
• Голдблатт, Роберт (1998). Лекции о гиперреальности . Нью-Йорк: Springer Verlag. ISBN  0-387-98464-Х .
• Гауэрс, Тимоти; Барроу-Грин, июнь; Лидер Имре (2008). Принстонский спутник математики . Принстон: Издательство Принстонского университета. стр. 635–646. ISBN  978-1-4008-3039-8 . OCLC   659590835 .
• Маркер, Дэвид (2002). Теория моделей: Введение . Тексты для аспирантов по математике . Том. 217. Спрингер. ISBN  978-0-387-98760-6 . OCLC   49326991 .
• Робинсон, Дж. А. (1965). «Машинно-ориентированная логика, основанная на принципе разрешения» . Журнал АКМ . 12 (1). Ассоциация вычислительной техники (ACM): 23–41. дои : 10.1145/321250.321253 . ISSN   0004-5411 . S2CID   14389185 .
• Трасс, Джон К. (1997). Основы математического анализа . Издательство Оксфордского университета. ISBN  0-19-853375-6 .

Внешние ссылки

• Теорема компактности , Интернет-энциклопедия философии .