On limitwise monotonicity and maximal block functions

Article type: Research Article

Authors: Harris, Charles M.

Affiliations: School of Mathematics, University of Bristol, University Walk, Bristol BS8 1TW, UK. [email protected]. http://www.maths.bris.ac.uk/~hh12242/

Abstract: We prove the existence of a limitwise monotonic function g:N→N∖{0} such that, for any Π10 function f:N→N∖{0}, Ranf≠Rang. Relativising this result we deduce the existence of an η-like computable linear ordering A such that, for any Π20 function F:Q→N∖{0}, and η-like B of order type ∑{F(q)∣q∈Q}, B≇A. We prove directly that, for any computable A which is either (i) strongly η-like or (ii) η-like with no strongly η-like interval, there exists 0′-limitwise monotonic 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≅A with Π10 block relation. We also use our results to prove the existence of an η-like computable linear ordering which is Δ30 categorical but not Δ20 categorical.

Keywords: Limitwise monotonicity, η-like, computable linear ordering, maximal block, categoricity

DOI: 10.3233/COM-150037

Journal: Computability, vol. 4, no. 2, pp. 119-139, 2015