THE SETTLING-TIME REDUCIBILITY ORDERING

BARBARA F. CSIMA AND RICHARD A. SHORE

Abstract. To each computable enumerable (c.e.) set A with a particular enumeration {A_{s}}_{s∈ω}, there is associated a settling function m_{A}(x), where m_{A}(x) is the last stage when a number less than or equal to x was enumerated into A. One c.e. set A is settling time dominated by another set B (B >_{st} A) if for every computable function f, for all but finitely many x, m_{B}(x) > f(m_{A}(x)). This settling-time ordering, which is a natural extension to an ordering of the idea of domination, was first introduced by Nabutovsky and Weinberger in [3] and Soare [6]. They desired a sequence of sets descending in this relationship to give results in differential geometry. In this paper we examine properties of the <_{st} ordering. We show that it is not invariant under computable isomorphism, that any countable partial ordering embeds into it, that there are maximal and minimal sets, and that two c.e. sets need not have an inf or sup in the ordering. We also examine a related ordering, the strong settling-time ordering where we require for all computable f and g, for almost all x, m_{B}(x) > f(m_{A}(g(x))).

August 24, 2006

1. Introduction

This paper concerns the settling-time reducibility ordering on c.e. sets, which we now define.

Definition 1.1. (i) For every computably enumerable (c.e.) set W_{e} and associated enumeration W_{e,s},we define the settling (or modulus) function: m_{e}(x) = (μs)[W_{e,s}↾↾x = W_{e}↾↾x] where A ↾↾x = {y ≤ x|y ∈ A}.

(ii) For c.e. sets A and B, we say A settling time dominates B and write A >_{st} B iff (∃W_{i} = A) (∃W_{j} = B)

(1) (∀ computable f)(a.e. x)[ m_{i}(x) > f(m_{j}(x)) ].

(We use “a.e. x” to mean “for all but finitely many x”.) Andre Nies showed that (ii) is equivalent to (∀W_{i} = A)(∀W_{j} = B) [(1) holds]. Hence we will abuse notation by writing m_{A} for m_{e} when A = W_{e}. We denote the structure of the c.e. sets with the relation <_{st} as E_{st}.

This ordering was first introduced by Nabutovsky and Weinberger [3] and Soare [6]. Nabutovsky and Weinberger desired a descending sequence

Partially supported by Canadian NSERC Discovery Grant 312501. Partially supported by NSF Grants DMS-0100035 and DMS-0554855.

in E_{st} to use in the construction of various manifolds that gave information on the geometry of Riemannian metrics modulo diffeomorphisms. Soare constructed such a sequence as described in [6]. Sequences with additional useful or interesting properties were constructed by Csima [1] and Csima and Soare [2]. For general background information on the ordering and its applications to differential geometry we suggest Soare [6], Csima and Soare [2] and Weinberger [8].

In this paper we investigate properties of the <_{st} relation and order theoretic facts about E_{st}. We show (Theorem 2.1) that the relation itself is not invariant under computable isomorphism. On the other hand, in §7, we examine a stronger relation <_{sst} introduced in [2] and show that it is invariant under not only computable isomorphism but even under wtt-degree. We also construct a descending chain in this ordering to answer a question from [2]. As for the structure of E_{st}, we show (Theorem 3.1) that any countable partial ordering embeds into it; it has maximal (Theorem 4.1) and minimal (Theorem 5.1) elements; and that there are pairs of c.e. sets with no inf and ones with no sup (Theorem 6.2).

For Computability Theory, we follow the notation of Soare’s Recursively enumerable sets and Degrees [5] and new notation from Soare’s Computability Theory and Applications [7], which we also define.

We let {W_{e,s}}_{e,s∈ω} be any standard enumeration of the c.e. sets. We let φ_{e} denote the e-th partial computable function according to some standard enumeration. We often use the convention that φ_{e,s}(n) ↓⇒ (∀m ≤ n)φ_{e,s}(m) ↓, i.e. that the partial computable functions converge on numbers in order.

We write “∀^{∞}x” and “for a.e. x” for “for all but finitely many x”. Similarly, “∃^{∞}x” denotes “there are infinitely many x”.

2. Noninvariance under computable isomorphism

Nies (unpublished, see [2]) showed that the settling time ordering is welldefined on c.e. sets. Csima and Soare [2] show that it is not well-defined on Turing degrees. In fact, the settling time ordering is not invariant under computable isomorphism.

Theorem 2.1. There exist c.e. sets A and B such that A ≡_{1} B but A >_{st} B.

Proof. We first recursively associate to each n ∈ ω an even x_{n} ∈ ω in the following way. Let x_{0} = 0. For n ≥ 0, let x_{n+1} = x_{n} + 2(n + 1).

We now construct the sets A and B by stages.

Stage s: Step 1. Enumerate x_{s} into A (to ensure that A will be infinite). Step 2. If x_{n+1} was enumerated into B at stage t < s and φ_{i}(t) converged

at stage s for some i < n, enumerate x_{n} + 2(i + 1) into A (note that this is the only circumstance under which x_{n} +2(i+1) will be enumerated into A).

Step 3. If 2m is enumerated into A, enumerate x_{m} into B.

Lemma 2.2. A ≤_{1} B.

Proof. Let f(2m) = x_{m} and f(2m+1) = x_{m}+1. By construction 2m ∈ A iff x_{m} ∈ B. Also, there are no odd numbers in A, and there are only numbers of the form x_{m} in B. Thus n ∈ A iff f(n) ∈ B. It is also clear that f is one to one and computable. □

Lemma 2.3. B ≤_{1} A.

Proof. Let g(m) = 2n if m = x_{n}, and g(m) = 2m + 1 otherwise. Then g is a computable one to one function such that m ∈ B iff g(m) ∈ A. □

Lemma 2.4. A >_{st} B.

Proof. Let f be a total computable function. We must show that (∀^{∞}x)m_{A}(x) > f(m_{B}(x)). It suffices to show that for a.e. x, if x entered B at a stage s, some z ≤ x entered A at a stage greater than f(s). Let i be such that f = φ_{i}. Let x > x_{i+1}, and suppose x entered B at stage s. Then by construction, x = x_{n+1} for some n > i. At the stage t when φ_{i}(s) converged, x_{n} + 2(i + 1) was enumerated into A. Note that f(s) = φ_{i}(s) < t, and that x_{n} + 2(i + 1) < x_{n+1}. □

Thus A ≡_{1} B and A >_{st} B. □

As A ≡_{1} B if and only if there is a computable permutation p of ℕ such that B is the image of A under p, the relation <_{st} is not invariant even under computable permutations (isomorphisms) of ℕ. From the viewpoint of computability theory presented by Rogers [4, Ch. 4], one can question if such a relation is properly viewed as computability theoretic. In §7 we study a stronger notion <_{sst} also described in [2] which is invariant under computable permutations and more and construct the descending chain desired by Nabutovsky and Weinberger in that ordering as asked for in [2].

3. Embedding Partial Orderings

Theorem 3.1. Consider a computable partial ordering P on ℕ. We build a uniformly c.e. sequence {A_{n}} of sets such that A_{i} <_{st} A_{j} ⟺ i <_{P} j. Hence, by the existence of a computable universal partial ordering, any countable partial ordering can be embedded into E_{st}.

Proof. We construct the sequence {A_{n}} by stages. At each stage s there will be only finitely many numbers enumerated.

If i <_{P} j we wish to ensure that φ_{n} total ⇒ (∀^{∞}x)m_{A_{j}}(x) > φ_{n} ∘ m_{A_{i}}(x). We do this by observing the following Golden Rule.

Golden Rule. If i <_{P} j and ⟨i, j⟩ ≤ s, then at stage s we enumerate x into A_{i} only if there are appointed x_{0}, ..., x_{s}, all less than x, and we make the commitment that x_{n} will be enumerated into A_{j} at the stage when φ_{n}(s) ↓, should this ever happen. We refer to the x_{n} as “guards” ready to enter A_{j} in case φ_{n} converges on s.

If i ≮_{P} j we wish to ensure that (∃^{∞}x)m_{A_{i}}(x) ≥ m_{A_{j}}(x). At each stage s with ⟨i, j⟩ < s, we will obtain a witness n_{s} and we will promise to keep m_{A_{i}}(n_{s}) ≥ m_{A_{j}}(n_{s}) by enumerating into A_{i} below n_{s} whenever we enumerate into A_{j} below n_{s}.

Stage s: For each n = ⟨i, j⟩ < s such that i ≮_{P} j, do as follows, in turn. Our plan is to choose an n_{s}, enumerate it into A_{i}, and ensure that no

y ≤ n_{s} enters A_{j} at t ≥ s unless some z < n_{s} enters A_{i} at t. To find n_{s}, note first that there are only finitely many elements that may enter A_{j} due to prior commitments, say m many. Now looking at P ↾ s × s, there are finitely many finite maximal chains of the form k_{0} = i <_{P} k_{1} <_{P} ... <_{P} k_{r}. Note that j does not appear in any of these chains. Choose m + 1 numbers that are ready to enter A_{i} (should something enter A_{j}) such that there are enough guards for φ_{0}, ..., φ_{s} for all P -chains. That is, at stage s we appoint finitely many possible entrants of sets, all greater than any number mentioned earlier in the construction, according to the following rules. We appoint z_{1}, ..., z_{m} < n_{s} and promise to enumerate z_{k} into A_{i} at the stage when the k^{th} number less than or equal to n_{s} is enumerated into A_{j}. For each P -chain of the form k_{0} = i <_{P} k_{1} <_{P} ... <_{P} k_{r}, and each pair (k_{p}, k_{q}) with 0 ≤ p < q ≤ r, for each possible entrant y of A_{k_{p}} appointed at this stage, we appoint y_{0}^{(k_{p},k_{q})}, ..., y_{s}^{(k_{p},k_{q})} < y and promise to enumerate y_{k}^{(k_{p},k_{q})} into A_{k_{q}} at the stage when φ_{k}(s(y, k_{p})) ↓, where s(y, k_{p}) denotes the stage when y enters A_{k_{p}}. Note that since j doesn’t appear in any of the P -chains, this won’t cause the number of possible future entrants of A_{j} to go up. Now we enumerate n_{s} into A_{i}.

Lemma 3.2. If i <_{P} j then A_{i} <_{st} A_{j}.

Proof. Suppose i <_{P} j. Suppose f is a total function. We must show ∀^{∞}x(m_{A_{j}}(x) > f(m_{A_{i}}(x))). Let k be such that f = φ_{k}. Let s = ⟨i, j⟩. By stage s, we have appointed only finitely many possible entrants of A_{i}. Let t ≥ k be a stage by which all of those that were appointed before stage s and belong to A_{i} entered A_{i}. Then any x which entered A_{i} after stage t was appointed after stage s, so the P -chain containing i and j was considered, and an x_{k}^{(i,j)} < x was appointed to enter A_{j} at the stage when φ_{k}(s(x, i)) ↓. □

Lemma 3.3. If i ≮_{P} j then A_{i} ≮_{st} A_{j}.

Proof. Suppose i ≮_{P} j. Let n = ⟨i, j⟩. At every stage s > n, an n_{s} was enumerated into A_{i}, and for every x ≤ n_{s} that entered A_{j} after stage s, something less than n_{s} entered A_{i}. So m_{A_{i}}(n_{s}) ≥ m_{A_{j}}(n_{s}), so A_{i} ≮_{st} A_{j}. □

By the above lemmas, the sequence {A_{n}} has the required properties. □

One anomaly about E_{st} relative to other partial orderings studied in computability theory is that it is a strict partial ordering rather than a reflexive one. This has the seemingly strange consequence that an embedding of, for example, an incomparable pair x, y can be realized by any set A as the image for both x and y (or A and any finite variation of A). The largest equivalence relation on E_{st} (or any strict partial order) that respects the given ordering and gives a reflexive partial ordering as a quotient is given by A ≡_{st} B ⇔ {C|C >_{st} A} = {C|C >_{st} B} & {C|C <_{st} A} = {C|C <_{st} B}. One could instead of E_{st} then reasonably study its quotient E_{st}^{∗} by this equivalence relation with the natural partial ordering ≤. It is easy to see, however, that by simply adding on extra elements to a given partial ordering P one can produce one P′ such that any embedding of P′ into E_{st} will restrict to one of P into E_{st}^{∗}. Thus every countable partial ordering can be embedded in E_{st}^{∗} as well.

4. A Maximal Set

Theorem 4.1. There exists an A such that for all e, W_{e} ≯_{st} A.

Proof. We will construct a c.e. set A by stages. For each e, we wish to ensure that W_{e} ≯_{st} A. That is, we must ensure that there is a computable function f and infinitely many “winning locations” x such that f(m_{A}(x)) > m_{e}(x). We will do this by having separate strategies for each e which do not interfere with one another. Note that the computable functions providing the counterexample for each e do not have to be found effectively in e.

We first outline the strategy for defeating W_{0}. We allow ourselves to enumerate even numbers for the sake of defeating W_{0}. We save the odds for other W_{e}.

To show W_{0} ≯_{st} A, we need a computable function f and infinitely many x such that f ∘ m_{A}(x) ≥ m_{0}(x).

If W_{0} is finite, we will win with the identity, by making A infinite (this will happen automatically, as an infinite W_{e} will cause infinitely many numbers to enter A).

If W_{0} is infinite, Γ_{0}, Γ_{1}, … will mark the winning locations.

We will define a partial computable function f. We will either win with the identity, or else f will be almost total, and we will win with a finite variation of f.

Start off with all Γ_{k} undefined. We let Γ_{k}[s] denote the position of the marker Γ_{k} at the end of stage s, and let Γ_{k} denote the final position of the marker, i.e., Γ_{k} = lim_{s} Γ_{k}[s]. We assume that Γ_{k}[s + 1] = Γ_{k}[s] unless the construction states otherwise.

Stage s + 1: Suppose x is enumerated into W_{0} at stage s.

Case 1: Γ_{k−1}[s] < x ≤ Γ_{k}[s] for some k. Let Γ_{l}[s + 1] be undefined for l > k. If a y with Γ_{k−1}[s] < y ≤ Γ_{k}[s] has already been enumerated into A at a stage y_{A} with f(y_{A}) not yet defined, define f(y_{A}) = s + 1. Otherwise, enumerate an even number y, Γ_{k−1}[s] < y ≤ Γ_{k}[s] into A.

Case 2: Γ_{k}[s] < x, and Γ_{l}[s] is undefined for l > k. If there is a y > Γ_{k}[s] that entered A at stage y_{A} with f(y_{A}) undefined, set f(y_{A}) = s + 1. If there is no such y, set Γ_{k+1}[s+1] to be an even number greater than x and greater than any number enumerated into A so far, and enumerate Γ_{k+1}[s + 1] into A.

If we did not enumerate anything into A at stage s, define f(s) = s.

If W_{0} is infinite then eventually all the Γ_{k} will be defined and reach a limit. Note also that by construction, m_{0}(Γ_{k−1}) < m_{0}(Γ_{k}), since whenever a number less than or equal to Γ_{k−1}[s] enters W_{0,s+1}, Γ_{k}[s + 1] is undefined, and Γ_{k}[t + 1] is only redefined at a later stage t + 1 (to be larger than any previously mentioned number) if a number greater than Γ_{k−1}[t] enters W_{e,t+1}.

In each interval (Γ_{k−1}, Γ_{k}], if some x entered W_{0}, we either enumerated into A in that interval, or defined f on a stage number of something that had already been enumerated into A in that interval. This is because if at stage s we act to define Γ_{l}[s], then we only do this if Γ_{m}[s−1] is defined for all m < l, and we define Γ_{l}[s] to be larger than any number previously mentioned in the construction. Hence there will exist a k ≤ l such that (Γ_{l−1}[s], Γ_{l}[s]] ⊆ (Γ_{k−1}, Γ_{k}]; and whenever x enters W_{0,s+1}, if Γ_{l−1}[s] < x ≤ Γ_{l}[s] then we either enumerate into A or define f on a stage number of something that had already been enumerated into A in the interval (Γ_{l−1}[s], Γ_{l}[s]], and if x > Γ_{l}[s] with Γ_{l+1}[s] undefined, we either define and enumerate Γ_{l+1}[s + 1] into A, or we define f on the stage number when a number y > Γ_{l}[s] entered A. In the latter case, if W_{0} is infinite, both x and y are in an interval (Γ_{m}[t], Γ_{m+1}[t]] for some t > s + 1 and m ≤ l.

Let A_{[0]} denote the part of A that we are controlling for W_{0} (in this case the even numbers). Note that for any x, m_{A_{[0]}}(x) ≤ m_{A}(x).

If there are infinitely many intervals where the last action was to enumerate into A, then on these intervals we have m_{0}(Γ_{k}) ≤ m_{A_{[0]}}(Γ_{k}) ≤ m_{A}(Γ_{k}). So W_{0} is defeated. If not, then on almost all intervals our last action was to define f on a stage number. So f is almost total, and m_{0}(Γ_{k}) ≤ f(m_{A_{[0]}}(Γ_{k})) for almost all k. Let f^{∗} be an increasing computable function with f^{∗}(x) ≥ f(x) for almost all x. Then m_{0}(Γ_{k}) ≤ f(m_{A_{[0]}}(Γ_{k})) ≤ f^{∗}(m_{A_{[0]}}(Γ_{k})) ≤ f^{∗}(m_{A}(Γ_{k})).

So we see that not only have we defeated W_{0}, but it doesn’t matter what we enumerate into A on the odd numbers.

To defeat W_{1} we will work with numbers of the form 1+4n. We will have to use three partial computable functions f_{1}, f_{2}, f_{3}. In this case we will first enumerate into A, then define f_{1} on the stage number, then f_{2}, and then f_{3}, before enumerating into A again. This way, if we don’t win on the identity, f_{1} is almost total. If we don’t win on f_{1}, then f_{2} is almost total, and so forth.

We now outline the general case. To defeat W_{e}, we work with numbers of the form 2^{e} −1+2^{e+1}n. That is, for each W_{e}, we enumerate a set A_{[e]} ⊆ ω_{[e]}, where ω_{[e]} = {2^{e} −1+2^{e+1}n | n ∈ ω}. Note that if e ≠ k then ω_{[e]} ∩ω_{[k]} = ∅.

We will build partial computable functions f_{1}^{e}, f_{2}^{e}, ..., f_{2^{e+1}−1}^{e}.

As before, if W_{e} is infinite, Γ_{0}^{e}, Γ_{1}^{e}, ... will mark the winning locations.

Start with all Γ_{k}^{e} undefined.

Stage s: Suppose x is enumerated into W_{e} at stage s.

Case 1: Γ_{k−1}^{e}[s] < x ≤ Γ_{k}^{e}[s] for some k. Let Γ_{l}^{e}[s + 1] be undefined for l > k. If some y with Γ_{k−1}^{e}[s] < y ≤ Γ_{k}^{e}[s] was enumerated into A_{[e]} at a stage y_{A} with f_{m}(y_{A}) undefined for some m, let m be the least such, and define f_{m}(y_{A}) = s. Otherwise, enumerate a number y ∈ ω_{[e]}, Γ_{k−1}^{e}[s] < y ≤ Γ_{k}^{e}[s] into A_{[e]}.

Case 2: Γ_{k}^{e}[s] < x, and Γ_{l}^{e}[s] is undefined for l > k. If there is an m and a y > Γ_{k}^{e}[s] which was enumerated into A_{[e]} at a stage y_{A} with f_{m}^{e}(y_{A}) now undefined, choose the least such m and define f_{m}^{e}(y_{A}) = s. If there is no such m and y, set Γ_{k+1}^{e}[s + 1] to be in ω_{[e]} and to be greater than x and greater than any number enumerated into A_{[e]} so far. Enumerate Γ_{k+1}^{e}[s+1] into A_{[e]}.

If we did not enumerate anything into A at stage s, define f_{m}^{e}(s) = s for all 1 ≤ m ≤ 2^{e+1} − 1.

If W_{e} is infinite then eventually all the Γ_{k}^{e} will be defined and reach a limit. Note also that by construction, m_{e}(Γ_{k−1}^{e}) < m_{e}(Γ_{k}^{e}).

In each interval (Γ_{k−1}, Γ_{k}], if some x entered W_{e}, we either enumerated into A in that interval, or defined f_{m} on a stage number of something that was enumerated into A in that interval for the least m for which f_{m} was undefined on a stage number of something already enumerated in that interval. This is because, as in the the discussion for W_{0}, any interval that is ever defined can only change by being absorbed by a larger interval. The fact that even in the limit interval it is still the least m for which f_{m} was undefined on a stage number of something enumerated into the interval that gets defined follows from the fact that an interval is only ever set by enumerating it’s right endpoint into A.

Let f_{0} denote the identity function.

Let m be least such that there are infinitely many intervals where our last action was to define f_{m}. Note that m exists by the Pigeon Hole Principle. By our convention of first trying to define f_{m} for the least m ≥ 1, and by the minimality of m, f_{m} is almost total. Let f^{∗} be a total computable increasing function such that f_{m}(x) ≤ f^{∗}(x) for all x on which f_{m} is defined. Then for those intervals (Γ_{k−1}, Γ_{k}] where our last action was to define the f_{m} we have m_{e}(Γ_{k}) ≤ f_{m}(m_{A_{[e]}}(Γ_{k})) ≤ f^{∗}(m_{A_{[e]}}(Γ_{k})) ≤ f^{∗}(m_{A}(Γ_{k})). □

Of course, any set maximal in E_{st} is (i.e. its equivalence class is) maximal in E_{st}^{∗}.

5. Minimal Sets

If A and B are c.e. sets such that A >_{st} B, then A must be high (see Csima-Soare [2]). Hence if A is not high, then A ≯_{st} B for any B. Thus A is minimal in E_{st}. However, this is not entirely satisfying since A does not settling time dominate any set at all. We note that if A >_{st} C for any infinite c.e. set C, then A settling time dominates every computable set. (So all the infinite computable sets are in the same class, 0, in E_{st}^{∗}.) Hence we will write A >_{st} 0 if A settling time dominates any infinite c.e. set.

In this section we show that there is a nontrivial (i.e. above 0) minimal set in E_{st}(and so in E_{st}^{∗}). That is, we construct a c.e. set A such that A >_{st} 0, and for any B, if A >_{st} B, then for all W_{e}, B ≯_{st} W_{e}. Indeed, we will build A such that for all e if W_{e} is noncomputable, then A ≯_{st} W_{e}.

Theorem 5.1. There exists a nontrivial minimal set in E_{st}. Indeed, there exists a c.e. set A such that A >_{st} 0 and if W_{e} is noncomputable then A ≯_{st} W_{e}.

Proof. We construct the c.e. set A, and also an infinite computable set C such that A >_{st} C. Let c_{0} = 0 and c_{n+1} = c_{n} + n + 1. Let a_{i}^{n} = c_{n} + i for 0 ≤ i ≤ n. At stage s we enumerate c_{s} into C (so C is computable).

The strategy to make A >_{st} C will be to try to enumerate a_{i}^{n} into A at a stage after the stage when φ_{i}(n + 1) ↓.

For each W_{e}, if W_{e} is noncomputable, we want infinitely many x with m_{e}(x) ≥ m_{A}(x). Thus, when some x enters W_{e}, it would be nice to restrain A below x to ensure that m_{e}(x) ≥ m_{A}(x).

For each e, we will have restraint functions r(e, j, s) for all j ≥ e. We will let R(j, s) = max{r(e, j, s) | e ≤ j}.

We now construct A by stages as follows.

Stage s+1: We start off with r̃(e, j) = r(e, j, s) for all e, j ∈ ω, and let R̃(j) = max{r̃(e, j) | e ≤ j}.

Suppose x is enumerated into W_{e,s+1}. If x < r̃(e, j) for any j, reset r̃(e, j) = x for all such j (note that there can be only finitely many such j). Otherwise, let j be least such that r̃(e, j) = 0, and reset r̃(e, j) = x.

Now, perform the following loop. Suppose φ_{i,s+1}(n+1) ↓ for some i, n with i ≤ n. If a_{i}^{n} > R̃(i), enumerate a_{i}^{n} into A_{s+1}. For all e, j with a_{i}^{n} < r̃(e, j), reset r̃(e, j) = 0. If anything is enumerated, repeat the loop. Otherwise end the loop and set r(e, j, s + 1) = r̃(e, j) for all e, j.

Note that by construction, the only way that r(e, j, s) can increase as a function of s is if the restraint is injured by enumeration into A during a loop and set to 0, and then reset to a larger number in a later stage. That is, we have r(e, j, s + 1) ≤ r(e, j, s) unless r(e, j, s) = 0. Also, if r(e, j, s + 1) > r(e, j, s) = 0, then this was because r(e, j, s+1) was enumerated into W_{e,s+1}. Hence for any e, j ∈ ω, lim_{s} r(e, j, s) < ∞ or lim sup_{s} r(e, j, s) = ∞.

Lemma 5.2. For all e, if W_{e} is noncomputable, then A ≯_{st} W_{e}.

Proof. Case 1: For all j ≥ e, lim_{s} r(e, j, s) < ∞. Let x_{j} = lim_{s} r(e, j, s). Then either W_{e} is finite, or there exist infinitely many j such that x_{j} < x_{j+1}, and for all j, m_{e}(x_{j}) ≥ m_{A}(x_{j}). To see this suppose that r(e, j, s) reaches its final value x at stage t. It must be that x entered W_{e} at stage t. If some y < x enters A at a later stage v then r(e, j, v) = 0 for a contradiction. Thus A ≯_{st} W_{e}.

Case 2: Otherwise, let j be the least such that lim sup_{s} r(e, j, s) = ∞. By our conventions, if φ_{i} is not total, then it converges on only finitely many n. Hence the function f(n) = (μs)[(∀i ≤ j)φ_{i}(n) ↓→ φ_{i,s}(n) ↓] is computable. For x > max{lim_{s} r(e, i, s) | i < j}, we can certainly compute m such that x < c_{m}. Then x ∈ W_{e} ⟺ x ∈ W_{e,f(m+1)} for otherwise we would have lim_{s} r(e, j, s) ≤ x. Thus W_{e} is computable. □

Lemma 5.3. A >_{st} C.

It suffices to show that for all i, if φ_{i} is total then there exists an m such that whenever a_{i}^{n} > m and φ_{i,s}(n + 1) ↓ then there is a stage t ≥ s where a_{i}^{n} is enumerated into A.

For e ≤ i, let r(e, i) = lim sup_{s} r(e, i, s). Let R(i) = max{r(e, i) | r(e, i) < ∞ ∧ e ≤ i}. Suppose a_{i}^{n} > R(i), and suppose φ_{i,s}(n + 1) ↓. For t ≥ s, let b(t) = min{r(e, i, t) | r(e, i, t) > 0 ∧ r(e, i) = ∞ ∧ e ≤ i}. We wish to show that there is a stage t ≥ s such that b(t) is undefined, and hence a_{i}^{n} would be enumerated into A_{t}. The function b(t) cannot increase without being undefined in between. (For b(v) to increase, r(e, i, v) must increase for the i such that r(e, i, t) is the smallest among the relevant values. Before it can increase, however, it must first become 0 because some smaller element entered A and so all the other relevant r(e, j, v) for which r(e, j, t) were larger than r(e, i, t) also become 0.) So we may assume for a contradiction that b = lim_{t} b(t) exists. Let t_{1} be such that b = r(e, i, t_{1}) with r(e, i) = ∞, e ≤ i, and b(t) = b for all t ≥ t_{1}. Since lim sup_{t} r(e, i, t) = ∞, there is some number less than b enumerated into A at a stage t_{2} > t_{1}. But then b(t_{2}) is undefined. □

6. No infs and sups

In this section, we show that infs and sups need not exist in E_{st} or E_{st}^{∗}. One way of showing that there is a pair with no sup, is to build a set

which is both maximal and minimal in the <_{st} ordering. We do not do this in detail, since the existence of such a pair follows from the construction we do to show there is a pair with no inf. However, we state the existence of such a set, and outline how to go about it’s construction.

Theorem 6.1. There exists a c.e. set which is both maximal and minimal with respect to the <_{st} ordering.

Proof Sketch. Combine the constructions of the maximal and minimal set A. There will be finite injury, since the minimal set construction wishes to hold members out of the set A. By introducing an extra function f_{2^{e+1}}^{e} for the e-th requirement of the maximal set construction, one can afford to injure the requirements by “kicking the Γ_{k}^{e} markers” a distance of 2^{e+1}r when a minimality requirement of higher priority wishes to restrain A below r. □

We now give a detailed construction showing that there are c.e. sets A and B which have no inf in E_{st} and ones C and D which have no sup. We do this by also building c.e. sets E, F, G such that A, B >_{st} C, D; E >_{st} A but E ≯_{st} B; F >_{st} D but F ≯_{st} C; C, D >_{st} G; A |_{st} B and C |_{st} D. We also ensure that there is no c.e. set H such that A >_{st} H >_{st} C, we refer to this property as having a gap between A and C (and indicate it by the double line from A to C in the diagram below). That is, the sets will satisfy the following diagram:

[figure: E; A; |; B; |; F; C; |; D; |; G]

Theorem 6.2. There are c.e. sets A and B such that A and B have no infimum in the <_{st} ordering, indeed, such A and B can be found with A ≢_{st} B. There are c.e. sets C and D such that C and D have no supremum in the <_{st} ordering, indeed, such C and D can be found with C ≢_{st} D.

Proof. We will construct A, B, C, D, E, F, and G as described above, and A, B, C, and D will be the desired sets. Since E >_{st} A and E ≯_{st} B, A ≢_{st} B. Since A ≮_{st} B and there is a gap between A and C, and since C <_{st} A and C <_{st} B, the only candidate for an inf of A and B is C. However, D <_{st} A and D <_{st} B, but D ≮_{st} C and D ≢_{st} C (since F >_{st} D but F ≯_{st} C). So A and B have no inf. We’ve seen that C ≢_{st} D. Since C ≯_{st} D and there is a gap between A and C, and since A >_{st} C and A >_{st} D, the only candidate for a sup of C and D is A. However B >_{st} C and B >_{st} D, but B ≯_{st} A and B ≢_{st} A, so C and D have no sup.

To construct the c.e. sets A, B, C, D, E, F and G, we will use the methods of embedding the above partial ordering as in the proof of Theorem 3.1, but with additional requirements to ensure that there is a gap between A and C. To do this, we will put restraint on A, as in the construction of a minimal set in §5. The restraint functions will be of the form r(e, j, s), and we start off with r(e, j, −1) = 0 for all e, j.

Stage s: To make B ≮_{st} E. Let l(E, s) be the total number of possible future entrants of E declared up to this point in the construction. Let β_{1} < ... < β_{l(E,s)} < n_{s}^{B} be greater than any number mentioned thus far in the construction. Enumerate n_{s}^{B} into B, and declare that β_{i} will enter B when the i-th number less than n_{s}^{B} enters E. There will be no restraint imposed on B, and we will never again declare anything less than n_{s}^{B} to be eligible to enter E, so this will ensure that m_{B}(n_{s}^{B}) > m_{E}(n_{s}^{B}).

To make C ≮_{st} F, respecting C <_{st} A <_{st} E and C <_{st} B. Let l(F, s) be the total number of possible future entrants of F declared up to this point in the construction. Let w_{i}(1 ≤ i ≤ l(F, s)), a_{j}^{w_{i}}(1 ≤ i ≤ l(F, s), 0 ≤ j ≤ s),

b_{j}^{w_{i}}(1 ≤ i ≤ l(F, s), 0 ≤ j ≤ s), e_{k}^{a_{j}^{w_{i}}} (1 ≤ i ≤ l(F, s), 0 ≤ j, k ≤ s), and n_{s}^{C} all be distinct numbers greater than any number mentioned thus far in the construction. Moreover, the w_{i} should all be less than n_{s}^{C}; the a_{j}^{w_{i}} and b_{j}^{w_{i}}

should all be less than w_{i}; and the e_{k}^{a_{j}^{w_{i}}} should all be less than a_{j}^{w_{i}}.

Enumerate n_{s}^{C} into C, and declare that w_{i} will enter C when the i-th number less than n_{s}^{C} enters F. There will be no restraint imposed on C, and we will never again declare anything less than n_{s}^{C} to be eligible to enter F. This will ensure that m_{C}(n_{s}^{C}) ≥ m_{F} (n_{s}^{C}).

If at some later stage t, φ_{j,t}(s(w_{i}, C)) ↓, for a j ≤ s, where s(w_{i}, C) denotes the stage when (if ever) w_{i} was enumerated into C, then enumerate b_{j}^{w_{i}} into B at stage t. This will help ensure that B >_{st} C. We would also like to enumerate a_{j}^{w_{i}} into A, but A is subject to restraint, so we will deal with this later in the construction.

If at some later stage t, φ_{k,t}(s(a_{j}^{w_{i}}, A)) ↓, and if k ≤ s, then enumerate

e_{k}^{a_{j}^{w_{i}}} into E at stage t. This will help ensure that E >_{st} A.

To make G infinite, while respecting other requirements. Let g, c_{i}^{g}(0 ≤

i ≤ s), a_{j}^{c_{i}^{g}}(0 ≤ i, j ≤ s), and e_{k}^{a_{j}^{c{g \atop i}}} (0 ≤ i, j, k ≤ s) all be greater than any

number mentioned so far in the construction, with e_{k}^{a_{j}^{c{g \atop i}}} < a_{j}^{c_{i}^{g}} < c_{i}^{g} < g(0 ≤ i, j, k ≤ s).

Enumerate g into G. If at some later stage t, φ_{i,t}(s) ↓, with i ≤ s, then enumerate c_{i}^{g} into C and into D at stage t. This will help ensure that C >_{st} G and D >_{st} G. In this and later action we will continue to ensure that something is enumerated into D only if at that same moment that same number is enumerated into C (though not vice versa, because of the F ≯_{st} C requirement above).

If at some later stage t, φ_{j,t}(s(c_{i}^{g}, C)) ↓, with i ≤ s, then enumerate a_{j}^{c_{i}^{g}} into B and F at stage t. Since c_{i}^{g} was enumerated into both C and D,

enumerating a_{j}^{c_{i}^{g}} into B will help ensure that B >_{st} C, and B >_{st} D, and

enumerating a_{j}^{c_{i}^{g}} into F will help ensure that F >_{st} D. We would also like to enumerate a_{j}^{c_{i}^{g}} into A, but A is subject to restraint, so we will deal with this later in the construction.

If at some later stage t, φ_{k,t}(s(a_{j}^{c_{i}^{g}}, A)) ↓, with k ≤ s, then enumerate e_{k}^{a_{j}^{c{g \atop i}}} into E at stage t. This will help ensure that E >_{st} A.

To make D ≮_{st} C. Let l(C, s) be the total number of possible future entrants of C declared up to this point in the construction. Let δ_{i}(1 ≤ i ≤

l(C, s)), a_{j}^{w_{i}}(1 ≤ i ≤ l(C, s), 0 ≤ j ≤ s), e_{k}^{a_{j}^{w_{i}}} (1 ≤ i ≤ l(C, s), 0 ≤ j ≤ s, 0 ≤

k ≤ s), n_{s}^{D}, a_{j}^{n_{s}^{D}}, (0 ≤ j ≤ s), e_{k}^{a_{j}^{n^{D}_{s}}} , (0 ≤ j, k ≤ s) all be distinct numbers greater than any number mentioned thus far in the construction. Moreover, the δ_{i} should all be less than n_{s}^{D}; the a_{j}^{δ_{i}} should all be less than δ_{i}; and the

e_{k}^{a_{j}^{δ_{i}}} should all be less than a_{j}^{δ_{i}}. Also, the e_{k}^{a_{j}^{n^{D}_{s}}} should all be less than the

a_{j}^{n_{s}^{D}} which should all be less than n_{s}^{D}.

Enumerate n_{s}^{D} into both C and D, and declare that δ_{i} will enter both C and D when the i-th number less than n_{s}^{D} which is not of the form δ_{m} enters C. There will be no restraint imposed on D, and we will never again declare anything less than n_{s}^{D} to be eligible to enter C (except for the δ_{m} which we enumerate into C only if we simultaneously enumerate it into D). This will ensure that m_{D}(n_{s}^{D}) = m_{C}(n_{s}^{D}). We have also maintained our rule that we enumerate a number into D only if we simultaneously enumerate the same number at the same moment into C.

If at some later stage t, φ_{j,t}(s(δ_{i}, D)) ↓ with j ≤ s, then enumerate a_{j}^{δ_{i}} into B and F at stage t. Since δ_{i} entered both C and D, enumerating a_{j}^{δ_{i}} into B will help ensure that B >_{st} C, and B >_{st} D, and enumerating a_{j}^{δ_{i}} into F will help ensure that F >_{st} D. We would also like to enumerate a_{j}^{δ_{i}} into A, but A is subject to restraint, so we will deal with this later in the construction. Similarly, if φ_{j,t}(s) ↓, enumerate a_{j}^{n_{s}^{D}} into B and F at stage t.

If at some later stage t, φ_{k,t}(s(a_{j}^{δ_{i}}, A)) ↓, and if k ≤ s, then enumerate

e_{k}^{a_{j}^{δ_{i}}} into E at stage t. Similarly if φ_{k,t}(s(a_{j}^{n_{s}^{D}}, A)) ↓, enumerate e_{k}^{a_{j}^{n^{D}_{s}}} into E at stage t. This will help ensure that E >_{st} A.

To make A ≮_{st} B. Let l(B, s) be the total number of possible future entrants of B declared up to this point in the construction. Let α_{i}^{s}(1 ≤ i ≤ l(B, s)), e_{j}^{α_{i}^{s}}(1 ≤ i ≤ l(C, s), 0 ≤ j ≤ s), and n_{s}^{A} all be distinct numbers greater than any number mentioned thus far in the construction. Moreover, the α_{i} should all be less than n_{s}^{A}, and the e_{j}^{α_{i}} should all be less than α_{i}.

Enumerate n_{s}^{A} into A (it was chosen to be greater than any number mentioned so far, so in particular it is beyond all restraints.) When the i-th number less than n_{s}^{A} is enumerated into B we will declare that α_{i}^{s} desires to enter A, and this will remain the case until (if ever) α_{i}^{s} is enumerated into A. If for all i ≤ l(A, s), whenever α_{i}^{s} desires to enter A, it is eventually enumerated into A (perhaps at a later stage than it first desired to be), we will have m_{A}(n_{s}^{A}) ≥ m_{B}(n_{s}^{A}), establishing that A ≮_{st} B.

If at a later stage t, φ_{j,t}(s(α_{i}^{s}, A)) ↓, enumerate e_{j}^{α_{i}^{s}} into E at stage s. This will help ensure that E >_{st} A.

To make a gap between A and C. We start off with r̃(e, j) = r(e, j, s − 1) for all e, j ∈ ω, and let R̃(j) = max{r̃(e, j) | e ≤ j}.

Suppose x is enumerated into W_{e,s}. If x < r̃(e, j) for any j, reset r̃(e, j) = x for all such j. Otherwise, let j be least such that r̃(e, j) = 0, and reset r̃(e, j) = x.

Now, perform the following loop. Suppose φ_{i,s}(s(x, C)) ↓ for some i, s such that a_{i}^{x} was appointed. If a_{i}^{x} > R̃(i), enumerate a_{i}^{x} into A_{s}. For all e, j with a_{i}^{x} < r̃(e, j), reset r̃(e, j) = 0. We define p̃(t), the priority for n_{t}^{A} to act, by induction. Let p̃(0) = 0. Let p̃(t + 1) = p̃(t) if there is some α_{k}^{t} that desires to be enumerated such that α_{k}^{t} ≤ R̃(p̃(t)), and let p̃(t+1) = p̃(t)+1 otherwise. If α_{k}^{t} desires to be enumerated and α_{k}^{t} > R̃(p̃(t)) then enumerate α_{k}^{t} into A_{s}, and for all e, j with α_{k}^{t} < r̃(e, j), reset r̃(e, j) = 0. If anything is enumerated, repeat the loop. Otherwise end the loop and set r(e, j, s) = r̃(e, j) for all e, j, and p(t, s) = p̃(t) for all t.

Note that as in the minimal set construction, the only way that r(e, j, s) can increase as a function of s is if the restraint is injured by enumeration into A during a loop and set to 0, and then reset to a larger number in a later stage. That is, we have r(e, j, s + 1) ≤ r(e, j, s) unless r(e, j, s) = 0. Also, if r(e, j, s + 1) > r(e, j, s) = 0, then this was because r(e, j, s + 1) was enumerated into W_{e,s+1}. Hence for any e, j ∈ ω, lim_{s} r(e, j, s) < ∞ or lim sup_{s} r(e, j, s) = ∞.

This completes the construction.

The facts that E >_{st} A, E ≯_{st} B, B >_{st} C, B >_{st} D, F ≯_{st} C, F >_{st} D, C ≯_{st} D, C >_{st} G, and D >_{st} G, follow exactly as in the embedding of the partial ordering in Theorem 3.1. We also easily see that A ≯_{st} B since E >_{st} A and E ≯_{st} B, and that D ≯_{st} C since F >_{st} D and F ≯_{st} C.

It remains to show that there is a gap between A and C, A ≮_{st} B, A >_{st} D, and A >_{st} C. Note that since we only enumerate into D if the same number is enumerated into C at the same moment, m_{C}(x) ≥ m_{D}(x) for all x, so once we show A >_{st} C, we immediately also have A >_{st} D.

Lemma 6.3. A >_{st} C.

Proof. It suffices to show that for all i, if φ_{i} is total then there exists an m such that whenever a_{i}^{x} > m and φ_{i,s}(s(x, C)) ↓ then there is a stage t ≥ s where a_{i}^{x} is enumerated into A.

For e ≤ i, let r(e, i) = lim sup_{s} r(e, i, s). Let R(i) = max{r(e, i) | r(e, i) < ∞ ∧ e ≤ i}. Suppose a_{i}^{x} > R(i), and suppose φ_{i,s}(x) ↓. For t ≥ s, let b(t) = min{r(e, i, t) | r(e, i, t) > 0 ∧ r(e, i) = ∞ ∧ e ≤ i}. We wish to show that there is a stage t ≥ s such that b(t) is undefined, and hence a_{i}^{x} would be enumerated into A_{t}. The function b(t) cannot increase without first being undefined. So we may assume for a contradiction that b = lim_{t} b(t) exists. Let t_{1} be such that b = r(e, i, t_{1}) with r(e, i) = ∞, e ≤ i, and b(t) = b for all t ≥ t_{1}. Since lim sup_{t} r(e, i, t) = ∞, there is some number less than b enumerated into A at a stage t_{2} > t_{1}. But then b(t_{2}) is undefined. □

Lemma 6.4. A ≮_{st} B.

Proof. First note that the value of p(t, s) can only change finitely often as s increases (since there are finitely many α_{i}^{t′} with t′ ≤ t, and each can desire to enter A and be enumerated at most once). Thus p(t) = lim_{s} p(t, s) exists for all t. Note also that p is nondecreasing. We show by induction on n that there exists a t_{n} = max{t | p(t) = n}. Let t_{−1} = −1. Let t > t_{n−1} be least such that all α_{i}^{t} > R(n), where R(n) = max{r(e, n) | r(e, n) < ∞ ∧ e ≤ n}, as in Lemma 6.3. Then, as in the proof of Lemma 6.3, any α_{i}^{t} that desires to enter A will eventually be enumerated into A unless p(t, s) > n for a.e. s. But this can only happen if there is some t′ with t_{n−1} < t′ < t such that every α_{i}^{t′} that desires to enter A eventually does. Hence t_{n} exists, indeed t_{n−1} < t_{n} ≤ t.

By definition of t_{n}, every α_{i}^{t_{n}} which desires to enter A eventually does, hence for all n, m_{A}(n_{t_{n}}^{A}) ≥ m_{B}(n_{t_{n}}^{A}). Thus A ≮_{st} B. □

Lemma 6.5. For all e, if W_{e} >_{st} C, then A ≯_{st} W_{e}.

Proof. Case 1: For all j ≥ e, lim_{s} r(e, j, s) < ∞. Let x_{j} = lim_{s} r(e, j, s). Then either W_{e} is finite, or there exist infinitely many j such that x_{j} < x_{j+1}, and for all j, m_{e}(x_{j}) ≤ m_{A}(x_{j}) and hence A ≯_{st} W_{e}.

Case 2: There is some j such that lim sup_{s} r(e, j, s) = ∞. Let j be the least such, let r = max{r(e, i, s) | i < j}, and let s′ be such that for any α_{i}^{t} ∈ A with t ≤ t_{e} we have α_{i}^{t} ∈ A_{s′}. By our conventions, if φ_{i} is not total, then it converges on only finitely many x. Hence the function f(x) = (μs)[(∀i ≤ j)φ_{i}(x) ↓→ φ_{i,s}(x) ↓] is computable. Let y > r be any entrant of C, and let x be the last entrant of W_{e} less than or equal to y. If in addition x ≥ r and x entered W_{e} after stage s′, we will have x = r(e, k, s) for some s > s′ and some k ≥ j. Then, since lim sup_{t} r(e, j, t) = ∞, we know that r(e, j, s) ≤ r(e, k, s) = x will be injured. The only reason this would happen is because some φ_{i} converged on the stage when something less than or equal to y was enumerated into C. Thus f(m_{C}(y)) > s = m_{e}(y). Since there are infinitely many such y, we see that W_{e} ≯_{st} C. □

Hence the sets A, B, C, D, E, F, and G have the required properties. □

7. Super Domination

To help simplify proofs in differential Geometry, Nabutovsky and Weinberger asked whether there exits a sequence {A_{i}} of c.e. sets such that

(∀ computable f)(∀n)(∀^{∞}x)[m_{A_{i}}(x) > f(m_{A_{i+1}}(nx))]

Csima answered this question in her thesis [1] as follows.

Definition 7.1. Let g be a computable function. For c.e. sets A and B we say A >_{g−st} B if for all computable functions f, for almost every x,

m_{A}(x) > f(m_{B}(g(x))).

Theorem 7.2. For any computable g, there exists a sequence {A_{i}} of c.e. sets such that

A_{i} >_{g−st} A_{i+1}

This answered the question of Nabutovsky and Weinberger using g(x) = x^{2}.

However, this also raised the question of whether there are sets A and B such that A >_{g−st} B for all computable g.

Definition 7.3. For c.e. sets A and B we say A strongly settling time dominates B, A >_{sst} B, if for all computable functions f and g, for almost every x,

m_{A}(x) > f(m_{B}(g(x))).

Equivalently, A >_{sst} B if A >_{g−st} B for all computable g. The associated strict partial ordering on c.e. sets is denoted by E_{sst}.

Note 7.4. For c.e. sets A and B, A >_{sst} B if and only if, for all strictly increasing computable functions f and g, for almost every x,

m_{A}(x) > f(m_{B}(g(x))).

Proof. If f is computable, then there is a strictly increasing computable function f^{∗} with f(x) ≤ f^{∗}(x). Note that for f and g computable, B c.e., f(m_{B}(g(x))) ≤ f^{∗}(m_{B}(g(x))) ≤ f^{∗}(m_{B}(g^{∗}(x))). □

We will follow the conventions that if φ is a partial computable function, then if φ(n) ↓ at stage s then φ(n) < s, and for all m < n, φ(m) ↓≤ φ(n).

Clearly <_{sst} implies <_{st}, moreover, it is invariant under computable permutations and so remedies that “defect” in E_{st}. In fact, it respects not only 1-reducibility but even wtt-reducibility.

Theorem 7.5. The <_{sst} ordering is well defined on wtt degrees. In fact, it respects wtt-reducibility in the sense that if A ≤_{wtt} B <_{sst} C or A <_{sst} B ≤_{wtt} C then A <_{sst} C.

Proof. We make use of the following lemma from Csima-Soare [2].

Lemma 7.6. Suppose A ≤_{wtt} B, with use bounded by h. Then there is a strictly increasing computable function p such that

(∀x)[ m_{A}(x) ≤ p ∘ m_{B}(h(x)) ].

Lemma 7.7. Let A, B, and C be c.e. sets with enumerations {A_{s}}_{s∈ω},{B_{s}}_{s∈ω}, and {C_{s}}_{s∈ω}, respectively. If A ≤_{wtt} B with use bounded by h, and B <_{sst} C then A <_{sst} C.

Proof. We wish to show that for all strictly increasing computable functions f and g, for a.e. x, f(m_{A}(g(x))) < m_{C}(x). By Lemma 7.6, there is a strictly increasing function p such that for all x, m_{A}(x) ≤ p(m_{B}(h(x))). So for all x, f(m_{A}(g(x))) ≤ f(p(m_{B}(h(g(x))))). Since B <_{sst} C, we have p(f(m_{B}(h(g(x))))) < m_{C}(x) for a.e. x. So for a.e. x, f(m_{A}(g(x))) < m_{C}(x), as desired. □

Lemma 7.8. Let A, B, and C be c.e. sets with enumerations {A_{s}}_{s∈ω},{B_{s}}_{s∈ω}, and {C_{s}}_{s∈ω}, respectively. If A <_{sst} B and B ≤_{wtt} C then A <_{sst} C.

Proof. We wish to show for all strictly increasing computable functions f and g, for a.e. x, f(m_{A}(g(x))) < m_{C}(x). By Lemma 7.6, there is a strictly increasing function p such that for all x, m_{B}(x) ≤ p(m_{C}(x)). Since A <_{sst} B, p(f(m_{A}(h(x)))) < m_{B}(x) for a.e. x. Now since p is strictly increasing, this gives f(m_{A}(g(x))) < m_{C}(x) for a.e. x as desired. □

These two lemmas show that <_{sst} respects wtt-reducibility and so is well defined on the wtt-degrees. □

We first show that the relation <_{sst} is nontrivial.

Theorem 7.9. There exist c.e. sets A and B such A >_{sst} B and B is noncomputable.

Proof. We construct A and B to meet the requirements:

R_{⟨i,j⟩}: φ_{i} and ψ_{j} total ⇒ (∀^{∞}x)m_{A}(x) > φ_{i}(m_{B}(ψ_{j}(x))).

N_{e}: B ≠ Φ_{e}.

Let Γ_{l} be spread out so that between Γ_{l} and Γ_{l+1} there are guards [i, j, k]_{l} for 0 ≤ i, j, k ≤ l.

We will have numbers x_{0}^{s} < x_{1}^{s} < ... which may be enumerated into B for the sake of N_{e}.

Stage 0: Begin with x_{m}^{0} = m.

Stage s + 1: For the least e for which Φ_{e}(x_{e}^{s}) ↓= 0 for some as yet unsatisfied N_{e}, enumerate x_{e}^{s} into B and declare N_{e} satisfied.

If ψ_{j} converges on Γ_{l+2} for some l ≥ j for the first time at this stage, reset all x_{e}^{s+1} to be greater than s + 1 for unsatisfied e ≥ l. Declare that the [i, j, 0]_{l} will enter A if φ_{i}(s + 1) ↓. Let t_{1} < ... < t_{n} denote the stages greater than s when something less than or equal to s + 1 enters B. Note that n ≤ l. If we find at a later stage that φ_{i}(t_{k}) ↓, enumerate [i, j, k]_{l} of A at that stage.

Lemma 7.10. lim_{s→∞} x_{e}^{s} < ∞.

Proof. x_{e}^{s+1} ≠ x_{e}^{s} only if some ψ_{j} converged on Γ_{l+2} for the first time at stage s, with j ≤ l ≤ e. This can only happen finitely often. □

Lemma 7.11. The N_{e} are satisfied.

Proof. Immediate since the x_{e}^{s} reach a limit. □

Lemma 7.12. The R_{⟨i,j⟩} are satisfied.

Proof. Suppose φ_{i} and ψ_{j} are total.

It suffices to show that for a.e. x, whenever some y ≤ ψ_{j}(x) is enumerated into B at a stage s then some z ≤ x is enumerated into A at a stage t ≥ φ_{i}(s).

Suppose Γ_{l+1} ≤ x < Γ_{l+2} for some l ≥ max{i, j}. By our conventions, ψ_{j}(x) ≤ ψ_{j}(Γ_{l+2}). At the stage when ψ_{j}(Γ_{l+2}) ↓, we appointed markers [i, j, k]_{l} < Γ_{l+1} ≤ x ready to enter A, one for each possible future entrant of B below ψ_{j}(Γ_{l+2}), and one in case there were no future entrants. □

□

Proof. Thus B is noncomputable and A >_{sst} B as required. □

We now answer the question raised about <_{sst} in [2] that asks, in this stronger ordering, for the descending sequence requested by Weinberger and Nabutovsky for their work in differential geometry. In fact, we prove a bit more.

Theorem 7.13. Let P be a computable partial ordering on ℕ with no infinite ascending sequence. There exists a computable sequence {A_{n}} of c.e. sets such that if m <_{P} n then A_{m} <_{sst} A_{n}.

Proof. We must meet the following requirements:

R_{⟨i,j⟩}^{⟨m,n⟩}: m <_{P} n, φ_{i} and ψ_{j} total ⇒ (∀^{∞}x)m_{A_{n}}(x) > φ_{i}(m_{A_{m}}(ψ_{j}(x))). As in the previous theorem, we will be using markers and guards to help

construct the sets. For each set A_{n} that we build, we will use moveable markers Γ_{l}^{n} with l ≥ n, and between each Γ_{l}^{n} and Γ_{l+1}^{n} there will be guards of the form [i, j, k]_{l}^{n} with 0 ≤ i, j ≤ l, 0 ≤ k < g_{n}(l) to aid in meeting the R requirements. Thus the number of guards between markers will be (l+1)^{2}g_{n}(l), where g_{n}(l) will be a uniformly computable function depending on P. The markers and their guards will be moved at most finitely often, and the only possible entrants of A_{n} will be the guards and markers. We will maintain that if k < n then Γ_{k}^{n} < Γ_{l}^{n}.

Each marker Γ_{l}^{n} will have priority ⟨n, l⟩. So if some ψ_{j}(Γ_{l+2}^{n}) ↓ for j ≤ l, markers of the form Γ_{k}^{m} with ⟨m, k⟩ > ⟨n, l⟩ and m <_{P} n will be moved. This means that each marker will be moved only finitely often, so eventually will settle down. Also, each marker Γ_{l}^{n} will only have finitely many markers (and hence finitely many possible entrants of sets) that it can’t move, and so (since it knows about them in advance) can ensure that there are enough guards between Γ_{l}^{n} and Γ_{l+1}^{n} to accommodate them.

We now define a computable function h(⟨m, k⟩) bounding the number of times marker Γ_{k}^{m} might be moved. We let h(⟨m, k⟩) = 0 if m ≮_{P} n for all ⟨n, l⟩ < ⟨m, k⟩, since in such a situation Γ_{k}^{m} will never be moved. We then inductively define

h(⟨m, k⟩) = ∑_{⟨n,l⟩<⟨m,k⟩∧m<_{P} n}(h(⟨n, l + 2⟩) + 1)(l + 1),

since the marker Γ_{k}^{m} can be moved only if ψ_{j}(Γ_{l+2}^{n}) ↓, where j ≤ l, ⟨n, l⟩ < ⟨m, k⟩ and m <_{P} n. Note that h is computable since P has no infinite ascending chain.

Now that we have h(⟨m, k⟩), we are ready to define the uniformly computable g_{n}(l). The function g_{n}(l) represents the total number of possible entrants of higher priority that can’t be moved when a convergence on Γ_{l+2}^{n} is observed, plus the number of times Γ_{l+2}^{n} might move. For each Γ_{k}^{m} that can’t be moved, there are (k + 1)^{2}g_{m}(k) possible entrants, and Γ_{k}^{m} might move h(⟨m, k⟩) many times. Note that if ⟨m, k⟩ = ⟨n, l⟩ then m = n and m ≮_{P} n. So we inductively define

g_{n}(l) = h(⟨n, l + 2⟩) + ∑_{⟨m,k⟩<⟨n,l⟩ and m<_{P} n}((k + 1)^{2}g_{m}(k))h(⟨m, k⟩).

Stage 0: Spread out the markers Γ_{l}^{n} such that there is room for the (l + 1)^{2}g_{n}(l) many guards of the form [i, j, k], 0 ≤ i, j ≤ l, 0 ≤ k < g_{n}(l) between Γ_{l}^{n} and Γ_{l+1}^{n}. Also ensure that all markers and guards are distinct, so at most one ψ_{j}(Γ_{l+2}^{n}) ↓ at any given stage.

Stage s + 1: If, for j < l, ψ_{j,s}(Γ_{l+2}^{n}[s]) ↓, but ψ_{j,s−1}(Γ_{l+2}^{n}[s]) ↑, we say (n, l, j) receives attention at stage s + 1. Reset all Γ_{k}^{m} with ⟨m, k⟩ > ⟨n, l⟩ and m <_{P} n which have already been defined, and their corresponding guards, to all be greater than s + 1. That is, if a marker Γ_{k}^{m} is moved, the guards between Γ_{k−1}^{m} and Γ_{k}^{m} should all be moved. They should be moved far enough that all the various markers and guards are on distinct numbers not yet enumerated.

Let a be the number of previous stages where (n, l, j) received attention. Note that 0 ≤ a < h(⟨n, l + 2⟩). Declare that the [i, j, a]_{l}^{n} will enter A_{n} if φ_{i}(s + 1) ↓. That is, at the stage t when φ_{i}(s + 1) converges, enumerate [i, j, a]_{l}^{n}[t] into A_{n}.

General Declaration: Recall that g_{n}(l) − h(⟨n, l + 2⟩) represents the total number of possible entrants of higher priority that can’t be moved when a convergence on Γ_{l+2}^{n} is observed. Let s_{1} < ... < s_{r} denote the stages, s, with the following property. There is some j ≤ l and t < s such that ψ_{j,t}(Γ_{l+2}^{n}[t]) ↓= ψ_{j,s}(Γ_{l+2}^{n}[s]) ↓, Γ_{l+2}^{n}[t] = Γ_{l+2}^{n}[s], and something of the form [a, b, c]_{k}^{m} less than ψ_{j}(Γ_{l+2}^{n}[s]) enters A_{m,s} for some ⟨m, k⟩ < ⟨n, l +2⟩, m <_{P} n. Note that r ≤ g_{n}(l) − h(⟨n, l + 2⟩). If we find at some stage t′ that for some i ≤ l, φ_{i}(s_{k}) ↓, enumerate [i, j, h(⟨n, l + 1⟩) + k − 1]_{l}^{n}[t′] into A_{n} at stage t′.

Lemma 7.14. The Γ_{l}^{n} reach a limit.

Proof. We have already computed that Γ_{l}^{n} can move at most h(⟨n, l⟩) times.

□

Lemma 7.15. The R_{⟨i,j⟩}^{⟨m,n⟩} are satisfied.

Proof. Suppose φ_{i} and ψ_{j} are total and m <_{P} n.

It suffices to show that for a.e. x, whenever some y ≤ ψ_{j}(x) is enumerated into A_{m} at a stage s then some z ≤ x is enumerated into A_{n} at a stage t ≥ φ_{i}(s).

Suppose Γ_{l+1}^{n} ≤ x < Γ_{l+2}^{n} for some l ≥ max{i, j}. By our conventions, ψ_{j}(x) ≤ ψ_{j}(Γ_{l+2}^{n}). Suppose y ≤ ψ_{j}(x) was enumerated into A_{m} at stage s. Then y ≤ ψ_{j}(Γ_{l+2}^{n}). Case 1: y ≤ ψ_{j,s}(Γ_{l+2}^{n}[s]) ↓. In this case, a marker [i, j, k]_{l}^{n}[t] < Γ_{l+1}^{n}[t] ≤ Γ_{l+1}^{n} ≤ x was enumerated into A_{n} at the stage t when φ_{i}(s) converged. Case 2: ψ_{j,s}(Γ_{l+2}^{n}[s]) ↑ or y > ψ_{j,s}(Γ_{l+2}^{n}[s]) ↓. In this case, there must have been a stage t > s such that y ≤ ψ_{j,t}(Γ_{l+2}^{n}[t]) ↓, and at stage t, we would have had a number [i, j, a]_{l}^{n}[t′] ≤ Γ_{l}^{n}[t′] ≤ Γ_{l}^{n} ≤ x which would be enumerated into A_{n} at the stage t′ when φ_{i}(t) converged, which by our conventions was after the stage when φ_{i}(s) converged. □

This completes the proof of the theorem. □

Now although Theorem 7.13 is phrased in terms of a partial ordering P, we have not done anything to preserve the nonordering facts in P. Thus essentially what is proven is that every countable linear ordering with no infinite ascending sequences (i.e. those of the form α^{∗} for a countable ordinal α) can be embedded in E_{sst}. We expect that further work along these lines should extend the result to all linear orderings. Adding the requirements to preserve nonorder needs additional types of arguments. We might also expect that the stronger result that makes A_{i} ≰_{T} A_{j} if i ≮_{P} j and i ≠ j is also true. Csima and Soare do this for the linear ordering ℤ in [2] and a tree argument should produce the same extension of Theorem 3.1 embedding every countable ordering in E_{st}. We thus close with a conjecture.

Conjecture 7.16. For every countable partial ordering P there is an embedding into the c.e. sets taking i ∈ P to A_{i} that is order preserving with respect to both <_{sst} and <_{T}, i.e. if i <_{P} j, then A_{i} <_{sst} A_{j} (and so, a fortiori, A_{i} ≤_{T} A_{j}) and if i ≮_{P} j and i ≠ j, then A_{i} ≰_{T} A_{j} (and so, a fortiori, A_{i} ≮_{sst} A_{j}). (Note that if i ≠ j, then either i ≮_{P} j or j ≮_{P} i and so A_{i}≢_{T} A_{j}.)

References

[1] B. F. Csima, Applications of Computability Theory to Prime Models and Differential Geometry, Ph.D. thesis, The University of Chicago, 2003.

[2] B. F. Csima and R. I. Soare, Computability Results Used in Differential Geometry, Journal of Symbolic Logic, to appear.

[3] A. Nabutovsky and S. Weinberger, The Fractal Nature of Riem/Diff I, Geometrica Dedicata 101 (2003), 1–54.

[4] H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.

[5] R. I. Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer-Verlag, Heidelberg, 1987.

[6] R. I. Soare, Computability theory and differential geometry, Bull. Symb. Logic 10 (2004), 457–486.

[7] R. I. Soare, Computability Theory and Applications, Springer-Verlag, Heidelberg, to appear.

[8] S. Weinberger, Computers, rigidity and moduli. The large scale fractal geometry of Reimannian moduli space, M.B. Porter Lectures, Princeton UNiversity Press, Princeton NJ, 2005.

Department of Pure Mathematics, University of Waterloo, Waterloo, ON, Canada N2L 3G1

URL: www.math.uwaterloo.ca/∼csima
E-mail address: csima@math.uwaterloo.ca

Department of Mathematics, Cornell University, Ithaca NY 14853

URL: http://www.math.cornell.edu/∼shore/
E-mail address: shore@math.cornell.edu