Языки и исчисления

Теория Th(Z,=,<,S,0)


Что изменится, если мы добавим к сигнатуре, помимо прибавления единицы, еще и отношение порядка? Как мы видели (см. доказательство теоремы 29 и задачу после него), элиминация кванторов по-прежнему возможна. Для придания законности нам нужны такие свойства интерпретации (которую мы предполагаем нормальной): она представляет собой линейно упорядоченное множество, в котором каждый элемент имеет непосредственно следующий (совпадающий с значением функции ) и непосредственно предшествующий. В отличие от предыдущего примера, нам достаточно конечного набора аксиом. Таким образом, теория конечно аксиоматизируема, а также (как и в предыдущем примере) полна, разрешима, но не категорична в счетной мощности.

Можно обойтись и без элиминации кванторов, рассуждая иначе. Рассмотрим теорию линейно упорядоченных множеств со следующим и предыдущим элементом и опишем все ее модели. Именно, мы покажем, что любая нормальная модель этой теории имеет вид , где — произвольное линейно упорядоченное множество (порядок на парах таков: сначала сравниваются -компоненты, а в случае равенства — -компоненты.) В самом деле, будем говорить, что элементы и лежат "в одной галактике", если между ними конечное число элементов. (Легко проверить, что это действительно отношение эквивалентности, и наше множество разбивается на галактики.) Далее проверяем, что каждая галактика изоморфна (как упорядоченное множество) и что на галактиках естественно определяется порядок.

Теперь с помощью игры Эренфойхта (см. раздел "Элементарная эквивалентность", теорема 37) мы показываем, что все нормальные модели этой теории элементарно эквивалентны. Отсюда заключаем, что теория полна (как в доказательстве теоремы 65, где мы по существу использовали элементарную эквивалентность моделей, а не их изоморфизм).

126. Покажите, что теория не категорична ни в какой несчетной мощности.

127. Будет ли теория конечно аксиоматизируемой? разрешимой? категоричной?

128. Будет ли теория конечно аксиоматизируемой? разрешимой? категоричной?



Содержание раздела