Эта публикация цитируется в 33 статьях

Индексные множества вычислимых моделей

У. Калверт^a, В. С. Харизанова^b, Д. Ф. Найт^c, С. Миллер<sup>c

a</sup> Murray State University
^b George Washington University
^c University of Notre Dame

Аннотация: Индексным множеством вычислимой модели $\mathcal A$ называется множество индексов вычислимых копий $\mathcal A$. Определяется сложность индексного множества различных математически интересных моделей, включая различные конечные модели, $\mathbb Q$-векторные пространства, архимедовы вещественно замкнутые упорядоченные поля, редуцированные абелевы $p$-группы длины менее $\omega^2$ и модели исходной теории Эренфойхта. Все индексные множества для этих моделей оказываются $m$-полными в классах $\Pi_n^0$, $d-\Sigma_n^0$ или $\Sigma_n^0$ для различных $n$. В каждом случае находится оптимальное предложение (т.е. предложение простейшего вида), которое описывает модель. Вид предложения (вычислимое $\Pi_n$, $d-\Sigma_n$ или $\Sigma_n$) явно задаёт сложность индексного множества. При проверке $m$-полноты индексного множества искомое предложение является оптимальным. Для некоторых моделей первое естественно возникающее предложение не является оптимальным. В таком случае доказывается, что другое предложение более простой формы подходит для наших целей, при этом для некоторых групп требуется теория Рамсея.

Ключевые слова: индексное множество, вычислимая модель, векторное пространство, архимедово вещественно замкнутое упорядоченное поле, редуцированная абелева $p$-группа, теория Эренфойхта.

УДК: 510.53

Поступило: 11.01.2006

 Англоязычная версия: Algebra and Logic, 2006, 45:5, 306–325

Реферативные базы данных:

• 
• 
•