TY - CHAP

T1 - Cantor–Bendixson Ranks for Almost Prime Models

AU - Bazhenov, Nikolay

AU - Marchuk, Margarita

N1 - The work of N. Bazhenov was supported by the program of fundamental scientific researches of the SB RAS № I.1.1, project № 0314-2019-0002. The reported study of M. Marchuk was funded by RFBR according to the research project № 17-01-00247. The work was done partially while the authors were visiting the Institute for Mathematical Sciences, National University of Singapore in 2017. The visit was supported by the Institute. The authors are grateful to D. Belanger and S. Goncharov for fruitful discussions.

PY - 2024

Y1 - 2024

N2 - For a complete theory T, the set of n-types of T admits a natural topology. This chapter studies connections between topological spaces of types and the algorithmic complexity of isomorphisms among decidable structures. Let d be a Turing degree. A decidable structure is decidably d-categorical if it has a unique decidable copy, up to d-computable isomorphisms. It is known that if T has a decidable prime model N, then N is decidably 0′-categorical. In other words, if the Cantor–Bendixson ranks of all types realized in a decidable model N |= T are equal to zero, then N is unique, up to computable isomorphisms. We obtain the following result: if all types realized in a countable model M |= T are ranked and the supremum of the Cantor–Bendixson ranks of these types, denoted by CB(M), is a successor ordinal, then M is an almost prime model (i.e. there is a finite tuple c¯ such that (M, c¯) is a prime model of its own first-order theory). As a corollary, we show that for any decidable model M |= T, if CB(M) is a finite ordinal, then M is decidably 0′-categorical. This solves a problem of Belanger. Furthermore, we prove that for any n ∈ ω, there is an almost prime model M with CB(M) = n.

AB - For a complete theory T, the set of n-types of T admits a natural topology. This chapter studies connections between topological spaces of types and the algorithmic complexity of isomorphisms among decidable structures. Let d be a Turing degree. A decidable structure is decidably d-categorical if it has a unique decidable copy, up to d-computable isomorphisms. It is known that if T has a decidable prime model N, then N is decidably 0′-categorical. In other words, if the Cantor–Bendixson ranks of all types realized in a decidable model N |= T are equal to zero, then N is unique, up to computable isomorphisms. We obtain the following result: if all types realized in a countable model M |= T are ranked and the supremum of the Cantor–Bendixson ranks of these types, denoted by CB(M), is a successor ordinal, then M is an almost prime model (i.e. there is a finite tuple c¯ such that (M, c¯) is a prime model of its own first-order theory). As a corollary, we show that for any decidable model M |= T, if CB(M) is a finite ordinal, then M is decidably 0′-categorical. This solves a problem of Belanger. Furthermore, we prove that for any n ∈ ω, there is an almost prime model M with CB(M) = n.

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85179415747&origin=inward&txGid=1c170048379d205235e71037dc118f26

UR - https://www.mendeley.com/catalogue/6b83d93d-a957-31a6-88d8-925a00f99b86/

U2 - 10.1142/9789811278631_0003

DO - 10.1142/9789811278631_0003

M3 - Chapter

SN - 9811278628

T3 - Lecture Notes Series, Institute for Mathematical Sciences

SP - 79

EP - 95

BT - Lecture Notes Series, Institute for Mathematical Sciences

PB - World Scientific

ER -