On Limitwise Monotonicity and Maximal Block Functions

Research output: Contribution to journalArticle (Academic Journal)peer-review

1 Citation (Scopus)
304 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)119-139
Number of pages20
JournalComputability
Volume4
Issue number2
DOIs
Publication statusPublished - 26 Jul 2015

Bibliographical note

Date of Acceptance: 08/04/2015

Keywords

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

Fingerprint Dive into the research topics of 'On Limitwise Monotonicity and Maximal Block Functions'. Together they form a unique fingerprint.

Cite this