Computability and Categoricity of Weakly Ultrahomogeneous Structures

2016/08/03 by Adams, Francis, Cenzer, Douglas · 1 citation
#FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1608.01254

Abstract

This paper investigates the effective categoricity of ultrahomogeneous structures. It is shown that any computable ultrahomogeneous structure is Δ⁰₂ categorical. A structure A is said to be weakly ultrahomogeneous if there is a finite (exceptional) set of elements a₁,…,a_n 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 Δ⁰₂ categorical structures. Index sets are used to determine the complexity of the notions of ultrahomegenous and weakly ultrahomogeneous for various families of structures.

Cited by

• sp-Homogeneous Linear Orderings

Related

• Notes on degrees of relative computable categoricity
• Coding in the automorphism group of a computably categorical structure
• Degrees of categoricity and treeable degrees
• Degrees of selector functions and relative computable categoricity
• Computability and Complexity of Categorical Structures