Эта публикация цитируется в
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.
УДК:
510.5
MSC: 03D45 Поступила 28 апреля 2020 г., опубликована
28 июля 2020 г.
Язык публикации: английский
DOI:
10.33048/semi.2020.17.076