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

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

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

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

История

Курт Гёдель доказал счетную теорему о компактности в 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 .

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

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