|
Эта публикация цитируется в 11 научных статьях (всего в 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$-разрешимых представлений структура.
Поступило: 12.09.2015
Образец цитирования:
Е. Б. Фокина, С. С. Гончаров, В. Харизанова, О. В. Кудинов, Д. Туретски, “Индексные множества $n$-разрешимых структур, категоричных относительно $m$-разрешимых представлений”, Алгебра и логика, 54:4 (2015), 520–528; Algebra and Logic, 54:4 (2015), 336–341
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al708 https://www.mathnet.ru/rus/al/v54/i4/p520
|
Статистика просмотров: |
Страница аннотации: | 277 | PDF полного текста: | 46 | Список литературы: | 46 | Первая страница: | 8 |
|