Computability and categoricity of weakly ultrahomogeneous structures

Article type: Research Article

Authors: Adams, Francis^a | Cenzer, Douglas^b

Affiliations: [a] Department of Mathematics, University of Florida, P.O. Box 118105, Gainesville, Florida 32611, USA. fsadams@ufl.edu | [b] Department of Mathematics, University of Florida, P.O. Box 118105, Gainesville, Florida 32611, USA. cenzer@math.ufl.edu; http://people.clas.ufl.edu/cenzer

Abstract: This paper investigates the effective categoricity of ultrahomogeneous structures. It is shown that any computable ultrahomogeneous structure is Δ20 categorical. A structure A is said to be weakly ultrahomogeneous if there is a finite (exceptional) set of elements a1,…,an such that A becomes ultrahomogeneous when constants representing these elements are added to the language. Characterizations are obtained for weakly ultrahomogeneous linear orderings, equivalence structures, injection structures and trees, and these are compared with characterizations of the computably categorical and Δ20 categorical structures. Index sets are used to determine the complexity of the notions of ultrahomegenous and weakly ultrahomogeneous for various families of structures.

Keywords: Computability, ultrahomogeneous, injections, effective categoricity, computable model theory

DOI: 10.3233/COM-170070

Journal: Computability, vol. 6, no. 4, pp. 365-389, 2017