Эта публикация цитируется в
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