Computability-theoretic categoricity and Scott families

https://doi.org/10.1016/j.apal.2019.01.003Get rights and content
Under an Elsevier user license
open archive

Abstract

Computability-theoretic investigation of algorithmic complexity of isomorphisms between countable structures is a key topic in computable structure theory since Fröhlich and Shepherdson, Mal'cev, and Metakides and Nerode. A computable structure A is called computably categorical if for every computable isomorphic B, there is a computable isomorphism from A onto B. By relativizing the notion of computable categoricity to a Turing degree d, we obtain the notion of d-computable categoricity. For the case when d is 0(n1), we also speak about Δn0-categoricity, for n1. More generally, A is relatively Δn0-categorical if for every isomorphic B, there is an isomorphism that is Δn0 relative to the atomic diagram of B. Equivalently, A is relatively Δn0-categorical if and only if A has a computably enumerable Scott family of computable (infinitary) Σn formulas. Relative Δn0-categoricity implies Δn0-categoricity, but not vice versa.

In this paper, we present an example of a computable Fraïssé limit that is computably categorical (that is, Δ10-categorical) but not relatively computably categorical. We also present examples of Δ20-categorical but not relatively Δ20-cate- gorical structures in natural classes such as trees of finite and infinite heights, and homogeneous, completely decomposable, abelian groups. It is known that for structures from these classes computable categoricity and relative computable categoricity coincide.

The categoricity spectrum of a computable structure M is the set of all Turing degrees d such that M is d-computably categorical. The degree of categoricity of M is the least degree in the categoricity spectrum of M, if such a degree exists. It provides the exact level of categoricity of the structure. In this paper, we compute degrees of categoricity for relatively Δ20-categorical abelian p-groups and for relatively Δ30-categorical Boolean algebras.

MSC

03D45
03C57
03D80
03D99

Keywords

Computable model theory
Categoricity
Scott family
Turing degree

Cited by (0)

1

Fokina acknowledges the support of the Austrian Science Fund FWF through the project P 27527. Harizanov was partially supported by the Simons Foundation Collaboration Grant 429466 for Mathematicians and by CCAS Dean's Research Chair and CCFF awards of the George Washington University. She thanks the Kurt Gödel Research Center for their support and hospitality during her stay. The authors thank Sy Friedman for valuable discussions. They also thank the anonymous referees for very helpful suggestions.