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

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

История

Теорема была открыта и доказана в два этапа. Первый результат, относящийся к счётным моделям, получил в 1915 году немецкий математик Леопольд Лёвенгейм (Leopold Löwenheim). В своей работе «Über Möglichkeiten im Relativkalkül» (О возможностях в реляционном исчислении) он показал, что если формула логики первого порядка (в то время — реляционное исчисление) имеет модель, то она имеет модель, мощность которой не превосходит счётной. Это был первый в истории результат, связывающий синтаксис формальной теории с мощностью её моделей.

В 1920 году норвежский математик Туральф Сколем (Thoralf Skolem) обобщил и упростил доказательство Лёвенгейма, а также распространил его на счётные множества формул. Он показал, что любая счётная теория первого порядка, имеющая бесконечную модель, имеет и счётную модель. Этот результат получил название теоремы Лёвенгейма — Сколема о понижении мощности (или просто теоремы Лёвенгейма — Сколема в узком смысле). Сколем также независимо доказал и обратное утверждение (о повышении мощности), которое позже было формализовано Альфредом Тарским.

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

Существуют две основные формулировки теоремы, которые часто объединяют в одну.

Теорема о понижении мощности (Downward Löwenheim–Skolem theorem)

Пусть \( \mathcal{L} \) — язык первого порядка мощности \( \kappa \) (счётный или несчётный), а \( T \) — теория (множество предложений) в этом языке, имеющая бесконечную модель. Тогда для любого бесконечного кардинала \( \lambda \), такого что \( \kappa \le \lambda \le |M| \), где \( |M| \) — мощность исходной модели, существует модель теории \( T \) мощности \( \lambda \).

В частном, но наиболее известном случае, когда язык счётен (\( \kappa = \aleph_0 \)): если теория \( T \) имеет бесконечную модель, то она имеет счётную модель.

Теорема о повышении мощности (Upward Löwenheim–Skolem theorem)

Пусть \( \mathcal{L} \) — язык первого порядка мощности \( \kappa \), а \( T \) — теория в этом языке, имеющая бесконечную модель. Тогда для любого бесконечного кардинала \( \lambda \ge \kappa \) существует модель теории \( T \) мощности \( \lambda \).

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

Объединённая формулировка

Наиболее общая формулировка, объединяющая обе части: Теорема Лёвенгейма — Сколема — Тарского. Если теория первого порядка \( T \) в языке мощности \( \kappa \) имеет бесконечную модель, то для любого бесконечного кардинала \( \lambda \ge \kappa \) существует модель теории \( T \) мощности \( \lambda \). Более того, если исходная модель бесконечна, то для любого \( \lambda \ge \kappa \) существует её элементарное расширение мощности \( \lambda \).

Доказательство (идея)

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

• Для понижения мощности (счётный язык): Пусть \( M \) — бесконечная модель теории \( T \). Рассмотрим счётное подмножество \( A \subseteq M \), содержащее все константы языка. Затем, используя аксиому выбора, можно построить счётную элементарную подмодель \( N \subseteq M \), содержащую \( A \). Эта подмодель будет удовлетворять тем же предложениям языка, что и \( M \), то есть будет моделью \( T \). Процесс построения основан на замыкании относительно скулемовских функций (функций, выбирающих свидетелей для формул вида \( \exists x \varphi(x) \)).

• Для повышения мощности: Доказательство использует теорему компактности. К языку теории \( T \) добавляется \( \lambda \) новых константных символов \( \{c_\alpha\}_{\alpha < \lambda} \). Затем строится теория \( T' \), состоящая из \( T \) и предложений \( c_\alpha \neq c_\beta \) для всех \( \alpha \neq \beta \). Любое конечное подмножество \( T' \) имеет модель (исходную модель, интерпретирующую новые константы как различные элементы, что возможно, так как исходная модель бесконечна). По теореме компактности, вся теория \( T' \) имеет модель, мощность которой не меньше \( \lambda \). Затем, применяя теорему о понижении мощности к этой модели, можно получить модель мощности ровно \( \lambda \).

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

Наиболее известным следствием теоремы Лёвенгейма — Сколема является так называемый парадокс Сколема. Он возникает при применении теоремы к аксиоматической теории множеств Цермело — Френкеля (ZF) или Цермело — Френкеля с аксиомой выбора (ZFC).

Теория ZFC является теорией первого порядка в счётном языке. Она постулирует существование несчётных множеств (например, множества всех действительных чисел \( \mathbb{R} \), которое по теореме Кантора имеет мощность континуума, большую, чем счётная). По теореме Лёвенгейма — Сколема о понижении мощности, если ZFC непротиворечива (имеет модель), то она имеет счётную модель.

Парадокс заключается в следующем: в счётной модели ZFC существует объект, который сама модель считает «множеством всех действительных чисел». Однако, поскольку вся модель счётна, множество, которое в ней интерпретируется как \( \mathbb{R} \), также счётно (как подмножество счётной модели). Тем не менее, внутри модели можно доказать (используя аксиомы ZFC), что это множество несчётно. Противоречия здесь нет, так как понятие «счётность» является относительным: модель «видит» своё \( \mathbb{R} \) как несчётное, потому что в ней нет биекции между этим множеством и натуральными числами (такая биекция существует, но она лежит вне модели). С точки зрения внешнего наблюдателя (метатеории), это множество счётно.

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

Значение и следствия

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

• Ограничения логики первого порядка: Теорема показывает, что логика первого порядка не может категорично описывать бесконечные структуры. Никакая счётная теория первого порядка не может иметь ровно одну (с точностью до изоморфизма) бесконечную модель. Это фундаментальное ограничение отличает логику первого порядка от логики второго порядка, которая может быть категоричной (например, аксиомы Пеано второго порядка категорично описывают натуральные числа).
• Нестандартные модели: Теорема гарантирует существование нестандартных моделей арифметики и теории множеств. Например, существуют счётные нестандартные модели арифметики Пеано, содержащие бесконечно большие числа (числа, большие любого стандартного натурального числа). Эти модели удовлетворяют всем аксиомам арифметики, но отличаются от стандартной модели \( \mathbb{N} \).
• Теория моделей: Теорема является основой для многих классификационных результатов в теории моделей, таких как теорема Морли о категоричности для счётных теорий и теория стабильности. Она позволяет строить модели с заданными свойствами и мощностями.
• Философские дискуссии: Парадокс Сколема активно обсуждался в философии математики, особенно в контексте реализма и номинализма. Он ставит под сомнение возможность однозначного описания «вселенной множеств» с помощью формальных аксиом первого порядка.

Критика и уточнения

Сам Сколем рассматривал свой парадокс как аргумент против наивного теоретико-множественного реализма. Однако современная теория моделей и теория множеств преодолели этот парадокс, введя понятия внутреннего и внешнего взгляда на модель. Парадокс не является логическим противоречием, а лишь демонстрирует относительность понятия мощности.

Критика теоремы иногда связана с её зависимостью от аксиомы выбора (при построении счётной элементарной подмодели). Однако существуют варианты доказательства, не требующие аксиомы выбора в полном объёме, а лишь использующие принцип выбора для счётных множеств.

Источники

• Löwenheim, L. (1915). «Über Möglichkeiten im Relativkalkül». Mathematische Annalen, 76(4), 447–470.
• Skolem, T. (1920). «Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen». Videnskapsselskapets skrifter, I. Matematisk-naturvidenskabelig klasse, 4, 1–36.
• Chang, C. C., & Keisler, H. J. (1990). Model Theory (3rd ed.). North-Holland. (Глава 2, раздел 2.1)
• Hodges, W. (1993). Model Theory. Cambridge University Press. (Глава 5, раздел 5.1)
• Ершов, Ю. Л., & Палютин, Е. А. (1987). Математическая логика. Москва: Наука. (Глава 4, раздел 4.4)