On limitwise monotonicity and maximal block functions

Abstract

We prove the existence of a limitwise monotonic function $g : N \to N ∖ {0}$ such that, for any $Π_{1}^{0}$ function $f : N \to N ∖ {0}$ , $Ran f \neq Ran g$ . Relativising this result we deduce the existence of an η-like computable linear ordering $A$ such that, for any $Π_{2}^{0}$ function $F : Q \to N ∖ {0}$ , and η-like $B$ of order type $\sum {F (q) ∣ q \in 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 \to N ∖ {0}$ such that $A$ has order type $\sum {G (q) ∣ q \in 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 $Π_{1}^{0}$ block relation. We also use our results to prove the existence of an η-like computable linear ordering which is $Δ_{3}^{0}$ categorical but not $Δ_{2}^{0}$ categorical.

Keywords

Limitwise monotonicity computable linear ordering maximal block categoricity

1. Introduction

The notion of a limitwise monotonic function was introduced by Khisamiev in the context of computable abelian groups [17–19]. Limitwise monotonicity, and its relativised variants, have since had a number of other applications in effective algebra and computable model theory – see for example [1, 14, 15, 20] or [5] for a recent survey. The first apparent application to computable linear orderings was the result by Coles et al. [2] that there exists a computable linear ordering with a (η-like) $Π_{2}^{0}$ initial segment not isomorphic to any computable linear ordering. Of particular interest to the work below is that this was proved by first showing that for any η-like computable linear ordering $L$ there exists a $0^{'}$ -limitwise monotonic function whose range is the set ${n ∣ L contains a maximal block of size n}$ . Also of special relevance to what follows is recent research showing that limitwise monotonocity is intrinsic to sets having specific representations as linear orderings. (Kenneth) Harris showed that a set A has an η-representation1

¹
$L$ is an η-representation of $A = {a_{0}, a_{1}, a_{2}, \dots} \subseteq N ∖ {0, 1}$ if $L$ is computable and has order type $η + a_{f (0)} + η + a_{f (1)} + η + a_{f (2)} + η + \dots$ for some surjective $f : N \to N$ .

if and only if it is the range of a

0^{'}

-limitwise monotonic function, and similarly Kach proved that the shuffle sum2

The shuffle sum of a set of linear orderings $A = {L_{n}}_{n \in N}$ is the (unique) linear ordering obtained by partitioning $Q$ into dense sets ${Q_{n}}_{n \in N}$ and replacing each $q \in Q_{n}$ by the linear ordering $L_{n}$ . Note that in Kach’s result A may contain any finite ordinal $> 0$ and ω.

of A is computable if and only if A satisfies this latter condition.

With the above in mind, the starting point of the present paper is the corollary to a result proved by Frolov and Zubkov [10] to the effect that, for any $0^{'}$ -limitwise monotonic function $F : Q \to N ∖ {0}$ there exists a computable linear ordering $L$ whose order type is determined by maximal block function F – meaning that $L$ has order type $τ = \sum {F (q) ∣ q \in Q}$ . The underlying idea is then to use the subclass of η-like computable linear orderings having such an order type τ to prove general results about (η-like) computable linear orderings.

In Section 3 – where we state results in full generality since relativisation is immediate in each case – we prove that there exists a set which is the range of a limitwise monotonic function but is not the range of any total $Π_{1}^{0}$ function. From this we deduce that the class of sets comprising the ranges of total $Π_{1}^{0}$ functions is properly subsumed by the class of sets comprising the ranges of limitwise monotonic functions, so that the same (proper subsumption) condition holds for the classes of functions themselves.

Then in Section 4, using the work of Frolov and Zubkov mentioned above, we apply these results to show the existence of an η-like computable linear ordering $A$ such that for any $Π_{2}^{0}$ function $F : Q \to N ∖ {0}$ and linear ordering $B$ of order type $τ = \sum {F (q) ∣ q \in Q}$ , it is not the case that $A ≅ B$ . We note that this result, which was obtained by the author via the construction of a counter example (linear ordering) in [11], solves a question mentioned by several authors including Fellner [8], Lerman and Rosenstein [23] and Downey and Moses [7]. We also show that if computable $A$ is (1) strongly η-like or is (2) η-like but contains no strongly η-like interval, then $A$ has order type τ determined by a $0^{'}$ -limitwise monotonic function F. We note that this can be proved using a result by Moses [25], but we also provide a direct proof by constructing F out of $A$ in the same way that Fellner [8] constructed, out of any η-like computable linear ordering $B$ , a $Δ_{3}^{0}$ maximal block function determining the order type of $B$ . In so doing, we obtain an alternative proof of the restriction of Moses’ result to the class of computable $A$ of order type (2) – namely that there exists computable $L ≅ A$ such that the block relation of $L$ is $Π_{1}^{0}$ .

At this point it is appropriate to mention the original motivation behind the present work. This is the fact that computable approximations to $0^{'}$ -limitwise monotonic functions have similar properties to those of $Π_{2}^{0}$ functions, and that this facilitates the use of strategy tree constructions to build η-like linear orderings whose order type τ is determined by a $0^{'}$ -limitwise monotonic maximal block function. The latter is exploited in [12] to provide a generalisation – to the class of all such order types τ – of Kierstead’s result [21] that there exists computable $L$ of order type $2 \cdot η$ such that $L$ has no nontrivial $Π_{1}^{0}$ automorphism.

Section 5, which concludes the paper, is a preliminary investigation of the question of finding, for given $n ⩾ 1$ , an η-like computable linear ordering $A_{n}$ which is $Δ_{n + 1}^{0}$ categorical but not $Δ_{n}^{0}$ categorical. We note the existence of such an $A_{n}$ for $n = 1$ and we prove, using our earlier results, the existence of $A_{n}$ for $n = 2$ .

2. Preliminaries

We assume ${W_{e}}_{e \in N}$ to be a standard listing of c.e. sets with associated c.e. approximation ${W_{e, s}}_{e, s \in N}$ . $\emptyset^{'}$ denotes the standard halting set for Turing machines in this context, i.e. the set ${e ∣ e \in W_{e}}$ and $0^{'}$ denotes the Turing degree of $\emptyset^{'}$ . More generally $a^{(n)}$ denotes the nth jump of degree $a$ . (Thus $a^{(1)} = a^{'}$ etc.) We suppose $Q_{N} : N \to Q$ to be a computable bijection and we use $q_{0}, q_{1}, q_{2}, \dots$ to denote the resulting listing of $Q$ , i.e. such that $q_{n} = Q_{N} (n)$ for all $n ⩾ 0$ . We also assume $⟨ x, y ⟩$ to be a standard computable pairing function over $N$ extended to use over $Q$ via the above listing. For any $S \subseteq N$ , $S^{[n]}$ denotes the set ${⟨ n, m ⟩ ∣ m \in N}$ . We call $S^{[n]}$ the nth column of S.

For any set X, we use $| X |$ to denote the cardinality of X. For any function F with domain and range (written $Dom F$ and $Ran F$ respectively) in $N$ or $Q$ we use $Graph F$ to denote the set ${⟨ x, y ⟩ ∣ F (x) ↓ = y}$ , i.e. the graph of F coded into $N$ via the pairing function $⟨ \cdot, \cdot ⟩$ . (Note that in this context we identify a pair $(x, y)$ with its code $⟨ x, y ⟩$ so that, for example, the shorthand $Graph F \subseteq Q \times N$ makes sense.) We define F to be Γ, for some arithmetical predicate/class of sets Γ, if $Graph F \in Γ$ . We use predicates of the form $Λ_{n}^{a, 0}$ for the Arithmetical Hierarchy relativised to degree $a$ . Thus for example $S \in Π_{2}^{a, 0}$ if and only if there exists $A \in a$ and $R ⩽_{T} A$ such that $S = {x ∣ \forall z \exists y R (x, y, z)}$ . We also use the standard notation $Λ_{n}^{0}$ when $a = 0$ . We will use the well known fact that for any $Π_{1}^{0}$ set A, $Σ_{2}^{0}$ set B and $Π_{2}^{0}$ set C, there exist computable approximations ${A_{s}}_{s \in N}$ , ${B_{s}}_{s \in N}$ and ${C_{s}}_{s \in N}$ such that $A = {n ∣ \forall s [n \in A_{s}]}$ , $B = {n ∣ \exists t (\forall s ⩾ t) [n \in B_{s}]}$ and $C = {n ∣ \forall t (\exists s ⩾ t) [n \in C_{s}]}$ , and moreover that for each such class we can find a uniformly computable approximation (of the corresponding type) for the whole class. We refer to the latter as (effective) $Π_{1}^{0}$ , $Σ_{2}^{0}$ and $Π_{2}^{0}$ approximations respectively.

In the context of linear orderings we use η to denote the order type of $Q$ whereas n denotes the finite order type with n elements. For linear orderings $L_{β} = ⟨ L_{β}, <_{L_{β}} ⟩$ and $L_{γ} = ⟨ L_{γ}, <_{L_{γ}} ⟩$ of order type β and γ respectively, $β \cdot γ$ denotes the order type of $L_{β} \times L_{γ}$ under lexicographical ordering (from the right). For example $2 \cdot η$ denotes the order type of a linear ordering formed by taking a copy of the rational numbers and replacing every element by an ordered pair.

Let $L = ⟨ L, <_{L} ⟩$ be a linear ordering. We call $S \subseteq L$ an interval if, for all $a, b \in S$ , and any c that lies $<_{L}$ between a and b, c is also in S. Notice that S does not necessarily have endpoints, also that this terminology refers implicitly to the subordering $⟨ S, <_{L} ⟩$ of $L$ . For any $a, b \in L$ , we say that a, b are finitely far apart – written $B_{L} (a, b)$ – if the interval S of elements lying between a and b is finite. (By definition $S = \emptyset$ if $a = b$ .) Noting that $B_{L}$ is an equivalence relation we say that the condensation type of $L$ is the order type of the quotient of $L$ by $B_{L}$ . Note also that we call $B_{L}$ the block relation of $L$ . If $L$ is countably infinite we define $L$ and its order type τ to be η-like if (i) $L$ has no $<_{L}$ least or greatest element and (ii) ${c ∣ B_{L} (a, c)}$ is finite for all $a \in L$ or, equivalently, if $τ = \sum {F (q) ∣ q \in Q}$ for some function $F : Q \to N ∖ {0}$ . We call any finite interval in $L$ a block and we call the equivalence classes under $B_{L}$ maximal blocks. We say that F is a maximal block function of $L$ and its order type τ (or that τ is determined by such F). We say that $L$ and its order type τ are strongly η-like if in addition F has finite range (i.e. the maximal block size is bounded).

Remark.
By these definitions any (strongly) η-like linear ordering or interval is infinite.

For any maximal block I of size $p ⩾ 1$ (written $| I | = p$ ) we use terminology of the form $I = {k_{1} <_{L} \dots <_{L} k_{p}}$ to denote I and we call $k_{1}$ ( $k_{p}$ ) the leftmost (rightmost) element of I. For any distinct elements $a, b \in L$ we say that a and b are adjacent – written $N_{L} (a, b)$ – if the interval of elements lying between a and b is empty. If $L = ⟨ L, <_{L} ⟩$ is countably infinite we derive a listing $l_{0}, l_{1}, l_{2}, \dots$ of L computable in $<_{L}$ . This allows us to assume that $L = N$ . We say that $L$ is computable if $<_{L}$ is computable.
Note 2.1.
$\neg N_{L}$ is computably enumerable in $<_{L}$ whereas $B_{L}$ is computably enumerable in $N_{L}$ . Hence, if $L$ is computable, $N_{L}$ is $Π_{1}^{0}$ and $B_{L}$ is $Σ_{2}^{0}$ .

Finally, if the condensation type of $L$ is η, $1 + η$ , $η + 1$ , or $1 + η + 1$ we say that $L$ has dense condensation type.

We assume the reader to be conversant with the Arithmetical Hierarchy and Turing reducibility ( $⩽_{T}$ ). We refer the reader to [3, 26, 29] for further background and notation in computability theory and to [4] for a review of computability theoretic results in the context of linear orderings.
3. Limitwise monotonicity

In this section we consider the notion of $a$ -limitwise monotonicity for functions and compare the properties of such functions with those of $Π_{1}^{a, 0}$ functions.

Definition 3.1.
Given degree $a$ , we say that $F : N \to N$ is $a$ -limitwise monotonic if there exists $a$ -computable $f : N \times N \to N$ satisfying, for all $n, s ⩾ 0$ , the following conditions.
$f (n, s) ⩽ f (n, s + 1)$ .

${lim}_{s \to \infty} f (n, s)$ exists.

$F (n) = {lim}_{s \to \infty} f (n, s)$ .
If $a = 0$ we simply say that F is limitwise monotonic. Note that we will refer to f as the function witnessing this definition.
Note 3.2.
By use of the computable bijection $Q_{N}^{- 1}$ defined on page 120 we will also apply Definition 3.1 when F and f have (respectively) domains $Q$ and $Q \times N$ . A similar observation applies to the definitions below.
Definition 3.3.
Given an arithmetical predicate of sets Γ, we say that a function $F : N \to N$ is column minimum Γ if there exists $U \in Γ$ such that U and F satisfy, for all $n ⩾ 0$ , the following conditions.
$U^{[n]} \neq \emptyset$ .

$F (n) = min {m ∣ ⟨ n, m ⟩ \in U}$ .
Note that we will refer to U as the set witnessing this definition.
Note 3.4.
Obviously if $F : N \to N$ is Γ – in the standard sense specified on page 120 – then $Graph F$ witnesses that F is column minimum Γ. Thus for any degree $a$ and $Π_{1}^{a, 0}$ function $F : N \to N$ , F is column mininum $Π_{1}^{a, 0}$ .
Lemma 3.5.
Given degree $a$ , for any function $F : N \to N$ the following are equivalent.
F is $a$ -limitwise monotonic.

F is column minimum $Π_{1}^{a, 0}$ .

Proof.
We prove the case $a = 0$ . The general case follows by relativisation.

(1)⇒(2) Let f be the function witnessing that F is limitwise monotonic. Define $Π_{1}^{0}$ approximation ${U_{s}}_{s \in N}$ by setting $U_{s} = N ∖ {⟨ n, m ⟩ ∣ n < s & m < f (n, s)}$ and let $U = ⋂_{s \in N} U_{s}$ . Clearly U witnesses that F is column minimum $Π_{1}^{0}$ .

(2)⇒(1) Suppose that $Π_{1}^{0}$ set V witnesses that F is column minimum $Π_{1}^{0}$ . Let ${V_{s}}_{s \in N}$ be a $Π_{1}^{0}$ approximation to V. Define $f : N \times N \to N$ by setting: $f (n) = \{\begin{matrix} min {m ∣ ⟨ n, m ⟩ \in V_{s}} & if n < s, \\ 0 & if n ⩾ s . \end{matrix}$ Clearly f witnesses that F is limitwise monotonic. □
Note 3.6.
Given degree $a$ and $n ⩾ 0$ , a set V is $Π_{1}^{a^{(n)}, 0}$ if and only if V is $Π_{n + 1}^{a, 0}$ . Hence, by Lemma 3.5, F is $a^{(n)}$ -limitwise monotonic if and only if F is column minimum $Π_{n + 1}^{a, 0}$ . In particular, F is $0^{'}$ -limitwise monotonic if and only if F is column minimum $Π_{2}^{0}$ .
Lemma 3.7 ([13, 16]).

For any function $F : N \to N$ the following are equivalent.

F is $0^{'}$ -limitwise monotonic.

There is a computable function $g : N \times N \to N$ such that, for all $n ⩾ 0$ , $F (n) = {lim inf}_{s \to \infty} g (n, s)$ .

Proof.
By Note 3.6 condition (1) is equivalent to saying that F is column minimum $Π_{2}^{0}$ . We use this below.

(1)⇒(2) Let U be a set witnessing that F is column minimum $Π_{2}^{0}$ and let ${U_{s}}_{s \in N}$ be a $Π_{2}^{0}$ approximation – defined such that $U_{s} \subseteq N ↾ s$ for all s – to U. (So that $U = {m ∣ \forall s (\exists t ⩾ s) [m \in U_{s}]}$ .) Then the function g defined by setting $g (n, s) = \{\begin{matrix} min {m ∣ ⟨ n, m ⟩ \in U_{s}} & if U_{s}^{[n]} \neq \emptyset, \\ s & otherwise, \end{matrix}$ is clearly such that $F (n) = {lim inf}_{s \to \infty} g (n, s)$ for all $n ⩾ 0$ .

(2)⇒(1) Define the approximation ${V_{s}}_{s \in N}$ by setting $V_{s} = {⟨ n, g (n, s) ⟩ ∣ n \in N}$ and set $V = {m ∣ \forall s (\exists t ⩾ s) [m \in V_{s}]}$ . Then V witnesses that F is column minimum $Π_{2}^{0}$ . □
Note 3.8.
Call F epigraph minimum Γ if for some $U \in Γ$ , U and F satisfy the conditions of Definition 3.3 in conjunction with the extra condition that, for every n, if $m < p$ , and $⟨ n, m ⟩ \in U$ then $⟨ n, p ⟩ \in U$ . Note that the set U defined in the proof of (1) ⇒ (2) of Lemma 3.5 witnesses that F is in fact epigraph minimum $Π_{1}^{0}$ . It follows by relativisation that, for any degree $a$ , a function F is column minimum $Π_{1}^{a, 0}$ if and only if F is epigraph minimum $Π_{1}^{a, 0}$ . Frolov and Zubkov essentially use this definition in the case $Γ = Π_{2}^{0}$ in Theorem 2.2 of [10] of which – under the equivalence of (1) and (2) in Lemma 3.7 – Theorem 4.3 is a corollary.

A standard argument shows that, for any computable function $f : N \to N$ such that $Ran f$ is infinite we can define an injective computable function $g : N \to N$ such that $Ran g = Ran f$ . Our next result, in its unrelativised form, shows that this property also holds in the context of $Π_{1}^{0}$ functions. Note that we use this property to prove the main result of this section stated in Theorem 3.12.
Proposition 3.9.
Given degree $a$ , for any $Π_{1}^{a, 0}$ function $f : N \to N$ such that $Ran f$ is infinite there exists an injective $Π_{1}^{a, 0}$ function $g : N \to N$ such that $Ran g = Ran f$ .
Proof.
We prove the case $a = 0$ . The general case follows by relativisation. We define the graph of g via a computable construction. For this, supposing V to be the graph of f and ${x_{s}}_{s \in N}$ to be a computable enumeration of $\overline{V}$ we define the $Π_{1}^{0}$ approximation ${V_{s}}_{s \in N}$ to V by setting $V_{0} = N$ , $V_{2 s + 1} = N ∖ {x_{0}, \dots, x_{s}}$ and $V_{2 s + 2} = V_{2 s + 1}$ for all $s ⩾ 0$ . Associated with f we have (implicit) f-witnesses $f_{n, s}$ for all (columns) n and stages s. For $2 n < s$ , $f_{n, s}$ is nontrivially defined and denotes the least number k such that $⟨ n, k ⟩ \in V_{s}$ . (For $2 n ⩾ s$ , $f_{n, s} = 0$ .) Note that this means that $f_{n, s} ⩽ f_{n, s + 1}$ for all s and that ${lim}_{s \to \infty} f_{n, s} = f (n)$ . We assume this behaviour during the construction – i.e. we do not explicitly define the f-witnesses.

We define a $Π_{1}^{0}$ approximation ${U_{s}}_{s \in N}$ to the graph of g (denoted U) starting with $U_{0} = N$ . We define g-witnesses which are used to track f-witnesses. At each stage s we define a column threshold $r_{s}$ . Note that the definition we use sets $r_{0} = 0$ and satisfies $2 r_{s} ⩽ s$ for all $s > 0$ . Corresponding to the latter we have that the g-witness $g_{n, s}$ (which we also call the g-witness for n) is nontrivially defined if and only if $n < r_{s}$ . When we define $g_{n, s}$ we also define a ceiling pointer $c_{n, s}$ which will satisfy $c_{n, s} > g_{n, s}$ for all s. The idea here is that, for all $n < r_{s}$ , $g_{n, s}$ is the s-stage approximation to $g (n)$ witnessed by the fact that $⟨ n, g_{n, s} ⟩ \in U_{s}$ is the unique element in $N^{[n]} ↾ ⟨ n, c_{n, s} ⟩$ . We will define the construction so that, for $l \in {g, c}$ , $l_{n, s} ⩽ l_{n, s + 1}$ for all s, ${lim}_{s \to \infty} g_{n, s} = g (n)$ is defined, and ${lim}_{s \to \infty} c_{n, s} = \infty$ (so that every number in $N^{[n]} ∖ {⟨ n, g (n) ⟩}$ is eventually removed from U). We call n the label of $g_{n, s}$ and we use similar terminology for f-witnesses.

At each stage s we define two disjoint sets of labels $T_{s}$ and $F_{s}$ – called respectively the (s-stage) tracking and free sets – such that $T_{s} \cup F_{s} = N ↾ r_{s}$ . When n enters $T_{s}$ , the g-witness $g_{n, s}$ is assigned to track an f-witness $f_{k, s}$ (say). This means that we set $g_{n, s} = f_{k, s}$ and at subsequent stages this equality is preserved subject to the collision and track switching protocols described below. To simplify terminology we say that the g-label n is tracking the f-label k in this case. $F_{s}$ contains all those g-labels $n < r_{s}$ such that n is not at present tracking any f-label. (Note that $n \in F_{s}$ implies that $n \in T_{t}$ for some $t < s$ .)

Note. We apply the standard priority ordering to g-labels – i.e. p has higher priority than q if and only if $p < q$ .

At each stage of the construction at most one f-witness can move. If, at stage s, an f-witness with label n moves onto a value already occupied by some other f-witness with label m, we say that f-label n converges onto f-label m (at stage s).

We now describe the four main protocols determining activity related to tracking. Each protocol is described relative to a given stage $s > 0$ .

Tracking protocol. If $n \in T_{s}$ and g-label n is tracking f-label k, then the ceiling pointer $c_{n, s}$ is set to the least $l > f_{k, s} = g_{n, s}$ such that $⟨ k, l ⟩ \in V_{s}$ . In other words $⟨ k, c_{n, s} ⟩$ is the second to least element in $V_{s}^{[k]}$ whereas $⟨ k, g_{n, s} ⟩$ is the least element in $V_{s}^{[k]}$ . Also, by definition of $g_{n, s}$ and $c_{n, s}$ these conditions are mirrored in $U_{s}^{[n]}$ .

Collision protocol. We say that two g-labels $n < m$ in $T_{s - 1}$ collide at stage s if the f-label that n is tracking converges onto the f-label that m is tracking or vice versa. In this case g-label m (which has lower priority) is transferred from $T_{s - 1}$ to $F_{s}$ and the values of the g-witness and ceiling pointer for m are reset according to the freedom protocol below. The g-label n on the other hand is retained in $T_{s}$ . (We say that n survives the collision.) The f-label that n is set to track is determined by the track switching protocol below.

Track switching protocol. Given g-label n and f-labels $l < k$ , if n is tracking k and k converges onto l at stage s then, if $n \in T_{s}$ – i.e. if n survives a possible collision with another g-label – n switches from tracking f-label k to tracking f-label l.

Remark. This switching behaviour is required in order for the condition $Ran f \subseteq Ran g$ to be fulfilled (as explained below). Notice that $c_{n, s - 1} = f_{l, s}$ ( $= f_{l, s - 1}$ ) by definition in this case so that ${⟨ n, u ⟩ ∣ u ⩾ f_{l, s}} \subseteq U_{s - 1}$ . Thus the g-witness for n can switch to tracking $f_{l, s}$ with no fear of a possible future break down. Note however that we do not specify switching in the case when the f-label l converges onto the f-label k (being tracked by g-label n). This is because it may be that $c_{n, s - 1} > f_{l, s} + 1$ , in which case the set $D = {⟨ n, u ⟩ ∣ f_{l, s} < u < c_{n, s - 1}} \subseteq \overline{U_{s - 1}}$ is nonempty. Thus, if we tried to re-assign the g-witness for n to track $f_{l, s}$ this tracking would break down if, at some stage $t > s$ , $f_{l, t} = u$ for some u such that $⟨ n, u ⟩ \in D$ .

Freedom protocol. If g-label n is moved into $F_{s}$ at stage s (as described in the collision protocol), then $g_{n, s}$ is set to $c_{n, s - 1}$ and $c_{n, s}$ is set to $c_{n, s - 1} + 1$ . Note that this means that ${⟨ n, u ⟩ ∣ u ⩾ g_{n, s} \subseteq U_{s}}$ so that future tracking carried out by g-label n will not break down. If $n \in F_{s} \cap F_{s + 1}$ , then by definition $l_{s + 1} = l_{s}$ for $l \in {g, c}$ . I.e. both the g-witness and the ceiling pointer for n remain constant for as long as n remains free, and in this case the ceiling pointer for n is the successor to the g-witness for n.

The Construction

Stage 0. $U_{0} = N$ and all the explicit parameters are trivially defined, i.e. $r_{0} = 0$ (so that $T_{0} = F_{0} = \emptyset$ ) and $g_{n, 0} = 0$ , $c_{n, 0} = 1$ for all n.

Staget + 1. There is an initial step specified according as to whether the stage is even or odd, and a final step. The final step involves default parameter updating and redefinition of the approximation to U.

The Initial Step for odd stage $t + 1 = 2 s + 1$ . $x_{s}$ is removed from V by definition. Suppose that $x_{s} \in V_{t}^{[k]}$ , i.e. $x_{s}$ is in the column associated with f-label k. If no g-label is tracking k at present nothing happens during this step. Suppose otherwise, i.e. that some g-label n is tracking k. If $x_{s} \notin {⟨ k, g_{n, t} ⟩, ⟨ k, c_{n, t} ⟩}$ , then again nothing happens during this step. If $x_{s} = ⟨ k, c_{n, t} ⟩$ , then $c_{n, t + 1}$ is updated in accordance with the tracking protocol (with the end effect that $⟨ k, c_{n, t + 1} ⟩$ and $⟨ n, c_{n, t + 1} ⟩$ are the second to least numbers in $V_{t + 1}^{[k]}$ and $U_{t + 1}^{[n]}$ respectively). If $x_{s} = ⟨ k, g_{n, t} ⟩$ and there is no collision then the g-witness and ceiling pointer for n are updated according to the track switching and tracking protocols. (Note that $n \in T_{t} \cap T_{t + 1}$ in both of the latter cases.) If however n is involved in a collision with another g-label then, supposing that the other g-label involved is m, $T_{t}$ , $F_{t}$ , and the g-witnesses and ceiling pointers for n and m are updated in accordance with the collision, track switching, tracking and freedom protocols. (Thus for $p, q \in {n, m}$ with $p < q$ , the construction arranges that $p \in T_{t} \cap T_{t + 1}$ , $q \in T_{t} \cap F_{t + 1}$ etc.)

The Initial Step for even stage $t + 1 = 2 s + 2$ . There are two cases. The first is when the free set is empty, i.e. $F_{t} = \emptyset$ . In this case the construction tests whether there exists k satisfying $2 k < t + 1$ such that, for all $m < r_{t}$ , $g_{m, t} \neq f_{k, t}$ . If so then $n = r_{t}$ is enumerated into the tracking set $T_{t + 1}$ and the g-label n is set to track f-label k for the least such k; this means that the g-witness and ceiling pointer for n are defined (for the first time) according to the tracking rules – i.e. $g_{n, t + 1} = f_{k, t}$ ( $= f_{k, t + 1}$ ) and $c_{n, t + 1}$ is defined to be the least $l > f_{k, t}$ such that $⟨ k, l ⟩ \in V_{t}$ . Also $r_{t + 1}$ is defined to be $r_{t} + 1$ . If $F_{t} = \emptyset$ but the above conditions do not both hold then nothing happens during this step. The second case is when $F_{t} \neq \emptyset$ . Let $n_{0}$ be the least label in $F_{t}$ . Then the construction repeats the same search as above but for $n = n_{0}$ (instead of $n = r_{t}$ ) and under the additional proviso that $f_{k, t} ⩾ g_{n_{0}, t}$ in this case. In other words, if such k exists the construction picks the least such k and sets g-label $n_{0}$ to track f-label k – i.e. removes $n_{0}$ from $F_{t}$ and adds it to $T_{t + 1}$ and now updates the g-witness and the ceiling pointer for $n_{0}$ according to the tracking protocol. If no such k exists then nothing happens during this step.

Final Step at stage $t + 1$ . The construction resets all explicit (i.e. g related) parameters that have not been redefined during the initial step to their value at stage t and then defines $U_{t + 1} = U_{t} ∖ {⟨ n, m ⟩ ∣ n < r_{t + 1} & m < c_{n, t + 1} & m \neq g_{n, t + 1}}$ .

Verification

Define $T = {n ∣ \exists t (\forall s ⩾ t) [n \in T_{s}]}$ . We proceed via Sublemmas 1–4 below. Sublemma 1.
For all $n, m \in T$ , ${lim}_{s \to \infty} g_{n, s} = g (n)$ exists and $g (n) \in Ran f$ . Also ${lim}_{s \to \infty} c_{n, s} = \infty$ , and $g (n) = g (m)$ implies $n = m$ .
Proof.
We see, by induction over the stages of the construction, that for all $s ⩽ t$ , if $m, n \in T_{s}$ and $m \neq n$ then $g_{m, s} \neq g_{n, s}$ ; also that, for any f-label k, if $n \in T_{r}$ for all $s ⩽ r ⩽ t$ , and if g-label n was tracking f-label k at stage s then n is tracking some f-label $l ⩽ k$ at stage t. The conditions stated in Sublemma 1 follow from these facts and the definition of the f-witnesses. □
Notation. In what follows we say that the g-witness $g_{n, s}$ has stabilised (at stage s) if $g_{n, t} = g_{n, s}$ for all $t ⩾ s$ . Sublemma 2.
$T = N$ .
Proof.
Consider any $n ⩾ 0$ . Suppose as inductive hypothesis, that for all $m < n$ , $m \in T$ . Let $s_{n}$ be a stage such that, for all $m < n$ , $m \in T_{s}$ for all $s ⩾ s_{n}$ (so that $r_{s_{n}} ⩾ n$ ) and such that the g-witness for every such m has already stabilised at stage $s_{n}$ . Note firstly that it suffices to show that $n \in T_{s}$ for some $s ⩾ s_{n}$ since in this case $n \in T_{t}$ for all $t ⩾ s$ . Indeed if n is involved in a collision with some $n^{'}$ at any such stage t, we have that $n < n^{'}$ (by definition of $s_{n}$ ) so that n remains in $T_{t + 1}$ . Suppose that $F_{s_{n}} \neq \emptyset$ . Then $r_{s_{n}} > n$ so that either $n \in T_{s_{n}}$ or $n \in F_{s_{n}}$ . But, if $n \notin T_{s_{n}}$ , we see that n is the least label in $F_{s_{n}}$ and will remain so until such a stage s when n is moved back into $T_{s}$ , i.e. when g-label n is reset to track some f-label. Note that such a stage exists as $Ran f$ is infinite – also that the same observation applies for the final case below. On the other hand, if $F_{s_{n}} = \emptyset$ , then either $n < r_{s_{n}}$ and $n \in T_{s_{n}}$ , or otherwise $r_{s_{n}} = n$ , meaning that $g_{n, s_{n}}$ has not yet been defined. However in this last case $F_{s} = \emptyset$ at all subsequent stages s until a stage t when a g-witness for n is defined and when n enters $T_{t}$ . We hence deduce – on the strength of our earlier observation – that, in every case there is some $s ⩾ s_{n}$ such that $n \in T_{t}$ for all $t ⩾ s$ . We can thus conclude by induction that $T = N$ . □

At this point in the verification we know that g is injective (with $Ran g$ infinite) and that $Ran g \subseteq Ran f$ . Sublemma 3.
$Ran f \subseteq Ran g$ .
Proof.
Note firstly that, as $T = N$ we know that the set ${s ∣ F_{s} = \emptyset}$ is infinite. Consider once again any $n ⩾ 0$ . Suppose as inductive hypothesis that, for all $k < n$ , there exists some m such that $g (m) = f (k)$ . Let $t_{n} + 1$ be a large enough even stage such that (i) $F_{t_{n}} = \emptyset$ , (ii) for all m such that $g (m) \in {f (0), \dots, f (n - 1)}$ the g-witness for m has stabilised at stage $t_{n}$ , and (iii) the f-witness for n has already stabilised – i.e. $f_{n, t_{n}} = f (n)$ . Then, if there is some g-witness tracking $f_{n, t_{n}} = f (n)$ it is clear that either this g-witness or some other g-witness of higher priority (i.e. whose label is smaller) will eventually stabilise on $f (n)$ . This is because, during any subsequent collision involving the value $f (n)$ the g-witness of higher priority will be set to track $f (n)$ , in accordance with the collision and track switching protocols. Since there are only finitely many g witnesses of higher priority than the g-witness tracking $f (n)$ at stage $t_{n}$ the tracking witness for $f (n)$ can change at most this many times.

Remark. Notice that since the f-witness for n has already stabilised as $f (n)$ , any subsequent collision associated with $f (n)$ is due to some f-label l converging on to n (and that track switching only happens if f-label l is being tracked by some g-label of higher priority than the g-label tracking $f (n)$ ). Hence any track switching happens without subsequent breakdown – as already mentioned in the Remark on page 123.

Likewise if there is no g-witness tracking $f (n)$ at stage $t_{n}$ then – letting $m = r_{t_{n}}$ – we see that witness $g_{m, t_{n} + 1}$ is defined and set to track $f (n)$ at stage $t_{n} + 1$ . Thus we can deduce as above that some g-witness eventually stabilises on $f (n)$ . In other words, in both cases we can conclude that there exists p such that $g (p) = f (n)$ . It follows by induction that $Ran f \subseteq Ran g$ . □
Sublemma 4.
$Graph g = ⋂_{s \in N} U_{s}$ . In other words g is a $Π_{1}^{0}$ function.
Proof.
This follows by induction over the stages of the construction using the definition of the tracking rules. □

This concludes the proof of Proposition 3.9. □

Suppose that f is a limitwise monotonic function such that $Ran f$ is infinite, and let V witness that f is epigraph minimum $Π_{1}^{0}$ where V is defined similarly to the set U in the proof of (1) ⇒ (2) of Lemma 3.5. Let ${x_{s}}_{s \in N}$ be a computable enumeration of $\overline{V}$ such that, for all $s, n ⩾ 0$ and $0 ⩽ p < m$ , if $x_{s} = ⟨ n, m ⟩$ , then $⟨ n, p ⟩ = x_{t}$ for some $0 ⩽ t < s$ . Note that such an enumeration is easily derived from any computable enumeration of $\overline{V}$ . Now apply the proof of Proposition 3.9 with V and ${x_{s}}_{s \in N}$ redefined as just stated. (Notice that in this case, by definition of ${x_{s}}_{s \in N}$ , $c_{n, s} = g_{n, s} + 1$ for all $s ⩾ 0$ , so that ${lim}_{s \to \infty} c_{n, s} = g (n) + 1$ .) Then we verify Sublemmas 1–4 with Sublemma 4 modified to the effect that g is epigraph minimum $Π_{1}^{0}$ (and so limitwise monotonic) as witnessed by U. With these straightforward modifications and relativisation we thus obtain a proof of the following result by Kenneth Harris.
Proposition 3.10 ([13]).

Given degree $a$ , for any $a$ -limitwise monotonic function f such that $Ran f$ is infinite there exists an injective $a$ -limitwise monotonic function g such that $Ran g = Ran f$ .

Note 3.11.
Suppose that f and g are functions with domain $N$ such that f is injective and $Ran f = Ran g$ . Then the set $I = {(i, e) ∣ i ⩽ e & f (i) = g (e)}$ is infinite. To see this suppose otherwise. Then there exists $\hat{i}$ such that, for all $i > \hat{i}$ , $f (i) = g (k)$ for some $k < i$ . Choose $i^{}$ to be such that $f ({0, \dots, \hat{i}}) \subseteq g ({0, \dots, i^{} - 1})$ . (Note that $i^{} > \hat{i}$ .) Set $E_{f} = {f (i) ∣ 0 ⩽ i ⩽ i^{}}$ and $E_{g} = {g (i) ∣ 0 ⩽ i < i^{}}$ . Then $E_{f} \subseteq E_{g}$ by definition of $i^{}$ . However $| E_{f} | = i^{} + 1$ as f is injective, whereas $| E_{g} | ⩽ i^{}$ . Thus our supposition must be wrong and I is indeed infinite.
Theorem 3.12.
Given degree $a$ , there exists an $a$ -limitwise monotonic function $g : N \to N ∖ {0}$ such that, for any $Π_{1}^{a, 0}$ function $f : N \to N ∖ {0}$ , $Ran f \neq Ran g$ .
Proof.
We prove the case $a = 0$ . The general case follows by relativisation. Assume ${U_{e}}_{e \in N}$ to be the listing of $Π_{1}^{0}$ sets with associated $Π_{1}^{0}$ approximation ${U_{e, s}}_{e, s \in N}$ derived in the standard manner from ${W_{e, s}}_{e, s \in N}$ on page 120. (I.e. $U_{e, s} = N ∖ W_{e, s}$ for all $e, s ⩾ 0$ .) We define $g : N \to N ∖ {0}$ via a computable construction such that $Ran g$ is infinite, g is limitwise monotonic, and such that, for all indices $e ⩾ 0$ , the requirement $\begin{array}{l} R_{e} : for all i, j ⩽ e, if U_{j} is the graph of a function f, then f (i) \neq g (e), \end{array}$ is satisfied. Note that satisfaction of ${R_{e}}_{e \in N}$ is sufficient to prove our result. To see this, suppose firstly that index j is such that $U_{j}$ is the graph of the identity function. Then, for all $e ⩾ j$ , $g (e) > e$ (due to satisfaction of $R_{e}$ ). In other words, $Ran g$ is infinite. (In fact we can easily modify the construction to make g injective as noted below.) Now suppose that for some $Π_{1}^{0}$ function f, $Ran f = Ran g$ . By Proposition 3.9 we can assume that f is injective. Let index j be such that $U_{j}$ is the graph of f. Then, by Note 3.11, there exists a pair $(i, e)$ such that $j ⩽ i ⩽ e$ and $f (i) = g (e)$ . However this is ruled out by the satisfaction of $R_{e}$ .

Parameters. For index $e ⩾ 0$ we define $Z_{e} = {1, \dots, {(1 + e)}^{2} + 1}$ to be the diagonalisation domain for $R_{e}$ and, for all stages s we define $g (e, s) \in Z_{e}$ which denotes the construction’s present approximation to the value of $g (e)$ . Note that the worst case that we have to deal with is if, for all $j ⩽ e$ , $U_{j}$ is the graph of a function $f_{j}$ (say) such that $f_{j} (i)$ is defined for all $i ⩽ e$ . Then notice that $| {f_{j} (i) ∣ i, j ⩽ e} | ⩽ {(1 + e)}^{2}$ . Thus there is some $x \in Z_{e}$ such that $x \neq f_{j} (i)$ for all $i, j ⩽ e$ . Hence the cardinality of $Z_{e}$ is large enough for satisfaction of $R_{e}$ to be obtained by arranging that ${lim}_{s \to \infty} g (e, s) = g (e) \in Z_{e}$ be defined appropriately. Note also that we need $Z_{e}$ to be fixed (i.e. with no variation from stage to stage) in order for the construction to be able to make valid guesses as to whether for any $i, j ⩽ e$ , $U_{j}$ looks like a function f (relative to codomain $Z_{e}$ ) at input i. We also define a finite set $D (e, s) \subseteq Z_{e}$ at stage s. If the construction guesses that $U_{j}$ looks like the graph of a function f with output $f (i) = r \in Z_{e}$ at stage s then it sets $r \in D (e, t)$ for all stages $t ⩾ s$ . Note that $⟨ i, r ⟩$ may be removed from $U_{j, t}$ at some subsequent stage t (as ${U_{j, s}}_{s \in N}$ is a $Π_{1}^{0}$ approximation). However in this case the construction knows that if indeed $U_{j}$ is the graph of a function f defined at input i then $f (i) \notin Z_{e}$ so that trivially $g (e) \neq f (i)$ . Note also that the fact that (in any case) the value $r = f (i)$ remains in $D (e, t)$ for all $t ⩾ s$ implies that $D (e, s) \subseteq D (e, s + 1)$ for all s. This ensures that $g (e, s) ⩽ g (e, s + 1)$ via the definition stated below.

The Construction

Stage 0. For all $e ⩾ 0$ , $D (e, 0) = \emptyset$ and $g (e, 0) = 1$ .

Stages + 1. There are $s + 1$ substages $0 ⩽ e ⩽ s$ that make up stage $s + 1$ . Note that any parameter not explicitly redefined is reset to its value at stage s.

Substage e . Process requirement $R_{e}$ as follows. Let $E \subseteq N ↾ (e + 1) \times N ↾ (e + 1)$ be the finite set such that $(i, j) \in E \Leftrightarrow | {⟨ i, r ⟩ ∣ r \in Z_{e}} \cap U_{j, s + 1} | ⩽ 1$ and let $D = {r ∣ (\exists (i, j) \in E) [⟨ i, r ⟩ \in U_{j, s + 1}]} .$ Set $D (e, s + 1) = D (e, s) \cup D$ and define $g (e, s + 1)$ to be the least element in $Z_{e} ∖ D (e, s + 1)$ .

Verification

We define g and verify that g satisfies the statement of the Theorem 3.12 via Sublemmas 1–3 below (taking into account our earlier observations about the satisfaction of the requirements). Sublemma 1.
For each index e and all stages s, $g (e, s) \in Z_{e} ∖ D (e, s)$ is defined and $g (e, s) ⩽ g (e, s + 1)$ .
Proof.
By definition $D (e, s) \subseteq Z_{e}$ and by inspection we see that $| D (e, s) | < | Z_{e} |$ . Thus $g (e, s) \in Z_{e} ∖ D (e, s)$ is indeed defined. Moreover $g (e, s) ⩽ g (e, s + 1)$ due to the fact $D (e, s) \subseteq D (e, s + 1)$ . □
Definition. We define g by setting $g (e) = {lim}_{s \to \infty} g (e, s)$ for all $e \in N$ . Sublemma 2.
g is limitwise monotonic.
Proof.
This is a direct corollary of Sublemma 1 (including the fact that $g (e)$ is defined for all $e \in N$ ). □
Sublemma 3.
For all indices e, $R_{e}$ is satisfied.
Proof.
Suppose that $U_{j}$ is the graph of a function f. If $f (i) \notin Z_{e}$ , then $g (e) \neq f (i)$ . If, on the other hand, $f (i) \in Z_{e}$ , then there is a stage $\hat{s} ⩾ e$ such that, for $s = \hat{s} + 1$ (and for all $s > \hat{s} + 1$ ), ${⟨ i, r ⟩ ∣ r \in Z_{e}} \cap U_{j, s} = {⟨ i, f (i) ⟩}$ . Thus, for all $s > \hat{s}$ , $f (i) \in D (e, s)$ so that $g (e, s) \neq f (i)$ . Hence $g (e) \neq f (i)$ . □

This concludes the proof of Theorem 3.12. □
Note 3.13.
Choosing any $p ⩾ 0$ , we can replace $g : N \to N ∖ {0}$ by $g : N \to N ∖ N ↾ p$ in the statement of Theorem 3.12 by a straightforward adjustment of the proof. We can also clearly force g to be injective. For example we could define $Z_{e}$ as before but with $min Z_{e + 1} = max Z_{e} + 1$ for every index e.

The result below follows from the conjunction of Note 3.4, Lemma 3.5 and Theorem 3.12. Corollary 3.14.
Given degree $a$ , the class ${Ran f ∣ Dom f = N & f \in Π_{1}^{a, 0}}$ is properly subsumed by the class ${Ran g ∣ g is a -limitwise monotonic}$ , and the class of $Π_{1}^{a, 0}$ functions with domain $N$ is properly subsumed by the class of $a$ -limitwise monotonic functions.

4. The complexity of maximal block functions

We now turn our attention to linear orderings. We begin by considering the bound on the arithmetical complexity of maximal block functions of η-like computable linear orderings established by Fellner.

Definition 4.1.
If, given an η-like linear ordering $A$ , we define (i) an enumeration ${I_{q}}_{q \in Q}$ of the maximal blocks of $A$ such that $A = \sum {I_{q} ∣ q \in Q}$ and (ii) a function $F : Q \to N ∖ {0}$ such that, for all $q \in Q$ , $F (q) = | I_{q} |$ – so showing that $A$ has order type $τ = \sum {F (q) ∣ q \in Q}$ – then we say that the maximal block function F is constructed out of $A$ .

Note that, in the above definition, F is derived from the enumerating function $F_{I} (q) = I_{q}$ by stripping away all the information relative to $I_{q}$ except its ordinality. Note also that, in the proof of Fellner’s result below, the maximal block function F is constructed out of $A$ in the above sense.
Theorem 4.2 ([8]).

If $A$ is an η-like computable linear ordering then there is a $Δ_{3}^{0}$ function $F : Q \to N ∖ {0}$ such that $A$ has order type $τ = \sum {F (q) ∣ q \in Q}$ .

Proof sketch.
Suppose that $A = ⟨ A, <_{A} ⟩$ and that $a_{0}, a_{1}, a_{2} \dots$ is a computable enumeration of A. We know that the adjacency relation $N_{A}$ is $Π_{1}^{0}$ as $A$ is computable. Moreover the fact that $A$ is computable also means that the choice set $C_{l}$ ( $C_{r}$ ) made up of the leftmost (rightmost) elements of maximal blocks in $A$ is $Π_{2}^{0}$ . Thus, using an $0^{″}$ oracle, we can build, for any $a \in A$ , the maximal block of a. Therefore we can construct out of $A$ a $Δ_{3}^{0}$ maximal block function F such that $A$ has order type $τ = \sum {F (q) ∣ q \in Q}$ . Indeed, working by stages, at stage 0 we define $I_{q_{0}}$ as the maximal block of $a_{0}$ and set $F (q_{0}) = | I_{q_{0}} |$ . At stage $s + 1$ we find $a_{n} \notin A ∖ ⋃_{0 ⩽ t ⩽ s} I_{q_{t}}$ such that n is least and such that (the maximal block of) $a_{n}$ is ordered under $<_{A}$ relative to ${I_{q_{t}} ∣ 0 ⩽ t ⩽ s}$ as $q_{s + 1}$ is ordered under $<_{Q}$ relative to ${q_{t} ∣ 0 ⩽ t ⩽ s}$ . We define $I_{q_{s + 1}}$ to be the maximal block of $a_{n}$ and set $F (q_{s + 1}) = | I_{q_{s + 1}} |$ . From the fact that $A$ is η-like we easily conclude that this construction defines F as stated. □

One of our main concerns below is the extent to which the bound in Theorem 4.2 can be tightened. Before considering this question however we look at the characterisation of an important subclass of η-like computable linear orderings determined by Frolov and Zubkov.
Theorem 4.3 ([10]).

Let τbe an η-like linear order type. Then the following are equivalent.

There exists $0^{'}$ -limitwise monotonic $F : Q \to N ∖ {0}$ such that $τ = \sum {F (q) ∣ q \in Q}$ .

There exists computable $A$ of order type τ such that $B_{A}$ is $Π_{1}^{0}$ .

Proof sketch.
(1)⇒(2) By Lemma 3.7, we know that there exists computable f such that $F (q) = {lim inf}_{s \to \infty} f (q, s)$ for all $q \in Q$ – and we can clearly also assume that $f (q, s) ⩾ 1$ for all $q \in Q$ and $s ⩾ 0$ . We define $A = ⟨ A, <_{A} ⟩$ so that $A = N$ via a computable construction. At any stage s, for each $q_{n}$ such that $n < s$ a block $I (n, s)$ of size $f (q_{n}, s)$ is defined. For distinct $m, n < s$ the blocks labelled by m and n are ordered according to the ordering of $q_{m}$ and $q_{n}$ (under $<_{Q}$ ). Moreover $I (n, s) = {x_{1} <_{A} \dots <_{A} x_{f (q_{n}, s)}}$ is defined such that $x_{i} <_{N} x_{i + 1}$ for all $1 ⩽ i < f (q_{n}, s)$ . Letting $n < s$ we now briefly describe the evolution of $I (n, s)$ at stage $s + 1$ . To do this suppose that $d = f (q_{n}, s + 1) - f (q_{n}, s)$ . Then at stage $s + 1$ , if $d < 0$ , then $I (n, s + 1)$ is obtained from $I (n, s)$ by shedding the d rightmost elements of the latter, that then become free. If, on the other hand, $d > 0$ then d new elements (i.e. bigger than any numbers already used in the construction) are added (with ordering corresponding to $<_{N}$ ) on the right of the block $I (n, s)$ to obtain $I (n, s + 1)$ . Lastly, if $d = 0$ , then $I (n, s + 1) = I (n, s)$ . Also at stage $s + 1$ the block $I (s, s + 1)$ is first defined. If there exists a free element x ordered relative to the existing blocks as $q_{s}$ is ordered relative to the set ${q_{m} ∣ m < s}$ then the least such x becomes the leftmost element of $I (s, s + 1)$ . Otherwise a new number x is chosen for this. Note that at no subsequent stage t does x leave $I (s, t)$ . Other new numbers (i.e. not free elements) are added to the right of the block in the appropriate way in order to obtain a block of size $f (q_{s}, s + 1)$ .

Having defined the construction we set $I (n) = {lim inf}_{s \to \infty} I (n, s)$ (under ordered set inclusion) for all $n \in N$ . Using the fact that $F (q_{n}) = {lim inf}_{s \to \infty} f (q_{n}, s)$ – and the density of $Q$ – we deduce that $I (n)$ is a maximal block in $A$ of size $F (q_{n})$ . We can also easily check that $A = N$ and that, for all distinct m, n, $I (m)$ and $I (n)$ are ordered in $A$ as $q_{m}$ and $q_{n}$ are ordered in $Q$ . Thus $A$ has order type $τ = \sum {F (q) ∣ q \in Q}$ . It is now also straightforward to check – using the fact that free elements are uniquely and permanently assigned to newly defined blocks in the way described above – that, for any distinct numbers x, y and stage s, if x and y belong to different blocks at stage s then for no stage $t ⩾ s$ will x and y belong to the same block. It thus follows that $\neg B_{A}$ is $Σ_{1}^{0}$ .

(2)⇒(1) Letting $A = ⟨ A, <_{A} ⟩$ we suppose that $a_{0}, a_{1}, \dots$ is a computable enumeration of A. We define by stages s a finite approximation $A_{s} = ⟨ A_{s}, <_{A} ⟩$ to $A$ . Note that, as $B_{A}$ is $Π_{1}^{0}$ , we are able to decide with a $0^{'}$ oracle which elements of $A_{s}$ belong to the same maximal block in $A$ .

At stage 0 of the construction we define $A_{0} = {a_{0}}$ , and the 0 stage set of labels $L_{0} = {0}$ corresponding to $q_{0}$ being assigned to the maximal block of $a_{0}$ . We define $a_{0}$ to be the delegate of this block. For all $n ⩾ 0$ we set $f (q_{n}, 0) = 1$ . At stage $s + 1$ of the construction we have already defined $A_{s} = ⟨ A_{s}, <_{A} ⟩$ with $A_{s} = {a_{0}, \dots, a_{s}}$ , and the set $L_{s}$ which labels the subset of $Q$ assigned to delegates of maximal blocks already defined in $A_{s}$ . We proceed by setting $A_{s + 1} = A_{s} \cup {a_{s + 1}}$ . If $B (a, a_{s + 1})$ holds for some delegate in $A_{s}$ and n is the label in $L_{s}$ such that $q_{n}$ is assigned to the maximal block of a, we set $f (q_{n}, s + 1) = f (q_{n}, s) + 1$ , $L_{s + 1} = L_{s}$ and reset $f (q, s + 1) = f (q, s)$ for all $q \in Q ∖ {q_{n}}$ . Otherwise, we find the least label $n \in N ∖ L_{s}$ such that $q_{n}$ is ordered under $<_{Q}$ relative to the subset of $Q$ labelled by $L_{s}$ as $a_{s + 1}$ is ordered relative to the delegates in $A_{s}$ . We assign $q_{n}$ to the maximal block of $a_{s + 1}$ , define $a_{s + 1}$ to be the delegate of this block, set $L_{s + 1} = L_{s}$ , and define $f (q, s + 1) = f (q, s)$ for all $q \in Q$ .

At the end of the construction we set $L = ⋃_{s \in N} L_{s}$ . We verify that a unique delegate is defined for each maximal block in $A$ so that $L = N$ using the fact that ordering of the maximal blocks in $A$ induced by $<_{A}$ has order type η. This means that, for every maximal block I in $A$ there is $n \in L$ such that $q_{n}$ is assigned to I. We also show that $f (q_{n}, s) ⩽ f (q_{n}, s + 1)$ for all s, and that ${lim}_{s \to \infty} f (q_{n}, s) = | I |$ . Verification is straightforward in each case. Thus by defining $F (q) = {lim}_{s \to \infty} f (q, s)$ for all $q \in Q$ we see that F is $0^{'}$ -limitwise monotonic and that $A$ has order type $\sum {F (q) ∣ q \in Q}$ . Note that F has been constructed out of $A$ in the sense of Definition 4.1. □
Note 4.4.
In Theorem 2.2 of [10] Frolov and Zubkov prove the equivalence of all of the conditions (1)–(4) (under application of Lemma 3.7 as mentioned in Note 3.8) where (3) and (4) are as follows.
There exists $Δ_{2}^{0}$ $A$ of order type τ such that $N_{A}$ and $B_{A}$ are $Δ_{2}^{0}$ .

There exists $Δ_{2}^{0}$ $A$ of order type τ such that $B_{A}$ is $Δ_{2}^{0}$ .
Notice that the implications (2) ⇒ (3) and (3) ⇒ (4) are trivial in that, for each $2 ⩽ i ⩽ 3$ , a witness $A$ of (i) is also a witness of ( $i + 1$ ).

The following observation will be useful in Section 5.
Note 4.5.
Suppose that $A = ⟨ A, <_{A} ⟩$ is an η-like linear ordering. For all $n ⩾ 1$ define $O_{A, n} \subseteq A$ to be the set of elements a such that a is the nth ( $<_{A}$ ) leftmost element in the maximal block I to which a belongs. Then, in Theorem 4.3 we can in fact replace (2) by (2 $^{}$ ) below.3
³
The author would like to thank the anonymous referee for suggesting the present form of Note 4.5 as also for several other improvements to the paper.

There exists computable $A$ of order type τ such that $B_{A}$ is $Π_{1}^{0}$ , $O_{A, 1}$ is $Σ_{1}^{0}$ and, for all $n > 1$ , $O_{A, n}$ is $Π_{1}^{0}$ .
To see this consider any $a \in A$ and let $s_{a}$ be the least stage such that $a \in A_{s_{a}}$ and m be the label such that $a \in I (m, s_{a})$ . Then $a \in O_{A, 1}$ if and only if either a* is the leftmost element in $I (m, s_{a})$ or there is a stage $s > s_{a}$ such that a becomes free, whereas for $n > 1$ , $a \in O_{A, n}$ if and only if a is the nth leftmost element in $I (m, s_{a})$ and there is no stage $s > s_{a}$ such that a becomes free.

The corollary of Theorem 4.3 – stating that, if $τ = \sum {F (q) ∣ q \in Q}$ for some $Π_{2}^{0}$ function $F : Q \to N ∖ {0}$ , then there exists computable $A$ of order type τ – was proved by Fellner in [8]. This naturally led to the question of whether “ $Δ_{3}^{0}$ ” can be replaced by “ $Π_{2}^{0}$ ” in the statement of Theorem 4.2. Note that this would give a strict characterisation of the class of η-like computable order types as those determined by a $Π_{2}^{0}$ maximal block function. Our next result answers this question in the negative.
Theorem 4.6 ([11]).

There exists an η-like computable linear ordering $A$ such that, for any $Π_{2}^{0}$ function $F : Q \to N ∖ {0}$ and η-like linear ordering $B$ such that $B$ has order type $τ = \sum {F (q) ∣ q \in Q}$ , $A ≇ B$ .

Proof.
Define $G : Q \to N ∖ {0}$ to be $g \circ Q_{N}^{- 1}$ where g is the $0^{'}$ -limitwise monotonic function given by Theorem 3.12 – when applied to the case $a = 0^{'}$ . I.e. g is such that, for any $Π_{2}^{0}$ function $f : N \to N$ , $Ran f \neq Ran g$ . (And $Q_{N} : N \to Q$ is the computable bijection stipulated on page 120.) Then by Theorem 4.3, and the fact that G is $0^{'}$ -limitwise monotonic by definition, there is an η-like computable linear ordering $A$ of order type $κ = \sum {G (q) ∣ q \in Q}$ . Suppose that $B$ is an η-like linear ordering of order type $τ = \sum {F (q) ∣ q \in Q}$ where $F : Q \to N ∖ {0}$ is $Π_{2}^{0}$ . Define $Π_{2}^{0}$ $f : N \to N ∖ {0}$ to be $f = F \circ Q_{N}$ . If $A ≅ B$ , then $Ran f = Ran g$ in contradiction with the definition of g. Hence there is no such $B$ . □

By the observation used to show that $Ran g$ is infinite at the beginning of the proof of Theorem 3.12 we see that, for all $n ⩾ 1$ , the set $E_{n} = {m ∣ g (m) = n}$ is finite. It follows that the linear ordering $A$ defined in the proof of Theorem 4.6 has no strongly η-like interval. Also, by Proposition 3.10 or Note 3.13, we can also define g to be injective so that, for all $n ⩾ 1$ , $A$ has at most one maximal block size of n.
Note 4.7.
We obtain an alternative proof4
⁴
The author is grateful to the referees of [11] for pointing this out.

to Theorem 4.6 via the work of Kach or (Kenneth) Harris. Indeed, we can assume $A$ to be either the shuffle sum of $Ran g$ derived via the proof of Proposition 2.1 of [16] or the η-representation of $Ran g$ derived via the proof of Theorem 3.3 of [13] – where, in this latter case, we use a witness g of Theorem 3.12 such that $Ran g \subseteq N ∖ {0, 1}$ . (See Note 3.13.) For the shuffle sum case we now complete the proof as above by setting $f = F \circ Q_{N}$ . In the η-representation case, choosing $k_{0} \in Ran g$ we complete the proof by setting $f = h \circ F \circ Q_{N}$ where computable $h : N \to N$ is defined by setting, for all $n \in N$ , $h (n) = \{\begin{matrix} k_{0} & if n = 1, \\ n & otherwise. \end{matrix}$
Note 4.8.
Moses proved in [25] that every computable linear ordering of dense condensation type possessing no strongly η-like interval has a computable isomorphic copy with $Π_{1}^{0}$ block relation. From this and Theorem 4.3 we know that if $A$ is a computable linear ordering satisfying (2) of Proposition 4.9 below, then there exists $0^{'}$ -limitwise monotonic $F : Q \to N ∖ {0}$ and computable $B ≅ A$ such that $B$ has order type $τ = \sum {F (q) ∣ q \in Q}$ . Note that, as mentioned in the proof of Theorem 4.3, F is constructed out of $B$ . In the proof of Proposition 4.9 we show that we can build such F out of $A$ itself. In so doing we also provide an alternative finite injury proof of Moses’s result restricted to the context of η-like computable linear orderings, as stated in Corollary 4.10.
Proposition 4.9 ([9]).

Suppose that $A$ is a computable linear ordering satisfying either of the following conditions.

$A$ is strongly η-like.

$A$ is η-like but has no strongly η-like interval.

Then there exists

0^{'}

-limitwise monotonic

F : Q \to N ∖ {0}

such that

A

has order type

τ = \sum {F (q) ∣ q \in Q}

Remark.
The proof presented below was developed independently by the author in order to establish the extent of application of Theorem 3.11 of [12]. However (1) had already been indicated by Frolov (via Corollary 1) in [9] whereas (2) follows from straightforward modification of the proof of Main Theorem 1 of [9].
Proof of Proposition 4.9.
(1) Suppose that n is an upper bound for the size of maximal blocks in $A$ . Then, for any element $a, b \in A$ , $\neg B_{A} (a, b)$ if and only if there exist n elements lying between a and b in $A$ . It follows that $B_{A}$ is $Π_{1}^{0}$ and so, by the construction proving (2) ⇒ (1) of Theorem 4.3, we prove that there exists $0^{'}$ -limitwise monotonic $F : Q \to N ∖ {0}$ such that $A$ has order type $τ = \sum {F (q) ∣ q \in Q}$ by constructing F out of $A$ .

(2) We suppose that $A = ⟨ A, <_{A} ⟩$ , where $A = N$ , and that $a_{0}, a_{1}, a_{2}, \dots$ is a computable enumeration of A.

Notation. We use the term least $a \in A$ as shorthand for “ $a_{i}$ such that i is least”.

We enumerate A by stages using oracle $\emptyset^{'} \in 0^{'}$ . At each stage s we define two finite sets $A_{s} \subseteq B_{s}$ . $B_{s}$ contains all the elements of A enumerated so far whereas $A_{s}$ contains all the elements whose s-stage adjacency block has already been assigned to some $q \in Q$ at stage s. Note that we call the s-stage adjacency block of a the maximal subset ${b_{0} <_{A} \dots <_{A} b_{k}} \subseteq B_{s}$ containing a and such that $N_{A} (b_{i}, b_{i + 1})$ for all $0 ⩽ i < k$ . We are able to determine all s-stage adjacency blocks of members of $B_{s}$ using oracle $\emptyset^{'}$ since (the adjacency relation) $N_{A}$ is $Π_{1}^{0}$ . We define at stage s the set of assigned labels $L_{s}$ . Label n is in $L_{s}$ if $q_{n}$ (or for short “n”) has already been assigned to an s-stage adjacency block in $B_{s}$ .

We also define the set of triples $G_{s}$ and the set of triples $H_{s}$ . For any label n there is a stage $s_{n}$ such that a unique triple of the form $(x, y, z)$ with $x = n$ exists in either $G_{s}$ or $H_{s}$ (where y and z may vary) at every stage $s ⩾ s_{n}$ . Roughly speaking, the presence of the triple $(n, b, m)$ (say) in $G_{s}$ indicates the construction’s guess that it will eventually assign $q_{n}$ to the adjacency block (i.e. maximal block) of b in $A$ and that the size of this block is m.

Notation. We say that b is the delegated element of the s-stage adjacency block assigned to n at stage s in the case above.

$H_{s}$ contains triples of the form $(n, - 1, m)$ . This indicates that $q_{n}$ has been de-assigned from an adjacency block in $A_{s}$ due to the absorption of this block by some other adjacency block in $A_{s}$ whose assigned label $n^{}$ was of higher priority than n (i.e. $n^{} <_{N} n$ ). $H_{s}$ is a sort of waiting area for this type of triple, the wait ending when $q_{n}$ is reassigned at a later stage s to a (new) adjacency block containing elements from $A ∖ A_{s - 1}$ . The set $P_{s}$ contains at most one pair of labels $(n, l)$ indicating that the construction is at present working uniquely over the elements of $B_{s}$ lying between the adjacency blocks labelled by n and l. We will suppose that $L_{s}$ contains two imaginary labels ${- \infty, + \infty}$ labelling imaginary rationals $q_{- \infty}$ and $q_{+ \infty}$ lying respectively to the left and to the right of all $q \in Q$ with each assigned to an imaginary adjacency block (adjacent to no element in A). Note that the use of these imaginary objects is no more than a heuristic device to simplify notation which allows us, in defining the parameter $P_{s}$ , to always work with an interval of rational numbers/labels with precisely two endpoints – although one of the endpoints may be imaginary.

Notation. In the present context we use the term adjacency block in $A$ to denote a maximal block in $A$ . However, in what follows, for the sake of simplicity, we also use this term as short hand for s-stage adjacency block.

At each stage s at most one element of A will be introduced into $B_{s}$ . There are three possibilities for such a relative to the adjacency blocks of all other elements in $B_{s}$ as follows.
a forms its own singleton adjacency block,

a is adjacent to precisely one adjacency block already present, in which case the size of that adjacency block increases by one, or

a is adjacent to two adjacency blocks – i.e. forms a bridge between the two blocks – and the resulting block has size the sum of the sizes of the two blocks that are bridged $+ 1$ .
During the construction we will usually speak about the adjacency block of a under the understanding that one of these three situations occurs.

The Construction

Stages = 0. Set $A_{0} = B_{0} = G_{0} = H_{0} = P_{0} = \emptyset$ and $L_{0} = {- \infty, + \infty}$ . Set outcome $R (0) = 0$ .

Stages + 1. There are three cases depending on the outcome $R (s)$ .

Case 1: R(s) = 0. Then find the least label $n \notin L_{s}$ , i.e. such that n has not yet been assigned. Find the least $a \in A$ such that a is not adjacent to any $b \in A_{s}$ – i.e. not adjacent to any assigned blocks – and such that a is ordered under $<_{A}$ relative to the blocks making up $A_{s}$ as $q_{n}$ is ordered relative to ${q_{i} ∣ i \in L_{s}}$ . Add the triple $(n, a, m)$ to $G_{s}$ to obtain $G_{s + 1}$ where m is the size of a’s adjacency block in $B_{s} \cup {a}$ . (Note that it may be that $a \in B_{s}$ , and that observations (i)–(iii) from above apply here.) Supposing ${b_{0}, \dots, b_{m - 1}}$ to be the elements in $B_{s} \cup {a}$ making up a’s adjacency block, set $B_{s + 1} = B_{s} \cup {a}$ and set $A_{s + 1} = A_{s} \cup {b_{0}, \dots, b_{m - 1}}$ and $L_{s + 1} = L_{s} \cup {n}$ . Set $R (s + 1) = 1$ .

Case 2: R(s) = 1. Find the least $a \notin A_{s}$ . (Note that a may already be in $B_{s}$ .) There are three subcases.

Subcase 2(i). a is not adjacent to any element of $A_{s}$ . Let m be the size of the adjacency block of a in5
⁵
Note that the adjacency block of a is in $(B_{s} ∖ A_{s}) \cup {a}$ in this and similar cases below.

$B_{s} \cup {a}$ . Find the least label n such that $q_{n}$ is ordered relative to ${q_{i} ∣ i \in L_{s}}$ as a is ordered relative to the adjacency blocks assigned to $L_{s}$ (i.e. making up $A_{s}$ ). Add the triple $(n, a, m)$ to $G_{s}$ to obtain $G_{s + 1}$ . Supposing ${b_{0}, \dots, b_{m - 1}}$ to be the elements in $B_{s} \cup {a}$ making up a’s adjacency block, set $B_{s + 1} = B_{s} \cup {a}$ and set $A_{s + 1} = A_{s} \cup {b_{0}, \dots, b_{m - 1}}$ and $L_{s + 1} = L_{s} \cup {n}$ . Set $R (s + 1) = 0$ .

Subcase 2(ii). a is adjacent to a unique assigned adjacency block (but may bridge this block with an unassigned adjacency block of elements in $B_{s} ∖ A_{s}$ ). Note that $a \notin B_{s}$ in this case. Letting n be the label of the assigned adjacency block, b the delegated element of the block at stage s, m the size of this block at stage s and p the size of the resulting block at stage $s + 1$ , obtain $G_{s + 1}$ from $G_{s}$ by removing the triple $(n, b, m)$ from $G_{s}$ and adding the triple $(n, b, p)$ to $G_{s}$ . Supposing ${b_{0}, \dots, b_{k - 1}}$ to be the elements in $B_{s} \cup {a}$ added to the block assigned to n (i.e. with $k = p - m$ ), set $B_{s + 1} = B_{s} \cup {a}$ and set $A_{s + 1} = A_{s} \cup {b_{0}, \dots, b_{k - 1}}$ and $L_{s + 1} = L_{s}$ . Set $R (s + 1) = 0$ .

Subcase 2(iii). a bridges two assigned adjacency blocks with associated triples $(n, b, m)$ and $(n^{'}, b^{'}, m^{'})$ in $G_{s}$ . Note that $a \notin B_{s}$ in this case. Supposing, without loss of generality, that $n <_{N} n^{'}$ , obtain $G_{s + 1}$ from $G_{s}$ by removing the triples $(n, b, m)$ and $(n^{'}, b^{'}, m^{'})$ from $G_{s}$ and adding the triple $(n, b, m + m^{'} + 1)$ to $G_{s}$ . Define $H_{s + 1} = {(n^{'}, - 1, m^{'})}$ and set $P_{s + 1} = {(n, l)}$ where $l \in L_{s}$ is such that $q_{n^{'}}$ is the unique element of ${q_{i} ∣ i \in L_{s}}$ positioned between $q_{n}$ and $q_{l}$ . Define $B_{s + 1} = B_{s} \cup {a}$ , $A_{s + 1} = A_{s} \cup {a}$ . Set $R (s + 1) = 2$ .

Case 3: R(s) = 2. In this case $P_{s} = {(n, l)}$ for some $n, l \in L_{s}$ (with $n \notin {- \infty, + \infty}$ ) and $H_{s}$ is a nonempty set of triples of the form $(n^{'}, - 1, m^{'})$ . Note that we can assume that, for any label $n ⩾ 0$ , $n \in L_{s}$ if and only if there is a unique triple in $G_{s} \cup H_{s}$ whose first component is n. (See the Note on page 133.)

Find the least $a \in A$ such that $a \notin B_{s}$ and such that a lies between the adjacency blocks associated with labels n and l in $B_{s}$ . There are three subcases. In each subcase we reset $L_{s + 1} = L_{s}$ .

Subcase 3(i). $n, l \in L_{s} ∖ {- \infty, + \infty}$ and a bridges the adjacency blocks assigned to n and l in $A_{s}$ . In this case, supposing that $(n^{'}, n^{″}) \in {(n, l), (l, n)}$ is such that $n^{'} <_{N} n^{″}$ and that $(n^{'}, b^{'}, m^{'})$ and $(n^{″}, b^{″}, m^{″})$ are the associated triples in $G_{s}$ , remove these two triples from $G_{s}$ and add the single triple $(n^{'}, b^{'}, m^{'} + m^{″} + 1)$ to $G_{s}$ to obtain $G_{s + 1}$ . Also add the triple $(n^{″}, - 1, m^{″})$ to $H_{s}$ to obtain $H_{s + 1}$ . Choose label $l^{'} \in L_{s}$ relative to $q_{n^{'}}$ , $q_{n^{″}}$ just as l was chosen relative to $q_{n}$ , $q_{n^{'}}$ in Subcase 2(iii) above and set $P_{s + 1} = {(n^{'}, l^{'})}$ . Set $B_{s + 1} = B_{s} \cup {a}$ , $A_{s + 1} = A_{s} \cup {a}$ and reset $R (s + 1) = 2$ .

Subcase 3(ii). a forms an adjacency block with members of $B_{s}$ such that, for each triple $(n^{'}, - 1, m^{'}) \in H_{s}$ we can now assign $n^{'}$ to an adjacency block of size $⩾ m^{'}$ in the interval of $B_{s}$ delimited by the blocks assigned to n and l in such a way that the ordering (under $<_{Q}$ ) of ${q_{n^{'}} ∣ n^{'} is the first component of a triple in H_{s}}$ is respected. ( $P_{s} = {(n, l)}$ by hypothesis.) In this case assign each such label $n^{'}$ to the appropriate adjacency block. In so doing, for each such $n^{'}$ , remove $(n^{'}, - 1, m^{'})$ from $H_{s}$ and add $(n^{'}, b^{'}, p)$ to $G_{s}$ where $p ⩾ m^{'}$ is the size of the newly chosen adjacency block assigned to $n^{'}$ and $b^{'}$ is the least element in the block. We thus obtain $G_{s + 1}$ such that $| G_{s + 1} | = | G_{s} | + | H_{s} |$ and $H_{s + 1} = \emptyset$ . Set $P_{s + 1} = \emptyset$ , $B_{s + 1} = B_{s} \cup {a}$ , and define $A_{s + 1}$ to be the union of $A_{s}$ with the set of elements belonging to all the newly assigned adjacency blocks. Set $R (s + 1) = 0$ .

Subcase 3(iii). Otherwise. If the adjacency block of a is the block assigned to $n^{'}$ for some $n^{'} \in {n, l}$ then, supposing that $(n^{'}, b^{'}, m^{'})$ is the associated triple in $G_{s}$ remove this triple from $G_{s}$ and add the triple $(n^{'}, b^{'}, p)$ to $G_{s}$ to obtain $G_{s + 1}$ – where $p > m^{'}$ is the size of the resulting adjacency block assigned to $n^{'}$ in $B_{s} \cup {a}$ . If there is no such $n^{'} \in {n, l}$ simply reset $G_{s + 1} = G_{s}$ . Set $B_{s + 1} = B_{s} \cup {a}$ and, if the adjacency block of a is assigned to some $n^{'} \in {n, l}$ (as in the case just described) then, supposing ${b_{0}, \dots, b_{k - 1}}$ to be the elements in $B_{s} \cup {a}$ added to the block assigned to $n^{'}$ (i.e. with $k = p - m^{'}$ ), define $A_{s + 1} = A_{s} \cup {b_{0}, \dots, b_{k - 1}}$ ; otherwise reset $A_{s + 1} = A_{s}$ . Reset $R (s + 1) = 2$ .

Ending substages + 1. Reset any parameters not mentioned above to the value of the parameter at stage s. Proceed to stage $s + 2$ .

Verification

Set $L = ⋃_{s ⩾ 0} L_{s}$ . We proceed via Sublemmas 1–5 below. Sublemma 1.
The set ${s ∣ R (s) = 0}$ is infinite.
Proof.
Suppose that t is a stage such that $R (s) = 2$ for all $s ⩾ t$ . Since $L_{t}$ is finite there is a stage $t^{'} ⩾ t$ such that Subcase 3(i) does not apply at any stage $s ⩾ t^{'}$ . But then, as $A$ has no strongly η like interval it follows that there is a stage $t^{″} ⩾ t^{'}$ such that Subcase 3(ii) will apply. But in this case $R (t^{″}) = 0$ contradicting our assumption. If follows that the set ${s ∣ R (s) = 0}$ is indeed infinite. □
Sublemma 2.
$L = N$ and $⋃_{s ⩾ 0} A_{s} = A$ .
Proof.
$L = N$ follows from the fact that ${s ∣ R (s) = 0}$ is infinite and $⋃_{s ⩾ 0} A_{s} = A$ follows from the fact that ${s ∣ R (s) = 1}$ is (as a consequence) also infinite. □
Note. For any label $n ⩾ 0$ , let $s_{n}$ be the least stage such that n enters $L_{s_{n}}$ and note that by definition some triple with first component n enters $G_{s_{n}}$ as a result. Then, by induction over the stages of the construction we see that, for every stage $s ⩾ s_{n}$ there is precisely one triple with first component n in $G_{s} \cup H_{s}$ .

Definition. We let $s_{n}$ be defined as in the above note. We define $\hat{F} : Q \times N \to N ∖ {0}$ such that $\hat{F} (n, s) = 1$ if $s < s_{n}$ , and $\hat{F} (n, s) = m$ where m is the third component of the unique triple contained in $G_{s} \cup H_{s}$ whose first component is n, if $s ⩾ s_{n}$ . Note that $\hat{F}$ is $0^{'}$ -computable, as the construction is computable in oracle $\emptyset^{'}$ . Sublemma 3.
Let $n ⩾ 0$ . There exists a stage $t_{n} ⩾ s_{n}$ such that, for all $s ⩾ t_{n}$ , there is no triple in $H_{s}$ with first component n (so there is a unique triple with first component n in $G_{s}$ ) .
Proof.
Assume as inductive hypothesis that there is a stage $u_{n} ⩾ s_{n}$ such that, for all $i < n$ there is a unique triple with first component i contained in $G_{s}$ (and so not in $H_{s}$ ) for every $s ⩾ u_{n}$ . Under this assumption we can now suppose that there exists a stage ${\hat{t}}_{n} ⩾ u_{n}$ such that there exists, for each $i < n$ , a unique triple $(i, b, m) \in G_{{\hat{t}}_{n}}$ such that $(i, b, m) \in G_{s}$ for all $s ⩾ {\hat{t}}_{n}$ . Indeed, our assumption tells us that there is a unique triple of the form $(i, b, m)$ in $G_{s}$ for all $s ⩾ u_{n}$ where we see that, even though m may vary, the delegate b remains fixed. However at a certain stage $s_{i} ⩾ u_{n}$ in the construction the whole of the adjacency block for b will have been enumerated into $A_{s_{i}}$ and so by definition, the value of m will remain fixed at every stage $s ⩾ s_{i}$ . Since this applies to all $i < n$ under our assumption we deduce the existence of stage ${\hat{t}}_{n}$ as defined above. Let $t_{n} > {\hat{t}}_{n}$ be a stage such that $R (t_{n}) = 0$ . Then $H_{t_{n}} = \emptyset$ by construction and so there is a unique triple in $(n, b^{'}, m^{'}) \in G_{t_{n}}$ (i.e. with first component n). Also, as $t_{n} > {\hat{t}}_{n}$ we see that for any given $s ⩾ t_{n}$ there is no triple in $H_{s}$ with first component n and that accordingly there is a unique triple $(n, b^{'}, m_{s}) \in G_{s}$ for some $m_{s} ⩾ m^{'}$ . □
Sublemma 4.
Let $n ⩾ 0$ . There exists a stage $v_{n}$ such that, for some fixed $b \in A$ and $m ⩾ 1$ there is a unique triple $(n, b, m) \in G_{s}$ for all $s ⩾ v_{n}$ where b is an element of the adjacency block assigned to label n and m is the size of this adjacency block in $A$ .
Proof.
This follows from Sublemma 3 in conjunction with the reasoning applied to the indices $i < n$ in the proof of Sublemma 3 now applied to the present index n. □
Definition. Define $F : Q \to N ∖ {0}$ by setting $F (q) = {lim}_{s \to \infty} \hat{F} (q, s)$ . Sublemma 5.
For every $n ⩾ 0$ , and all $s ⩾ 0$ , $\hat{F} (q_{n}, s) ⩽ \hat{F} (q_{n}, s + 1)$ and $F (q_{n})$ is defined. Thus F is $0^{'}$ -limitwise monotonic. Moreover $A$ has order type $\sum {F (q) ∣ q \in Q}$ .
Proof.
Given any $n ⩾ 0$ clearly $\hat{F} (q_{n}, s) ⩽ \hat{F} (q_{n}, s + 1)$ for all $s ⩾ 0$ by construction. By Sublemma 4 we see that $F (q_{n}) = {lim}_{s \to \infty} \hat{F} (q_{n}, s)$ is defined.

Choose $a \in A$ . Let $s_{a}$ be the stage at which a enters $A_{s_{a}}$ , i.e. when the adjacency block of a is first assigned to some label n. Then by construction the adjacency block of a is assigned to some label m for all stages $s ⩾ s_{a}$ . Moreover $m ⩽_{N} n$ since, if at some stage $s ⩾ s_{a}$ , the adjacency block of a is assigned to some label p and this block is reassigned to some label r at stage $s + 1$ , then $r <_{N} p$ . This also means that there is some stage $t_{a} ⩾ s_{a}$ and fixed label $\hat{m} ⩽_{N} n$ such that the adjacency block of a remains assigned to $\hat{m}$ for all stage $s ⩾ t_{a}$ .

On the other hand, by Sublemma 3 and Sublemma 4, we see that, for all labels $n ⩾ 0$ , some unique triple $(n, b, m)$ eventually enters $G_{s}$ permanently where b is a member of the adjacency block assigned to n and m is the size of this adjacency block in $A$ .

From these observations, and bearing in mind that every label n corresponds to $q_{n}$ in our listing $q_{0}, q_{1}, q_{2}, \dots$ of $Q$ , we see that the adjacency block of every $a \in A$ is in effect eventually assigned to a fixed $q \in Q$ and that every $q \in Q$ is eventually assigned to a fixed adjacency block in $A$ such that $F (q)$ is the size of this block. It thus follows that $\sum {F (q) ∣ q \in Q}$ is indeed the order type of $A$ . □

This concludes the proof of Proposition 4.9. □
Corollary 4.10 ([9, 25]).

Suppose that $A$ is an η-like computable linear ordering with no strongly η-like interval. Then there exists computable $L ≅ A$ such that (the block relation of $L$ ) $B_{L}$ is $Π_{1}^{0}$ .

Proof.
By Proposition 4.9(2) we know that there exists $0^{'}$ -limitwise monotonic $F : Q \to N ∖ {0}$ such that $A$ has order type $τ = \sum {F (q) ∣ q \in Q}$ . We thus obtain computable $L ≅ A$ such that $B_{L}$ is $Π_{1}^{0}$ by application of Theorem 4.3. □

Rosenstein ([28], Theorem 10.48) noted that every computable linear ordering $L$ of order type $τ = 2 \cdot η$ has a computable nontrivial self-embedding. A straightforward extension of Rosenstein’s argument shows that any order type τ has this property if it contains a strongly η-like interval. This led to the question of whether this latter condition is also necessary in the following sense.
Conjecture 1 ([6]).

Let $L$ be an infinite computable linear ordering which has no strongly η-like interval. Then there is a computable linear ordering $B ≅ L$ which has no computable nontrivial self-embedding.

Downey et al. ([6], Main Theorem) proved Conjecture 1 for the case when the order type τ of $L$ is η-like and Moses extended this result to τ of dense condensation type. To do this Moses proved the following.

The statement of Corollary 4.10 for the more general case when $A$ has dense condensation type ([25], Theorem 1).

If $A$ is an infinite computable linear ordering with no strongly η-like interval such that there exists computable $L ≅ A$ with the property that $B_{L}$ is $Π_{1}^{0}$ , then there exist computable $B ≅ A$ such that $B$ has no computable nontrivial self-embedding ([25], Corollary 3).

Readjusting (i) and (ii) to the present context we can extrapolate that Proposition 4.9(2) used in conjunction with Theorem 4.3 and (ii) provides us with sufficient tools to verify the Main Theorem of [6].

5. On $Δ_{n}^{0}$ categoricity of η-like computable linear orderings

In this concluding section we briefly consider η-like computable linear orderings with regard to categoricity at low levels of the Arithmetical Hierarchy.

Definition 5.1.

For $n ⩾ 0$ , we say that computable linear ordering $A$ is $Δ_{n}^{0}$ categorical if, for any computable $B ≅ A$ there exists a $Δ_{n}^{0}$ function G witnessing this isomorphism.

Lempp et al. [22] proved that, for every $n ⩾ 1$ there is a computable tree of finite height which is $Δ_{n + 1}^{0}$ -categorical but not $Δ_{n}^{0}$ -categorical. The question that we address here is that of how we obtain this sort of result – for small n at least – in the context of η-like computable linear orderings.

Definition 5.2.

Given a linear ordering $A = ⟨ A, <_{A} ⟩$ we say that $S \subseteq A$ is a choice set of $A$ if, for each maximal block I in $A$ , $| I \cap S | = 1$ .

Lerman and Rosenstein [23] proved the existence of a computable linear ordering $L$ of order type $(ω^{*} + ω) \cdot τ$ , with $τ = η$ , such that no choice set of $L$ has an infinite $Σ_{2}^{0}$ subset (so that $A$ has no $Σ_{2}^{0}$ dense subset) and Downey and Moses [7] extended this result to the general case when τ can be any order type. We prove and use a similar result in the setting of η-like linear orderings in order to show the existence of an η-like linear ordering that is not $Δ_{2}^{0}$ categorical (but is $Δ_{3}^{0}$ categorical).

Proposition 5.3.

There exists an η-like computable linear ordering $L$ satisfying the following conditions.

For all $n ⩾ 1$ the set of maximal blocks in $L$ of size n – written $S_{L, n}$ – is finite, and the set $M_{L} = {⟨ n, | S_{L, n} | ⟩ ∣ n ⩾ 1}$ is $Δ_{3}^{0}$ .

No choice set of $L$ has an infinite $Σ_{2}^{0}$ subset.

Proof.

Let ${V_{e}}_{e \in N}$ be a listing of the $Σ_{2}^{0}$ sets with associated (effective) $Σ_{2}^{0}$ approximation ${V_{e, s}}_{e, s \in N}$ . (I.e. $V_{e} = {n ∣ \exists t (\forall s ⩾ t) [n \in V_{e, s}]}$ for all $e ⩾ 0$ .) We define $L = ⟨ L, <_{L} ⟩$ via a computable construction by stages with $L = N$ (and $L_{s}$ an initial segment of $N$ ) such that, for all $e ⩾ 0$ , the requirement $\begin{array}{l} R_{e} : V_{e} infinite \Rightarrow there exists a maximal block I of L such that | I \cap V_{e} | ⩾ 2, \end{array}$ is satisfied. For the construction of $L$ we define a computable listing of finite linear orderings ${b_{i}}_{i \in N}$ which we call basic blocks, such that6

⁶

Defining ${b_{i}}_{i \in N}$ in this way has the nice property that the set $O_{L, 1}$ – as defined in Note 4.5 – is a choice set of $L$ . However we could also, for example, work with ${b_{i}}_{i \in N}$ such that $| b_{i} | = i + 1$ for all $i ⩾ 0$ .

| b_{i} | = i + 2

for all

i ⩾ 0

and

N = ⋃_{i \in N} b_{i}

and we assume (for simplicity) that

<_{N}

dictates the ordering of each block. All elements in L are enumerated via the basic blocks in this listing. Basic blocks are never broken up but may be joined with other basic blocks to form a maximal block in

L

. Moreover the ordering in each basic block is inherited by

L

. (The obvious listing for us to use thus results in

b_{0} = {0 <_{L} 1}

b_{1} = {2 <_{L} 3 <_{L} 4}

, etc.) Note that we call i the label of

b_{i}

We use a strategy tree construction in $B = 2^{< N}$ in which all strategies/nodes of length e work for the satisfaction of requirement $R_{e}$ . At stage $s + 1$ we define a path $α_{s + 1}$ through the tree subsuming $s + 1$ strategies with each such strategy being processed in order as the path descends down from the root of the tree. We also define finite $T_{s + 1} \subseteq B$ . Assuming $L_{0} = T_{0} = \emptyset$ and the two parameters introduced below to be undefined at stage 0, we now outline stage $s + 1$ via the manner in which each strategy is processed. We proceed under the assumption that7

⁷

We use the shorthand $<_{L}$ for the ordering of $L_{s}$ – written formally as $<_{L}^{s}$ – since, for any $a, b \in L_{s}$ such that $a <_{L}^{s} b$ , for all $t ⩾ s$ , $a <_{L}^{t} b$ . (This property is essential for $L$ to be computable.)

L_{s} = ⟨ L_{s}, <_{L} ⟩

is defined such that

L_{s} = ⋃_{i < i_{s}} b_{i}

with

i_{s} ⩾ s

(and

i_{0} = 0

by definition).

Note. We use the standard ordering over $B$ : for any strategies $α, β \in B$ we define $α ⩽ β$ if and only if $α \subseteq β$ or $α <_{lex} β$ .

Action of $α \subset α_{s + 1}$ . Suppose that $| α | = e$ . α has two parameters, a special pair $p (α, s)$ and a block parameter $b (α, s)$ . Note that, if $b (α, s)$ is defined we say that it is the s-stage combined block defined by α and we say that αrestrains the basic blocks contained in $b (α, s)$ . We also say that any basic block not restrained by any strategy α at stage s is s-stage free. For any $m, n \in N$ and stage s, such that $m, n \in L_{s}$ let $c (m, n, s)$ denote the block made up of the basic blocks containing m and n and all the basic blocks lying in between the latter in $L_{s}$ . (Note that $c (m, n, s)$ may be a single basic block.) We say that the pair $p = (m, n)$ requires attention at stage $s + 1$ if all of the following conditions hold.

${m, n} \subseteq V_{e, s}$ .

For any label i such that $b_{i} \subseteq c (m, n, s)$ , $i > e$ (so that $| b_{i} | > e$ ).

$c (m, n, s) \cap b (γ, s) = \emptyset$ for all $γ < α$ .

There are several cases as follows.

Case 1. No pair requires attention. Then α does nothing and declares $α \hat{} ⟨ 0 ⟩$ to be eligible to act next.

Case 2. Otherwise. α chooses a pair $p = (m, n)$ requiring attention such that ${m, n}$ has been in the approximation ${V_{e, t}}_{t ⩽ s}$ for longest. I.e. letting $t_{p}$ denote, for any such pair p, the last stage t at which ${m, n} ⊈ V_{t}$ , it is a pair p such that $t_{p}$ is least, which is chosen. If there is more than one such pair α chooses the least such p under the coding $⟨ \cdot, \cdot ⟩$ .

Case 2.1. $p (α, s)$ is defined and $p \neq p (α, s)$ . Then α sets both $p (α, s + 1)$ and $b (α, s + 1)$ to undefined and declares $α \hat{} ⟨ 0 ⟩$ to be eligible to act next.

Case 2.2. $p (α, s)$ is defined and $p = p (α, s)$ . Then α resets $p (α, s + 1) = p (α, s)$ and $b (α, s + 1) = b (α, s)$ and declares $α \hat{} ⟨ 1 ⟩$ to be eligible to act next.

Remark. In the last case below $p (α, s)$ is not defined.

Case 2.3. Otherwise. α defines $b (α, s + 1)$ to be the block made up of $c (m, n, s)$ combined with the set of blocks ${b (γ, s) ∣ α \hat{} ⟨ 0 ⟩ \subseteq γ & b (γ, s) \cap c (m, n, s) \neq \emptyset}$ . α sets $p (α, s + 1) = p$ and declares $α \hat{} ⟨ 1 ⟩$ to be eligible to act next.

Completing stage $s + 1$ . Having completed the above action, if $| α | < s$ , supposing that $β = α \hat{} ⟨ i ⟩$ was declared by α to be eligible to act next, the construction proceeds by processing β. Otherwise (i.e. if $| α | = s$ ) the construction sets $α_{s + 1} = β$ , defines $T_{s + 1} = {γ ∣ γ \subset α_{s + 1}} \cup {γ ∣ γ <_{lex} α_{s + 1} & γ \in T_{s}}$ , and reinitialises all $α <_{lex} γ$ . In other words the parameters $p (γ, s + 1)$ and $b (γ, s + 1)$ are set to undefined. (Note that any such γ is now considered to be in its initial state and that $T_{s + 1}$ contains precisely those strategies that are not in their initial state.) Any other parameters not so far mentioned are reset to their s-stage value. If $b (γ, s)$ was defined, and $b (γ, s + 1)$ is undefined (via Case 2.1 or reinitialisation) then any basic block $b_{i}$ contained in $b (γ, s)$ and not restrained by any other strategy $β < α_{s + 1}$ becomes $s + 1$ -stage free.

Note. For any γ and stage $t ⩽ s + 1$ , if $b (γ, t)$ is defined then $γ \hat{} ⟨ 1 ⟩ \in T_{t}$ . Also, for any $γ, β \in T_{t}$ , if $b (γ, t) \cap b (β, t) \neq \emptyset$ , then either $β \hat{} ⟨ 0 ⟩ \subseteq γ$ and $b (γ, t) \subseteq b (β, t)$ or otherwise $γ \hat{} ⟨ 0 ⟩ \subseteq β$ and $b (β, t) \subseteq b (γ, t)$ . These facts can be proved by induction over t relative to the definition of the tree $T_{t}$ .

With the above in mind, we say, for any strategy γ such that $γ \hat{} ⟨ 1 ⟩ \in T_{s + 1}$ , that $b (γ, s + 1)$ is an $s + 1$ -stage maximal combined block if for any $β \neq γ$ such that $b (β, s + 1) \cap b (γ, s + 1) \neq \emptyset$ , $γ \hat{} ⟨ 0 ⟩ \subseteq β$ . Clearly, by the above note, for every β such that $β \hat{} ⟨ 1 ⟩ \in T_{s + 1}$ there exists $γ \in T_{s + 1}$ such that $b (γ, s + 1)$ is an $s + 1$ -stage maximal block and $b (β, s + 1) \subseteq b (γ, s + 1)$ . Let $B_{s + 1}$ be the union of the sets of $s + 1$ -stage maximal combined blocks and free blocks. To end the stage, the construction now densifies $B_{s + 1}$ by inserting the set of $| B_{s + 1} | + 1$ new basic blocks ${b_{i_{s}}, \dots, b_{i_{s} + | B_{s + 1} |}}$ (which we also refer to as $s + 1$ -stage free blocks) so that between every new $b_{j}$ , $b_{k}$ there exists at least one member8

⁸

Thus, as by definitions $B_{1} = \emptyset$ , at stage 1 of the construction only $b_{0}$ (of size 2) is enumerated into $L$ during densification (so that $i_{1} = 1$ ).

B_{s + 1}

L_{s + 1}

is defined to be the resulting configuration of

2 \times | B_{s + 1} | + 1

blocks (which we call

s + 1

-stage maximal blocks). Note that by definition

i_{s + 1}

is set to be

i_{s} + | B_{s + 1} | + 1

Verification sketch. It is clear that the linear ordering $L = ⟨ L, <_{L} ⟩$ resulting from this construction – i.e. such that $L = ⋃_{s ⩾ 0} L_{s}$ – is computable. Let δ be the true path of the construction, i.e. letting $δ_{e} = δ ↾ e$ and $J_{γ} = {s ∣ γ \subset α_{s}}$ , δ is such that $J_{δ_{e}}$ is infinite and for all γ such that $| γ | = e$ and $γ <_{lex} δ_{e}$ , $J_{γ}$ is finite. Define $T = {γ ∣ \exists t (\forall s ⩾ t) [γ \in T_{s}]}$ (and note that $δ_{e}$ is the rightmost strategy in $T$ for all $e ⩾ 0$ ). By inspection we see that, for every strategy β such that $β \hat{} ⟨ 1 ⟩ \in T$ , there exists a stage $s_{β}$ such that, for all $s ⩾ s_{β}$ , $b (β, s_{β})$ is defined and $b (β, s) = b (β, s_{β})$ for all $s ⩾ s_{β}$ . We define $b (β) = {lim}_{s \to \infty} b (β, s)$ for any such β. Also, from the note above it follows easily that, for any other γ such that $b (γ) \cap b (β)$ , either $β \hat{} ⟨ 0 ⟩ \subseteq γ$ and $b (γ) \subseteq b (β)$ or vice versa. Accordingly we say, for any strategy γ such that $γ \hat{} ⟨ 1 ⟩ \in T$ , that $b (γ)$ is a maximal combined block if for any $β \neq γ$ such that $b (β) \cap b (γ) \neq \emptyset$ , $γ \hat{} ⟨ 0 ⟩ \subseteq β$ . Thus if $b (γ)$ is a maximal combined block, then for any $b (β)$ such that $b (β) \cap b (γ)$ we know that $b (β) \subseteq b (γ)$ . Moreover we see that, for every β such that $b (β)$ is defined, $b (β) \subseteq b (γ)$ for some maximal combined block $b (γ)$ and also that, for any α such that $α \hat{} ⟨ 1 ⟩ \subseteq δ$ , $b (α)$ is a maximal combined block. On the other hand, if $γ \hat{} ⟨ 1 ⟩ \notin T$ , then $b (γ, s)$ is undefined at infinitely many stages s.

Consider – using $δ_{i}$ to denote $δ ↾ i$ as above – any basic block $b_{i}$ and note that by construction, for any γ and s such that $b_{i} \subseteq b (γ, s)$ , $| γ | < i$ so that, if $b_{i} \subseteq b (γ)$ , $γ < δ_{i}$ . Suppose that $b_{i} ⊈ b (γ)$ for any such γ and let $s_{i}$ be such that $δ_{i} ⩽ α_{s}$ for all $s ⩾ s_{i}$ . Then at every stage $s ⩾ s_{i}$ such that $δ_{i} \subseteq α_{s}$ , $b_{i}$ is s-stage free. Set $b_{i}^{*} = b_{i}$ in this case. If, on the other hand, $b_{i} \subseteq b (γ)$ for some γ, set $b_{i}^{*} = b (γ)$ for the one such strategy γ for which $b (γ)$ is maximal. Note that $b (γ, t) = b (γ)$ for all $t ⩾ s_{i}$ in this case. Let $t ⩾ s_{i}$ and basic block $b_{j}$ be such that $b_{j}$ is adjacent to $b_{i}^{*}$ at stage t. Let $s^{*} > t$ be a stage s such that $δ_{i} \subseteq α_{s}$ . Then, at stage $s^{*}$ a basic block is inserted between $b_{i}^{*}$ and $b_{j}$ . Thus $b_{i}^{*}$ is a maximal block in $L$ . Moreover, as for each $k ⩾ 0$ , $b_{k}^{*} \supseteq b_{k}$ is defined we see that each maximal block in $L$ is of the form $b_{k}^{*}$ for some label9

⁹

Of course $b_{k}^{*} = b_{l}^{*}$ for every basic block $b_{l} \subseteq b_{k}^{*}$ .

k. It follows therefore that

L

is η-like.

Clearly by construction the set $S_{L, n}$ of maximal blocks of size n is finite for all $n ⩾ 1$ . Define $H = {⟨ α, s, n ⟩ ∣ α \subseteq α_{s} & | α | = n & P (α, s) & R (α, s)},$ where $P (α, s) = (\forall t ⩾ s) [α ⩽ α_{s}]$ and $R (α, s) = \forall t (\exists s ⩾ t) [α \subseteq α_{s}]$ . Then H is $Π_{2}^{0}$ . So for any $n ⩾ 2$ , the search to find the least $\hat{m} = ⟨ α, s, p ⟩ \in H$ such that $p = n$ is computable using oracle $\emptyset^{″} \in 0^{″}$ . Note that by definition, $α = δ_{n}$ . Now, as $| b_{i} | > i$ for all $i ⩾ 0$ , it follows from the argument in the last paragraph that I is a maximal block of $L$ of size n, if and only if at stage s either (i) $I = b (γ, s) = b (γ)$ for some $γ < α$ or (ii) I is an s-stage free block. Hence, using $\hat{m}$ we can determine the set $S_{L, n}$ of maximal blocks of size n in $L$ and thus compute its cardinality $| S_{L, n} |$ .

Suppose that $e ⩾ 0$ and let $α = δ_{e}$ . If $V_{e}$ is finite then $R_{e}$ is trivially satisfied. If, on the other hand, $V_{e}$ is infinite then, at every large enough α-true stage s strategy α will pick the same pair $p = (m, n)$ via Case 2.2, after a final application of Case 2.3. Thus the activity of α will eventually stabilise with the outcome that $α \hat{} ⟨ 1 ⟩ \subseteq δ$ and ${n, m}$ is contained in the maximal combined block $b (α)$ . Thus $R_{e}$ is also satisfied in this case. □

Note 5.4.

Suppose that $B$ is an η-like computable linear ordering with a strongly η-like interval. Then we can find maximal blocks $I_{a}$ and $I_{b}$ in this interval and some $n ⩾ 1$ such that, between $I_{a}$ and $I_{b}$ , there exist infinitely many maximal blocks of size n and, for all $m > n$ , no maximal blocks of size m. Let C denote the union of this set of maximal blocks. Then, if $n = 1$ , C is an infinite computable subset of any choice set of $B$ . If on the other hand $n > 1$ then, for each $1 ⩽ k ⩽ n$ , $O_{A, k} \cap C$ is an infinite $Σ_{2}^{0}$ subset of a choice set of $B$ . (See Note 4.5 for the definition of $O_{A, k}$ .) Hence, any $L$ satisfying the statement of Proposition 5.3 contains no strongly η-like interval, whether or not condition (a) holds.

Theorem 5.5.

For $1 ⩽ n ⩽ 2$ , there exists an η-like computable linear ordering $A_{n}$ such that $A_{n}$ is $Δ_{n + 1}^{0}$ categorical but not $Δ_{n}^{0}$ categorical.

Proof.

Case $n = 1$ (Folklore). Note firstly that every computable linear ordering $A_{1} = ⟨ A_{1}, <_{A} ⟩$ of order type $k \cdot η$ , for some $k ⩾ 2$ , is $Δ_{2}^{0}$ categorical (and $Δ_{1}^{0}$ categorical for $k = 1$ ). Indeed, for $a \in A_{1}$ the maximal block containing a can be constructed using oracle $\emptyset^{'} \in 0^{'}$ (given that we know its size). Thus for any computable $B ≅ A_{1}$ we can construct a $Δ_{2}^{0}$ isomorphism witnessing this by using a back and forth argument using oracle $\emptyset^{'}$ .

Remark. The above is also a corollary of Theorem 2.6 of [24].

On the other hand, for $k > 1$ it follows from Theorem 1 of [27] that $A_{1}$ is not $Δ_{1}^{0}$ categorical since it contains an infinite set of adjacent elements.

Case $n = 2$ . Consider firstly any η-like computable $L$ satisfying condition (a) of Proposition 5.3. Then, supposing that computable $B$ is such that $L ≅ B$ , we can construct $G ⩽_{T} \emptyset^{″}$ witnessing this isomorphism in stages as follows. At each stage $n ⩾ 1$ , we find m such that $⟨ n, m ⟩ \in M_{L}$ . Equipped with m (i.e. the cardinality of $S_{L, n}$ ) we then compute the sets $S_{L, n}$ and $S_{B, n}$ of maximal blocks in $L$ and $B$ respectively by performing an exhaustive search10

¹⁰

We are using the fact that, for any element a in $L$ or $B$ , the maximal block containing a can be constructed computably in $\emptyset^{″}$ .

inside each ordering. We then construct G over

S_{L, n}

so that

⋃ S_{L, n}

is mapped order isomorphically onto

⋃ S_{B, n}

and proceed to stage

n + 1

. It then follows by definition that G is a

Δ_{3}^{0}

isomorphism witnessing

L ≅ B

Now, letting $A_{2}$ be the computable linear ordering constructed in the proof of Proposition 5.3, we know by the above argument that $A_{2}$ is $Δ_{3}^{0}$ categorical. Suppose that $A ≅ A_{2}$ is the computable ordering constructed relative to the order type of $A_{2}$ in the proof of (1) ⇒ (2) of Theorem 4.3. Notice that the set $O_{A, 1}$ – as defined in Note 4.5 – is a $Σ_{2}^{0}$ (and in fact $Σ_{1}^{0}$ ) choice set for $A$ . ( $O_{A, 1}$ contains the leftmost element in every maximal block in $A$ .) Suppose that $G : A ≅ A_{2}$ is a $Δ_{2}^{0}$ isomorphism. Then $G (O_{A, 1})$ is a $Σ_{2}^{0}$ choice set in $A_{2}$ . Hence there is no such G. □

We note finally that if $L$ is any η-like computable linear ordering such that, for all $n ⩾ 1$ , $L$ has at most finitely many maximal blocks of size n, then $L$ is $Δ_{4}^{0}$ categorical. This is because, given computable $B = ⟨ B, <_{B} ⟩$ such that $B ≅ L$ , for any $b \in B$ the question of whether the maximal block containing b has size n is $Δ_{3}^{0}$ , so that the query as to whether there exists such $b \in B$ is $Σ_{3}^{0}$ . Thus for each $n ⩾ 1$ we can decide whether there exist any maximal blocks in $B$ of size n and, if so, perform an exhaustive search to find all such blocks using a $0^{(3)}$ oracle.

References

[1]

Calvert,

Cenzer,

Harizanov and

Morozov, Effective categoricity of equivalence structures, Annals of Pure and Applied Logic 141(1,2) (2006), 61–78.

[2]

R.J.

Coles,

Downey and

Khoussainov, On initial segments of computable linear orders, Order 14 (1997), 107–124.

[3]

S.B.

Cooper, Computability Theory, CRC Mathematics Series, Chapman and Hall, London, 2004.

[4]

Downey, Computability theory and linear orderings, in: Handbook of Recursive Mathematics, Vol.2: Recursive Algebra, Analysis and Combinatorics, Studies in Logic and the Foundations of Mathematics,

Y.L.

Ershov,

S.S.

Goncharov,

Nerode and

J.B.

Remmel, eds, North Holland, 1998, pp. 823–976.

[5]

R.G.

Downey,

A.M.

Kach and

Turetsky, Limitwise monotonic functions and their applications, in: Proceedings of the 11th Asian Logic Conference,

Arai,

Feng,

Kim,

Wu and

Yang, eds, World Sci. Publ., Hackensack, NJ, 2012, pp. 59–85.

[6]

R.G.

Downey,

Kastermans and

Lempp, On computable self-embeddings of computable linear orderings, Journal of Symbolic Logic 74(4) (2009), 1352–1366.

[7]

R.G.

Downey and

M.F.

Moses, On choice sets and strongly non-trivial self-embeddings of recursive linear orders, Zeitshrift Math. Logik Grundlagen Math. 35 (1989), 237–246.

[8]

Fellner, Recursiveness and finite axiomatizability of linear orderings, PhD thesis, Rutgers University, New Brunswick, New Jersey, 1976.

[9]

A.N.

Frolov, Low linear orderings, Journal of Logic and Computation 22(4) (2012), 745–754.

10.

[10]

A.N.

Frolov and

M.V.

Zubkov, Increasing η-representable degrees, Mathematical Logic Quarterly 55(6) (2009), 633–636.

11.

[11]

C.M.

Harris, On maximal block functions of computable η-like linear orderings, in: Language, Life, Limits: 10th Conference on Computablitiy in Europe, CiE 2014, Budapest,

Beckmann,

Csuhaj-Varjú and

Meer, eds, Lecture Notes in Computer Science, Vol. 8493, Springer, 2014, pp. 214–223.

12.

[12]

C.M.

Harris,

K.I.

Lee and

S.B.

Cooper, Automorphisms of η-like computable linear orderings, Mathematical Logic Quarterly (2015), to appear.

13.

[13]

Harris, η-representations of sets and degrees, Journal of Symbolic Logic 73(4) (2008), 1097–1121.

14.

[14]

Hirschfeldt,

Miller and

Podzorov, Order-computable sets, Notre Dame Journal of Formal Logic 48(3) (2007), 317–347.

15.

[15]

D.R.

Hirschfeldt, Prime models of theories of computable linear orderings, Proceedings of the American Mathematical Society 129(10) (2001), 3079–3083.

16.

[16]

A.M.

Kach, Computable shuffle sums of ordinals, Archive for Mathematical Logic 47(3) (2008), 211–219.

17.

[17]

N.G.

Khisamiev, Criterion for constructivizability of a direct sum of cyclic p-groups, Izv. Akad. Nauk Kazakh. SSR Ser. Fiz.-Mat. 1 (1981), 51–55, 86.

18.

[18]

N.G.

Khisamiev, The arithmetical hierarchy of abelian groups, Sibirsk. Mat. Zh. 29(6) (1988), 144–159.

19.

[19]

N.G.

Khisamiev, Constructive abelian groups, in: Handbook of Recursive Mathematics Vol. 2: Recursive Algebra, Analysis and Combinatorics, Studies in Logic and the Foundations of Mathematics,

Y.L.

Ershov,

S.S.

Goncharov,

Nerode and

J.B.

Remmel, eds, North Holland, 1998, pp. 1177–1231.

20.

[20]

Khoussainov,

Nies and

R.A.

Shore, Computable models of theories with few models, Notre Dame Journal of Formal Logic 38(2) (1997), 165–178.

21.

[21]

H.A.

Kierstead, On

Π_{1}

-automorphisms of recursive linear orders, Journal of Symbolic Logic 52 (1987), 681–688.

22.

[22]

Lempp,

McCoy,

Miller and

Solomon, Computable categoricity of trees of finite height, Journal of Symbolic Logic 70 (2005), 152–215.

23.

[23]

Lerman and

J.G.

Rosenstein, Recursive linear orderings, in: Patras Logic Symposium (Proc. Logic Sympos. Patras, Greece, Aug. 18–22, 1980),

Metakides, ed., Studies in Logic and the Foundations of Mathematics, Vol. 109, Elsevier Science B.V., 1982, pp. 123–136.

24.

[24]

C.F.D.

McCoy,

Δ_{2}^{0}

-categoricity in boolean algebras and linear orderings, Annals of Pure and Applied Logic 119 (2003), 85–120.

25.

[25]

Moses, The block relation in computable linear orders, Notre Dame Journal of Formal Logic 52(3) (2011), 289–306.

26.

[26]

P.G.

Odifreddi, Classical Recursion Theory, Elsevier Science B.V., Amsterdam, 1989.

27.

[27]

J.B.

Remmel, Recursively categorical linear orderings, Proceedings of the American Mathematical Society 83 (1981), 387–391.

28.

[28]

J.G.

Rosenstein, Linear Orderings, Pure and Applied Mathematics, Vol. 98, Academic Press, 1982.

29.

[29]

R.I.

Soare, Recursively Enumerable Sets and Degrees, Springer Verlag, Berlin, 1987.

On limitwise monotonicity and maximal block functions

Abstract

Keywords

1. Introduction

1 L is an η-representation of A = { a 0 , a 1 , a 2 , … } ⊆ N ∖ { 0 , 1 } if L is computable and has order type η + a f ( 0 ) + η + a f ( 1 ) + η + a f ( 2 ) + η + ⋯ for some surjective f : N → N .

5. On Δ n 0 categoricity of η-like computable linear orderings

References

¹
$L$ is an η-representation of $A = {a_{0}, a_{1}, a_{2}, \dots} \subseteq N ∖ {0, 1}$ if $L$ is computable and has order type $η + a_{f (0)} + η + a_{f (1)} + η + a_{f (2)} + η + \dots$ for some surjective $f : N \to N$ .

5. On $Δ_{n}^{0}$ categoricity of η-like computable linear orderings