Аннотация:
A structure SS is decidably categorical if SS has a decidable copy, and for any decidable copies AA and BB of SS, there is a computable isomorphism from AA onto BB. Goncharov and Marchuk proved that the index set of decidably categorical graphs is Σ0ω+2Σ0ω+2 complete. In this paper, we isolate two familiar classes of structures KK such that the index set for decidably categorical members of KK has a relatively low complexity in the arithmetical hierarchy. We prove that the index set of decidably categorical real closed fields is Σ03Σ03 complete. We obtain a complete characterization of decidably categorical equivalence structures. We prove that decidably presentable equivalence structures have a Σ04Σ04 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.
The work is supported by Mathematical Center in Akademgorodok under agreement No. 075-15-2019-1613 with the Ministry of Science and Higher Education of the Russian Federation.
Поступила28 апреля 2020 г., опубликована 28 июля 2020 г.
\RBibitem{BazMar20}
\by N.~Bazhenov, M.~Marchuk
\paper A note on decidable categoricity and index sets
\jour Сиб. электрон. матем. изв.
\yr 2020
\vol 17
\pages 1013--1026
\mathnet{http://mi.mathnet.ru/semr1270}
\crossref{https://doi.org/10.33048/semi.2020.17.076}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000557456400001}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1270
https://www.mathnet.ru/rus/semr/v17/p1013
Эта публикация цитируется в следующих 1 статьяx:
Dariusz Kalociński, Michał Wrocławski, “Generalization of Shapiro's theorem to higher arities and noninjective notations”, Arch. Math. Logic, 62:1-2 (2023), 257