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

Теорема

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

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

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

История

Курт Гёдель доказал теорему о счетной компактности в 1930 году. Анатолий Мальцев доказал несчетный случай в 1936 году. ^{[3] [4]}

Приложения

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

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

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

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

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

Теорема Левенгейма–Скулема вверх

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Примечания

1. См. Трасс (1997).
2. J. Barwise, S. Feferman, eds., Model-Theoretic Logics (New York: Springer-Verlag, 1985) [1], в частности, Makowsky, JA Chapter XVIII: Compactness, Embeddings and Definability. 645--716, см. Theorems 4.5.9, 4.6.12 и Proposition 4.6.9. О компактных логиках для расширенного понятия модели см. Ziegler, M. Chapter XV: Topological Model Theory. 557--577. Для логик без свойства релятивизации возможно одновременное наличие компактности и интерполяции, в то время как для логик с релятивизацией проблема все еще открыта. См. Xavier Caicedo, A Simple Solution to Friedman's Fourth Problem, J. Symbolic Logic, Volume 51, Issue 3 (1986), 778-784. doi : 10.2307/2274031 JSTOR  2274031
3. Vaught, Robert L .: «Работа Альфреда Тарского в теории моделей». Journal of Symbolic Logic 51 (1986), № 4, 869–882
4. Робинсон, А .: Нестандартный анализ . North-Holland Publishing Co., Амстердам, 1966. стр. 48.
5. Marker 2002, стр. 40–43.
6. Гауэрс, Барроу-Грин и Лидер 2008, стр. 639–643.
7. Terence, Tao (7 марта 2009 г.). «Бесконечные поля, конечные поля и теорема Акса-Гротендика».
8. Голдблатт 1998, стр. 10–11.
9. Голдблатт 1998, стр. 11.
10. См. Ходжес (1993).

Ссылки

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

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

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