|
This article is cited in 1 scientific paper (total in 1 paper)
Mathematical logic, algebra and number theory
A note on decidable categoricity and index sets
N. Bazhenov, M. Marchuk Sobolev Institute of Mathematics, 4, Acad. Koptyug Ave., Novosibirsk, 630090, Russia
Abstract:
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.
Keywords:
decidable categoricity, autostability relative to strong constructivizations, index set, real closed field, equivalence structure, strong constructivization, decidable structure.
Received April 28, 2020, published July 28, 2020
Citation:
N. Bazhenov, M. Marchuk, “A note on decidable categoricity and index sets”, Sib. Èlektron. Mat. Izv., 17 (2020), 1013–1026
Linking options:
https://www.mathnet.ru/eng/semr1270 https://www.mathnet.ru/eng/semr/v17/p1013
|
Statistics & downloads: |
Abstract page: | 192 | Full-text PDF : | 72 | References: | 17 |
|