Limitwise monotonic sequences and degree spectra of structures
ISKANDER SH. KALIMULLIN, Bakhadyr Khoussainov, Alexander Melnikov · Proceedings of the American Mathematical Society · 2013
In this paper, we study effective monotonic approximations of sets and sequences of sets. We show that there is a sequence of sets which has no uniform computable monotonic approximation but has an x \mathbf {x} -computable monotonic approximation for every hyperimmune degree x \mathbf {x} . We also construct a Σ 2 0 \Sigma ^0_2 set which is not limitwise monotonic but is x \mathbf {x} -limitwise monotonic relative to every non-zero Δ 2 0 \Delta ^0_2 degree x \mathbf {x} . We show that if a sequence of sets is uniformly limitwise monotonic in x \mathbf {x} for all except countably many degrees x \mathbf {x} , then it has to be uniformly limitwise monotonic. Finally, we apply these results to investigate degree spectra of abelian groups, equivalence relations, and ℵ 1 \aleph _1 -categorical structures.