Computable choice functions for computable linear orderings
Manuel Lerman, Richard Watnick · Mathematical logic quarterly · 2003
Abstract A choice set for a computable linear ordering is a set which contains one element from each maximal block of the ordering. We obtain a partial characterization of the computable linear order‐types for which each computable model has a computable choice set, and a full characterization in the relativized case; Every model of the linear order‐type α of degree ≤ d has a choice set of degree ≤ d iff α can written as a finite sum of order‐types, each of which either has finitely many blocks, or has order‐type n · η for some integer n.