Homogeneous Linear Orderings: Index sets, Approximations and Categoricity

We study linear orderings expanded by functions for successor and predecessor. In particular, the sp-homogeneous and weakly sp-homogeneous linear orderings are those which are homogeneous or weakly homogeneous with this additional structure. We demonstrate that these orderings are always relatively Δ₄ categorical and determine exactly which ones are (uniformly) relatively Δ₃ categorical. We also provide a classification for sp-homogeneity and weak sp-homogeneity. We establish that this is the best possible classification by showing that the set of sp-homogeneous linear orderings is Π₅⁰-complete and that the set of weakly sp-homogeneous linear orderings is Σ₆⁰-complete. This result is obtained in two different ways, one using a hands-on computability theoretic approach and another using more abstract descriptive set theory. In understanding the categoricity and classification of sp-homogeneous orderings, we define a sequence of strong homogeneity notions that approximate sp-homogeneity called Cn,m-homogeneity. For finite values of $n,m$ there are only finitely many Cn,m-homogeneous orderings, and these are very closely related to the homogeneous colored linear orderings with finitely many colors. We provide an analytic-combinatorial analysis of the number of Cn,m-homogeneous orderings and the number of homogeneous colored linear orderings with k colors, resulting in precise asymptotic bounds for these sequences.