|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Математическая логика, алгебра и теория чисел
A note on decidable categoricity and index sets
N. Bazhenov, M. Marchuk Sobolev Institute of Mathematics, 4, Acad. Koptyug Ave., Novosibirsk, 630090, Russia
Аннотация:
A structure $S$ is decidably categorical if $S$ has a decidable copy, and for any decidable copies $A$ and $B$ of $S$, there is a computable isomorphism from $A$ onto $B$. Goncharov and Marchuk proved that the index set of decidably categorical graphs is $\Sigma^0_{\omega+2}$ complete. In this paper, we isolate two familiar classes of structures $K$ such that the index set for decidably categorical members of $K$ has a relatively low complexity in the arithmetical hierarchy. We prove that the index set of decidably categorical real closed fields is $\Sigma^0_3$ complete. We obtain a complete characterization of decidably categorical equivalence structures. We prove that decidably presentable equivalence structures have a $\Sigma^0_4$ complete index set. A similar result is obtained for decidably categorical equivalence structures.
Ключевые слова:
decidable categoricity, autostability relative to strong constructivizations, index set, real closed field, equivalence structure, strong constructivization, decidable structure.
Поступила 28 апреля 2020 г., опубликована 28 июля 2020 г.
Образец цитирования:
N. Bazhenov, M. Marchuk, “A note on decidable categoricity and index sets”, Сиб. электрон. матем. изв., 17 (2020), 1013–1026
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1270 https://www.mathnet.ru/rus/semr/v17/p1013
|
Статистика просмотров: |
Страница аннотации: | 211 | PDF полного текста: | 83 | Список литературы: | 23 |
|