Теорема компактности - Compactness theorem
В математической логике , то Компактность теорема утверждает , что множество из первого порядка предложений имеет модель тогда и только тогда , когда каждое конечное подмножество его имеет модель. Эта теорема является важным инструментом в теории моделей , поскольку она предоставляет полезный (но обычно не эффективный) метод построения моделей любого набора предложений, которые являются конечно непротиворечивыми .
Теорема о компактности для исчисления высказываний является следствием теоремы Тихонова (что говорит о том , что продукт из компактных пространств компактно) применяется для компактных каменных пространств , отсюда и названия теоремы в. Точно так же это аналогично характеристике свойства конечного пересечения для компактности в топологических пространствах : набор замкнутых множеств в компактном пространстве имеет непустое пересечение, если каждое конечное подгруппа имеет непустое пересечение.
Теорема компактности является одним из двух ключевых свойств, наряду с нисходящей теоремой Левенгейма – Сколема , которая используется в теореме Линдстрема для характеристики логики первого порядка. Хотя есть некоторые обобщения теоремы компактности на логики не первого порядка, сама теорема компактности в них не выполняется, за исключением очень ограниченного числа примеров.
История
Курт Гёдель доказал теорему счетной компактности в 1930 году. Анатолий Мальцев доказал несчетный случай в 1936 году.
Приложения
Теорема компактности имеет множество приложений в теории моделей; здесь представлены несколько типичных результатов.
Компактность теорема вытекает принцип Робинсона : Если первый заказ предложение имеет место в каждой области по характерному нулю, то существует константа р такое , что предложение имеет место для каждого поля характеристики больше , чем р . Это можно увидеть следующим образом: предположим, что φ - предложение, которое выполняется в любом поле нулевой характеристики. Тогда его отрицание ¬φ вместе с аксиомами поля и бесконечной последовательностью предложений 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 и т. Д., Показывает, что существование бесконечно больших целых чисел не может быть исключено какой-либо аксиоматизацией Σ вещественных чисел.
Доказательства
Можно доказать теорему компактности, используя теорему Гёделя о полноте , которая устанавливает, что набор предложений выполним тогда и только тогда, когда из него нельзя доказать противоречие. Поскольку доказательства всегда конечны и, следовательно, включают только конечное число заданных предложений, следует теорема компактности. Фактически, теорема компактности эквивалентна теореме Гёделя о полноте, и обе эквивалентны булевой теореме о простом идеале , слабой форме аксиомы выбора .
Гёдель первоначально доказал теорему компактности именно таким образом, но позже были найдены некоторые «чисто семантические» доказательства теоремы компактности, т. Е. Доказательства, которые относятся к истинности, но не к доказуемости . Одно из этих доказательств опирается на ультрапродукты, зависящие от выбранной аксиомы:
Доказательство. Зафиксируем язык 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
Используя теорему Лоша, мы видим, что φ выполняется в ультрапроизведении . Итак, это ультрапроизведение удовлетворяет всем формулам из Σ.
Смотрите также
- Теорема Барвайса о компактности
- Теорема Эрбрана
- Список тем по булевой алгебре - статья со списком Викимедиа
- Теорема Левенгейма – Сколема - Математическая теорема
Заметки
Рекомендации
- Булос, Джордж; Джеффри, Ричард; Берджесс, Джон (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 .