RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2020 Volume 17, Pages 1013–1026 (Mi semr1270)

This article is cited 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.

UDC: 510.5

MSC: 03D45

Received April 28, 2020, published July 28, 2020

Language: English

DOI: 10.33048/semi.2020.17.076



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024