The settling-time reducibility ordering
Barbara F. Csima, Richard A. Shore · Journal of Symbolic Logic · 2007
Abstract To each computable enumerable (c.e.) setAwith a particular enumeration {As}s∈ωthere is associated a settling functionmA(x), wheremA(x) is the last stage when a number less than or equal toxwas enumerated intoA. One c.e. setAis settling time dominated by another setB(B>stA) if for every computable functionf, for all but finitely manyx, mB(x) >f(mA(x)). This settling-time ordering, which is a natural extension to an ordering of the idea of domination, was first introduced by Nabutovsky and Weinberger in [3] and Soare [6]. They desired a sequence of sets descending in this relationship to give results in differential geometry. In this paper we examine properties of the f(mA(g(x))).