RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 2015, том 54, номер 4, страницы 520–528 (Mi al708)

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

Индексные множества $n$-разрешимых структур, категоричных относительно $m$-разрешимых представлений

Е. Б. Фокинаa, С. С. Гончаровbc, В. Харизановаd, О. В. Кудиновbc, Д. Туретскиe

a Vienna Univ. of Tech., Inst. Discr. Math. Geom., Wiedner Hauptstraße 8-10/104, 1040 Vienna, AUSTRIA
b Ин-т матем. им. С. Л. Соболева СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ
c Новосибирский гос. ун-т, ул. Пирогова, 2, г. Новосибирск, 630090, РОССИЯ
d Dep. Math., George Washington Univ., Washington, DC 20052 USA
e Kurt Gödel Research Center for Math. Log., Univ. Vienna, Währinger Straße 25, 1090 Vienna, AUSTRIA

Аннотация: Структура называется категоричной относительно $n$-разрешимых представлений (или автоустойчивой относительно $n$-конструктивизаций), если любые две $n$-разрешимые копии структуры вычислимо изоморфны. В случае $n=0$ определение эквивалентно классическому определению вычислимо категоричной (автоустойчивой) структуры. Доуни, Кэч, Лемпп, Льюис, Монталбан и Туретски доказали, что не существует простой синтаксической характеризации вычислимой категоричности. Более строго, они доказали $\Pi^1_1$-полноту индексного множества вычислимо категоричных структур.
Исследуются индексные множества $n$-разрешимых структур, которые категоричны относительно $m$-разрешимых представлений, где $m,n\in\omega$. Если $m\ge n\ge0$, то индексное множество снова $\Pi^1_1$-полно, т.е. не существует хорошего описания класса $n$-разрешимых, категоричных относительно $m$-разрешимых представлений структур. В случае $m=n-1\ge0$ индексное множество $\Pi^0_4$-полно, а в случае $0\le m\le n-2$ индексное множество $\Sigma^0_3$-полно.

Ключевые слова: индексное множество, категоричная относительно $n$-разрешимых представлений структура, $n$-разрешимая, категоричная относительно $m$-разрешимых представлений структура.

УДК: 510.53

Поступило: 12.09.2015

DOI: 10.17377/alglog.2015.54.407


 Англоязычная версия: Algebra and Logic, 2015, 54:4, 336–341

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


© МИАН, 2024