RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2020, том 17, страницы 1013–1026 (Mi semr1270)

Эта публикация цитируется в 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



Реферативные базы данных:


© МИАН, 2024