On limitwise monotonicity and maximal block functions
Charles M. Harris · Computability · 2015
Abstract We prove the existence of a limitwise monotonic function [Formula: see text] such that, for any [Formula: see text] function [Formula: see text], [Formula: see text]. Relativising this result we deduce the existence of an η-like computable linear ordering [Formula: see text] such that, for any [Formula: see text] function [Formula: see text], and η-like [Formula: see text] of order type [Formula: see text], [Formula: see text]. We prove directly that, for any computable [Formula: see text] which is either (i) strongly η-like or (ii) η-like with no strongly η-like interval, there exists [Formula: see text]-limitwise monotonic [Formula: see text] such that [Formula: see text] has order type [Formula: see text]. In so doing we provide an alternative proof to the fact that, for every η-like computable linear ordering [Formula: see text] with no strongly η-like interval, there exists computable [Formula: see text] with [Formula: see text] block relation. We also use our results to prove the existence of an η-like computable linear ordering which is [Formula: see text] categorical but not [Formula: see text] categorical.