Linearisations and the Ershov hierarchy

Abstract

A partial order is computably well founded if it does not computably embed a copy of $ω^{*}$ , the order type of the negative integers. It is computably scattered if it does not computably embed a copy of η, the order type of $Q$ . It is known that, for each of these properties, there are computable partial orders satisfying the property which do not have a computable linear extension with the same property. Rosenstein showed, however, that for both of these properties, every computable partial order satisfying the property has a $Δ_{2}^{0}$ linear extension also satisfying the property. Thus, linear extensions of a computable order preserving the properties of computable well foundedness or computable scatteredness can always be found at the $Δ_{2}^{0}$ level of the arithmetical hierarchy, but not at the $Δ_{1}^{0}$ level. In this paper, we investigate at which level of the Ershov hierarchy such linear extensions can be found. We show that, for both properties, every computable partial order satisfying the property has an ω-c.e. linear extension with the same property. We establish that this is the best possible result within the Ershov hierarchy by constructing, respectively, computably well founded and computably scattered orders which do not have n-c.e. linear extensions which are computably well founded and computably scattered respectively, for any $n < ω$ . In a strengthening of Rosenstein’s theorems in another direction, we show that a linear extension preserving each of these properties can be computed using any oracle satisfying an escape property, which includes the class of non-generalised low₂ sets. Finally, we show that the analogue of Rosenstein’s theorems do not hold for the property of not computably embedding a copy of ζ, the order type of the integers, by constructing a computable partial ordering which does not embed ζ, but such that every $Δ_{2}^{0}$ linear extension of the ordering does admit a computable embedding of ζ.

Keywords

Computable partial order linear extension well founded scattered Ershov hierarchy arithmetical hierarchy

1. Dedication

This paper is dedicated to the memory of S. Barry Cooper. Barry was a valued teacher, colleague and friend to us all. We all completed our PhD theses under Barry’s supervison, and our subsequent careers bear the hallmarks of his influence. We each benefited greatly from his enthusiasm and generosity. Barry was a purveyor of ideas who, despite the enormous demands on his time and energy made by his various roles within and outside the university, remained generous with his time and advice. This paper reflects that. The main questions considered in this paper were originally articulated by Barry. It was his insight and perseverance that made possible the joint work presented below. When Barry died on the 26th October 2015 we lost both a mentor and a friend. We lost a man who unreservedly shared with each of us his vision of mathematics and the wider world. He is greatly missed.

— James, Charles, Kyung Il and Anthony

2. Introduction

A common question in the study of partial orders is: which properties Q of a partial order $P$ can be preserved when taking a linear extension of $P$ ? That is to say, $\begin{matrix} (1) & \begin{matrix} if P is a partial order satisfying property Q, \\ is there a linear extension L of P which also satisfies Q ? \end{matrix} \end{matrix}$ Prominent examples of properties Q for which this is true include the property of being well founded, due to Bonnet [2], and the property of being scattered, due to Bonnet & Pouzet [3] and Galvin & MacKenzie (unpublished). ‘Well founded’ and ‘scattered’ mean, respectively, not embedding the order type $ω^{*}$ of the negative integers, and the order type η of the rational numbers. (Precise definitions of these and other notions referred to above are deferred until Section 3.)

From a computability perspective, we may ask: $\begin{matrix} (2) & \begin{matrix} if P is a computable partial order satisfying property Q, \\ is there a computable linear extension L of P which also satisfies Q ? \end{matrix} \end{matrix}$ In the case where Q is the property of being well founded, Rosenstein and Kierstead (in [14]) showed that the answer is yes: every well founded computable partial order does have a well founded computable linear extension. For the property of being scattered, the answer was later shown to be ‘no’ by Downey, Hirschfeldt, Lempp and Solomon [6].

Rosenstein and Kierstead’s result is a partial effectivisation of Bonnet’s theorem that every well founded partial order has a well founded linear extension. However, Rosenstein noted that it is not a complete effectivisation as, although the notion of order has been effectivised (by the introduction of the adjective computable), the notion of well foundedness has not. Therefore, Rosenstein proposed a weaker form of the properties of well foundedness and scatteredness. An order $P$ is computably well founded (respectively, computably scattered) if there is no computable embedding of $ω^{*}$ (respectively, η) into $P$ . Rosenstein and Statman (in [14]) showed that (2) does not hold for the property of computable well foundedness: there is a computably well founded, computable partial order $P$ which does not have a computably well founded, computable linear extension. Their counterexample $P$ was a computable tree with no computable infinite path.

If the answer to (2) is ‘no’ for a particular property Q, then we may ask the more general question, what is the minimum complexity of a linear extension $L$ of $P$ needed to preserve property Q? The complexity of an order may be measured, for example, by its position in the arithmetical hierarchy, or by the type of oracle needed to compute the order. Rosenstein took the first steps toward answering this question for the properties of computable well foundedness and computable scatteredness, offering the following two theorems in [14].

Theorem 2.1 (Rosenstein).

Every computably well founded computable partial order $P$ has a computably well founded linear extension $L$ which is $Δ_{2}^{0}$ .

Theorem 2.2 (Rosenstein).

Every computably scattered computable partial order $P$ has a computably scattered linear extension $L$ which is $Δ_{2}^{0}$ .

The proof of Theorem 2.1 uses an oracle for the halting set $\emptyset^{'}$ to construct the required linear extension (thus yielding a $Δ_{2}^{0}$ order by the Limit Lemma, given below as Lemma 3.1). No proof of Theorem 2.2 was given in [14], and to our knowledge a proof of this theorem has not yet appeared in publication.

Rosenstein’s theorems thus give an upper bound of $Δ_{2}^{0}$ for the minimum complexity of a linear extension required to preserve the properties of computable well foundedness and computable scatteredness. In a survey chapter [5] for the Handbook of Recursive Mathematics, Downey asks whether this bound on the minimum complexity can be reduced any further. Rosenstein’s theorems give the best possible bound within the arithmetical hierarchy, since any $Π_{1}^{0}$ or $Σ_{1}^{0}$ linear order with computable domain is in fact computable.

Therefore, to further sharpen our understanding of the minimum complexity, two approaches present themselves: to investigate the complexity within a more fine-grained subhierarchy of the class of $Δ_{2}^{0}$ sets, or to use another measure of complexity aside from the arithmetical hierarchy.

In this paper, taking the first approach, we investigate the problem using the Ershov hierarchy, a well-known subhierarchy of the class of $Δ_{2}^{0}$ sets. In Section 4, we show that the bound on the minimum complexity can be reduced to ω-c.e. within the Ershov hierarchy. That is, every computably well founded (respectively, computably scattered) computable partial order has a computably well founded (computably scattered) linear extension which is ω-c.e. In Section 5, we show that this bound cannot be reduced any further within the Ershov hierarchy, by constructing a computably well founded (respectively, classically scattered) computable partial order $P$ which does not have a computably well founded (computably scattered) linear extension $L$ which is n-c.e. for any $n < ω$ . We thus identify the minimum level in the Ershov hierarchy at which linear extensions preserving the properties of computable well foundedness and computable scatteredness may be found.

As a step towards the second approach, in Section 4 we also show that any oracle satisfying an escape property, which includes all non-generalised low₂ (non-GL₂) sets, can compute a computably well founded (respectively, computably scattered) linearisation of a computably well founded (computably scattered) computable partial order. Thus the information content of the oracle $\emptyset^{'}$ used in Rosenstein’s proof of Theorem 2.1 can be reduced. To conclude, we turn our attention briefly to the property of not computably embedding the order type ζ of the integers. We show that in this case the minimum complexity required to preserve the property of not computably embedding ζ is higher: we construct a computable linear order $P$ which does not embed ζ, but such that every $Δ_{2}^{0}$ linearisation of $P$ admits a computable embedding of ζ.

3. Preliminaries

We assume ${W_{e}}_{e \in N}$ to be a listing of c.e. sets with associated c.e. approximation ${W_{e} [s]}_{e, s \in N}$ , such that $x \in W_{e} [s] ⟹ x < s$ and $| W_{e} [s + 1] ∖ W_{e} [s] | ⩽ 1$ for all e and s. We use $\emptyset^{'}$ to denote the halting set ${e ∣ e \in W_{e}}$ and $A ⩽_{T} B$ to signify that the set A is Turing reducible to set B (or is B-computable) – meaning that there is some Turing machine with oracle B that computes A (under the identification of a set with its characteristic function). $⟨ \cdot, \cdot ⟩$ is a standard 1–1 computable pairing function over the integers satisfying $max {n, m} ⩽ ⟨ n, m ⟩$ for all $n, m \in N$ .

Lemma 3.1 (Schoenfield).

Let A be a set. The following are equivalent.

$A ⩽_{T} \emptyset^{'}$ .

A is $Δ_{2}^{0}$ .

There is a computable function $f : N \times N \to {0, 1}$ such that

For all $n \in N$ , $f (n, 0) = 0$ .

For all $n \in ω$ , ${lim}_{s \to \infty} f (n, s) = A (n)$ .

We generally use notation of the form $A (n) [s]$ to denote such $f (n, s)$ and ${A [s]}_{s \in N}$ to denote the derived approximation to A – where we may also think of $A [s]$ as a (finite) set. We say that such an approximation is $Δ_{2}^{0}$ .

Ershov’s Hierarchy [1,7–9] gives a classification of the $Δ_{2}^{0}$ sets in terms of (notations of) the computable ordinals. Roughly speaking the place of a $Δ_{2}^{0}$ set A in the Ershov Hierarchy is given by measuring how long it takes for an optimal (in terms of time) $Δ_{2}^{0}$ approximation ${A [s]}_{s \in N}$ to A to settle down on any input $n \in N$ – where we say that ${A [s]}_{s \in N}$ has settled down at stage t on input n if $A (n) [s] = A (n)$ for all $s ⩾ t$ .

The present paper is concerned with the initial segment of the Ershov Hierarchy defined relative to the finite ordinals $0, 1, 2, \dots$ and ω. Accordingly we apply the following commonly used variant of Ershov’s original definition.

Definition 3.2.
A $Δ_{2}^{0}$ set A is said to be ω-computably enumerable (or ω-c.e.) if there is a $Δ_{2}^{0}$ approximation ${A [s]}_{s \in N}$ to A and computable function $g : N \to N$ such that $\begin{matrix} | {s ∣ A (n) [s + 1] \neq A (n) [s]} | ⩽ g (n) \end{matrix}$ for all $n \in N$ . A is said to be k-computably enumerable (or k-c.e.) for finite k if we can choose $g : N \to {k}$ , i.e. if $A (n) [s + 1] \neq A (n) [s]$ for at most k stages s. For $γ ⩽ ω$ , we use $Σ_{γ}^{- 1}$ to denote the class of γ-c.e. sets and $Σ_{< ω}^{- 1}$ to denote $⋃_{k < ω} Σ_{k}^{- 1}$ , i.e. the class of all sets that are k-c.e. for some finite k.

We note the existence of a listing ${R_{⟨ k, e ⟩}}_{k, e \in N}$ – which we shall use in Section 5 – of the class $Σ_{< ω}^{- 1}$ with computable approximation ${R_{⟨ k, e ⟩} [s]}_{k, e, s \in N}$ where, for any $k, e \in N$ , ${R_{⟨ k, e ⟩} [s]}_{s \in N}$ is a $k + 1$ -c.e. approximation to the $k + 1$ -c.e. set $R_{⟨ k, e ⟩}$ . Indeed this easily follows1
¹
Another way of doing this directly is in terms of the representation of n-c.e. sets as the union of differences of c.e. sets. Accordingly – letting ${(e)}_{i}$ denote the ith projection of e coded as a sequence of length $n + 1$ – define $g : N^{3} \to N$ such that $\begin{matrix} W_{g (n, e, k)} = \{\begin{matrix} ⋂_{0 ⩽ i ⩽ k} W_{{(e)}_{i}} & if 0 < k ⩽ n \\ \emptyset & otherwise. \end{matrix} \end{matrix}$ Note that n dictates the choice of sequence into which we decode e (using the coding of finite sequences induced by our pairing function). Thus if $n = 2$ the code $e = ⟨ d_{0}, d_{1}, d_{2} ⟩$ is used with ${(e)}_{i} = d_{i}$ . Notice that, by convention, if $n = 0$ , $e = ⟨ e ⟩$ so that ${(e)}_{0} = e$ . We now set $\begin{matrix} R_{⟨ n, e ⟩} = ⋃_{i = 0}^{⌊ \frac{n}{2} ⌋} W_{g (n, e, 2 i)} ∖ W_{g (n, e, 2 i + 1)} \end{matrix}$ with $R_{⟨ n, e ⟩} [s]$ defined by using the s stage approximations of the c.e. sets involved in its definition. It is easy to check that ${R_{⟨ n, e ⟩} [s]}_{s \in N}$ defines an $n + 1$ -c.e. approximation to $R_{⟨ n, e ⟩}$ . For example, if $e = ⟨ e ⟩ = ⟨ c_{0}, c_{1} ⟩ = ⟨ d_{0}, d_{1}, d_{2} ⟩$ then $R_{⟨ 0, e ⟩} = W_{e}$ , $R_{⟨ 1, e ⟩} = W_{c_{0}} ∖ (W_{c_{0}} \cap W_{c_{1}})$ and $\begin{matrix} R_{⟨ 2, e ⟩} = W_{d_{0}} ∖ (W_{d_{0}} \cap W_{d_{1}}) \cup (W_{d_{0}} \cap W_{d_{1}} \cap W_{d_{3}}), \end{matrix}$ from which it is obvious that the associated approximations (e.g. $R_{⟨ 0, e ⟩} [s] = W_{e} [s]$ etc.) are respectively c.e., 2-c.e. and 3-c.e. Note also that it is also easy to show that ${R_{⟨ n, e ⟩}}_{n, e \in N}$ lists all the $n + 1$ -c.e. sets.

from the result (originally due to Ershov) that such a listing exists for any fixed $k + 1$ , by observing that the associated ( $k + 1$ -c.e.) approximation is constructed uniformly in $k + 1$ .

We say that $P = (P, <_{P})$ is a partial order if $<_{P}$ is irreflexive, asymmetric and transitive. For (distinct) $a, b \in P$ if neither $a <_{P} b$ nor $b <_{P} a$ we say that $a, b$ are $<_{P}$ -incomparable written $a |_{P} b$ and we say that $a, b$ are $<_{P}$ -comparable otherwise. We use ${(a, b)}_{P}$ to denote the subpartial order of $P$ made up of those element lying strictly $<_{P}$ -between a and b and we use square brackets to indicate inclusion of the limiting elements. (E.g. ${[a, b]}_{P}$ includes both a and b.) We refer to the latter as $<_{P}$ -intervals. Note that in Section 5, having duly forewarned the reader, we drop the “P” subscript in our notation for intervals. We use the notation ${(a, b)}_{P }$ to denote the set* of elements lying strictly $<_{P}$ -between a and b in $P$ – where the actual $<_{P}$ -ordering of a and b is not significant. For convenience we use $- \infty$ and $+ \infty$ to denote notional elements such that $- \infty <_{P} x$ and $x <_{P} + \infty$ for all x. We say that $L = (L, <_{L})$ is a linear order (that we sometimes also call a chain) if, for all distinct $a, b \in L$ , a and b are $<_{L}$ -comparable. (I.e. $a <_{L} b$ or $b <_{L} a$ .) We say that $L$ is a linear extension of (or linearises) $P$ if $L = P$ and, for all $a, b \in P$ $a <_{P} b \Rightarrow a <_{L} b$ .

For a computational complexity class Γ (such as $Δ_{1}^{0}$ , $Σ_{1}^{0}$ , $Π_{1}^{0}$ , $Σ_{< ω}^{- 1}$ , $Σ_{ω}^{- 1}$ or $Δ_{2}^{0}$ ) we say that $P = (P, <_{P})$ is Γ if both P and $<_{P}$ are Γ. If the domain P is in fact computable we usually make the identification $P = (N, <_{P})$ via a (computably invertible) computable labelling of P. Note that any linear extension of a computable partial order $P$ has computable domain by definition.

We think of $<_{P}$ as both a subset of $N \times N$ and a characteristic function over $N$ under our pairing function $⟨ \cdot, \cdot ⟩$ . Accordingly $<_{P} (⟨ n, m ⟩) = 1$ if and only if $n <_{P} m$ . We also generalise this notation to that of approximations of sets with $<_{P} (⟨ n, m ⟩) [s]$ denoting the s-stage approximation to $<_{P} (⟨ n, m ⟩)$ . We sometimes use letters such as R to denote the order relation, for example using $(N, R)$ to denote a partial/linear order.

A linear order type α is said to be computable if there exists a computable linear order $L = (L, <_{L})$ of type α. Note that we also refer to $L$ as a computable copy of α in this case. We say that partial order $P = (P, <_{P})$ (computably) embeds order type α if there is a (computable) copy $L = (L, <_{L})$ of α such that $L \subseteq P$ and $<_{L}$ coincides with $<_{P}$ over L – i.e. such that $L = (L, <_{P} ↾ L)$ . For two order types α, β we say that β embeds α – written $α ⩽ β$ – if there is a copy $L_{β}$ of β which embeds α. $1 + α$ ( $α + 1$ ) denotes α with a bottom (top) element adjoined. More generally $α + β$ denotes the linear sum of α and β. ω, $ω^{}$ , ζ and η denote respectively the order types of the nonnegative integers, negative integers, integers, and rationals.

A partial order is said to be (computably) well founded* if it does not (computably) embed the order type $ω^{}$ . Note that it is easily shown that $P$ is well founded if and only if there is no infinite descending sequence $x_{0} >_{P} x_{1} >_{P} x_{2} >_{P} \dots$ contained in $P$ – which we refer to as an $ω^{}$ sequence – and also that $P$ is computably well founded if and only if, for all indices e, ${W_{e} [s]}_{s \in N}$ does not enumerate such a sequence. We say that $P$ is (computably) scattered if $P$ does not (computably) embed the order type of the rationals η. Now, defining the dyadic function $d : N \to Q \cap (0, 1)$ by setting $\begin{matrix} d (n) = \{\begin{matrix} \frac{1}{2} & if n = 0 \\ \frac{1 + 2 m}{2^{k + 1}} & if n = (2^{k} - 1) + m for some k ⩾ 1 and 0 ⩽ m < 2^{k}, \end{matrix} \end{matrix}$ we say that $x_{0}, x_{1}, x_{2}, \dots$ is an η-sequence in $P$ if, for all distinct $n, m ⩾ 0$ , $x_{n} <_{P} x_{m} \Leftrightarrow d (n) < d (m)$ . Note that we can also think of the $x_{i}$ as labelling nodes on a binary tree – and thus alternatively use binary instead of dyadic representations of the indices of the sequence – so that $x_{0}$ labels the root and introduction of the labels of nodes of length $l + 1$ corresponds to “densifying” (from left to right) the labels of nodes of length $⩽ l$ . For example, after enumerating 7 elements of our sequence – i.e. those elements labelled by nodes of length $⩽ 2$ – we have: $\begin{matrix} x_{3} <_{P} x_{1} <_{P} x_{4} <_{P} x_{0} <_{P} x_{5} <_{P} x_{2} <_{P} x_{6} . \end{matrix}$ Now it is also easily shown that $P$ is scattered if and only if there is no η sequence contained in $P$ and is computably scattered if and only if, for all indices e, ${W_{e} [s]}_{s \in N}$ does not enumerate such a sequence.
Remark.
Using these notions and the methods used below and in [10] we can build, via computable constructions, ω-c.e. copies – with computable domain – $L_{ω^{}}$ and $L_{η}$ of $ω^{}$ and η respectively, such that $L_{ω^{*}}$ is computably well founded and $L_{η}$ is computably scattered.

Further background on the basic computability theoretic techniques used here can be found in [4,13,15,16]. We also refer the reader to [5] for a review of computability theoretic results in the context of linear orderings.
4. Extendibility results

In this section we show that, for both of the properties computable scatteredness and computable well foundedness and any computable partial order which satisfies one of these properties, there exists an ω-c.e. linearisation of $P$ that also satisfies that property.

Remark.
Given a computable order type α and a computable copy of η, we know that η computably embeds α. Note in particular that this implies that any partial order $P$ which is computably well founded is also computably scattered.

Before considering Theorem 4.1 below we note that an alternative proof of this result using the notion of an η-sequence can be found in Chapter 4 of [10].
Theorem 4.1.
Every computably scattered computable partial order has a computably scattered ω-c.e. linear extension.
Proof.
Let $P = (N, <_{P})$ be a computably scattered computable partial order. We will build a linear order $L = (N, <_{L})$ via a computable construction where at each stage s we define a finite approximation $L [s] = (L [s], <_{L} [s])$ to $L$ where $<_{L} [s]$ is a linearisation of $<_{P}$ restricted to domain $L [s]$ . These approximations are defined such that $L [0] = \emptyset$ and, for all $s > 0$ , $L [s] = {0, \dots, ⌊ \frac{s}{2} ⌋}$ (so that $L [2 t] = L [2 t + 1] = {0, \dots, t}$ ). Defining $\begin{matrix} <_{L} (⟨ n, m ⟩) = lim_{s \to \infty} <_{L} (⟨ n, m ⟩) [s] \end{matrix}$ the construction will ensure that $<_{L} (⟨ n, m ⟩)$ is defined for all $n, m \in N$ and moreover that $| {s ∣ <_{L} (⟨ n, m ⟩) [s] \neq <_{L} (⟨ n, m ⟩) [s + 1]} | < 2^{⟨ n, m ⟩}$ so that $<_{L}$ is ω-c.e. Our construction will also be defined to satisfy for all indices e the following requirements: $\begin{matrix} Q_{e} : if W_{e} is infinite then there exist distinct x, y \in W_{e} such that W_{e} \cap {(x, y)}_{L } = \emptyset . \end{matrix}$ In this way $W_{e}$ cannot be the domain of a dense linear order embedded in $L$ so that satisfaction of $Q_{e}$ for all e implies that $L$ is computably scattered.2
²
It follows from the Remark at the end of the Section 3 that the class $C$ of computable copies of η is a proper subclass of the class $D$ of copies of η whose domain is computable. Therefore our proof rules out any embedding in $L$ of a member of $D$ and so, in effect, delivers more than just computable scatteredness of $L$ .

The requirements are ordered in the usual way so that $Q_{i}$ has higher priority than $Q_{j}$ if $i < j$ .

Notes and notation

For any index e we let $x_{0}^{e}, x_{1}^{e}, \dots$ denote the members of $W_{e}$ in the order dictated by the approximation ${W_{e} [s]}_{s \in N}$ of $W_{e}$ . We say, if $x_{i}^{e}$ , $x_{j}^{e}$ are both defined, that $x_{i}^{e}$ is e-older than* $x_{j}^{e}$ if $i < j$ (and likewise that $x_{j}^{e}$ is e-younger than $x_{i}^{e}$ ) and we apply this terminology directly without use of indices.

The strategy to satisfy requirement $Q_{e}$ is to find a suitable pair ${x_{e}, y_{e}} \subseteq W_{e}$ – a witness – and to endeavour to ensure that the interval ${(x_{e}, y_{e})}_{L}$ remains empty. Formally, a witness is a tuple $⟨ e, x_{e}, y_{e} ⟩$ where $e \in N$ , $x_{e}, y_{e} \in W_{e}$ . The construction will ensure that $x_{e} <_{L} y_{e}$ for such witnesses. A witness set is a finite set of witnesses M such that there is at most one tuple $⟨ e, x_{e}, y_{e} ⟩ \in M$ for each e. In addition to the ordering $L [s]$ , our construction will define a witness set $M [s]$ at each stage s. Define $\begin{matrix} t_{e} [s] = \{\begin{matrix} max {x_{e}, y_{e}} & if there is some ⟨ e, x_{e}, y_{e} ⟩ \in M [s] \\ 0 & otherwise, \end{matrix} \end{matrix}$ and note that $t_{e} [s]$ essentially specifies the ‘portion’ of $L$ that $Q_{e}$ wishes to preserve in order to ensure ${(x_{e}, y_{e})}_{L } = \emptyset$ . We also define $\begin{matrix} (3) & T_{e} [s] = max {t_{i} [s] ∣ i < e} \cup {e} \end{matrix}$ which is the (length of the) initial segment of $N$ on which $Q_{e}$ is not permitted to modify $<_{L}$ . Accordingly, elements smaller than $T_{e} [s]$ act as “barriers” against action taken by requirement $Q_{e}$ at stage $s + 1$ in order to preserve the work of higher priority requirements (with the term ${e}$ added to ensure that $<_{L}$ is ω-c.e.).

We now define some procedures which will be used in the construction as well as in Theorem 4.9. The first procedure takes as input an ordering $J = (J, <_{J})$ on a finite set $J = N ↾ k$ for some k, and a witness set M of witnesses to be respected, such that $J$ is a linear extension of $P ↾ J = (J, <_{P} ↾ J)$ , $x <_{J} y$ and ${(x, y)}_{J}$ is empty for any $⟨ i, x, y ⟩ \in M$ . The procedure extends the ordering $J$ by one element, by inserting the new element as high as possible in the ordering while respecting the witnesses, i.e. maintaining ${(x, y)}_{J}$ empty.

Procedure $P_{1} (J, M)$ : Single-point extension of* $J$ respecting M.

Let $n = | J |$ . Produce a new linear order $J^{'}$ on domain $J^{'} = J \cup {n}$ (i.e., extending the domain of J by one) by inserting n as follows.

Case 1. There is no $m \in J$ with $n <_{P} m$ . Then insert n as the top element in $J^{'}$ , thus defining $x <_{J^{'}} n$ for all $x \in J$ .

Case 2. There is some $m \in J$ with $n <_{P} m$ . Let m be the $<_{J}$ -least such. There are two subcases.

Case 2a. m is not equal to $y_{i}$ for any $⟨ i, x_{i}, y_{i} ⟩ \in M$ . Then obtain $J^{'}$ by inserting n as the immediate predecessor of m in $J$ , thus defining $x <_{J^{'}} n$ for $x \in J$ with $x <_{J} m$ , and $n <_{J^{'}} x$ for $x \in J$ with $m <_{J} x$ or $x = m$ .

Case 2b. m is equal to $y_{i}$ for some $⟨ i, x_{i}, y_{i} ⟩ \in M$ . Then obtain $J^{'}$ by inserting n as the immediate predecessor of $x_{i}$ in $J$ , thus defining $x <_{J^{'}} n$ for $x \in J$ with $x <_{J} x_{i}$ , and $n <_{J^{'}} x$ for $x \in J$ with $x_{i} <_{J} x$ or $x = x_{i}$ .

The result of $P_{1} (J, M)$ is the order $J^{'} = (J^{'}, <_{J^{'}})$ obtained above.

End of Procedure $P_{1}$ .

The next procedure creates a new empty interval ${(x_{e}, y_{e})}_{J^{'}}$ to satisfy $Q_{e}$ , via a method we call plummeting. The procedure takes as input a linear order $J = (J, <_{J})$ , a pair $p = {x, y} \subseteq J$ such that $x |_{P} y$ and an index e of a c.e. set such that $x, y \in W_{e}$ .

Procedure $P_{2} (J, p, e)$ : e-plummeting the pair $p = {x, y}$ in the order $J$ .

Assume without loss of generality that $x <_{J} y$ . Let S be the $<_{J}$ -ordered set lying in the $<_{J}$ -interval ${(x, y)}_{J}$ comprising precisely those elements z such that $x <_{P} z$ . If y is e-older than x, then we remove the set ${x} \cup S$ and reinsert it immediately above y to obtain $J^{'}$ , whereas if y is e-younger than x, then we reinsert S immediately above y and x immediately below y. We do this in such a way that the $<_{J}$ -order of ${x} \cup S$ is preserved. For example, if $S = {x_{0} <_{J} x_{1} <_{J} \dots <_{J} x_{k}}$ and y is e-older than x, then $y <_{J^{'}} x$ and the $<_{J^{'}}$ -interval ${[y, x_{k}]}_{J^{'}}$ in $J^{'}$ is precisely the chain $\begin{matrix} (4) & y <_{J^{'}} x <_{J^{'}} x_{0} <_{J^{'}} x_{1} <_{J^{'}} \dots <_{J^{'}} x_{k} \end{matrix}$ whereas if y is e-younger than x, then $x <_{J^{'}} y$ and the $<_{J^{'}}$ -interval ${[x, x_{k}]}_{J^{'}}$ is the chain in (4) with the order of x and y reversed. Note that x and y are $<_{J^{'}}$ -juxtaposed (i.e. adjacent) in both cases.

The result of $P_{2} (J, p, e)$ is the order $J^{'} = (J, <_{J^{'}})$ where $<_{J^{'}}$ is as above.

End of Procedure $P_{2}$ .

Note that, in the present construction the use of the ages of x and y is irrelevant beyond the fact that it helps to fully determine the plummeting process. However, as we shall see, it allows the present construction to be applied directly in Theorem 4.8.

At each stage s of the construction we will define a finite linear order $L [s]$ and a set of witnesses $M [s] = {⟨ i, x_{i}, y_{i} ⟩ : i \in D}$ where D is a finite subset of $N$ . If there is some $⟨ i, x_{i}, y_{i} ⟩ \in M [s]$ then we say that $Q_{i}$ is on at the end of stage s; otherwise we say that $Q_{i}$ is off at the end of stage s.

$Q_{e}$ requires attention at stage $s + 1$ if it is off at the end of stage s and there are distinct numbers $x, y$ such that
$x, y \in L [s] \cap W_{e} [s]$ , and

$x |_{P} y$ , and

both x, y and every number lying $<_{L} [s]$ between them is greater (under $<_{N}$ ) than $T_{e} [s]$ .
The construction

Stage 0. Define $L$ to be the trivial order on $L [0] = \emptyset$ and define $M [0] = \emptyset$ .

Stage $s + 1$ with s even. We add $n = \frac{s}{2}$ to the order.

Let $L [s + 1]$ be the order obtained by running Procedure $P_{1} (L [s], M [s])$ .3
³
Procedure $P_{1}$ requires that $x <_{J} y$ and ${(x, y)}_{J}$ is empty for each $⟨ i, x, y ⟩ \in M$ ; we verify later that this holds.

Declare $M [s + 1] = M [s]$ and proceed to stage $s + 2$ .

Stage $s + 1$ with s odd. We look to take action for some requirement $Q_{e}$ by e-plummeting.

Case 1. Some requirement $Q_{e}$ with $e < \frac{s + 1}{2}$ requires attention.4
⁴
The condition $e < \frac{s + 1}{2}$ ensures that it is always the case that $N ↾ (T_{e} [s] + 1) \subseteq L [s]$ when $Q_{e}$ requires attention.

In this case choose the least such e and the least (under coding $⟨ \cdot, \cdot ⟩$ ) pair $x, y$ satisfying (i)–(iii). Let $L [s + 1]$ be the order obtained by running Procedure $P_{2} (L [s], {x, y}, e)$ . Let $x_{e}$ be the e-older of the pair ${x, y}$ and $y_{e}$ be the e-younger. Let $M [s + 1] = {⟨ i, x_{i}, y_{i} ⟩ : ⟨ i, x_{i}, y_{i} ⟩ \in M [s] and i < e} \cup {⟨ e, x_{e}, y_{e} ⟩}$ (hence $Q_{e}$ becomes on and all $Q_{j}$ with $j > e$ become off). We say that $Q_{e}$ receives attention in this case.

Case 2. Otherwise.

Simply define $L [s + 1] = L [s]$ and $M [s + 1] = M [s]$ .

Verification

Let $WHA [s]$ denote our Working Hypothesis A at stage s defined to be the conjunction of Conditions (1)–(3) below.
$L [s]$ is a linear extension of $<_{P} ↾ L [s]$ .

If $Q_{e}$ is on at the end of stage s then there is a (unique) pair $x_{e}, y_{e}$ such that $⟨ e, x_{e}, y_{e} ⟩ \in M [s]$ and the $<_{L} [s]$ -interval ${(x_{e}, y_{e})}_{L [s]}$ is empty. Also $x_{e}$ is e-older than5
⁵
This part of the Working Hypothesis is only relevant to the proof of Theorem 4.8.

$y_{e}$ . (And if $Q_{e}$ is off then there are no such elements.)

For any $⟨ i, x, y ⟩$ and $⟨ j, x^{'}, y^{'} ⟩ \in M [s]$ with $i \neq j$ , ${x, y} \cap {x^{'}, y^{'}} = \emptyset$ .
Remark.
Condition 3 of $WHA [s]$ , when taken in conjunction with Condition 2, says that, for witnesses $⟨ i, x, y ⟩$ and $⟨ j, x^{'}, y^{'} ⟩$ at stage s, either $x <_{L} y <_{L} x^{'} <_{L} y^{'}$ or $x^{'} <_{L} y^{'} <_{L} x <_{L} y$ . So $WHA [s]$ implies that there is a linear ordering over the set of witnesses at stage s. Note that the truth of $WHA [s]$ validates the ‘pre-condition’ of Procedure 1 that $J = L [s]$ is a linear extension of $P ↾ J$ , $x <_{J} y$ and ${(x, y)}_{J}$ is empty for $⟨ i, x, y ⟩ \in M = M [s]$ .

A straightforward analysis of the construction and Procedures $P_{1}$ and $P_{2}$ yields the following. Lemma 4.2.
For any stage $s ⩾ 0$ of the construction, $WHA [s] \Rightarrow WHA [s + 1]$ .

Now also let $WHB [s]$ denote our Working Hypothesis B at stage s defined to be the conjunction of Conditions (4)–(5) below.
For any i such that $Q_{i}$ is on at the end of both stage s and $s + 1$ , and any $x, y \in L [s]$ such that $z ⩽ t_{i} [s]$ ( $= t_{i} [s + 1]$ ) for some $z \in {x, y}$ , $x <_{L} [s + 1] y \Leftrightarrow x <_{L} [s] y$ .

For any $x, y \in L [s]$ if, for all $i ⩽ max {x, y}$ , $Q_{i}$ does not receive attention at stage $s + 1$ , then $x <_{L} [s + 1] y \Leftrightarrow x <_{L} [s] y$ .

Define $WH [s]$ to be our overall Working Hypothesis at stage s, i.e. the conjunction $WHA [s] & WHB [s]$ of all five conditions. Then our next Lemma follows by induction over stages for $WHA [s]$ and direct inspection for $WHB [s]$ . Lemma 4.3.
For any stage $s ⩾ 0$ of the construction, $WH [s]$ is true.
Note 4.4.
Suppose that $s^{}$ is such that $Q_{e}$ is on at the end of every stage $s ⩾ s^{}$ . Note that $T_{e} [s] = T_{e} [s^{}]$ for all $s ⩾ s^{}$ in this case. Then it follows from Lemma 4.3 that, for any $n, m \in N$ such that $z ⩽ T_{e} [s^{}]$ for some $z \in {n, m}$ , and all $s ⩾ s_{n, m}$ , $n <_{L} [s] m \Leftrightarrow n <_{L} [s_{n, m}] m$ , where $s_{n, m}$ is the least stage $⩾ s^{}$ such that $n, m \in L [s_{n, m}]$ . In other words $<_{L} (⟨ n, m ⟩)$ is defined and coincides with $<_{L} (⟨ n, m ⟩) [s]$ for all $s ⩾ s_{n, m}$ . Moreover Lemma 4.3 also implies that $Q_{e}$ will be satisfied in this case as the witness $⟨ e, x_{e}, y_{e} ⟩ \in M [s^{}]$ remains in $M [s]$ henceforth and the $<_{L}$ -interval ${(x_{e}, y_{e})}_{L}$ remains empty.
Lemma 4.5.
For all* $e ⩾ 0$ , $Q_{e}$ receives attention at most $2^{e}$ times and is satisfied. 6
⁶
Note that we are not assuming that $<_{L} (⟨ n, m ⟩)$ is defined for all $n, m \in N$ .

Proof.
Consider index $e > 0$ and suppose that there is a stage $s_{e}$ such that, for all $s > s_{e}$ and $i < e$ , $Q_{i}$ does not receive attention at stage s. Suppose also that $s_{e}$ is the least such stage. As already mentioned in Note 4.4 we know that $T_{e} [s] = T_{e} [s_{e}]$ for all $s ⩾ s_{e}$ so we can define $T_{e} = {lim}_{s \to \infty} T_{e} [s] = T_{e} [s_{e}]$ . Label $N ↾ (T_{e} + 1)$ as ${b_{0}, \dots, b_{T_{e}}}$ in such a way that $\begin{matrix} b_{0} <_{L} [s_{e}] b_{1} <_{L} [s_{e}] \dots <_{L} [s_{e}] b_{T_{e}} \end{matrix}$ and notice that, by Note 4.4, this ordering coincides with $<_{L} [s]$ for all $s ⩾ s_{e}$ and so also with $<_{L}$ . (I.e. the ordering of the $b_{i}$ ’s is terminally fixed from stage $s_{e}$ onwards.) Letting $b_{- 1}$ and $b_{T_{e} + 1}$ denote $- \infty$ and $+ \infty$ respectively, for $0 ⩽ i ⩽ T_{e} + 1$ define the sets $\begin{matrix} U_{i} = W_{e} \cap {z \in N ∣ b_{i - 1} <_{L} z <_{L} b_{i}} \end{matrix}$ (i.e. $U_{i} = W_{e} \cap {(b_{i - 1}, b_{i})}_{L }$ ) and observe that, by Note 4.4, $U_{i}$ is a c.e. set with c.e. approximation ${U_{i} [s]}_{s \in N}$ defined by setting $\begin{matrix} U_{i} [s] = \{\begin{matrix} \emptyset & if s < s_{e} \\ W_{e} [s] \cap L [s] \cap {z \in N ∣ b_{i - 1} <_{L} z <_{L} b_{i}} & otherwise. \end{matrix} \end{matrix}$ Remark.
Intuitively Note 4.4 tells us that, from stage $s_{e}$ onwards, the $b_{i}$ ’s act as a set of fixed barriers across which nothing in the construction now moves. In other words any reordering of elements in the ongoing approximation $L [s]$ either occurs strictly below $b_{0}$ or strictly above $b_{T_{e}}$ or strictly in between $b_{i - 1} <_{L} b_{i}$ , for some $1 ⩽ i ⩽ T_{e}$ and so, by definition, this involves two elements $x, y$ that are both in the same set $U_{j}$ .

Suppose that $W_{e}$ is infinite. Then we can choose i such that $U_{i}$ is infinite. If there exist distinct elements $x, y \in U_{i}$ such that $x |_{P} y$ then clearly $Q_{e}$ will receive attention at some stage $s > s_{e}$ and be satisfied by Note 4.4. Otherwise $U_{i}$ is linearly ordered by $<_{P}$ . This means that $<_{L}$ is defined and coincides with $<_{P}$ over $U_{i}$ . However computable scatteredness of $P$ implies that there is some pair $x, y \in U_{i}$ such that $U_{i} \cap {(x, y)}_{L }$ is empty. So, as the latter is the same as $W_{e} \cap {(x, y)}_{L }$ , $Q_{e}$ is once again satisfied.

Now suppose that $Q_{i}$ in fact receives attention at most $2^{i}$ times for all $i ⩽ e$ so that this condition applies to all such i at stage $s_{e}$ . By inspection – using the observation that for as long as a requirement is on it does not receive attention – we see that this implies that $Q_{e}$ has received attention at most $(2^{e - 1} - 1) \times 2 + 1 = 2^{e} - 1$ times by (the end of) stage $s_{e}$ . But, noting in the above that $Q_{e}$ receives attention at most once after stage $s_{e}$ , we see that $Q_{e}$ receives attention at most $2^{e}$ times.

As the argument for $e = 0$ is an easy variant of the argument applied to the case $e > 0$ , Lemma 4.5 follows by induction over indices $e ⩾ 0$ . □
Lemma 4.6.
For all* $n, m \in N$ , $<_{L} (⟨ n, m ⟩)$ is defined and $\begin{matrix} | {s ∣ <_{L} (⟨ n, m ⟩) [s + 1] \neq <_{L} (⟨ n, m ⟩) [s]} | < 2^{⟨ n, m ⟩} . \end{matrix}$ In other words $<_{L}$ is ω-c.e.
Proof.
Note firstly that, for any $n, m \in N$ , $max {n, m} ⩽ ⟨ n, m ⟩$ . Also (by definition of $T_{e}$ ), for any stage $s + 1$ , a requirement $Q_{i}$ can only change the $<_{L}$ -order of n and m at stage $s + 1$ if $i < max {n, m}$ .7
⁷
In fact we could use $min {n, m}$ instead of $max {n, m}$ here.

It follows by Lemma 4.5 that there exist at most $\sum_{i = 0}^{⟨ n, m ⟩ - 1} 2^{i} = 2^{⟨ n, m ⟩} - 1$ such stages $s + 1$ . □
Lemma 4.7.
$L = (N, <_{L})$ is a linear extension of $P$ .

This Lemma follows directly from the conjunction of Lemmas 4.3 and 4.6 and concludes the proof of Theorem 4.1. □

We now reapply the above construction to prove Theorem 4.8 below. We note that this result was first proved in Chapter 2 of [11].
Theorem 4.8.
Every computably well founded computable partial order has a computably well founded ω-c.e. linear extension.
Proof.
Let $P = (N, <_{P})$ be a computably well founded computable partial order and constuct the linear order $L = (N, <_{L})$ precisely as in the proof of Theorem 4.1. In this case we need to satisfy, for all indices e, the following requirement: $\begin{array}{l} Q_{e} : & if W_{e} is infinite then there exist x, y \in W_{e} such that x is e -older than y \\ and x <_{L} y . \end{array}$ This means that ${W_{e} [s]}_{s \in N}$ does not enumerate an $ω^{}$ sequence in $L$ so that satisfaction of $Q_{e}$ for all e implies that $L$ is computably well founded.

Apply the same Verification as that in the proof of Theorem 4.1 except for the analysis of $<_{L}$ relative to the sets $U_{i}$ in Lemma 4.5. Here, under the assumption that $W_{e}$ is infinite we consider the least i such that $U_{i}$ is nonempty. If $U_{i}$ is finite then there is some $j > i$ and $x \in U_{i}$ , $y \in U_{j}$ such that x is e-older than y. But, by Note 4.4 (and the definitions of the elements $b_{k}$ and sets $U_{k}$ ), we know that, $x <_{L} b_{i}$ , $b_{j - 1} <_{L} y$ and that if $i < j - 1$ then $b_{i} <_{L} b_{j - 1}$ , so that $x <_{L} y$ . On the other hand, if $U_{i}$ is infinite, and there exist distinct $x^{'}, y^{'} \in U_{i}$ such that $x^{'} |_{P} y^{'}$ then clearly $Q_{e}$ will receive attention at some stage $s > s^{}$ and will thus be satisfied, as Procedure $P_{2}$ ensures that the e-oldest of $x^{'}, y^{'}$ is placed $<_{L}$ -below the e-youngest. Otherwise $U_{i}$ is (infinite and) linearly ordered by $<_{P}$ and so $<_{L}$ coincides with $<_{P}$ over $U_{i}$ . However, as $U_{i}$ is itself a c.e. set, computable well foundedness of $P$ implies that there are elements $x, y \in U_{i}$ such that x is e-older than y and $x <_{L} y$ . Thus in each case $Q_{e}$ is satisfied.

Since the rest of the Verification is unchanged we see that not only Lemma 4.5 but also Lemmas 4.6 and 4.7 follow as before so that $L$ is a ω-c.e. computably well founded linear extension of $P$ in this case. □

We now give an extension of Rosenstein’s theorems in a different direction. By the Limit Lemma 3.1, Rosenstein’s theorems 2.1 and 2.2 show that every computably well founded (respectively, computably scattered) computable partial order $P$ has a computably well founded (computably scattered) linearisation which is computable in $\emptyset^{'}$ . Indeed, Rosenstein’s original proof of Theorem 2.1 uses an oracle for $\emptyset^{'}$ to construct the desired extension. We now show that the oracle $\emptyset^{'}$ can be replaced with any oracle satisfying the following property. Say that $X \subseteq N$ has the $\emptyset^{'}$ escape property if8
⁸
Recall that $\exists^{\infty} x P (x)$ means $\forall n \exists x > n P (x)$ .

$\begin{matrix} (5) & \forall total functions f ⩽_{T} \emptyset^{'} \exists total function g ⩽_{T} X s.t. \exists^{\infty} x g (x) ⩾ f (x) . \end{matrix}$ The class of sets satisfying (5) includes the non-generalised low₂ (non-GL₂) sets.9
⁹
Recall that a set X is generalised low₂ (GL₂) if $X^{″} \equiv_{T} {(\emptyset^{'} \oplus X)}^{'}$ .

Indeed it is well known (see for example [12] Exercise 1.5.21) that X is non-GL₂ if and only if $\begin{matrix} \forall total functions f ⩽_{T} \emptyset^{'} \oplus X \exists total function g ⩽_{T} X s.t. \exists^{\infty} x g (x) ⩾ f (x) \end{matrix}$ which immediately implies (5).
Theorem 4.9.
Let $X \subseteq N$ satisfy ( 5 ). For any computably scattered computable partial order $P$ , there is a computably scattered linear extension $L$ of $P$ which is computable in X.
Proof.
We first prove the theorem for the case when $X = \emptyset^{'}$ . (This is in essence a proof of Rosenstein’s Theorem 2.2.) We later show how to adapt the construction for an oracle satisfying (5).

We will build the required linear extension $L$ in finite extensions. Much of the terminology and notation will be the same as in the proof of Theorem 4.1. We will satisfy the same requirements $\begin{matrix} Q_{e} : if W_{e} is infinite then there exist distinct x, y \in W_{e} such that W_{e} \cap {(x, y)}_{L } = \emptyset . \end{matrix}$ The basic strategy to satisfy a requirement $Q_{e}$ at stage $s + 1$ is: repeatedly extend the order $L [s]$ element-by-element using Procedure $P_{1}$ , until we find a suitable pair $x, y$ to plummet using Procedure $P_{2}$ in order to satisfy $Q_{e}$ . Of course, this may not terminate as we may never find a suitable $x, y$ , but that can be determined with the oracle $\emptyset^{'}$ . If the oracle tells us there is no such ${x, y}$ then we can argue, similarly to Lemma 4.5, that $Q_{e}$ is automatically satisfied due to computable scatteredness of $<_{P}$ .

At stage $s + 1$ , we will have a linear order $L [s]$ on some initial segment $L [s]$ of $N$ , along with a finite witness set $M [s] = {⟨ i, x_{i}, y_{i} ⟩ : i \in D}$ , and we define $L [s + 1]$ and $M [s + 1]$ . We define one further procedure which will be used in the construction, which takes as input a finite linear order $J$ , a witness set $M = {⟨ i, x_{i}, y_{i} ⟩ : i \in D}$ with $x_{i} <_{J} y_{i}$ and ${(x_{i}, y_{i})}_{J}$ empty, and an index e of a c.e. set.

Procedure $P_{3} (J, M, e)$ : Search for a candidate to e-plummet.*

Let $T = | J |$ where $J = (J, <_{J})$ . Build an order $I = (I, <_{I})$ in substages.

Substage $t = 0$ : Set $I [0] = J$ .

Substage $t + 1$ : Check if there are distinct numbers $x, y$ such that
$x, y \in W_{e} [t] \cap I [t]$ , and

$x |_{P} y$ , and

both $x, y$ and every number lying $<_{I} [t]$ between them is greater (under $<_{N}$ ) than T.

If there is such a pair $x, y$ then choose the least such (under $⟨ \cdot, \cdot ⟩$ ) and let $I$ be the ordering obtained by running Procedure $P_{2} (I [t], {x, y}, e)$ . Say that $P_{3} (J, M, e)$ terminates after $t + 1$ steps and returns output $I$ .

If there is no such $x, y$ then let $J [t + 1]$ be the ordering obtained by running Procedure $P_{1} (I [t], M)$ . Continue to stage $t + 2$ .

End of Procedure $P_{3}$ .

The construction ( $\emptyset^{'}$ version)

Stage $s = 0$ . Define $L [0]$ to be the trivial order on $L [0] = \emptyset$ and define $M [0] = \emptyset$ .

Stage $s + 1$ . We are given $L [s]$ and $M [s]$ . Find the least $e ⩽ s$ , if it exists, such that $Q_{e}$ is off at the end of stage s and $\begin{matrix} (6) & \exists t \in N such that Procedure P_{3} (L [s], M [s], e) terminates after t steps. \end{matrix}$ Note that whether (6) holds can be determined using the oracle $\emptyset^{'}$ .

Case 1. If there is such an e, then let $L [s + 1]$ be the ordering obtained by running $P_{3} (L [s], M [s], e)$ . Let $M [s + 1] = M [s] \cup {⟨ e, x, y ⟩}$ where $x, y$ is the pair plummeted by $P_{3} (L [s], M [s], e)$ and x is e-older than y. Say that action is taken for $Q_{e}$ at stage $s + 1$ .

Case 2. If there is no such e, then let $L [s + 1]$ be the ordering obtained by running Procedure $P_{1} (L [s], M [s])$ , and let $M [s + 1] = M [s]$ .

End of construction

The construction described above satisfies the Working Hypothesis A $WHA [s]$ from Theorem 4.1 at every stage s. The required linear extension of $P$ is $L = {lim}_{s} L [s]$ . It is computable in $\emptyset^{'}$ since the $L$ -ordering of x and y is determined at stage $s = max {x, y} + 1$ at the latest. We now verify that we can either take action to satisfy each $Q_{e}$ , or else $Q_{e}$ is automatically satisfied. Lemma 4.10.
Suppose that $W_{e}$ is infinite and $s_{0}$ is a stage such that $Q_{e}$ is off at the end of stage $s_{0}$ , and ( 6 ) does not hold for e at stage $s_{0} + 1$ . Then there are distinct $x, y \in W_{e}$ such that $W_{e} \cap {(x, y)}_{L } = \emptyset$ .
Proof.
Suppose that $W_{e}$ is infinite and $s_{0}$ is as stated in the lemma. Let $\begin{matrix} b_{0} <_{L} [s_{0}] b_{1} <_{L} [s_{0}] \dots <_{L} [s_{0}] b_{k - 1} \end{matrix}$ be a listing of $L [s_{0}]$ in ascending $<_{L} [s_{0}]$ -order, and let $b_{- 1}$ and $b_{k}$ denote $- \infty$ and $+ \infty$ respectively. First, observe that for any $x \in N ∖ L [s_{0}]$ and $0 ⩽ i ⩽ k$ , $\begin{matrix} (7) & b_{i - 1} <_{L} x <_{L} b_{i} ⟺ (\begin{matrix} x ≮_{P} b_{i - 1}, and either x <_{P} b_{i} or \\ b_{i} = x_{j} for some ⟨ j, x_{j}, y_{j} ⟩ \in M [s_{0}] and x <_{P} y_{j} . \end{matrix}) \end{matrix}$ That is, the ultimate position of x in $L$ relative to $L [s_{0}]$ is computable. This can be seen by noting that Procedure $P_{1}$ preserves property (7), as does the application of Procedure $P_{2}$ in conjunction with condition (iii) in Procedure $P_{3}$ . For $0 ⩽ i ⩽ k$ , let $\begin{matrix} U_{i} = W_{e} \cap {z \in N ∣ b_{i - 1} <_{L} z <_{L} b_{i}} . \end{matrix}$ The sets $U_{i}$ are computably enumerable due to (7). Moreover, each $U_{i}$ is linearly ordered by $<_{P}$ – as otherwise the procedure $P_{3} (L [s_{0}], M [s_{0}], e)$ would terminate – and its $<_{P}$ -ordering coincides with $<_{L}$ . Let i be such that $U_{i}$ is infinite. Then computable scatteredness of $P$ implies that there is some pair $x, y \in U_{i}$ such that $U_{i} \cap {(x, y)}_{L }$ is empty. It now suffices to note that the latter is the same as $W_{e} \cap {(x, y)}_{L }$ . □

To finish our verification that $L$ is computably scattered for the case of $X = \emptyset^{'}$ , let $s_{e}$ be the least stage such that $s_{e} ⩾ e$ and action is not taken for any $Q_{e^{'}}$ with $e^{'} < e$ at any stage $s ⩾ s_{e} + 1$ . At stage $s_{e} + 1$ we either take action for $Q_{e}$ (if we haven’t already done so earlier), or Lemma 4.10 guarantees that $Q_{e}$ is satisfied without taking action for $Q_{e}$ .10
¹⁰
Moreover, it is possible to show that if (6) holds for e at some stage $s + 1$ , then it also holds for e at any $s^{'} + 1 < s + 1$ . Therefore in fact $s_{e} = e$ , and we either take action for $Q_{e}$ at stage $e + 1$ or not at all.

Modifications necessary for an oracle satisfying ( 5 )

The strategy we will use with an oracle X satisfying the escape property (5) is to find a $\emptyset^{'}$ -computable function $f (s)$ which will bound the number of steps needed for Procedure $P_{3}$ to terminate at stage s of the construction. Instead of asking the oracle directly whether (6) holds, we can run $P_{3}$ and see if it terminates within $f (s)$ steps.

Although the weaker oracle cannot compute f directly, it can compute a function $g (s)$ which escapes f and this will be sufficient. Instead of checking (6) directly, we will run $P_{3}$ for $g (s)$ steps. If it terminates within $g (s)$ steps then we proceed to satisfy $Q_{e}$ as above. If not, we will assume for now that it does not terminate (and thus $Q_{e}$ is satisfied automatically as in Lemma 4.10). Later it may turn out that our bound $g (s)$ was incorrect so we have to take action for $Q_{e}$ at a later stage. Thus the requirements will not be satisfied in sequential order. However, we can argue that our approximation $g (s)$ will eventually bound the termination time for $P_{3} (L [s], M [s], e)$ .

Note that the role of the oracle X is limited to computing g, and thus determining which requirement will take action at each stage. The construction (for a fixed X) thus traces out a path in a finitely branching, $\emptyset^{'}$ -computable subtree T of ${- 1, 0, 1, 2, \dots}^{< ω}$ defined as follows. With each node σ of T is associated a construction state* $(L [σ], M [σ])$ . The root of T is the empty string; the root node is associated with construction state $(L [0], M [0])$ as defined in stage 0 of the construction. Given a string $σ \in T$ of length s, the string $σ \hat{} ⟨ i ⟩$ is in T if
$0 ⩽ i ⩽ s$ , and

$σ (m) \neq i$ for all $m < s$ (i.e., requirement $Q_{i}$ has not yet been satisfied on this branch), and

there exists $t \in N$ such that Procedure $P_{3} (L [σ], M [σ], i)$ terminates after t steps.
In this case the construction state associated with $σ \hat{} ⟨ i ⟩$ is the pair $(L [s + 1], M [s + 1])$ obtained by following Case 1 of the construction with $L [s]$ , $M [s]$ and e replaced by $L [σ]$ , $M [σ]$ and i, respectively. The string $σ \hat{} ⟨ - 1 ⟩$ is also in T, and its construction state is the pair $(L [s + 1], M [s + 1])$ obtained by taking Case 2 of the construction with $L [s]$ and $M [s]$ replaced by $L [σ]$ and $M [σ]$ , respectively.

Note that, given a string $σ \in {- 1, 0, 1, 2, \dots}^{< ω}$ , the oracle $\emptyset^{'}$ can compute the construction state $(L [σ], M [σ])$ , if $σ \in T$ , or determine that $σ \notin T$ . The construction with oracle $\emptyset^{'}$ , defined earlier, corresponds to one infinite path α through T.11
¹¹
By note 10, α is defined by $α (s) = s$ , if Case 1 was taken at stage $s + 1$ , or $α (s) = - 1$ , if Case 2 was taken at stage $s + 1$ .

We now define the $\emptyset^{'}$ -computable function f which will be escaped by g. For $e \in N$ and a string $σ \in {- 1, 0, 1, 2, \dots}^{< ω}$ , define $\begin{matrix} q (e, σ) = \{\begin{matrix} the least t such that Procedure P_{3} (L [σ], M [σ], e) \\ terminates in t steps, if σ \in T and if such t exists \\ 0 if there is no such t, or if σ \notin T . \end{matrix} \end{matrix}$ Then q is computable from $\emptyset^{'}$ and $q (e, σ)$ bounds the time needed to determine (6) at step $s + 1 = | σ | + 1$ of a construction extending σ. However, as the construction will be done computably in X, we don’t know in advance the path which the construction will take through T; moreover it may not be computable in $\emptyset^{'}$ if $X ≰_{T} \emptyset^{'}$ . So to define our $\emptyset^{'}$ -computable search bound f we must also search over all branches of T of length s: $\begin{matrix} f (s) = max_{σ, e} q (e, σ) \end{matrix}$ where σ ranges over all nodes of T of length s and $0 ⩽ e ⩽ | σ |$ .

We can now give the construction for the oracle X. By (5), X computes a function g such that $\exists^{\infty} s g (s) ⩾ f (s)$ . The construction for X runs exactly as specified above for oracle $\emptyset^{'}$ , except we replace (6) with the following: $\begin{matrix} (8) & \exists t ⩽ g (s) such that Procedure P_{3} (L [s], M [s], e) halts after t steps. \end{matrix}$ By construction, the resulting $L = {lim}_{s} L [s]$ is an X-computable linear extension of $P$ . We verify that it is computably scattered. Let $W = W_{e}$ be an infinite c.e. set. Let $s_{e}$ be the least number $⩾ e$ such that action is not taken for any $Q_{e^{'}}$ with $e^{'} < e$ at any stage $s^{'} ⩾ s_{e} + 1$ . If there is some stage s such that (6) does not hold, then by Lemma 4.10 requirement $Q_{e}$ is satisfied automatically. Otherwise, (6) holds for e at every s, so the function $\begin{array}{l} p (s) = & the least t such that P_{3} (L [s], M [s], e) halts after t steps \end{array}$ is total. Let $σ_{s}$ be the node from T corresponding to the construction after stage s; that is, $σ_{s}$ is such that $L [σ_{s}] = L [s]$ and $M [σ_{s}] = M [s]$ . Now by definition of q and f, for $s ⩾ e$ we have $\begin{matrix} p (s) = q (e, σ_{s}) ⩽ f (s) . \end{matrix}$ But the function g escapes f, so there is an $s_{1} ⩾ s_{e}$ such that $g (s_{1}) ⩾ f (s_{1}) ⩾ p (s_{1})$ . At stage $s_{1} + 1$ , action will be taken for $Q_{e}$ (if it has not already), ensuring that $Q_{e}$ is satisfied and the suborder $L ↾ W_{e} = (W_{e}, <_{L} ↾ W_{e})$ does not have order type η. This establishes Theorem 4.9. □

We note again that the same construction, if applied to a computably well founded partial order $P$ , will yield a computably well founded linear extension $L$ . Thus we may replace “computably scattered” in the statement of Theorem 4.9 with “computably well founded”.

The property (5) appears to be exactly what is required for the construction above to succeed. We conjecture that the strength of the oracle can not be reduced any further.
5. Nonextendibility results

We now show that the results in Section 4 are the best possible in the sense that, whereas for $γ = ω$ , a γ-c.e. linearisation can always be found that preserves computable scatteredness or computable well foundedness, this is not the case for any $γ < ω$ . We note that proofs of Theorems 5.1, 5.2 and 5.4 first appeared in [10]. We also draw the reader’s attention to the fact that the fundamental methods used for the constructions in this section are based on those used in the proofs of Theorems 1(3), 2(2) and 3 of [6].

Remark.

The reader might find it instructive, before reading the Construction in the proof of Theorem 5.1, but having understood the general context presented in the preceding material – i.e. in the Notes and Notation etc. – to make an excursion via Theorem 5.4 whose proof affords a simplified version of some of the underlying ideas.

Theorem 5.1.

There exist a computably well founded computable partial order $P$ which has no computably well founded $Σ_{< ω}^{- 1}$ linear extension.

Proof.

We construct a computable partial order $P = (P, <_{P})$ with $P = N$ as a countable disjoint union of subpartial orders $P_{e} = (P_{e}, <_{P} ↾ P_{e})$ such that each $P_{e}$ forms a connected component of $P$ and also such that every element of $P_{i}$ is incomparable with every element of $P_{j}$ for any $i \neq j$ . We will assume a computable listing ${R_{e}}_{e \in N}$ – as stipulated in Section 2 – of the class $Σ_{< ω}^{- 1}$ with associated computable approximation ${R_{e} [s]}_{e, s \in N}$ defined in such a way that, for any $n ⩾ 1$ , $R_{⟨ n - 1, i ⟩}$ is an n-c.e. set and ${R_{⟨ n - 1, i ⟩} [s]}_{s \in N}$ is an n-c.e. approximation to $R_{⟨ n - 1, i ⟩}$ .

For any e we will construct $P_{e}$ in such a way that any infinite chain – so a fortiori any $ω^{*}$ sequence – in $P_{e}$ computes the halting set $\emptyset^{'}$ and is therefore not computable. Since there are no $<_{P}$ -comparabilities between the different components of $P$ this will imply that $P$ is computably well founded. On the other hand, for any set $R \in Σ_{< ω}^{- 1}$ there is an index e such that $R = R_{e}$ and our construction will ensure that, if $(N, R_{e})$ – with $R_{e}$ seen as a set of ordered pairs – is a linear extension of $P$ , then there will be a computable $ω^{*}$ sequence ${a_{n}}_{n \in N}$ in $(P_{e}, R_{e} ↾ P_{e})$ . Notation.

We use the shorthand $R_{e}$ linearises $P_{e}$ to mean that $(P_{e}, R_{e} ↾ P_{e})$ is a linear extension of $P_{e}$ and use similar shorthand relative to the approximations used during the construction, as also for $R_{e}$ with regard to $P$ itself.

At each stage $s + 1$ of the construction we define an approximation $P [s + 1]$ with domain some finite initial segment of $N$ . To do this we firstly compute the approximations $R_{e} [s + 1]$ for $e < s$ and an approximation $\emptyset^{'} [s + 1]$ to the halting set. Starting at stage 0 with $P [0] = \emptyset$ , at stage $s + 1$ we add up to four new elements to each component $P_{e} [s]$ such that $e < s$ to obtain $P_{e} [s + 1]$ and four new elements to the (at this point) empty component $P_{s} [s]$ to obtain $P_{s} [s + 1]$ . When a number n enters the construction at a stage s all of the $<_{P}$ -comparabilities of n with numbers $k < n$ are set at stage s and do not change at any later stage. So each $P_{e}$ (and $P$ itself) is computable because, to decide whether a number k is in $P_{e}$ it suffices to run the construction until stage $k + 1$ whereas to decide $<_{P}$ relative to numbers $m, n$ , it suffices to run the construction until stage $s = max {m, n} + 1$ .

Notes and notation

Figure 1.

The first two stages of the construction of $P_{e}$ with $w <_{P} z$ and $w' R_{e} z'$ denoted by $w \cdot - \leftarrow \cdot z$ and $w' \cdot \cdot \cdot \cdot R_{e} \cdot \cdot \cdot \cdot z'$ respectively.

Our description will mostly relate to a single component $P_{e}$ of $P$ . We call a stage $s + 1 > e + 1$ e-good if $R_{e} [s + 1]$ linearises $P_{e} [s]$ . The construction of $P_{e}$ only proceeds at e-good stages. It is important to note that the set of e-good stages is computable.

If $s + 1$ is an e-good stage then, for $m, n \in P_{e} [s]$ we say that $m R_{e} n$ is computed at stage s if $⟨ m, n ⟩ \in R_{e} [s + 1]$ . Note that, as $s + 1$ is e-good, $R_{e} [s + 1]$ linearises $P_{e} [s]$ and so $⟨ n, m ⟩ \notin R_{e} [s]$ . Notice also that for $m, n \in P_{e}$ , $m R_{e} n$ is only computed at e-good stages by definition so that, from now on, when we say that $m R_{e} n$ is computed (or r-computed as defined below) at stage s we mean that s is an e-good stage. We say that $m R_{e} n$ is 1-computed at stage s if it is computed at stage s and there is no earlier stage t at which $n R_{e} m$ is computed. For $r > 1$ we say that $m R_{e} n$ is r-computed at stage s if $m R_{e} n$ is computed at stage s, there is an earlier stage t such that $n R_{e} m$ is $r - 1$ -computed at stage t and, for any stage $t < s^{'} < s$ and l such that $n R_{e} m$ is l-computed at stage $s^{'}$ , $l = r - 1$ . Note that, if $R_{e}$ is k-c.e. and $m R_{e} n$ is r-computed at some stage s then $r ⩽ k$ . Notice also that it might be the case that $m R_{e} n$ is 1-computed at stage s and there is an earlier stage t such that $m, n \in P_{e} [t - 1]$ and $⟨ n, m ⟩ \in R_{e} [t]$ . In fact it might be the case that $⟨ m, n ⟩ \in R_{e} [t]$ as well. However this just means by definition that t is not an e-good stage so that neither $n R_{e} m$ nor $m R_{e} n$ was computed at stage t. A similar observation applies for r-computations with $r > 1$ .

Important Shorthand Convention. To avoid cluttering notation we use the shorthand12

¹²

This shorthand is entirely unambiguous as any interval to which we refer is always a $<_{P}$ -interval.

“interval” to refer to a

<_{P}

-interval in

P

and – as mentioned in Section 3 – drop subscripts in the notation for the latter so that, for example,

(b_{i}, a_{i})

denotes the open interval with

<_{P}

-lower bound

b_{i}

and

<_{P}

-upper bound

a_{i}

We use $Q_{i}$ to denote the construction’s requirement – that we also think of as a strategy – that any infinite chain in $P$ computes the question $\emptyset^{'} (i)$ of whether i belongs to the halting set. The reader should note that $Q_{i}$ can intervene in the construction of any individual component $P_{e}$ and at any Level (see later) of the construction of $P_{e}$ . These requirements interact (at any given Level) according to the usual process of finite injury with $Q_{i}$ being able to injure $Q_{j}$ if $i < j$ .

The construction

We consider fixed index e and describe the construction of the associated component $P_{e}$ . Assuming that $e = ⟨ k - 1, i ⟩$ we know that $R_{e}$ is k-c.e. and that ${R_{e} [s]}_{s \in N}$ is a k-c.e. approximation to $R_{e}$ . For $k > 1$ the construction has k different nested Levels. For this reason we consider three different cases according to the value of k.

Case 1: $k = 1$ . Remark.

$k = 1$ implies that $R_{e}$ is c.e. with ${R_{e} [s]}_{s \in N}$ a c.e. approximation to $R_{e}$ .

At all stages $s ⩽ e$ by definition $P_{e} [s] = \emptyset$ . At stage $e + 1$ four new elements $a_{- 1}$ , $b_{- 1}$ , x and y are added to $P_{e} [e]$ to obtain $P_{e} [e + 1]$ in such a way that $b_{- 1} <_{P} x <_{P} a_{- 1}$ and $b_{- 1} <_{P} y <_{P} a_{- 1}$ with $x |_{P} y$ as shown in Fig. 1. Note that in the present case, as $k = 1$ , only 1-computations are involved in the construction and so by definition everything here happens at Level 1. For simplicity we will omit mention of the Level at present. However the reader should keep this aspect of the construction in mind as, for the case when $k > 1$ the present case describes the Level 1 part of a construction involving k Levels. We think of the interval $(a_{- 1}, b_{- 1})$ as the base interval of the construction. $(a_{- 1}, b_{- 1})$ is now also the active interval (until the first e-good stage).

We suppose for the sake of the present argument that the set of e-good stages is nonempty (and sufficiently large). At the first such stage $s + 1 > e + 1$ we have that, for some $u, v \in {x, y}$ , $u R_{e} v$ is 1-computed. Accordingly the x, y labels are removed with $c_{0}$ now labelling the element u and $b_{0}$ labelling the element v. Also four new elements $a_{0}$ , $d_{0}$ , x and y are added to $P_{e} [s]$ to obtain $P_{e} [s + 1]$ in such a way that $b_{- 1} <_{P} d_{0} <_{P} c_{0}$ , $b_{0} <_{P} x <_{P} a_{0} <_{P} a_{- 1}$ , $b_{0} <_{P} y <_{P} a_{0} <_{P} a_{- 1}$ and $x |_{P} y$ as shown in Fig. 1. The element $a_{0}$ is now 0-activated and painted red and the interval $(b_{0}, a_{0})$ becomes the active interval of the construction. Note that the 0-activation of $a_{0}$ means that the intervals $(d_{0}, c_{0})$ and $(b_{0}, a_{0})$ have been commandeered by strategy $Q_{0}$ . The fact that $a_{0}$ is also red indicates that $Q_{0}$ has not yet registered that13

¹³

For the sake of simplicity this can only happen at a subsequent e-good stage following the activation of $a_{0}$ even though it might already be the case that $0 \in \emptyset^{'} [s + 1]$ .

0 \in \emptyset^{'}

and that the ongoing construction of

P_{e}

will proceed entirely in the interval

(b_{0}, a_{0})

for the time being. If, at some e-good stage

t + 1 > s + 1

strategy

Q_{0}

registers

0 \in \emptyset^{'}

(i.e. receives attention) then

a_{0}

will be repainted blue and the construction will switch to constructing

P_{e}

in the interval

(d_{0}, c_{0})

We now consider the general case of a subsequent e-good stage $t + 1 > s + 1$ . We suppose that, for some $n ⩾ 0$ precisely the set ${a_{0}, \dots, a_{n}}$ has been defined (with the associated elements $b_{i}, c_{i}, d_{i}$ for each $0 ⩽ i ⩽ n$ ) and that there are elements ${a_{i_{0}}, \dots, a_{i_{h}}} \subseteq {a_{0}, \dots, a_{n}}$ such that $a_{i_{r}}$ is r-active for each $0 ⩽ r ⩽ h$ . By definition there is also an active interval which is the (smallest) interval in which the next element $a_{n + 1}$ will be defined (provided that the next e-good stage is not a $\emptyset^{'}$ -coding stage as defined below). Note that the active interval contains two elements labelled $x, y$ such that $x |_{P} y$ . There are two cases. Notation.

Strategy $Q_{i}$ requires attention at e-good stage s if there is a red i-active element $a_{m}$ (at the beginning of stage s) and $i \in \emptyset^{'} [s]$ . We say that s is a $\emptyset^{'}$ -coding stage if there is a strategy $Q_{i}$ that requires attention at stage s.

Remark.

To facilitate understanding of the construction we recommend a brief first reading of the Cases below combined with inspection of the ensuing example.

Case A.

t + 1

is not a

\emptyset^{'}

-coding stage. There are two subcases.

Case A(i). The active interval is $(b_{n}, a_{n})$ . This means that $a_{i_{h}} = a_{n}$ and that $a_{n}$ is red. Also – as $t + 1$ is an e-good stage – for some $u, v \in {x, y}$ , $u R_{e} v$ is 1-computed at stage $t + 1$ . Accordingly the $x, y$ labels are removed with u being relabelled $c_{n + 1}$ and v being relabelled $b_{n + 1}$ . Moreover four new elements $a_{n + 1}, d_{n + 1}, x, y$ are added to $P_{e} [t]$ to obtain $P_{e} [t + 1]$ in such a way that $b_{n} <_{P} d_{n + 1} <_{P} c_{n + 1}$ , $b_{n + 1} <_{P} x <_{P} a_{n + 1} <_{P} a_{n}$ , $b_{n + 1} <_{P} y <_{P} a_{n + 1} <_{P} a_{n}$ and $x |_{P} y$ , similarly to the case $n = - 1$ described above. The element $a_{n + 1}$ is $h + 1$ -activated and painted red.14

¹⁴

I.e. the strategy $Q_{h + 1}$ has commandeered the intervals $(d_{n + 1}, c_{n + 1})$ and $(b_{n + 1}, a_{n + 1})$ and now waits for further e-good stages to register (or not) that $h + 1 \in \emptyset^{'}$ .

The active interval is now

(b_{n + 1}, a_{n + 1})

Case A(ii). The active interval is $(d_{m}, c_{m})$ for some $0 ⩽ m ⩽ n$ . Note that this means that $a_{i_{h}} = a_{m}$ and that $a_{m}$ is blue; also that, for any $m ⩽ l ⩽ n$ , $a_{l}$ has been disactivated. Note also that each such $a_{l}$ was previously j-activated for some $j > h$ but was, by definition of the construction, disactivated at the previous e-good stage $t^{'} + 1$ (if not already disactivated) since the fact that $(d_{m}, c_{m})$ is the active interval implies that $Q_{h}$ received attention at stage $t^{'} + 1$ . Notice also that we will be able to show that, if $n > m$ , the set ${a_{m + 1}, \dots, a_{n}}$ lies within the interval $(b_{m}, a_{m})$ and forms a descending sequence under $R_{e}$ (i.e. $a_{n} R_{e} \dots R_{e} a_{m + 1}$ ). Now just as in Case A(i) we have $u, v \in {x, y}$ such that $u R_{e} v$ is 1-computed at stage $t + 1$ . So, as before, the $x, y$ labels are removed with u being relabelled $c_{n + 1}$ and v being relabelled $b_{n + 1}$ . Once again four new elements $a_{n + 1}, d_{n + 1}, x, y$ are added to $P_{e} [t]$ to obtain $P_{e} [t + 1]$ but this time in such a way that $d_{m} <_{P} d_{n + 1} <_{P} c_{n + 1}$ , $b_{n + 1} <_{P} x <_{P} a_{n + 1} <_{P} c_{m}$ , $b_{n + 1} <_{P} y <_{P} a_{n + 1} <_{P} c_{m}$ and $x |_{P} y$ . Also, as before, the element $a_{n + 1}$ is $h + 1$ -activated and painted red. The active interval is now $(b_{n + 1}, a_{n + 1})$ .

Case B. $t + 1$ is a $\emptyset^{'}$ -coding stage. This means that, for some $0 ⩽ j ⩽ h$ strategy $Q_{j}$ requires attention – i.e. $a_{i_{j}}$ is red and $j \in \emptyset^{'} [s + 1]$ . Picking the least such j and letting $m = i_{j}$ , $Q_{j}$ now repaints $a_{m}$ blue and disactivates all $a_{l}$ such that $m < l ⩽ n$ . Note that this disactivation only actually involves elements $a_{i_{r}}$ such that $j < r ⩽ h$ since any other such $a_{l}$ are already disactivated by definition of the construction. The $x, y$ labels are removed from the two elements contained in the present active interval, and two new elements $x, y$ are added to $P_{e} [t]$ to obtain $P_{e} [t + 1]$ in such a way that $d_{m} <_{P} x <_{P} c_{m}$ , $d_{m} <_{P} y <_{P} c_{m}$ and $x |_{P} y$ . The active interval is now $(d_{m}, c_{m})$ .

This ends the description of the construction. However in order to illustrate the underlying mechanics we consider a particular hypothetical example. Example.

We suppose that there are at least four e-good stages $s + 1, s_{1} + 1, s_{2} + 1, s_{3} + 1$ and that $0 \in \emptyset^{'} [s_{2} + 1]$ whereas $0 \notin \emptyset^{'} [s_{1} + 1]$ . We have that $P_{e} [s + 1]$ is represented in Fig. 1 with $a_{0}$ 0-activated and red and with $(b_{0}, a_{0})$ now the active interval. At stage $s_{1} + 1$ Case A(i) applies resulting in $P_{e} [s_{1} + 1]$ as shown in Fig. 2. $a_{1}$ is 1-activated and red and $(b_{1}, a_{1})$ is now the active interval. At stage $s_{2} + 1$ Case B applies with $Q_{0}$ receiving attention resulting in $P_{e} [s_{2} + 1]$ . Accordingly $a_{0}$ is repainted blue, $a_{1}$ is disactivated and the active interval now becomes $(d_{0}, c_{0})$ . At stage $s_{3} + 1$ case A(ii) applies resulting in $P_{e} [s_{3} + 1]$ . $a_{2}$ is now 1-activated and red and $(b_{2}, a_{2})$ has become the active interval.

Figure 2.

Example stages of the construction of $P_{e}$ with $w <_{P} z$ and $w' R_{e} z'$ denoted by $w \cdot - \leftarrow \cdot z$ and $w' \cdot \cdot \cdot \cdot R_{e} \cdot \cdot \cdot \cdot z'$ respectively.

Note in the above example that – under the assumption that there are infinitely many e-good stages – we now have $a_{2} R_{e} a_{1} R_{e} a_{0}$ as $R_{e}$ is computably enumerable. Also notice that $a_{0}$ remains permanently 0-active whereas the 1-active element was redefined once. In fact more generally it is clear by construction that, for any $i ⩾ 0$ , after an i-active element is defined, it can be redefined up to $2^{i} - 1$ times. The reader might also observe that if 0 had entered $\emptyset^{'}$ only after several e-good stages the 1-active element would have been redefined as some $a_{n}$ with $n > 2$ .

Verification of Case 1.

Note firstly that if there are only finitely many e-good stages then $P_{e}$ will be finite and so will not embed an infinite chain. Also, an easy contrapositive argument shows us that, if $R_{e}$ linearises $P_{e}$ , then there will be infinitely many e-good stages. We thus assume without loss of generality that there are infinitely many e-good stages.

Now consider any e-good stage s and let $n_{s}$ be the greatest n such that $a_{n_{s}}$ is defined at stage s. Then Case A must apply, and so $a_{n_{s} + 1}$ is defined, at one of the subsequent $n_{s} + 2$ e-good stages (as the construction “runs out” of elements to which to apply Case B). It follows by induction on n that $a_{n}$ is defined for all $n ⩾ 0$ .

Also the existence of infinitely many e-good stages and the fact that $R_{e}$ is c.e. means that, for any $n ⩾ 0$ , $c_{n} R_{e} b_{n}$ and moreover that this fact can be decided at the stage at which $c_{n}$ and $b_{n}$ are defined.

Arguing by induction over indices we see that, for each $i ⩾ 0$ , there will be a stage $t_{i}$ at which some element $a_{n}$ is permanently i-activated (i.e. not disactivated at any subsequent stage). We call such an element $a_{n}$ the $Q_{i}$ witness.

Let $T (s + 1)$ denote the statement that, for all indices $0 ⩽ m < n$ and j satisfying the conjunction of conditions (i), (ii) and (iii) below, it is the case that $b_{m} <_{P} u_{n}$ , for each $u \in {a, b, c, d}$ .

$a_{m}$ is j-active and red at the beginning of stage $s + 1$ .

$a_{n}$ is defined at or before stage $s + 1$ .

$a_{m}$ is still j-active at the end of stage $s + 1$ (although not necessarily red).

Then using induction over the e-good stages of the construction we deduce that, for any such stage

s + 1

T (s + 1)

is true.

Now consider $n ⩾ 0$ and let $t + 1$ be the stage at which $a_{n + 1}$ is defined. Thus $t + 1$ is an e-good stage and $a_{n}$ was already defined before the end of the previous e-good stage $s + 1$ . Note that necessarily Case A of the construction applies at stage $t + 1$ . If Case A(i) applies then $a_{n + 1} <_{P} a_{n}$ so that a fortiori $a_{n + 1} R_{e} a_{n}$ . Also Case A(ii) only applies if Case B applied at stage $s + 1$ so that – using the notation from the construction above – either $m = n$ , so that $b_{m} <_{P} a_{n}$ by construction, or otherwise $m < n$ in which case $b_{m} <_{P} a_{n}$ due to the truth of $T (s + 1)$ . But then $a_{n + 1} <_{P} c_{m} R_{e} a_{n}$ (as $c_{m} R_{e} b_{m}$ ) so that, once again, $a_{n + 1} R_{e} a_{n}$ . It follows that, if $R_{e}$ linearises $P$ (and thus also its subcomponent $P_{e}$ ), then ${a_{n}}_{n \in N}$ is a $ω^{*}$ sequence in $(P_{e}, R_{e} ↾ P_{e})$ . Clearly also ${a_{n}}_{n \in N}$ is computable.

Now suppose that $S = (S, <_{P} ↾ S)$ is an infinite chain in $P_{e}$ . Enumerate S until an element is found in either the interval $[b_{0}, a_{0}]$ or the interval $[d_{0}, c_{0}]$ . (In fact in this first case we only need to enumerate three elements of S.) Note that only one of these intervals I is infinite and thus I must contain elements from S whereas, as $S$ is a chain in $P_{e}$ the other interval cannot contain any element of S. Note also that establishing which interval contains a member of S immediately decides $\emptyset^{'} (0)$ . Moreover this information combined with simulation of the construction allows the $Q_{1}$ witness $a_{n}$ , to be computed. Then the same query made relative to the intervals $[b_{n}, a_{n}]$ and $[d_{n}, c_{n}]$ decides $\emptyset^{'} (1)$ and allows the $Q_{2}$ witness to be computed. Continuing in this way we see that $\emptyset^{'}$ is computable in $S$ (and in fact in the set S itself).

Case 2: $k = 2$ . Remark.

$k = 2$ implies that $R_{e}$ is 2-c.e. and that ${R_{e} [s]}_{s \in N}$ is a 2-c.e. approximation to $R_{e}$ .

The construction proceeds as in the case $k = 1$ except that there are now 2 Levels. At stage $e + 1$ , $P_{e} [e + 1]$ is defined as in the case $k = 1$ with $a_{- 1}, b_{- 1}, x, y$ being added (as in Fig. 1) with the difference here that we consider these labels to be Level 1 as also $(b_{- 1}, a_{- 1})$ to be the Level 1 base interval and the present Level 1 active interval. We also apply Level 2 labels $a_{- 1}^{'}, b_{- 1}^{'}$ to the elements already labelled $a_{- 1}, b_{- 1}$ and consider $(b_{- 1}^{'}, a_{- 1}^{'})$ to be the Level 2 base interval and the present Level 2 active interval.

Note here that Level 2 is the controlling level of the construction. The Level 2 construction begins by passing control to Level 1 so that the construction now continues precisely as before for as long as there is no n such that $a_{n}$ (and $b_{n}, c_{n}, d_{n}$ ) is defined and $b_{n} R_{e} c_{n}$ is 2-computed (∗). (Remember that $a_{n}, b_{n}, c_{n}, d_{n}$ are defined when $c_{n} R_{e} b_{n}$ is first 1-computed.) Note that it may be the case that the whole of the construction remains Level 1 – i.e. if (∗) occurs for no n. However, for the general case we suppose that there is a (least) e-good stage $s + 1$ such that $b_{n} R_{e} c_{n}$ is 2-computed for some n. Then the Level 2 construction intervenes and, choosing the pair $b_{n}, c_{n}$ such that n is least (if there are several such pairs) relabels $b_{n}$ as $c_{0}^{'}$ and $c_{n}$ as $b_{0}^{'}$ and adds four new elements $a_{0}^{'}, d_{0}^{'}, x, y$ to $P_{e} [s]$ to obtain $P_{e} [s + 1]$ in such a way that $b_{- 1}^{'} <_{P} d_{0}^{'} <_{P} c_{0}^{'}$ , $b_{0}^{'} <_{P} x <_{P} a_{0}^{'} <_{P} a_{- 1}^{'}$ , $b_{0}^{'} <_{P} y <_{P} a_{0}^{'} <_{P} a_{- 1}^{'}$ and $x |_{P} y$ precisely as in Fig. 1 but with prime labels added. The Level 2 construction now abandons the preceding Level 1 definitions and all elements not bearing a Level 2 label are henceforth ignored.

Note that $a_{0}^{'}, d_{0}^{'}$ are defined to be $<_{P}$ -incomparable with all elements u bearing only a Level 1 label except if $u <_{P} b_{0}^{'}$ or $c_{0}^{'} <_{P} u$ when the fact that $b_{0}^{'} <_{P} a_{0}^{'}$ and $d_{0}^{'} <_{P} c_{0}^{'}$ induces $<_{P}$ -comparability (due to the fact that we are constructing $<_{P}$ to be transitive). Since Level 2 builds in new elements to be as incomparable as possible with Level 1 elements in this way we see that the unused Level 1 elements merely leave a finite amount of “background noise” in the Level 2 construction. It is important to note that this is an ongoing feature of the Level 2 construction and so, as the latter proceeds, the unused Level 1 elements can be safely ignored without impairing the outcome of the construction.

The element $a_{0}^{'}$ is now 0-activated and painted red and the interval $(b_{0}^{'}, a_{0}^{'})$ becomes the Level 2 active interval. Note that 0-activation of $a_{0}^{'}$ means that the intervals $(d_{0}^{'}, c_{0}^{'})$ and $(a_{0}^{'}, b_{0}^{'})$ have been commandeered by the strategy $Q_{0}$ working at Level 2 in precisely the same way that this happened at Level 1. The Level 2 construction now resets $a_{- 1} = a_{0}^{'}$ and $b_{- 1} = b_{0}^{'}$ thereby stipulating that $(a_{0}^{'}, b_{0}^{'})$ is the new Level 1 base interval, and the ongoing Level 1 active interval, and that the Level 1 construction must start again from scratch in this interval. In this way the Level 2 construction effectively passes control back to the Level 1 construction which can be thought of as starting in a new incarnation (so that we can reuse the Level 1 labels without ambiguity). It will now only intervene in the ongoing Level 1 construction if there is an e-good stage $t + 1$ at which $Q_{0}$ requires attention at Level 2 or if it finds some pair $b_{m}, c_{m}$ (under the present reincarnated labelling) such that $b_{m} R_{e} c_{m}$ is 2-computed. In the first case it introduces new elements $x |_{P} y$ to the interval $(d_{0}^{'}, c_{0}^{'})$ , paints $a_{0}^{'}$ blue and resets $(d_{0}^{'}, c_{0}^{'})$ to be the Level 2 active interval and, in so doing, resets $b_{- 1} = d_{0}^{'}$ and $a_{- 1} = c_{0}^{'}$ . In the second case the Level 2 construction determines the least m such that $b_{m} R_{e} c_{m}$ is 2-computed at stage $t + 1$ , relabels $b_{m}$ as $c_{1}^{'}$ and $c_{m}$ as $b_{1}^{'}$ and adds new elements $a_{1}^{'}, d_{1}^{'}, x, y$ in such a way that $b_{0}^{'} <_{P} d_{1}^{'} <_{P} c_{1}^{'}$ , $b_{1}^{'} <_{P} x <_{P} a_{1}^{'} <_{P} a_{0}^{'}$ , $b_{1}^{'} <_{P} y <_{P} a_{1}^{'} <_{P} a_{0}^{'}$ and $x |_{P} y$ . It paints $a_{1}^{'}$ red and resets the Level 2 interval to be $(b_{1}^{'}, a_{1}^{'})$ and, in so doing resets $b_{- 1} = b_{1}^{'}$ and $a_{- 1} = a_{1}^{'}$ . In both cases all previous Level 1 work is abandoned and the Level 2 construction passes control back to Level 1 which again restarts from scratch in the newly reassigned interval $(b_{- 1}, a_{- 1})$ .

The Level 2 construction thus proceeds in precisely the same way as the Level 1 construction with the difference that Level 1 progress is dictated by registering 1-computations on pairs supplied directly by the construction whereas Level 2 progress is dictated by registering 2-computations on pairs supplied by Level 1. In other words Cases A(i), A(ii) and B are applied in precisely the same way at Level 2 with appropriate modifications made specifying the Level 1/Level 2 interactions involved.

To verify the construction in the present case we assume as in the case $k = 1$ that there are infinitely many e-good stages. In the case that only a finite number of elements $a_{n}^{'}$ are defined we know that the Level 1 base interval $(b_{- 1}, a_{- 1})$ is either never reassigned (i.e. if not even $a_{0}^{'}$ is defined) or eventually stabilises during the construction (as either $(b_{m}^{'}, a_{m}^{'})$ for some $m ⩾ - 1$ or $(d_{l}^{'}, c_{l}^{'})$ for some $l ⩾ 0$ ). Hence the verification described for the case $k = 1$ applies directly to the Level 1 construction in the (eventually permanent assignment of the) interval $(b_{- 1}, a_{- 1})$ in this case. In the case when $a_{n}^{'}$ is defined for all $n ⩾ 0$ we can now apply the same verification but at Level 2. (Notice in particular that now $c_{n}^{'} R_{e} b_{n}^{'}$ for all $n ⩾ 0$ and that this fact can be decided at the stage at which $b_{n}^{'}, c_{n}^{'}$ are defined.) Accordingly we can show, just as in the verification of the Level 1 construction, that ${a_{n}^{'}}_{n \in N}$ is a computable $ω^{*}$ sequence in $(P_{e}, R_{e} ↾ P_{e})$ and that, if $S = (S, <_{P} ↾ S)$ is an infinite chain embedded in $P_{e}$ , then we can compute $\emptyset^{'}$ by querying, for $n = 0, 1, 2, \dots$ , the intervals $[c_{n}^{'}, d_{n}^{'}]$ , $[b_{n}^{'}, a_{n}^{'}]$ for a member of S and simulating the Level 2 construction.

Case 3: $k > 2$ . Notation.

In the following we use notation of the form $a_{n}^{(0)}$ , $a_{n}^{(1)}$ to denote the labels that we previously (for simplicity) denoted respectively $a_{n}$ , $a_{n}^{'}$ (and similarly for labels involving the letters $u \in {b, c, d}$ ). Level j labels are accordingly of the form $a_{n}^{(j - 1)}, b_{n}^{(j - 1)}, c_{n}^{(j - 1)}, d_{n}^{(j - 1)}$ .

Remark.

$R_{e}$ is k-c.e. and ${R_{e} [s]}_{s \in N}$ is a k-c.e. approximation to $R_{e}$ .

This is a straightforward generalisation of the Case 2 construction but now with $k > 2$ different Levels of construction. At stage $e + 1$ , $P_{e} [e + 1]$ is defined as in the case $k = 1$ (see Fig. 1) with $a_{- 1}^{(0)}, b_{- 1}^{(0)}, x, y$ being added but this time with $a_{- 1}^{(0)}, b_{- 1}^{(0)}$ also being relabelled as $a_{- 1}^{(j - 1)}, b_{- 1}^{(j - 1)}$ for each $1 < j ⩽ k$ . Accordingly, for each $1 ⩽ j ⩽ k$ , under these different labellings we consider the (same) interval $(b_{- 1}^{(j - 1)}, a_{- 1}^{(j - 1)})$ to be the Level j base interval and ongoing Level j active interval.

Note that Level k is the controlling level of the construction. The Level k construction begins by passing control to Level $k - 1$ and in this way control cascades down the levels to Level 1. Hence the construction starts at Level 1 in precisely the way described in Case 2. Now consider some $1 < j ⩽ k$ . The Level j construction waits for a (least) e-good stage $s + 1$ and Level $j - 1$ pair $b_{n}^{(j - 2)}, c_{n}^{(j - 2)}$ such that $b_{n}^{(j - 2)} R_{e} c_{n}^{(j - 2)}$ is j-computed. If this happens the Level j construction intervenes choosing the pair $b_{n}^{(j - 2)}, c_{n}^{(j - 2)}$ such that n is least and relabelling $b_{n}^{(j - 2)}$ as $c_{0}^{(j - 1)}$ and $c_{n}^{(j - 2)}$ as $b_{0}^{(j - 1)}$ . It now adds four new elements $a_{0}^{(j - 1)}, d_{0}^{(j - 1)}, x, y$ to $P_{e} [s]$ to obtain $P_{e} [s + 1]$ in such a way that $b_{- 1}^{(j - 1)} <_{P} d_{0}^{(j - 1)} <_{P} c_{0}^{(j - 1)}$ , $b_{0}^{(j - 1)} <_{P} x <_{P} a_{0}^{(j - 1)} <_{P} a_{- 1}^{(j - 1)}$ and also $b_{0}^{(j - 1)} <_{P} y <_{P} a_{0}^{(j - 1)} <_{P} a_{- 1}^{(j - 1)}$ and $x |_{P} y$ . The Level j construction now abandons the preceding Level i definitions for all $1 ⩽ i < j$ and all elements not bearing a Level j label are henceforth ignored. The element $a_{0}^{(j - 1)}$ is 0-activated and painted red and the interval $(b_{0}^{(j - 1)}, a_{0}^{(j - 1)})$ becomes the Level j active interval.15

¹⁵

Note that 0-activation of $a_{0}^{(j - 1)}$ means that the intervals $(d_{0}^{(j - 1)}, c_{0}^{(j - 1)})$ and $(b_{0}^{(j - 1)}, a_{0}^{(j - 1)})$ have been commandeered by the strategy $Q_{0}$ working at Level j.

The Level j construction now resets

a_{- 1}^{(i - 1)} = a_{0}^{(j - 1)}

and

b_{- 1}^{(i - 1)} = b_{0}^{(j - 1)}

for all

1 ⩽ i < j

thereby stipulating that

(a_{0}^{(j - 1)}, b_{0}^{(j - 1)})

is the newly assigned Level i base interval and ongoing Level i active interval for all such i. Control gets passed back from Level j to Level

j - 1

and hence cascaded back down to Level 1 so that each Level starts again from scratch in the interval16

¹⁶

This interval is “seen” by each level $1 ⩽ i < j$ as $(a_{- 1}^{(i - 1)}, b_{- 1}^{(i - 1)})$ .

(a_{0}^{(j - 1)}, b_{0}^{(j - 1)})

. Thus we see that, for each Level

1 < j ⩽ k

the Level j construction proceeds relative to the Level

j - 1

precisely as described for

j = k = 2

relative to Level 1 in Case 2 with progress of the Level j construction dictated by registering j-computations on pairs supplied by Level

j - 1

. Note however that Level j proceeds under the proviso that its work can be interrupted by any Level

j < i ⩽ k

causing the Level j base interval to be reset and the Level j construction having to start from scratch once again. In other words Cases A(i), A(ii) and B are applied at each Level j precisely as described for the case

k = 1

with appropriate modification now specifying the Level j/Level

j - 1

interaction involved, but with the further condition that in each case, for all

1 ⩽ i < j

the Level i base interval is appropriately reassigned (as described above) and each such Level starts again from scratch.

To verify the construction we assume as before that there are infinitely many e-good stages. It follows that there is some $1 ⩽ j ⩽ k$ such that the definition of the Level j base interval $(b_{- 1}^{(j - 1)}, a_{- 1}^{(j - 1)})$ either is never reassigned or eventually stabilises and that, within this interval, $a_{n}^{(j - 1)}$ is defined for all $n ⩾ 0$ . We can now apply the verification procedure from Case 1 to the Level j construction in the interval $(b_{- 1}^{(j - 1)}, a_{- 1}^{(j - 1)})$ . (Notice once again that $c_{n}^{(j - 1)} R_{e} b_{n}^{(j - 1)}$ for all $n ⩾ 0$ and that this fact can be decided at the stage at which $b_{n}^{(j - 1)}, c_{n}^{(j - 1)}$ are defined.) Accordingly we can show that ${a_{n}^{(j - 1)}}_{n \in N}$ is a (computable) $ω^{*}$ sequence in $(P_{e}, R_{e} ↾ P_{e})$ and that, if $S = (S, <_{P} ↾ S)$ is an infinite chain embedded in $P_{e}$ then, by querying the intervals $[c_{n}^{(j - 1)}, d_{n}^{(j - 1)}]$ and $[b_{n}^{(j - 1)}, a_{n}^{(j - 1)}]$ for a member of S for $n = 0, 1, 2, \dots$ and simulating the Level j construction, we can compute $\emptyset^{'}$ . Remark.

We in fact see that this verification procedure can be bundled into two algorithms, the first of which performs a search on the k-levels of the construction and, if $P_{e}$ is infinite, extracts the $ω^{*}$ sequence in $(P_{e}, R_{e} ↾ P_{e})$ from the Level at which it is defined. The second algorithm can then be used to compute $\emptyset^{'}$ (in parallel) relative to the $ω^{*}$ sequence extracted using as oracle any infinite chain $S$ embedded in $P_{e}$ . Note that these algorithms can be defined uniformly in $e = ⟨ k - 1, i ⟩$ so that for the overall partial order $P$ we have two universal algorithms performing respectively the necessary k Level search and oracle computations relative to $P_{e}$ for any index $e ⩾ 0$ .

We now conclude from the work above that $P$ satisfies the statement of Theorem 5.1. Indeed, suppose that $R \in Σ_{< ω}^{- 1}$ linearises $P$ . Then, for some index e, $R = R_{e}$ and it follows that there are infinitely many e-good stages during the construction so that a computable $ω^{*}$ sequence is constructed in $(P_{e}, R_{e} ↾ P_{e})$ as described above. Now suppose that $S$ is an infinite chain embedded in $P$ then, as the elements in different components are mutually incomparable, there is an index e such that $S$ is entirely contained in the component $P_{e}$ and so, as we have seen, computes $\emptyset^{'}$ . It follows in particular that $P$ is computably well founded. □

Note that our construction will work for any choice of listing ${R_{e}}_{e \in N}$ of the class $Σ_{< ω}^{- 1}$ with associated effective approximation ${R_{e} [s]}_{e, s \in N}$ provided that, for each e, ${R_{e} [s]}_{s \in N}$ is a k-c.e. approximation for some k. (Moreover we will still obtain two search algorithms as described in the above Remark.17

¹⁷

Our actual choice of listing ${R_{e}}_{e \in N}$ simply makes the first algorithm “neater” in the sense that, given $e = ⟨ k - 1, i ⟩$ it knows at the start that there are k Levels involved in searching $P_{e}$ .

)

Now suppose that our listing includes a set $R_{e}$ which linearises $P$ and is ω-c.e. but is not in $Σ_{< ω}^{- 1}$ . Suppose for the sake of argument that it is also the case that, for any $⟨ u, v ⟩$ , ${R_{e} [s]}_{s \in N}$ “changes its mind” on $⟨ u, v ⟩$ at least $⟨ u, v ⟩$ times. (However there is of course by definition a computable function f such that this number of “changes of mind” is bounded by $f (⟨ u, v ⟩)$ .) The problem that now arises during the construction is that, for any Level j, if n is such that $a_{n}^{(j - 1)}$ is defined and is also (large enough) such that $⟨ c_{n}^{(j - 1)}, b_{n}^{(j - 1)} ⟩ > j$ , then $b_{n}^{(j - 1)} R_{e} c_{n}^{(j - 1)}$ will eventually be $j + 1$ -computed. Accordingly the construction of our putative $ω^{*}$ sequence at Level j will be abandoned and the Level j construction will be restarted in a base interval newly assigned by Level $j + 1$ . Since this will happen infinitely often for all j we see that the construction of an $ω^{*}$ sequence as described in Theorem 5.1 breaks down. This illustrates why our construction will, as expected, not work at the ω-c.e. level.

Theorem 5.2.

There exists a (classically) scattered computable partial order $P$ which has no computably scattered $Σ_{< ω}^{- 1}$ linear extension.

Proof.

We construct a computable partial order $P$ as a disjoint union of subpartial orders $P_{e} = (P_{e}, <_{P} ↾ P_{e})$ with no comparabilities between different components as in the proof of Theorem 5.1. We will again use the listing ${R_{e}}_{e \in N}$ with its associated computable approximation ${R_{e} [s]}_{e, s \in N}$ . We will assume the same basic definitions and notation of the construction in the proof of Theorem 5.1. In this case however we will not be trying to code $\emptyset^{'}$ and so, for example, the fundamental Level 1 construction will involve only the definitions of pairs $b_{n}, c_{n}$ (instead of the quadruples $a_{n}, b_{n}, c_{n}, d_{n}$ defined in Theorem 5.1). Accordingly the strategies $Q_{i}$ do not intervene here so that we do not need the notion of an i-active element. We will now in fact be able to talk directly about the nth active interval on any Level where for example, on Level 1, this interval is the one in which the pair $b_{n}, c_{n}$ will be defined.

Here, given index e, we will construct $P_{e}$ such that, for every element $d \in P_{e}$ , either the set ${z \in P_{e} ∣ z <_{P} d}$ is finite or otherwise the set ${z \in P_{e} ∣ d <_{P} z}$ is finite. Thus each individual such component $P_{e}$ is scattered so that, by the incomparability of elements in different components, $P$ is itself scattered. On the other hand, we will construct $P_{e}$ so that, if $R_{e}$ linearises $P$ , then there will be a computable η sequence embedded in $(P_{e}, R_{e} ↾ P_{e})$ .

The construction

We consider fixed index e and describe the construction of the associated component $P_{e}$ . Assuming that $e = ⟨ k - 1, i ⟩$ we know that ${R_{e} [s]}_{s \in N}$ is a k-c.e. approximation to $R_{e}$ and that, as before, if $k > 1$ , then the construction has k different nested Levels. Due to the similarities with the construction of Theorem 5.1 we split our description into two cases only – the case $k = 1$ and the case $k > 1$ .

Case 1: $k = 1$ .

At all stages $s ⩽ e$ by definition $P_{e} [s] = \emptyset$ . At stage $e + 1$ four new elements $b_{- 1}$ , $c_{- 1}$ , x and y are added to $P_{e} [e]$ to obtain $P_{e} [e + 1]$ in such a way that $b_{- 1} <_{P} x <_{P} c_{- 1}$ and $b_{- 1} <_{P} y <_{P} c_{- 1}$ with $x |_{P} y$ as shown in Fig. 1 under the relabelling of $a_{- 1}$ and $b_{- 1}$ by $c_{- 1}$ and $b_{- 1}$ respectively. Note once again here that everything in the present ( $k = 1$ ) case happens at Level 1 but that, for simplicity we will omit mention of the Level for the time being. The interval $(b_{- 1}, c_{- 1})$ is defined to be the 0-active interval.

Now consider the general case of the $n + 1$ st e-good stage with $n ⩾ 1$ . By definition the n-active interval is defined as $(b_{i}, c_{j})$ for some distinct $- 1 ⩽ i, j < n$ and contains precisely the two $<_{P}$ -incomparable elements presently labelled $x, y$ . We have that, for some $u, v \in {x, y}$ , $u R_{e} v$ is 1-computed. Accordingly the x, y labels are removed with $c_{n}$ now labelling the element u and $b_{n}$ labelling the element v. Remark.

The construction is working under the assumption that $b_{0}, \dots, b_{n - 1}$ forms the initial segment of an η sequence under $R_{e}$ and that the active n-interval was chosen so that now $b_{0}, \dots, b_{n - 1}, b_{n}$ will also form an initial segment of the sequence. Accordingly the choice of the $n + 1$ -active interval is now made in such a way that when (or if) $b_{n + 1}$ is defined in this interval it also will continue the η sequence. Note that, as mentioned in Section 3, we can think of the $b_{i}$ ’s as labelling nodes on a binary tree with $b_{0}$ labelling the root. Under this representation the choice of the active interval at this stage is made in terms of a process of labelling the nodes of the tree of a certain length $w + 1$ from left to right so as to “densify” the $b_{i}$ ’s which label nodes of length $⩽ w$ . Thus when this process has labelled the rightmost node of length $w + 1$ (corresponding to action taken in an active interval of the form $(b_{j}, c_{- 1})$ ) the process restarts at the leftmost node of length $w + 2$ (corresponding to a new active interval of the form $(b_{- 1}, c_{h})$ ).

Now, with the above remark and the fact that the n-active interval was defined as $(b_{i}, c_{j})$ in mind, if $j \neq - 1$ then the $n + 1$ -active interval is defined to be $(b_{j}, c_{l})$ where $c_{l}$ is the immediate $R_{e}$ -successor of $b_{j}$ . If $j = - 1$ , on the other hand, then the $n + 1$ -active interval is defined to be $(b_{- 1}, c_{h})$ where $c_{h}$ is the immediate $R_{e}$ -successor of $b_{- 1}$ . It is important to note here that in the first case $c_{l}$ is the (unique) immediate $<_{P}$ -successor of $b_{j}$ over the set ${c_{0}, \dots, c_{n - 1}}$ and that likewise in the second case $c_{h}$ is the immediate $<_{P}$ -successor of $b_{- 1}$ over this set. Thus in both cases the $n + 1$ -active interval is indeed a well defined (and empty) $<_{P}$ -interval. Also note that, by construction, $b_{j}$ is the immediate $R_{e}$ -successor of $c_{j}$ . (The properties assumed here can be easily checked during the induction argument over the e-good stages of the construction stipulated below.) Using $(b_{\hat{i}}, c_{\hat{j}})$ to denote the $n + 1$ -active interval, two new elements x and y are added to $P_{e} [s]$ to obtain $P_{e} [s + 1]$ in such a way that $b_{\hat{i}} <_{P} x <_{P} c_{\hat{j}}$ , $b_{\hat{i}} <_{P} y <_{P} c_{\hat{j}}$ and $x |_{P} y$ .

To illustrate what is happening note that, at the end of the third e-good stage $s + 1$ , $P_{e} [s + 1] ∖ {x, y}$ is as follows, $\begin{matrix} b_{- 1} <_{P} c_{1} R_{e} b_{1} <_{P} c_{0} R_{e} b_{0} <_{P} c_{2} R_{e} b_{2} <_{P} c_{- 1} \end{matrix}$ with the 3-active interval being $(b_{- 1}, c_{1})$ and the elements $x, y$ inserted into this interval. Note also that $b_{1} R_{e} b_{0} R_{e} b_{2}$ . Continuing further we find at the end of the seventh e-good stage that $\begin{matrix} b_{3} R_{e} b_{1} R_{e} b_{4} R_{e} b_{0} R_{e} b_{5} R_{e} b_{2} R_{e} b_{6} \end{matrix}$ and we see that the construction has now enumerated the first 7 elements of an η sequence (under $R_{e}$ ).

Verification of Case 1.

We assume again without loss of generality – see the proof of Theorem 5.1 – that there are infinitely many e-good stages.

Then, by induction over e-good stages we easily check that, for all $n ⩾ 0$ , at the end of the $n + 1$ st e-good stage the construction has enumerated the elements $b_{0}, \dots, b_{n}$ ordered under $R_{e}$ as the initial segment of an η sequence. Therefore our assumption that there are infinitely many e-good stages implies that the construction computes ${b_{n}}_{n \in N}$ as an η sequence (and so dense chain) under $R_{e}$ .

For all $m ⩾ 0$ , define $C_{m}$ to be the set of elements $u \in P_{e} [\hat{s} + 1]$ such that $c_{m} <_{P} u$ with $\hat{s} + 1$ being the $m + 1$ st e-good stage, i.e. the stage when $c_{m}$ is defined. We now show by induction over e-good stages that, for any such m, and e-good stage $s + 1$ such that $c_{m}$ has been defined before the end of this stage, (i) and (ii) below hold.

$C_{m} \subseteq {c_{- 1}, \dots, c_{m - 1}}$ ,

For all $u \in P_{e} [s + 1]$ , $c_{m} <_{P} u \Leftrightarrow u \in C_{m}$ .

Indeed at the first e-good stage we have $b_{- 1} <_{P} c_{0} <_{P} c_{- 1}$ and $b_{- 1} <_{P} b_{0} <_{P} c_{- 1}$ and no other $<_{P}$ -comparabilities. Therefore both (i) and (ii) hold with $C_{0} = {c_{- 1}}$ . Now at the (beginning of the) $n + 1$ st e-good stage $s + 1$ there exist $- 1 ⩽ i, j < n$ such that $(b_{i}, c_{j})$ is the n-active interval with $x, y \in (b_{i}, c_{j})$ and such that the construction relabels these elements as $b_{n}, c_{n}$ so that $c_{n} R_{e} b_{n}$ . Accordingly we have under this new labelling $b_{i} <_{P} b_{n} <_{P} c_{j}$ and $b_{i} <_{P} c_{n} <_{P} c_{j}$ and no other new comparabilities introduced beyond those dictated by the transitivity of $R_{e}$ . By the induction hypothesis relative to the nth e-good stage $t + 1$ , for each $0 ⩽ h < n$ the set $C_{h}$ is defined such that $C_{h} \subseteq {c_{- 1}, \dots, c_{h - 1}}$ and such that, for all $u \in P_{e} [t + 1]$ , $c_{h} <_{P} u \Leftrightarrow u \in C_{h}$ . This implies that, as $b_{i} \notin C_{h}$ , for all $u \in P_{e} [s + 1]$ , we also have $c_{h} <_{P} u \Leftrightarrow u \in C_{h}$ . On the other hand clearly, for $u \in P_{e} [s + 1]$ , $c_{n} <_{P} u \Leftrightarrow u \in C_{n}$ where we define $C_{n} = {c_{j}} \cup C_{j}$ . Note that our induction hypothesis (relative to $C_{h}$ for $h < n$ ) and the fact that $j < n$ implies that $C_{n} \subseteq {c_{- 1}, \dots, c_{n - 1}}$ . We thus conclude that the statement above is true. Note that this means that, for any $n ⩾ 0$ , the set of elements $<_{P}$ -above $c_{n}$ in $P_{e}$ is the finite set $C_{n}$ . A similar argument shows that, for any $n ⩾ 0$ the set of elements $<_{P}$ -below $b_{n}$ in $P_{e}$ is finite. Thus $P_{e}$ is scattered.

Case 2: $k > 1$ . Notation.

We use notation of the form $b_{n}^{(0)}$ , $c_{n}^{(0)}$ to denote the labels that we previously denoted respectively $b_{n}$ , $c_{n}$ . Level j labels are accordingly of the form $b_{n}^{(j - 1)}, c_{n}^{(j - 1)}$ .

This is a straightforward application of Cases 2 and 3 in the proof of Theorem 5.1 to the context of the present Level 1 construction. In other words the construction now has k Levels and each Level $j > 1$ processes its m-active interval by searching the Level $j - 1$ construction in this interval for a Level $j - 1$ pair $b_{n}^{(j - 2)}, c_{n}^{(j - 2)}$ such that $b_{n}^{(j - 2)} R_{e} c_{n}^{(j - 2)}$ is j-computed (whereas the Level $j - 1$ labels have been in place since $c_{n}^{(j - 2)} R_{e} b_{n}^{(j - 2)}$ was first $j - 1$ computed). When (or if) such a pair is found the Level j construction chooses the pair with least index n and relabels $c_{n}^{(j - 2)}$ as $b_{m}^{(j - 1)}$ and $b_{n}^{(j - 2)}$ as $c_{m}^{(j - 1)}$ (so that we now have $c_{m}^{(j - 1)} R_{e} b_{m}^{(j - 1)}$ ) chooses its $m + 1$ -active interval $(b_{i}^{(j - 1)}, c_{l}^{(j - 1)})$ in precisely the way that this is done at Level 1, and inserts two new elements $x, y$ such that $x |_{P} y$ in this interval. It then, for all $1 ⩽ r < j$ , resets the Level r 0-active interval to its $m + 1$ -active interval by resetting $b_{- 1}^{(r - 1)} = b_{i}^{(j - 1)}$ and $c_{- 1}^{(r - 1)} = c_{l}^{(j - 1)}$ thus causing Level r to abandon all previous work and signalling that it is to restart in this interval. Level j then passes control back to Level $j - 1$ so that the control cascades down to Level 1 and the construction restarts from scratch at all Levels $r < j$ in this interval.

The Level j construction thus proceeds precisely as described for Level 1 with the difference that it registers j-computations of pairs supplied by the Level $j - 1$ – instead of the process of registering 1-computations of pairs supplied directly by the construction as happens at Level 1 – under the proviso that its own work may be interrupted by the action of some Level t with $j < t ⩽ k$ in a similar way to that just described. It is important to note that, whenever Level j intervenes all elements of the construction that do not have a Level j label are abandoned. (Note here that an element has Level r label with $j < r ⩽ k$ only if it already has a Level j label.) Thus, for example, when Level j intervenes for the first time the only elements now relevant to the construction are $b_{- 1}^{(j - 1)}, c_{- 1}^{(j - 1)}, b_{0}^{(j - 1)}, c_{0}^{(j - 1)}$ and the newly chosen elements $x, y$ (with $b_{- 1}^{(j - 1)}, c_{- 1}^{(j - 1)}$ being the elements that were also originally labelled $b_{- 1}^{(0)}, c_{- 1}^{(0)}$ whereas $b_{0}^{(j - 1)}, c_{0}^{(j - 1)}$ is the relabelling of some pair $c_{n}^{(j - 2)}, b_{n}^{(j - 2)}$ as described above but with $m = 0$ ). Note that the abandoned elements of lower Levels once again cause a certain amount of “background noise” at Level j. However, since no $<_{P}$ -comparabilities between new elements and abandoned elements are defined (beyond those dictated by the fact that $<_{P}$ must be transitive) this “background noise” causes only finite interference to the work carried out at Level j and can thus be safely ignored.

To verify the construction for $k > 1$ we assume as before that there are infinitely many e-good stages. It follows that there is some $1 ⩽ j ⩽ k$ such that the definition of the Level 1 base interval $(b_{- 1}^{(j - 1)}, c_{- 1}^{(j - 1)})$ either is never reassigned or eventually stabilises and that, within this interval $a_{n}^{(j - 1)}$ is defined for all $n ⩾ 0$ . We can now apply the Case 1 verification procedure to the Level j construction in the interval $(b_{- 1}^{(j - 1)}, c_{- 1}^{(j - 1)})$ . (Notice that $c_{n}^{(j - 1)} R_{e} b_{n}^{(j - 1)}$ for all $n ⩾ 0$ and that this fact can be decided at the stage at which $b_{n}^{(j - 1)}, c_{n}^{(j - 1)}$ are defined.) Accordingly we can show that ${b_{n}^{(j - 1)}}_{n \in N}$ is a (computable) η sequence in $(P_{e}, R_{e} ↾ P_{e})$ and that every element in $P_{e}$ has either at most finitely elements $<_{P}$ -above it at most finitely many elements $<_{P}$ below it. (Here we take into account the abandoned elements of the construction as well as the elements $b_{n}^{(j - 1)}, c_{n}^{(j - 1)}$ .) Remark.

Similarly to before we see that the construction intrinsic to the verification procedure can be bundled into a single algorithm, which performs a search on the k-levels of the construction and, if $P_{e}$ is infinite, extracts the η sequence in $(P_{e}, R_{e} ↾ P_{e})$ from the Level at which it is defined. Note that this algorithm can be defined uniformly in $e = ⟨ k - 1, i ⟩$ so that for the overall partial order $P$ we have a universal algorithm performing the necessary k Level search relative to $P_{e}$ for any index $e ⩾ 0$ .

We now conclude from the work above that $P$ satisfies the statement of Theorem 5.2. Indeed, suppose that $R \in Σ_{< ω}^{- 1}$ linearises $P$ . Then for some index e, $R = R_{e}$ and it follows that there are infinitely many e-good stages during the construction so that a computable η sequence is constructed in $(P_{e}, R_{e} ↾ P_{e})$ as described above. Now as we have seen, for any index e the component $P_{e}$ is scattered. Thus, as elements from different components are pairwise incomparable we see that $P$ is itself scattered. □

Note 5.3.

Suppose that α is a computable order type such that $ζ ⩽ α$ . Then the computable partial order $P$ constructed in Theorem 5.2 does not embed α whereas any $Σ_{< ω}^{- 1}$ linearisation $L$ of $P$ computably embeds α (as α computably embeds into the η sequence that is constructed in $L$ ).

To end this section we turn our attention to the order type of the integers ζ. We firstly note that, given a computable partial order $P = (N, <_{P})$ which does not computably embed ζ, there is a $Δ_{5}^{0}$ linearisation of $P$ that does not computably embed ζ. Indeed let $G_{0}$ be the set of numbers a such that, for any index e, if $W_{e} \subseteq {z \in N ∣ z <_{P} a}$ , then $W_{e}$ does not define an $ω^{*}$ sequence in $P$ . Then $G_{0}$ is $Π_{3}^{0}$ . Also, letting $G_{1} = N ∖ G_{0}$ (so that $G_{1}$ is $Σ_{3}^{0}$ ) we see that, as $P$ does not computably embed ζ, for any $b \in G_{1}$ and all indices e, if $W_{e} \subseteq {z \in N ∣ b <_{P} z}$ , then $W_{e}$ does not define an ω sequence in $P$ . Moreover, for any $a \in G_{0}$ and $b \in G_{1}$ it is not the case that $b <_{P} a$ . Hence, as both $G_{0}$ and $G_{1}$ are $\emptyset^{(3)}$ -computable, using our construction in the proof of Theorem 4.8 (or Rosenstein’s construction proving Theorem 2.1), relativised to $\emptyset^{(3)}$ we obtain $\emptyset^{(4)}$ -computable linearisations $L_{0}$ and $L_{1}$ of $(G_{0}, <_{P} ↾ G_{0})$ and $(G_{1}, <_{P} ↾ G_{1})$ respectively such that $L_{0}$ does not computably embed $ω^{*}$ and $L_{1}$ does not computably embed ω. Thus $L = L_{0} + L_{1}$ is a $Δ_{5}^{0}$ linearisation of $P$ that does not computably embed ζ. So the question that now arises is whether, using more delicate arguments, we can find such a linearisation $L$ which is $Δ_{2}^{0}$ or even ω-c.e. We now answer this question in the negative.

Theorem 5.4.

There exists a computable partial order $P$ which does not embed ζ such that any $Δ_{2}^{0}$ linearisation of $P$ computably embeds ζ.

Proof.

For the present proof we assume that ${R_{e}}_{e \in N}$ is a listing of the class of $Σ_{2}^{0}$ sets with associated effective $Σ_{2}^{0}$ approximation ${R_{e} [s]}_{e, s \in N}$ . In other words – using in addition our identification of numbers with pairs coded by $⟨ \cdot, \cdot ⟩$ – we have that, for all indices e, $\begin{matrix} R_{e} = {⟨ n, m ⟩ ∣ \exists t (\forall s ⩾ t) [R_{e} (⟨ n, m ⟩) [s] = 1]} \end{matrix}$ and that, for every $Σ_{2}^{0}$ set R, there is some e such that $R = R_{e}$ .

We construct a computable partial order $P$ as a disjoint union of subpartial orders $P_{e}$ with no $<_{P}$ -comparabilities between different components as in the proofs of Theorem 5.1 and 5.2 with the main difference that this time we use the $Σ_{2}^{0}$ approximation ${R_{e} [s]}_{e, s \in N}$ . Again we assume the basic definitions of our earlier proofs but with an ingredient of simplification which will be described below.

Given index e we will construct $P_{e} = (P_{e}, <_{P} ↾ P_{e})$ such that, for every chain $L$ in $P_{e}$ , if $L$ is not finite, then it has order type either $ω^{*}$ or ω. Our construction will also ensure that, if $(N, R_{e})$ linearises $P$ then there will be a computable copy of ζ embedded in $(P_{e}, R_{e} ↾ P_{e})$ .

The construction

We consider fixed index e and describe the construction of the associated component $P_{e}$ . At all stages $s ⩽ e$ by definition $P_{e} [s] = \emptyset$ . At stage $e + 1$ two new elements x and y are added to $P_{e} [e]$ to obtain $P_{e} [e + 1]$ in such a way that $x |_{P} y$ . We say that $s + 1$ is an e-good18

¹⁸

If we choose ${R_{e}}_{e \in N}$ and its $Σ_{2}^{0}$ approximation such that, for every $Σ_{2}^{0}$ (so in particular every $Δ_{2}^{0}$ ) set R there is an index e such that $R = R_{e}$ and the approximation ${R_{e} [s]}_{s \in N}$ has infinitely many good stages – i.e. stages s such that $R_{e} [s] \subseteq R_{e}$ – then we can apply the definition of e-good stage from our earlier proofs. However since this approach is not necessary here, for simplicity we apply the above modified version of e-goodness.

stage during the present construction if

R_{e} [s + 1]

linearises the subcomponent of

P_{e}

comprising these two

<_{P}

-incomparable elements (whatever the ongoing labelling of the elements). Note that, as before, the set of e-good stages is computable.

We suppose, for the sake of the present argument, that the set of e-good stages is nonempty (and sufficiently large). At the first e-good stage $s + 1 > e + 1$ we have that, for some $u, v \in {x, y}$ , $u R_{e} v$ is 1-computed. We now remove the x, y labels and label the element u as c and v as b. We also add two new elements $a_{0}$ and $d_{0}$ to $P_{e} [s]$ to obtain $P_{e} [s + 1]$ such that $d_{0} <_{P} c$ and $b <_{P} a_{0}$ (with no other $<_{P}$ -comparabilities introduced). Note that the idea is that $d_{0}$ is to be the second element of an $ω^{*}$ sequence in $P_{e}$ and $a_{0}$ is to be the second19

¹⁹

From the point of view of Note 5.5 below $d_{0}$ and $a_{0}$ are respectively the first elements of the $ω^{*}$ and ω sequences.

element of an ω sequence in

P_{e}

. Accordingly at each subsequent e-good stage for as long as

b R_{e} c

is not 2-computed – i.e.

c R_{e} b

is 1-computed at every such stage – the construction adds two new elements so as to continue building an

ω^{*}

sequence

<_{P}

-below c and an ω sequence

<_{P}

-above b in

P_{e}

. Thus for

n > 0

, if

c R_{e} b

is 1-computed at the

n + 1

st e-good stage

s + 1

, then

P_{e} [s]

is made up of the two chains

d_{n - 1} <_{P} \dots <_{P} d_{0} <_{P} c

and

b <_{P} a_{0} <_{P} \dots <_{P} a_{n - 1}

and two new elements

d_{n}, a_{n}

are added so that

P_{e} [s + 1]

is made up of

d_{n} <_{P} d_{n - 1} <_{P} \dots <_{P} d_{0} <_{P} c

and

b <_{P} a_{0} <_{P} \dots <_{P} a_{n - 1} <_{P} a_{n}

In the spirit of our earlier proofs we say that the construction is Level 1 for as long as $b R_{e} c$ is not 2-computed. Note that clearly, if there are infinitely many e-good stages and the construction remains permanently at Level 1, then $P_{e}$ will consist of a copy of $ω^{*}$ with first element c and a copy of ω with first element b (with no comparabilities between pairs of elements in the two different chains). If – as will generally be the case – there is an e-good stage at which $b R_{e} c$ is 2-computed then the construction abandons the Level 1 construction and moves to Level 2 which means that it starts building – from the first such e-good stage onwards – an $ω^{*}$ sequence $<_{P}$ -below b and an ω sequence $<_{P}$ -above c in $P_{e}$ . Level 2 now continues constructing these sequences at all e-good stages for as long $c R_{e} b$ is not 3-computed at any such stage. If $c R_{e} b$ is eventually 3-computed the construction abandons the Level 2 construction and moves to Level 3 which starts from scratch building an $ω^{*}$ sequence $<_{P}$ -below c, whose elements are $<_{P}$ -incomparable with the (finite) Level 1 chain previously built $<_{P}$ -below c, and an ω sequence $<_{P}$ -above b, whose elements are likewise $<_{P}$ -incomparable with the Level 1 chain previously built $<_{P}$ -above b.

Overall the construction proceeds in Levels in a similar way to that outlined above for Levels 1-3 with the construction always working at some specific Level $k ⩾ 1$ . Now supposing without loss of generality that k is odd – noting that the case when k is even is the same with the roles of b and c inverted – the construction remains at Level k, provided that at every intervening e-good stage $c R_{e} b$ is k-computed. Meanwhile the construction proceeds to build (at each e-good stage) an $ω^{*}$ sequence $<_{P}$ -below c, whose elements are $<_{P}$ -incomparable with all elements belonging to chains previously built $<_{P}$ -below c, and an ω sequence $<_{P}$ -above b, whose elements are likewise $<_{P}$ -incomparable with all elements belonging to chains previously built $<_{P}$ -above b. (Notice that the chains concerned are those built at Levels i with $i < k$ and i odd.) If however $b R_{e} c$ is $k + 1$ computed at some subsequent e-good stage, then the construction moves to Level $k + 1$ and starts from scratch building sequences $<_{P}$ -below b and $<_{P}$ -above c satisfying the same (incomparability) conditions as those just described with k being replaced by $k + 1$ and b and c swapped.

Verification

We assume again without loss of generality, as in the proofs of Theorem 5.1 and 5.2 – that there are infinitely many e-good stages (otherwise $P_{e}$ is finite and it cannot be the case that $R_{e}$ linearises $P$ ). Notice that elements b and c are permanently defined from the first e-good stage onwards. There are two cases. The first is the case in which the construction processes Level k for all $k ⩾ 1$ . Note that this means that there will be infinitely many pairwise $<_{P}$ -incomparable finite chains built $<_{P}$ -below b and infinitely many pairwise $<_{P}$ -incomparable finite chains built $<_{P}$ -above b and likewise for c in place of b. Moreover any maximal chain either includes b and is made up of b added to one of the finite chains built $<_{P}$ -below b and to one of the finite chains built $<_{P}$ -above b, or otherwise includes c and has the same description with c swapped for b. I.e. any such chain is finite. The second case is when there is a Level k such that, from some stage onwards the construction remains at Level k. Then, supposing without loss of generality that k is odd, $P_{e}$ is made up of an $ω^{*}$ sequence with c as first element and an ω sequence with b as first element – with no $<_{P}$ -incomparabilities between members of the different sequences – and a finite part corresponding to action taken at levels $i < k$ (i.e. the “background noise” of the construction of $P_{e}$ ). It follows therefore that in both cases $P_{e}$ does not embed ζ. Moreover since the present description applies to all indices e and the subcomponents $P_{e}$ of $P$ are pairwise $<_{P}$ -incomparable we see that $P$ itself does not embed ζ.

Now suppose that $R_{e}$ linearises $P$ . Suppose also, without loss of generality, that $b R_{e} c$ . Then there is a stage $t_{e} > e + 1$ such that, for all $s ⩾ t_{e}$ , $R_{e} (⟨ b, c ⟩) [s] = 1$ . Moreover, as $R_{e}$ linearises $P$ and ${R_{e} [s]}_{s \in N}$ is a $Σ_{2}^{0}$ approximation to $R_{e}$ we know that for infinitely many stages $s ⩾ t_{e}$ , $R_{e} (⟨ c, b ⟩) [s] = 0$ . However clearly each one of these stages is an e-good stage of the construction. Moreover the construction is at some fixed level k at all such stages (where $k - 1$ is in effect the total number of “changes of mind” of $R_{e}$ relative to the pair b,c at previous e-good stages of the construction.) Thus, as already mentioned above, c is the first element of an $ω^{*}$ sequence and b is the first element of an ω sequence in $P_{e}$ . Also, since $c R_{e} b$ and $R_{e}$ linearises $P_{e}$ we have a copy of ζ in $(P_{e}, R_{e} ↾ P_{e})$ . Clearly this copy of ζ is computable by construction. This concludes the proof of Theorem 5.4 given that, for any $Δ_{2}^{0}$ set R, there is some e such that20

²⁰

Note that any $R_{e}$ that linearises $P = (N, <_{P})$ is $Δ_{2}^{0}$ . This is a special case of the fact (already mentioned in the unrelativised case in the Introduction) that, for any set A, any linear order which is either A-c.e. or A-co-c.e. but which has A-computable domain is in fact A-computable. (In the present case $R_{e}$ is A-c.e. for $A = \emptyset^{'}$ .) Note also that we can also easily prove that $R_{e}$ is $Δ_{2}^{0}$ directly in this case by including an analysis of the ages of both the element $⟨ n, m ⟩$ and $⟨ m, n ⟩$ in the approximation ${R_{e} [s]}_{s \in N}$ . Notice moreover that we could assume our (choice of) listing ${R_{e}}_{s \in N}$ to be such that, if R is $Δ_{2}^{0}$ then there is an index such that $R = R_{e}$ with ${R_{e} [s]}_{s \in N}$ being a $Δ_{2}^{0}$ approximation. We do not make this assumption as it does not simplify our argument.

R = R_{e}

. □

Note 5.5.

Let α and β be infinite computable order types for which there exist, respectively, computable copies $L_{α}^{+}$ and $L_{β}^{-}$ of $α + 1$ and $1 + β$ such that neither $L_{α}^{+}$ nor $L_{β}^{-}$ computably embeds the order type $α + β$ . (In particular, this is obviously the case when both $α + β ⩽̸ α + 1$ and $α + β ⩽̸ 1 + β$ .) Then by modifying the construction in the proof of Theorem 5.4 to construct $L_{α}^{+}$ instead of a copy of $ω^{*}$ ( $= ω^{*} + 1$ ) and $L_{β}^{-}$ instead of a copy of ω ( $= 1 + ω$ ) we see that, for any such α and β, there exists a computable partial order $P$ which does not computably embed $α + β$ such that any $Δ_{2}^{0}$ linearisation of $P$ computably embeds $α + β$ . Moreover, if in fact $α + β ⩽̸ α + 1$ and $α + β ⩽̸ 1 + β$ , then the first “computably” in this statement can be dropped. Thus, for example, we could replace ζ by the order type $ω + ω^{*}$ in the statement of Theorem 5.4.

Note 5.6.

Suppose that in the construction of $P$ in the proof of Theorem 5.4, for all $e ⩾ 0$ , we use the component $P_{2 e}$ (instead of $P_{e}$ ) to “diagonalise” against $R_{e}$ – i.e. to ensure that, if $R_{e}$ linearises $P$ , then $(P_{2 e}, R_{e} ↾ P_{2 e})$ computably embeds ζ – and that we use component $P_{2 e + 1}$ to code $\emptyset^{'} (e)$ as in the proof of Claim 1 of Theorem 3 in [6] (choosing f such that $Ran f = \emptyset^{'}$ ). Note that we can do this as follows. We name the first two elements to be put into $P_{2 e + 1}$ as $x_{e}$ , $y_{e}$ (instead of using the temporary labels x, y as in the above proof). Then at every subsequent stage, for as long as we see that e has not entered $\emptyset^{'}$ , we add two new elements in such a way as to progressively construct a copy of $ω^{*}$ $<_{P}$ -below $x_{e}$ and a copy of ω $<_{P}$ -above $y_{e}$ in $P_{2 e + 1}$ . However if we see that e enters $\emptyset^{'}$ then we switch to building a copy of $ω^{*}$ $<_{P}$ -below $y_{e}$ and a copy of ω $<_{P}$ -above $x_{e}$ in $P_{2 e + 1}$ . Then we find that any linearistion $L = (N, <_{L})$ of $P$ which does not computably embed ζ is not only not $Δ_{2}^{0}$ but also computes the halting set $\emptyset^{'}$ since $\emptyset^{'} = {e ∣ x_{e} <_{L} y_{e}}$ . In other words this variant of the construction forces the Turing degree of such $L$ to be strictly above ${0^{'}}_{}$ , the Turing degree of $\emptyset^{'}$ . Observe also that Note 5.5 can again be applied to this result.

References

M.M.

Arslanov, The Ershov hierarchy, in: Computability in Context: Computation and Logic in the Real World,

S.B.

Cooper and

Sorbi, eds, World Scientific, 2011, pp. 49–100. doi:10.1142/9781848162778_0003.

Bonnet, Stratifications et extension des genres de chaınes dénombrables, CR Acad. Sci. Paris Sér. AB269 (1969), A880–A882.

Bonnet and

Pouzet, Linear extensions of ordered sets, in: Ordered Sets, Springer, 1982, pp. 125–170. doi:10.1007/978-94-009-7798-3_4.

S.B.

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

Downey, Computability theory and linear orderings, in: Handbook of Recursive Mathematics Volume 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. doi:10.1016/S0049-237X(98)80047-5.

R.G.

Downey,

D.R.

Hirschfeldt,

Lempp and

Solomon, Computability-theoretic and proof-theoretic aspects of partial and linear orderings, Israel Journal of Mathematics138 (2003), 271–289. doi:10.1007/BF02783429.

Y.L.

Ershov, A certain hierarchy of sets I, Algebra and Logic7(1) (1968), 47–74. doi:10.1007/BF02218750.

Y.L.

Ershov, A certain hierarchy of sets II, Algebra and Logic7(4) (1968), 15–47. doi:10.1007/BF02218664.

Y.L.

Ershov, A hierarchy of sets III, Algebra and Logic9 (1970), 34–51.

10.

Gay, Computably extendible order types, PhD thesis, The University of Leeds, UK, 2016, available online at http://etheses.whiterose.ac.uk/13976.

11.

K.I.

Lee, Automorphisms and linearisations of computable orderings, PhD thesis, The University of Leeds, UK, 2011, available online at http://etheses.whiterose.ac.uk/2166.

12.

Nies, Computability and Randomness, Oxford University Press, Oxford, New York, 2009.

13.

P.G.

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

14.

J.G.

Rosenstein, Recursive linear orderings, North-Holland Mathematics Studies99 (1984), 465–475. doi:10.1016/S0304-0208(08)73836-2.

15.

R.I.

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

16.

Weber, Computability Theory, American Mathematical Society, 2012.