Теоремы о компактности и Лёвенгейма-Сколема

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

Definition

Теорема о компактности утверждает, что множество предложений первого порядка выполнимо тогда и только тогда, когда выполнимо каждое его конечное подмножество; теоремы Лёвенгейма-Сколема утверждают, что любая теория первого порядка с бесконечной моделью имеет модели любой бесконечной мощности, по крайней мере, равной мощности ее языка.

Scope

Эта тема охватывает теорему о компактности и ее доказательство через полноту или ультрапроизведения, теоремы Лёвенгейма-Сколема о понижении и повышении мощности моделей, их стандартные следствия, включая существование нестандартных моделей арифметики и анализа, а также парадокс Сколема.

Core questions

• Почему конечная выполнимость теории гарантирует существование модели?
• Как эти теоремы порождают нестандартные модели арифметики и вещественных чисел?
• Почему никакая теория первого порядка не может характеризовать бесконечную структуру с точностью до мощности?
• Что такое парадокс Сколема и как он разрешается?

Key theories

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

Если каждое конечное подмножество множества предложений имеет модель, то и все множество имеет модель; это следует из полноты или может быть доказано семантически с помощью ультрапроизведений.

Теорема Лёвенгейма-Сколема о понижении

Любая бесконечная структура имеет элементарную подструктуру мощности не более мощности ее языка, поэтому счетные теории с бесконечными моделями имеют счетные модели.

Теорема Лёвенгейма-Сколема о повышении

Любая бесконечная модель может быть элементарно расширена до моделей любой большей мощности, поэтому теории первого порядка не могут фиксировать размер своих бесконечных моделей.

Clinical relevance

Эти теоремы являются основными инструментами теории моделей: компактность используется для построения нестандартных моделей, которые доказывают или переносят результаты, а теоремы Лёвенгейма-Сколема объясняют, почему аксиоматизации первого порядка натуральных чисел или вещественных чисел всегда допускают непредусмотренные модели, что влияет на выбор логических фреймворков.

History

Лёвенгейм доказал версию теоремы о понижении в 1915 году, а Сколем обобщил и уточнил ее в 1920-х годах. Компактность была получена Гёделем как следствие полноты и распространена на несчетные языки Мальцевым, который впервые использовал ее для вывода алгебраических теорем, открыв путь к прикладной теории моделей.

Key figures

• Leopold Loewenheim
• Thoralf Skolem
• Kurt Goedel
• Anatoly Maltsev

Seminal works

• changkeisler1990
• marker2002
• hodges1993

Frequently asked questions

Что такое нестандартная модель арифметики?

По теореме о компактности можно добавить к аксиомам арифметики константу, большую любого числа; полученная непротиворечивая теория имеет модель, содержащую бесконечные элементы, выходящие за рамки стандартных натуральных чисел. Такие модели удовлетворяют тем же предложениям первого порядка, что и стандартная.

Что такое парадокс Сколема?

Теорема Лёвенгейма-Сколема о понижении дает счетную модель теории множеств, хотя эта теория доказывает существование несчетных множеств. Разрешение состоит в том, что несчетность относительна к модели: множество, которое модель считает несчетным, не имеет биекции с натуральными числами внутри модели, хотя такая биекция существует извне.