Computability and categoricity of weakly ultrahomogeneous structures
Francis Adams, Douglas Cenzer · Computability · 2017
This paper investigates the effective categoricity of ultrahomogeneous structures. It is shown that any computable ultrahomogeneous structure is [Formula: see text] categorical. A structure [Formula: see text] is said to be weakly ultrahomogeneous if there is a finite ( exceptional) set of elements [Formula: see text] such that [Formula: see text] 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 [Formula: see text] categorical structures. Index sets are used to determine the complexity of the notions of ultrahomegenous and weakly ultrahomogeneous for various families of structures.