Abstract: 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.

Cite: Bazhenov N. , Marchuk M.I.
Cantor–Bendixson Ranks for Almost Prime Models
In compilation Aspects of Computation and Automata Theory with Applications. – World Scientific Publishing Co. Pte. Ltd.., 2023. – Т.42. – C.79-95. – ISBN 9789811278624. DOI: 10.1142/9789811278631_0003 Scopus OpenAlex

Dates:

Published print:	Nov 13, 2023
Published online:	Nov 13, 2023

Identifiers:

Scopus:	2-s2.0-85179415747
OpenAlex:	W4388441294

Citing: Пока нет цитирований

Altmetrics: