Теорема Гёделя о компактности — Википедия. Что такое Теорема Гёделя о компактности
Wiki.sc

Теорема Гёделя о компактности

Материал из Википедии — свободной энциклопедии

Теорема Гёделя о компактности утверждает, что набор из предложений в логике первого порядка имеет модель, тогда и только тогда, когда каждое конечное подмножество предложений имеет модель.

Эта теорема является важным инструментом в теории моделей, так как она обеспечивает удобный метод для построения моделей для бесконечного набора предложений.

Теорема является следствием теоремы Тихонова о том, что произведение компактных пространств компактно. Кроме того, она является аналогом характеризации компактных пространств через свойство конечных пересечений.

История

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

Следствия

  • Если, предложение выполнено в каждом поле характеристики нуль, то оно верно во всех полях достаточно большой характеристики.
    • Действительно, пусть φ выполнено в каждом поле характеристики нуль. Тогда его отрицание ¬φ, вместе с аксиомами поля и бесконечной последовательности предложений 1+1 ≠ 0, 1+1+1 ≠ 0, ..., приводят к противоречию (поскольку отсутствует поля характеристики 0, в котором φ не имеет места — бесконечная последовательность предложений гарантирует, что любая модель будет полем характеристики 0). Следовательно, существует конечное подмножество A из этих предложений, приводящая к противоречию. Пусть B содержит все предложения A за исключением ¬φ. Тогда любое поле с дастатоно болшой характеристики есть модель B, и ¬φ вместе с B не выполнима. Это означает, что φ выполняется в каждой моделе B, в частности φ выполнено в каждом поле достаточно большой характеристики.
  • Если теория имеет произвольно большие конечные модели, или одну бесконечную модель, то она имеет модели сколь угодно большой мощности. (Это частный случай теоремы Лёвенгейма — Скулема).
    • Так, например, существуют нестандартные модели арифметики Пеано с несчётным числом натуральных чисел.
    • Доказательство. Пусть М есть модель исходной теории. Добавим к языку один символ для каждого элемента множества T большой мощности. Затем добавим набор предложений, которые говорят, что все эти символы различны. Поскольку для каждого конечного подмножествоа этой новой теории есть модель, то есть модель и для самой теории.
  • Построение нестандартной модели вещественных чисел, то есть, расширения теории вещественных чисел, содержащего «бесконечно малые».
    • Пусть Σ есть аксиоматизация теории вещественных чисел первого порядка. Рассмотрим теорию, полученную путем добавления новой константы ε к языку и предложениями ε > 0 и ε < 1/n для всех натуральных чисел n. Очевидно, что стандартные вещественные числа являются моделью для любого конечного подмножества из этих аксиом. По теореме компактности существует модель удовлетворяющая всем предложениям. То есть модель с бесконечно малым числом ε.

О доказательствах

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

Примечания

Ссылки

  • Boolos, George. Computability and Logic / George Boolos, Jeffrey, Richard, Burgess, John. — fourth. — Cambridge University Press, 2004.
  • Chang, C.C. Model Theory / C.C. Chang, Keisler, H. Jerome. — third. — Elsevier, 1989. — 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. Model theory. — Cambridge University Press, 1993. — ISBN 0-521-30442-3.
  • Marker, David. Model Theory: An Introduction. — Springer, 2002. — ISBN 0-387-98760-6.
  • Truss, John K. Foundations of Mathematical Analysis. — Oxford University Press, 1997. — ISBN 0-19-853375-6.
Что такое Wiki.sc Вики является главным информационным ресурсом в интернете. Она открыта для любого пользователя. Вики это библиотека, которая является общественной и многоязычной.

Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License.

Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI.SC является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).

E-mail: admin@wiki.sc