On Decidable Categoricity and Almost Prime Models | Sciact - Система учета научной деятельности ИМ СО РАН

On Decidable Categoricity and Almost Prime Models Научная публикация

Журнал

Siberian Advances in Mathematics
ISSN: 1055-1344 , E-ISSN: 1934-8126

Вых. Данные

Год: 2020, Том: 30, Номер: 3, Страницы: 200-212 Страниц : 13 DOI: 10.3103/S1055134420030050

Ключевые слова

almost prime model; complete formula; computable model; decidable model; decidable theory; degree of decidable categoricity; prime model; Turing degree; uniform decidable categoricity

Авторы

Goncharov S.S. ^1,2 , Harizanov V. ³ , Miller R. ⁴

Организации

1	Sobolev Institute of Mathematics, Novosibirsk, 630090, Russian Federation
2	Novosibirsk State University, Novosibirsk, 630090, Russian Federation
3	George Washington University, Washington, DC 20052, United States
4	Queens College and CUNY Graduate Center, Queens, NY 11367, United States

Abstract: The complexity of isomorphisms for computable and decidable structures plays animportant role in computable model theory. Goncharov [26] defined the degree ofdecidable categoricity of a decidable model (M to be the least Turing degree, if it exists, which iscapable of computing isomorphisms between arbitrary decidable copies of (M. If this degree is 0, we say that the structure (M is decidablycategorical. Goncharov established that every computably enumerable degree is thedegree of categoricity of a prime model, and Bazhenov showed that there is a prime model with nodegree of categoricity. Here we investigate the degrees of categoricity of various prime models withadded constants, also called almost prime models. Werelate the degree of decidable categoricity of an almost prime model (M to the Turing degree of the set C(M) of complete formulas. We also investigate uniformdecidable categoricity, characterizing it by primality of (M and Turing reducibility of C(M) to the theory of (M. © 2020, Allerton Press, Inc.

Goncharov S.S. , Harizanov V. , Miller R.
On Decidable Categoricity and Almost Prime Models
Siberian Advances in Mathematics. 2020. V.30. N3. P.200-212. DOI: 10.3103/S1055134420030050 Scopus OpenAlex

Scopus:	2-s2.0-85089529243
OpenAlex:	W3062138362

БД	Цитирований
Scopus	3
OpenAlex	4