Теорема про компактність

У математичній логіці теорема компактності стверджує, що набір пропозицій першого порядку має модель тоді і тільки тоді, коли кожна кінцева підмножина має модель. Ця теорема є важливим інструментом в теорії моделей, оскільки вона являє собою корисний метод побудови моделей будь-якого набору пропозицій, який є кінцево несуперечливі. Теорема компактності для обчислення виразів є наслідком теореми Тихонова (яка стверджує, що твір компактних просторів компактно), застосоване до компактних кам'яних просторів , і, отже, назви теореми. Так само воно аналогічно характеристиці властивості скінченного перетину компактності в топологічних просторах: набір замкнутих множин в компактному просторі має непорожній перетин, якщо у кожного кінцевого підкомплексу є непорожній перетин. Теорема компактності є однією з двох ключових властивостей, як і теорема зниження Льовенгейма-Сколема, що використовується в теоремі Ліндстрема для характеристики логіки першого порядку. Хоча є деякі узагальнення теореми компактності в логіках не першого порядку, сама теорема компактності в них не виконується.

Історія

Курт Гедель довів теорему про лічильну компактність у 1930 році. Анатолій Мальцев довів незліченний випадок в 1936 році.

Додатки

Теорема компактності має багато додатків у теорії моделей. Тут наведено кілька типових результатів. З теореми компактності випливає принцип Робінсона: якщо в кожному полі характеристики нуль є пропозиція першого порядку, то існує константа p така, що пропозиція виконується для будь-якого поля характеристики, більшого p. Це можна побачити в такий спосіб: припустимо, що φ — пропозиція, яка виконується в кожному полі характеристики нуль. Тоді її заперечення ¬φ разом з аксіомами полів і нескінченної послідовністю пропозицій 1 + 1 ≠ 0, 1 + 1 + 1 ≠ 0, …, не здійснено (оскільки не існує поля характеристики 0, в якому виконано ¬φ, І нескінченна послідовність пропозицій гарантує, що будь-яка модель буде полем характеристики 0). Тому існує кінцева підмножина А цих пропозицій, яка не може бути здійсненною. Припустимо, що A містить ¬φ, аксіоми поля, і для деяких k перші k пропозицій виду 1 + 1 + … + 1 ≠ 0 (оскільки додавання більшої кількості пропозицій не змінює незручності). Нехай B містить всі пропозиції A, крім ¬φ. Тоді будь-яке поле з характеристикою, більшою k, є моделлю B, а ¬φ разом з B нездійсненна. Це означає, що φ має виконуватися в кожній моделі B, а це значить, що φ має місце в кожному полі характеристики більше k.

Друге застосування теореми компактності показує, що будь-яка теорія, що має великі кінцеві моделі або одну нескінченну модель, має моделі довільної великої потужності (це висхідна теорема Левенгейма — Сколема). Так, наприклад, існують нестандартні моделі арифметики Пеано з незліченною кількістю «натуральних чисел». Для цього нехай T — вихідна теорія і κ — кардинальне число. Додайте до мови T один постійний символ для кожного елемента κ. Потім додайте в T набір пропозицій, які говорять, що об'єкти, позначені будь-якими двома різними постійними символами з нової колекції, різні (це набір пропозицій κ²). Так як кожна кінцева підмножина цієї нової теорії здійсненна за допомогою досить великої кінцевої моделі Т або будь-якої нескінченної моделі, то вся розширена теорія здійсненна. Але будь-яка модель розширеної теорії має потужність, принаймні х.

Третє застосування теореми компактності — це побудова нестандартних моделей дійсних чисел, тобто послідовних розширень теорії дійсних чисел, що містять «нескінченно малі» числа. Щоб переконатися в цьому, хай Σ — аксіоматизація першого порядку теорії дійсних чисел. Розглянемо теорію, отриману додаванням до мови нового постійного символу ε і прилеглу до Σ аксіому ε> 0 і аксіом ε <1 / n для всіх натуральних чисел n. Ясно, що стандартні речові числа R є моделлю будь-якої кінцевої підмножини цих аксіом, так як речові числа задовольняють у Σ і при відповідному виборі ε можуть бути виконані для будь-якої кінцевої підмножини аксіом щодо ε. За теоремою компактності існує модель * R, яка задовольняє Σ і містить нескінченно малий елемент ε. Аналогічне міркування, що примикає до аксіом ω> 0, ω> 1 і т. д.,показує, що існування нескінченно великих цілих чисел не може бути виключено будь-якою аксіоматизацією Σ дійсних чисел.

Докази

Можна довести теорему компактності, використовуючи теорему Геделя про повноту, яка встановлює, що безліч пропозицій здійсненна тоді і тільки тоді, коли на ній не можна довести протиріччя. Оскільки докази завжди кінцеві і, отже, містять тільки кінцеве число заданих пропозицій, слідує теорема компактності. Справді, теорема компактності еквівалентна теоремі Геделя про повноту, і обидві вони еквівалентні теоремі про булевий простий ідеал, слабку форму аксіоми вибору. Спочатку Гедель довів теорему компактності саме таким чином, але пізніше були знайдені деякі «чисто семантичні» доведення теореми компактності, тобто докази, які відносяться до істини, але не до доказовості. Одне з цих доказів ґрунтується на ультрадобутках, що залежать від аксіоми вибору наступним чином: Proof: Зафіксуємо мову першого порядку L, і нехай Σ набір L-пропозицій, таких, що кожна кінцева добірка L-пропозицій, i ⊆ Σ , є модель ${\mathcal {M}}_{i}$. Нехай прямий добуток структур, а I — набір кінцевих підмножин Σ. Для кожного i з I нехай: A_i := { j ∈ I : j ⊇ i}.

Сімейство всіх цих множин Ai породжує власний фільтр, тому існує ультрафільтр U, що містить всі множини виду Ai.

Тепер для будь-якої формули φ з Σ маємо:

• множина A_{φ}  знаходиться в U
• щоразу, коли j ∈ A_{φ},то φ ∈ j, отже φ лежить в ${\mathcal {M}}_{j}$
• множина усіх j с властивістю, що φ, яка лежить в ${\mathcal {M}}_{j}$, є надмножиною A_{φ}, лежить також в U

Використовуючи теорему Лося, ми бачимо, що φ має лежить в ультрадобутку $\prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}/U$. Таким чином, цей ультрадобуток, задовольняє всім формулам з Σ.

Див. також

• Список тем Булевої Алгебри
• Теорема Льовенгейма — Сколема
• Теорема Ербрана
• Теорема Баруайза

Посилання

• Boolos, George; Jeffrey, Richard; Burgess, John (2004). Computability and Logic (вид. fourth). "Cambridge University Press.
• Chang, C.C.; Keisler, H. Jerome (1989). Model Theory (вид. third). Elsevier. ISBN 0-7204-0692-7.
• Dawson, John W. junior (1993). The compactness of first-order logic: From Gödel to Lindström. History and Philosophy of Logic. 14: 15—37. doi:10.1080/01445349308837208.
• Hodges, Wilfrid (1993). Model theory. Cambridge University Press. ISBN 0-521-30442-3.
• Marker, David (2002). Model Theory: An Introduction. Graduate Texts in Mathematics 217. Springer. ISBN 0-387-98760-6.
• Truss, John K. (1997). Foundations of Mathematical Analysis. Oxford University Press. ISBN 0-19-853375-6.

Додатковий матеріал

• Hummel, Christoph (1997). Gromov's compactness theorem for pseudo-holomorphic curves. Basel, Switzerland: Birkhäuser. ISBN 3-7643-5735-5.