On limitwise monotonicity and maximal block functions

Abstract

Abstract

We prove the existence of a limitwise monotonic function $\mathit{g}:\mathbb{N}\to \mathbb{N}\setminus \{0\}$ such that, for any ${\mathrm{\Pi }}_1^0$ function $\mathit{f}:\mathbb{N}\to \mathbb{N}\setminus \{0\}$ , $Ran\mathit{f}\ne Ran\mathit{g}$ . Relativising this result we deduce the existence of an η-like computable linear ordering $\mathcal{A}$ such that, for any ${\mathrm{\Pi }}_2^0$ function $\mathit{F}:\mathbb{Q}\to \mathbb{N}\setminus \{0\}$ , and η-like $\mathcal{B}$ of order type $\sum \{\mathit{F}\mathrm{(}\mathit{q}\mathrm{)}\mid \mathit{q}\in \mathbb{Q}\}$ , $\mathcal{B}\ncong \mathcal{A}$ . We prove directly that, for any computable $\mathcal{A}$ which is either (i) strongly η-like or (ii) η-like with no strongly η-like interval, there exists ${\mathbf{0}}^{\prime }$ -limitwise monotonic $\mathit{G}:\mathbb{Q}\to \mathbb{N}\setminus \{0\}$ such that $\mathcal{A}$ has order type $\sum \{\mathit{G}\mathrm{(}\mathit{q}\mathrm{)}\mid \mathit{q}\in \mathbb{Q}\}$ . In so doing we provide an alternative proof to the fact that, for every η-like computable linear ordering $\mathcal{A}$ with no strongly η-like interval, there exists computable $\mathcal{B}\cong \mathcal{A}$ with ${\mathrm{\Pi }}_1^0$ block relation. We also use our results to prove the existence of an η-like computable linear ordering which is ${\mathrm{\Delta }}_3^0$ categorical but not ${\mathrm{\Delta }}_2^0$ categorical.