Число Левенхайма - Löwenheim number

В математическая логика то Число Левенхайма из абстрактная логика самый маленький количественное числительное для которых слабый нисходящий Теорема Левенгейма – Сколема держит.^[1] Они названы в честь Леопольд Левенхайм, который доказал, что они существуют для очень широкого класса логик.

Абстрактная логика

Абстрактная логика для чисел Левенхайма состоит из:

Сборник «предложений»;
Коллекция «моделей», каждой из которых присвоена мощность;
Отношение между предложениями и моделями, которое гласит, что определенное предложение «удовлетворяется» определенной моделью.

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

Определение

Число Левенгейма логики L наименьший кардинал κ такой, что если произвольное предложение L имеет любую модель, предложение имеет модель мощности не больше κ.

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

{κ_φ : φ - предложение в L }

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

Расширения

Были рассмотрены два расширения определения:^[2]

В Число Левенхайма – Сколема абстрактной логики L наименьший кардинал κ такой, что если любой набор предложений Т ⊆ L есть модель, то у нее есть модель размером не более макс (|Т|, κ).
В Число Левенхайма – Сколема – Тарского из L наименьший кардинал такой, что если А любая структура для L существует элементарная подструктура из А размером не более κ. Для этого необходимо, чтобы в логике было подходящее понятие «элементарной подструктуры», например, с использованием обычного определения «структуры» из логики предикатов.

Для любой логики, для которой существуют числа, число Левенхайма – Сколема – Тарского будет не меньше числа Левенхайма – Сколема, которое, в свою очередь, будет не меньше числа Левенхайма.

Примеры

В Теорема Лёвенгейма – Сколема показывает, что число Левенгейма – Сколема – Тарского логики первого порядка равно ℵ₀. Это означает, в частности, что если предложение логики первого порядка выполнимо, то предложение выполнимо в счетной модели.
Известно, что число Левенгейма – Сколема логика второго порядка больше первого измеримый кардинал, если есть измеримый кардинал.^[3] (То же самое и с его Номер Hanf.) Число Левенгейма универсальной (фрагмента) логики второго порядка, однако, меньше, чем первое. сверхкомпактный кардинал (при условии, что он существует).

Примечания

^ Чжан 2002, стр.77
^ Магидор и Вяэнянен 2009/2010
^ Магидор и Вяэнянен 2009/2010.