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

Теорема Лёвенхейма-Сколема

Мотивация: ЛПП не может «зафиксировать» мощность

Теорема Лёвенхейма–Сколема — первый глубокий результат теории моделей. Она показывает, что первопорядковая теория не контролирует мощность своих моделей: теория, имеющая счётную модель, имеет несчётную, и наоборот. Это «парадокс Сколема» — счётная модель теории ZFC содержит «несчётные» множества.

Теоремы Лёвенхейма–Сколема

Нисходящая (Löwenheim 1915, Skolem 1920): Если T имеет бесконечную модель, то T имеет счётную модель.

Восходящая (Тарский–Ваот): Если T имеет бесконечную модель мощности κ, то T имеет модель мощности λ для любой λ ≥ max(κ, |σ|, ℵ₀).

Объединённая версия: Если T имеет модель мощности κ ≥ |T|, то T имеет модель мощности λ для любой λ ≥ |T|.

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

Теория ZFC — аксиоматическая теория множеств. В ZFC доказывается существование несчётных множеств (теорема Кантора: |P(ℕ)| > |ℕ|). По теореме Лёвенхейма–Сколема ZFC имеет счётную модель M!

Парадокс: M — счётная, но в M «содержатся» несчётные множества?

Разрешение: Несчётность — относительное понятие. В M нет биекции (внутри M) между «несчётным» множеством X_M и ω_M. Но внешний наблюдатель видит, что сам M счётен. «Несчётность X_M» — это отсутствие биекции в модели M, а не отсутствие биекции в реальном мире.

Это иллюстрирует ограниченность ЛПП: «несчётность» не абсолютна, а относительна к модели.

Изоморфизм и элементарная эквивалентность

Изоморфизм M ≅ N: существует биекция f: M → N, сохраняющая все предикаты и функции. Изоморфные структуры неразличимы.

Элементарная эквивалентность M ≡ N: M и N удовлетворяют одним и тем же предложениям ЛПП.

Изоморфизм → элементарная эквивалентность. Обратное неверно: (ℚ, <) ≡ (ℝ, <) (оба — плотные линейные порядки без концов) но (ℚ, <) ≇ (ℝ, <) (разные мощности).

Численный пример

Задача: Доказать, что (ℚ, <) и (ℝ, <) элементарно эквивалентны, построив явное предложение ЛПП, истинное в обоих.

Шаг 1. Теория плотного линейного порядка без концов (DLO): аксиомы

• Линейность: ∀x∀y (x<y ∨ x=y ∨ y<x)
• Транзитивность: ∀x∀y∀z (x<y ∧ y<z → x<z)
• Плотность: ∀x∀y (x<y → ∃z (x<z ∧ z<y))
• Без концов: ∀x ∃y (y<x) ∧ ∃y (x<y)

Шаг 2. И ℚ, и ℝ — модели DLO. Теорема (Кантор, Гунтер): DLO — полная теория: каждое предложение ЛПП либо выводится из DLO, либо его отрицание выводится. Следовательно, все модели DLO элементарно эквивалентны: ℚ ≡ ℝ ✓.

Шаг 3. Пример предложения: ∀x∀y (x<y → ∃z(x<z ∧ z<y)) — «плотность». Истинно и в ℚ, и в ℝ ✓.

Шаг 4. Предложение, отличающее ℚ от ℝ «второго порядка»: «каждое ограниченное множество имеет точную верхнюю грань» — это свойство НЕ ЛПП (говорит о произвольных множествах) → в ЛПП не выразить.

Вывод: ℚ и ℝ неизоморфны (|ℚ| = ℵ₀, |ℝ| = 2^{ℵ₀}) но элементарно эквивалентны (первопорядковая логика не различает их).

Реальное приложение

Теория баз данных: элементарная эквивалентность означает, что два различных хранилища данных (например, разные конкретизации) отвечают одинаково на все запросы на языке реляционной алгебры первого порядка. Это основа для оптимизации запросов через «логически эквивалентные» планы выполнения.

Дополнительные аспекты

Теория моделей изучает связь синтаксиса (формальных теорий) с семантикой (структурами, в которых эти теории истинны). Базовые теоремы: компактности (любое подмножество выполнимой теории конечной выполнимости влечёт выполнимость всей теории), Лёвенгейма–Скулема (наличие моделей всех бесконечных мощностей), elementary equivalence. Прикладной взлёт теории моделей — работы Шеллаха по классификации теорий и устойчивости (stability theory). О-минимальные теории нашли применение в реальной алгебраической геометрии и теории чисел (доказательство гипотезы Андре–Оорта для арифметических многообразий через о-минимальность). В компьютерных науках теория моделей лежит в основе языков описания баз данных и SMT-решателей, где задача — найти модель формулы в подходящей теории (арифметика, массивы, битовые векторы).

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

Связь с другими разделами математики

Лёвенгейм–Сколемовская картина спектра мощностей тесно связана с алгеброй через универсальную алгебру и теорию полей. Теорема о существовании элементарных подструктур (часто доказываемая с помощью нисходящей теоремы Лёвенгейма–Сколема и компактности) лежит в основе построения ультрапроизведений, применяемых в доказательстве теоремы Лосса об элементарности ультрапроизведений. Последняя, в свою очередь, используется в доказательстве теоремы Акс–Кохена о характеристике формальных степенных рядов и в неархимедовой геометрии.

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

В топологии аппарат теории моделей, основанный на теоремах Лёвенгейма–Сколема и компактности, используется в нестандартном анализе Робинсона: каждому топологическому пространству сопоставляется расширение с гиперточками, а понятия предела и непрерывности выражаются через элементарные подструктуры. Аналогичные идеи лежат за модельно-теоретическими подходами к вероятностным структурам: например, в теории вероятностных графов (работы Шелаха, Спенсера) модельные конструкции позволяют строить счетные и несчетные случайные объекты с одинаковыми элементарными свойствами.

В численных методах результаты Лёвенгейма–Сколема косвенно проявляются через корректность логико-ориентированных алгоритмов: SMT-решатели используют то, что наличие бесконечной модели определенной мощности можно «сжать» до более управляемой, зачастую счетной модели, на которой проверяется выполнимость системы ограничений.

Историческая справка и развитие идеи

Первую форму нисходящей теоремы опубликовал Леопольд Лёвенгейм в 1915 году в статье в Mathematische Annalen, работая в рамках логики второго порядка и стремясь понять, какие теории допускают счетные интерпретации. Торскианская редакция первого порядка и упрощение доказательства были выполнены Торфином Сколемом в 1920-х годах; именно Сколем сделал акцент на применении к теории множеств Цермело и сформулировал парадоксическую ситуацию со счетной моделью, содержащей «несчетные» множества. Восходящий вариант, связывающий существование моделей всех больших мощностей, был систематизирован Альфредом Тарским и его учениками, в частности Вайотом, в 1940–1950-х годах, в контексте общей теории моделей, изложенной затем в книге Тарски–Мостовски–Робински 1953 года. Эти результаты стали фундаментом для теории компактности, разработанной Куртом Гёделем и Малтцевым, и послужили отправной точкой для шелаxовской теории классификации в 1960–1970-х годах.