Теорема Лёвенгейма — Скулема¶

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

¶История

Теорема была открыта и доказана в два этапа. В 1915 году немецкий математик Леопольд Лёвенгейм опубликовал работу, в которой впервые сформулировал утверждение о том, что любая выполнимая формула логики первого порядка (или, в более общем виде, любая счётная теория) имеет модель, мощность которой не превосходит счётной. Это был первый результат, связавший синтаксис формальных теорий с мощностью их моделей. Доказательство Лёвенгейма было громоздким и содержало пробелы, которые впоследствии устранил его ученик Торальф Скулем.

В 1920 году норвежский математик Торальф Скулем опубликовал работу, в которой дал строгое доказательство теоремы Лёвенгейма — Скулема «вниз» (понижающей версии). Позднее, в 1928 году, Скулем также доказал и повышающую версию теоремы (теорема Лёвенгейма — Скулема «вверх»), используя методы, основанные на добавлении новых констант и применении теоремы о компактности. Полное и современное доказательство обеих частей теоремы было дано в 1930-х годах Альфредом Тарским и другими логиками в рамках развития теории моделей.

¶Формулировки

Теорема Лёвенгейма — Скулема обычно формулируется в двух вариантах: понижающем и повышающем.

¶Понижающая теорема Лёвенгейма — Скулема (теорема «вниз»)

Если теория первого порядка T имеет бесконечную модель, то она имеет модель мощности, не превосходящей мощности языка теории (то есть счётную, если язык счётный). Иными словами, любая выполнимая теория первого порядка со счётным языком имеет счётную модель. Это утверждение часто называют теоремой Лёвенгейма — Скулема в узком смысле.

¶Повышающая теорема Лёвенгейма — Скулема (теорема «вверх»)

Если теория первого порядка T имеет бесконечную модель, то для любой бесконечной мощности κ, не меньшей мощности языка теории, теория T имеет модель мощности κ. Это означает, что из существования одной бесконечной модели можно получить модели сколь угодно большой мощности.

¶Доказательство (схема)

Доказательство обеих частей теоремы опирается на методы теории моделей.

¶Доказательство понижающей части

Для доказательства понижающей теоремы используется теорема Лёвенгейма — Скулема о подмодели. Пусть M — бесконечная модель теории T. Рассмотрим подмножество A ⊆ M, которое замкнуто относительно всех функций, определённых в языке теории (элементарная подмодель). По теореме Лёвенгейма — Скулема о подмодели, для любого подмножества X ⊆ M существует элементарная подмодель N ⊆ M, содержащая X, мощность которой не превосходит max(|X|, |L|), где |L| — мощность языка. Выбрав X = ∅, получим элементарную подмодель мощности не более |L|. Если язык счётный, мощность такой подмодели не более счётной. Поскольку N — элементарная подмодель M, она является моделью теории T (так как все формулы теории истинны в M, они истинны и в N). Таким образом, существует счётная модель.

¶Доказательство повышающей части

Для доказательства повышающей части используется теорема о компактности. Пусть M — бесконечная модель теории T мощности λ. Выберем бесконечную мощность κ ≥ |L|. Добавим к языку теории T новые константные символы c_i для каждого i < κ (то есть κ новых констант). Рассмотрим теорию T', состоящую из T и всех формул вида c_i ≠ c_j для i ≠ j (то есть утверждений, что все новые константы попарно различны). Любое конечное подмножество T' выполнимо в модели M, так как в M есть бесконечно много элементов, и мы можем интерпретировать конечное число новых констант различными элементами. По теореме о компактности, вся теория T' имеет модель N. Мощность N не меньше κ, так как в ней есть κ различных элементов, соответствующих новым константам. Применяя понижающую теорему Лёвенгейма — Скулема к модели N (или к её подмодели, содержащей все эти элементы), можно получить модель мощности ровно κ. Таким образом, существует модель теории T мощности κ.

¶Следствия и значение

Теорема Лёвенгейма — Скулема имеет глубокие следствия для оснований математики и философии логики.

¶Парадокс Скулема

Наиболее известное следствие — парадокс Скулема. Он заключается в том, что аксиоматическая теория множеств Цермело — Френкеля (ZFC), которая постулирует существование несчётных множеств (например, множества всех вещественных чисел), имеет счётную модель (по понижающей теореме). В этой счётной модели «несчётные» множества оказываются счётными с точки зрения внешней теории, но внутри модели они выглядят как несчётные, поскольку не существует биекции между ними и натуральными числами, которая была бы элементом этой модели. Парадокс Скулема не является логическим противоречием, а демонстрирует относительность понятия «мощность» в рамках формальных систем.

¶Некатегоричность теорий первого порядка

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

¶Применение в теории моделей

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

¶Примеры

¶Пример 1: Теория плотных линейных порядков

Рассмотрим теорию плотных линейных порядков без концевых точек (например, аксиомы для рациональных чисел). Эта теория имеет счётную модель (рациональные числа Q) и несчётные модели (например, вещественные числа R). По повышающей теореме, существуют модели любой бесконечной мощности. При этом все счётные плотные линейные порядки без концевых точек изоморфны (теорема Кантора), но несчётные модели могут быть неизоморфны.

¶Пример 2: Теория полей характеристики 0

Теория полей характеристики 0 (например, аксиомы для поля рациональных чисел) имеет счётную модель (поле рациональных чисел Q) и несчётные модели (например, поле вещественных чисел R или поле комплексных чисел C). По теореме Лёвенгейма — Скулема существуют модели этой теории любой бесконечной мощности, в том числе алгебраически замкнутые поля характеристики 0.

¶Критика и ограничения

Теорема Лёвенгейма — Скулема не является противоречием, но она выявила фундаментальные ограничения логики первого порядка. В частности, она показывает, что многие интуитивные понятия (например, «конечность», «счётность», «несчётность») не могут быть адекватно выражены в рамках формальной системы первого порядка без привлечения внешних моделей. Это привело к развитию логики второго порядка и других неклассических логик, которые обладают большей выразительной силой, но не имеют полной аксиоматизации.

¶Источники

• Лёвенгейм, Л. «Über Möglichkeiten im Relativkalkül» (1915)
• Скулем, Т. «Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze» (1920)
• Тарский, А. «Some remarks on the notion of logical consequence» (1936)
• Чен, Ч., Кейслер, Г. «Теория моделей» (1973)
• Ходжес, У. «Теория моделей» (1993)