Interested Article - Теорема Гёделя о компактности
![](/images/007/200/7200073/1.jpg?rand=120003)
![](https://cdn.wafarin.com/avatars/99c307a7bcd9067efb2967906eef4b87.jpg)
- 2021-03-01
- 1
Теорема Гёделя о компактности утверждает, что набор из предложений в логике первого порядка имеет модель , тогда и только тогда, когда каждое конечное подмножество предложений имеет модель.
Эта теорема является важным инструментом в теории моделей , так как она обеспечивает удобный метод для построения моделей для бесконечного набора предложений.
Теорема является следствием теоремы Тихонова о том, что произведение компактных пространств компактно. Кроме того, она является аналогом характеризации компактных пространств через свойство конечных пересечений.
История
Курт Гедель доказал теорему компактности для счётного числа предложений в 1930 году; несчётный случай доказан Анатолием Ивановичем Мальцевым в 1936 году.
Следствия
-
Если, предложение выполнено в каждом
поле
характеристики
нуль, то оно верно во всех полях достаточно большой характеристики.
- Действительно, пусть φ выполнено в каждом поле характеристики нуль. Тогда его отрицание ¬φ, вместе с аксиомами поля и бесконечной последовательности предложений 1+1 ≠ 0, 1+1+1 ≠ 0, ..., приводят к противоречию (поскольку отсутствует поля характеристики 0, в котором φ не имеет места — бесконечная последовательность предложений гарантирует, что любая модель будет полем характеристики 0). Следовательно, существует конечное подмножество A из этих предложений, приводящая к противоречию. Пусть B содержит все предложения A за исключением ¬φ. Тогда любое поле с дастатоно болшой характеристики есть модель B , и ¬φ вместе с B не выполнима. Это означает, что φ выполняется в каждой моделе B , в частности φ выполнено в каждом поле достаточно большой характеристики.
-
Если теория имеет произвольно большие конечные модели, или одну бесконечную модель, то она имеет модели сколь угодно большой
мощности
. (Это частный случай
теоремы Лёвенгейма — Скулема
).
- Так, например, существуют нестандартные модели арифметики Пеано с несчётным числом натуральных чисел .
- Доказательство. Пусть М есть модель исходной теории. Добавим к языку один символ для каждого элемента множества T большой мощности . Затем добавим набор предложений, которые говорят, что все эти символы различны. Поскольку для каждого конечного подмножествоа этой новой теории есть модель, то есть модель и для самой теории.
-
Построение
нестандартной модели
вещественных чисел
, то есть, расширения теории вещественных чисел, содержащего «
бесконечно малые
».
- Пусть Σ есть аксиоматизация теории вещественных чисел первого порядка. Рассмотрим теорию, полученную путем добавления новой константы ε к языку и предложениями ε > 0 и ε < 1/ n для всех натуральных чисел n . Очевидно, что стандартные вещественные числа являются моделью для любого конечного подмножества из этих аксиом . По теореме компактности существует модель удовлетворяющая всем предложениям. То есть модель с бесконечно малым числом ε.
О доказательствах
Теорема следует из теоремы Гёделя о полноте . Гедель доказал теорему компактности изначально именно так. Позже были найдены «чисто семантические » доказательства. Одно из этих доказательств опирается на ультрапределы .
Ссылки
- Boolos, George; Jeffrey, Richard; Burgess, John. Computability and Logic (неопр.) . — fourth. — Cambridge University Press , 2004.
- Chang, C.C.; Keisler, H. Jerome. Model Theory (неопр.) . — third. — Elsevier , 1989. — ISBN 0-7204-0692-7 .
- Dawson, John W. junior. The compactness of first-order logic: From Gödel to Lindström (англ.) // History and Philosophy of Logic : journal. — 1993. — Vol. 14 . — P. 15—37 . — doi : .
- Hodges, Wilfrid. (неопр.) . — Cambridge University Press , 1993. — ISBN 0-521-30442-3 .
- Marker, David. (неопр.) . — ISBN 0-387-98760-6 . , 2002. —
- Truss, John K. (англ.) . — Oxford University Press , 1997. — ISBN 0-19-853375-6 .
![](https://cdn.wafarin.com/avatars/99c307a7bcd9067efb2967906eef4b87.jpg)
- 2021-03-01
- 1