В математической логике , то Компактность теорема утверждает , что множество из первого порядка предложений имеет модель тогда и только тогда , когда каждое конечное подмножество его имеет модель. Эта теорема является важным инструментом в теории моделей , поскольку она предоставляет полезный (но обычно не эффективный) метод построения моделей любого набора предложений, которые являются конечно непротиворечивыми .
Теорема о компактности для исчисления высказываний является следствием теоремы Тихонова (что говорит о том , что продукт из компактных пространств компактно) применяется к компактным Каменным пространствам , [1] , следовательно , название теоремы в. Аналогичным образом, это аналогично характеристике свойства конечного пересечения для компактности в топологических пространствах : совокупность замкнутых множеств в компактном пространстве имеет непустое пересечение, если каждое конечное подгруппа имеет непустое пересечение.
Теорема компактности является одним из двух ключевых свойств, наряду с нисходящей теоремой Левенгейма – Сколема , которая используется в теореме Линдстрема для характеристики логики первого порядка. Хотя есть некоторые обобщения теоремы компактности на логики не первого порядка, сама теорема компактности в них не выполняется, за исключением очень ограниченного числа примеров. [2]
История
Курт Гёдель доказал теорему счетной компактности в 1930 году. Анатолий Мальцев доказал несчетный случай в 1936 году. [3] [4]
Приложения
Теорема компактности имеет множество приложений в теории моделей; здесь представлены несколько типичных результатов.
Компактность теорема вытекает принцип Робинсона : Если первый заказ предложение имеет место в каждой области по характерному нулю, то существует константа р такое , что предложение имеет место для каждого поля характеристики больше , чем р . Это можно увидеть следующим образом: предположим, что φ - предложение, которое выполняется в любом поле нулевой характеристики. Тогда его отрицание ¬φ вместе с аксиомами поля и бесконечной последовательностью предложений 1 + 1 ≠ 0, 1 + 1 + 1 ≠ 0, ... невыполнимо (поскольку нет поля характеристики 0, в котором ¬φ выполняется , а бесконечная последовательность предложений гарантирует, что любая модель будет полем характеристики 0). Следовательно, существует конечное подмножество A этих предложений, которое не выполнимо. Мы можем предположить, что A содержит ¬φ, аксиомы поля и, для некоторого k , первые k предложений вида 1 + 1 + ... + 1 ≠ 0 (потому что добавление дополнительных предложений не меняет неудовлетворительности). Пусть B содержит все предложения A, кроме ¬φ. Тогда любое поле с характеристикой, большей, чем k, является моделью B , и ¬φ вместе с B невыполнимо . Это означает, что φ должен выполняться в каждой модели B , а это в точности означает, что φ выполняется в любом поле характеристики больше k .
Второе применение теоремы компактности показывает, что любая теория, которая имеет произвольно большие конечные модели или единственную бесконечную модель, имеет модели произвольной большой мощности (это теорема Апварда Левенгейма – Сколема ). Так, например, существуют нестандартные модели арифметики Пеано с несчетным количеством «натуральных чисел». Для этого пусть T - исходная теория, а κ - любое кардинальное число . Добавьте в язык T один постоянный символ для каждого элемента κ. Затем добавьте к T набор предложений, в которых говорится, что объекты, обозначенные любыми двумя различными постоянными символами из нового набора, различны (это набор из κ 2 предложений). Поскольку каждое конечное подмножество этой новой теории выполняется достаточно большой конечной моделью T или любой бесконечной моделью, выполнима вся расширенная теория. Но любая модель расширенной теории имеет мощность не менее κ
Третье приложение теоремы компактности - построение нестандартных моделей действительных чисел, то есть последовательных расширений теории действительных чисел, содержащих «бесконечно малые» числа. Чтобы убедиться в этом, пусть Σ - аксиоматизация первого порядка теории действительных чисел. Рассмотрим теорию, полученную путем добавления нового постоянного символа ε к языку и присоединения к Σ аксиомы ε> 0 и аксиом ε <1 / n для всех натуральных чисел n . Ясно, что стандартные действительные числа R являются моделью для каждого конечного подмножества этих аксиом, потому что действительные числа удовлетворяют всему в Σ и при подходящем выборе ε могут быть выполнены так, чтобы удовлетворять любому конечному подмножеству аксиом о ε. По теореме компактности существует модель * R , удовлетворяющая Σ, а также содержащая бесконечно малый элемент ε. Аналогичное рассуждение, примыкающее к аксиомам ω> 0, ω> 1 и т. Д., Показывает, что существование бесконечно больших целых чисел не может быть исключено какой-либо аксиоматизацией Σ вещественных чисел. [5]
Доказательства
Можно доказать теорему компактности, используя теорему Гёделя о полноте , которая устанавливает, что набор предложений выполним тогда и только тогда, когда из него нельзя доказать противоречие. Поскольку доказательства всегда конечны и, следовательно, включают только конечное число заданных предложений, следует теорема компактности. Фактически, теорема компактности эквивалентна теореме Гёделя о полноте, и обе эквивалентны булевой теореме о простом идеале , слабой форме аксиомы выбора . [6]
Гёдель первоначально доказал теорему компактности именно таким образом, но позже были найдены некоторые «чисто семантические» доказательства теоремы компактности, т. Е. Доказательства, которые относятся к истинности, но не к доказуемости . Одно из этих доказательств опирается на ультрапродукты, зависящие от выбранной аксиомы:
Доказательство. Зафиксируем язык L первого порядка и пусть Σ будет набором L-предложений таким образом, что каждая конечная подгруппа L-предложений, i ⊆ Σ, имеет модель. Также позвольте- прямое произведение структур, а I - набор конечных подмножеств Σ. Для каждого i в I положим A i : = { j ∈ I : j ⊇ i }. Семейство всех этих наборов A i порождает правильный фильтр , поэтому существует ультрафильтр U, содержащий все наборы вида A i .
Теперь для любой формулы φ из Σ имеем:
- множество A {φ} лежит в U
- если j ∈ A {φ} , то φ ∈ j , следовательно, φ выполняется в
- множество всех j со свойством, что φ выполняется вявляется надмножеством A {φ} , следовательно, и в U
Используя теорему Лоша, мы видим, что φ выполняется в ультрапроизведении . Итак, это ультрапроизведение удовлетворяет всем формулам из Σ.
Смотрите также
- Теорема Барвайса о компактности
- Теорема Эрбрана
- Список тем по булевой алгебре - статья со списком Викимедиа
- Теорема Левенгейма – Сколема - Математическая теорема
Заметки
- ^ См. Truss (1997).
- ^ Дж. Барвайз, С. Феферман, ред., Теоретико-модельная логика (Нью-Йорк: Springer-Verlag, 1985) [1] , в частности, Маковски, JA Глава XVIII: Компактность, вложения и определимость. 645--716, см. Теоремы 4.5.9, 4.6.12 и предложение 4.6.9. Компактные логики для расширенного понятия модели см. Ziegler, M. Глава XV: Теория топологической модели. 557-577. Для логик без свойства релятивизации можно одновременно иметь компактность и интерполяцию, в то время как для логик с релятивизацией проблема остается открытой. См. Ксавье Кайседо, Простое решение четвертой проблемы Фридмана, J. Symbolic Logic, Volume 51, Issue 3 (1986), 778-784. [2]
- ^ Воот, Роберт Л .: "Работа Альфреда Тарски по теории моделей". Журнал символической логики 51 (1986), вып. 4, 869–882
- ^ Робинсон, А .: Нестандартный анализ . North-Holland Publishing Co., Амстердам, 1966. стр. 48.
- ^ Голдблатт, Роберт (1998). Лекции о гиперреалах . Нью-Йорк: Springer Verlag. стр. 10 -11. ISBN 0-387-98464-X.
- ^ См. Hodges (1993).
Рекомендации
- Булос, Джордж; Джеффри, Ричард; Берджесс, Джон (2004).Вычислимость и логика(четвертое изд.). Издательство Кембриджского университета.
- Чанг, СС; Кейслер, Х. Джером (1989). Теория моделей (третье изд.). Эльзевир. ISBN 0-7204-0692-7.
- Доусон, Джон У. младший (1993). «Компактность логики первого порядка: от Гёделя до Линдстрема». История и философия логики . 14 : 15–37. DOI : 10.1080 / 01445349308837208 .
- Ходжес, Уилфрид (1993). Теория моделей . Издательство Кембриджского университета. ISBN 0-521-30442-3.
- Маркер, Дэвид (2002). Теория моделей: Введение . Тексты для выпускников по математике 217. Springer. ISBN 0-387-98760-6.
- Трасс, Джон К. (1997). Основы математического анализа . Издательство Оксфордского университета. ISBN 0-19-853375-6.