Browse/search for people

Publication - Dr Charles Harris

    On Limitwise Monotonicity and Maximal Block Functions

    Citation

    Harris, C, 2015, ‘On Limitwise Monotonicity and Maximal Block Functions’. Computability, vol 4., pp. 119-139

    Abstract

    We prove the existence of a limitwise monotonic function g : N → N \ {0} such that, for any Π^0_1 function f : N → N \ {0}, Ran f = Ran g. Relativising this result we deduce the existence of an η -like computable linear ordering A such that, forany Π^0_2 function F : Q→N\{0}, and η-like B of ordertype ∑{F(q)|q∈Q},B is not ismorphic to A. Weprove directly that,for any computable A which is either (i) strongly η-like or (ii) η-like with no strongly η-like interval, there exists 0′-limitwisemonotonic G : Q → N\{0} such that A has order type ∑{G(q) | q ∈ Q}. In so doing we provide an alternative proof to the fact that, for every η-like computable linear ordering A with no strongly η-like interval, there exists computable B isomorphic to A with Π^0_1 block relation. We also use our results to prove the existence of an η-like computable linear ordering which is ∆^0_3 categorical but not ∆^0_2 categorical.

    Full details in the University publications repository