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

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

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

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

История

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

Приложения

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

Из теоремы компактности следует Принцип Робинсона: Если предложение первого порядка выполняется в каждом поле из характеристика нуля, то существует постоянная п такое, что предложение верно для каждого поля характеристики больше, чем п. Это можно увидеть следующим образом: предположим, что φ - предложение, которое выполняется в любом поле нулевой характеристики. Тогда его отрицание ¬φ вместе с аксиомами поля и бесконечной последовательностью предложений 1 + 1 ≠ 0, 1 + 1 + 1 ≠ 0, ... невыполнимо (поскольку нет поля характеристики 0, в котором ¬φ выполняется , а бесконечная последовательность предложений гарантирует, что любая модель будет полем характеристики 0). Следовательно, существует конечное подмножество А из этих предложений, которые не могут быть выполнены. Можно предположить, что А содержит ¬φ, аксиомы поля, и для некоторых k, первый k предложения формы 1 + 1 + ... + 1 ≠ 0 (поскольку добавление большего количества предложений не меняет неудовлетворенности). Позволять B содержат все предложения А кроме ¬φ. Тогда любое поле с характеристикой больше k это модель B, а ¬φ вместе с B не выполняется. Это означает, что φ должно выполняться в каждой модели B, что в точности означает, что φ выполняется в любом поле характеристики, большей, чем k.

Второе применение теоремы компактности показывает, что любая теория, которая имеет произвольно большие конечные модели или единственную бесконечную модель, имеет модели произвольно больших мощность (это Теорема Левенхайма – Сколема, направленная вверх ). Так, например, есть нестандартные модели Арифметика Пеано с несчетным количеством «натуральных чисел». Для этого пусть Т - исходная теория, и пусть κ - произвольная количественное числительное. Добавить к языку Т один постоянный символ для каждого элемента κ. Затем добавьте к Т набор предложений, в которых говорится, что объекты, обозначенные любыми двумя различными постоянными символами из новой коллекции, различны (это набор κ2 фразы). Поскольку каждый конечный подмножество этой новой теории удовлетворяет достаточно большой конечной модели Т, или любой бесконечной моделью, вся расширенная теория выполнима. Но любая модель расширенной теории имеет мощность не менее κ

Третье приложение теоремы компактности - построение нестандартные модели действительных чисел, то есть последовательные расширения теории действительных чисел, содержащие «бесконечно малые» числа. Чтобы убедиться в этом, пусть Σ - аксиоматизация первого порядка теории действительных чисел. Рассмотрим теорию, полученную добавлением к языку нового постоянного символа ε и присоединением к Σ аксиомы ε> 0 и аксиом ε <1 /п для всех положительных целых чисел п. Ясно, что стандартные действительные числа р являются моделью для каждого конечного подмножества этих аксиом, потому что действительные числа удовлетворяют всему в Σ и, при подходящем выборе ε, могут быть выполнены так, чтобы удовлетворять любому конечному подмножеству аксиом о ε. По теореме компактности существует модель *р который удовлетворяет Σ и также содержит бесконечно малый элемент ε. Аналогичное рассуждение, примыкающее к аксиомам ω> 0, ω> 1 и т. Д., Показывает, что существование бесконечно больших целых чисел не может быть исключено какой-либо аксиоматизацией Σ вещественных чисел.[5]

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

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

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

Доказательство. Зафиксируем язык L первого порядка и пусть Σ - это набор L-предложений такой, что каждый конечный набор L-предложений я ⊆ Σ имеет модель . Также позвольте быть прямым продуктом структур и я - набор конечных подмножеств Σ. Для каждого я в я пусть Ая := { j ∈ я : j ⊇ я}. Семейство всех этих множеств Aя генерирует надлежащий фильтр, так что есть ультрафильтр U содержащий все множества вида Aя.

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

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

С помощью Теорема Лося мы видим, что φ выполняется в сверхпродукт . Таким образом, это ультрапроизведение удовлетворяет всем формулам из Σ.

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

Заметки

  1. ^ См. Truss (1997).
  2. ^ Дж. Барвайз, С. Феферман, ред., Теоретико-модельная логика (Нью-Йорк: Springer-Verlag, 1985) [1], в частности, Маковски Дж. А. Глава XVIII: Компактность, вложения и определимость. 645--716, см. Теоремы 4.5.9, 4.6.12 и предложение 4.6.9. О компактных логиках для расширенного понятия модели см. Ziegler, M. Глава XV: Topological Model Theory. 557-577. Для логик без свойства релятивизации можно одновременно иметь компактность и интерполяцию, тогда как для логик с релятивизацией проблема остается открытой. См. Ксавье Кайседо, Простое решение четвертой проблемы Фридмана, J. ​​Symbolic Logic, Volume 51, Issue 3 (1986), 778-784.[2]
  3. ^ Воот, Роберт Л.: "Работа Альфреда Тарского по теории моделей". Журнал символической логики 51 (1986), нет. 4, 869–882
  4. ^ Робинсон, А.: Нестандартный анализ. North-Holland Publishing Co., Амстердам, 1966. стр. 48.
  5. ^ Голдблатт, Роберт (1998). Лекции о гиперреалах. Нью-Йорк: Springer Verlag. стр.10 –11. ISBN  0-387-98464-X.
  6. ^ См. Hodges (1993).

использованная литература