Теорема компактности - 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  : = { jI  : ji }. Семейство всех этих наборов A i порождает правильный фильтр , поэтому существует ультрафильтр U, содержащий все наборы вида A i .

Теперь для любой формулы φ из Σ имеем:

  • множество A {φ} лежит в U
  • если j  ∈ A {φ} , то φ ∈  j , следовательно, φ выполняется в
  • множество всех j со свойством, в котором выполняется φ, является надмножеством A {φ} , а значит, и в U

Используя теорему Лоша, мы видим, что φ выполняется в ультрапроизведении . Итак, это ультрапроизведение удовлетворяет всем формулам из Σ.

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

Заметки

Рекомендации