Π_{1}^{0} CLASSES WITH COMPLEX ELEMENTS.

STEPHEN BINNS

Abstract. An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a Π_{1}^{0} class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y ⊆ ω there is an X in P such that X ⩾_{wtt} Y. We show that this is also equivalent to the Π_{1}^{0} class’s being large in some sense. We give an example of how this result can be used in the study of scattered linear orders.

§1. Introduction. There has been interest in the literature over many years in studying various notions of the size of subclasses of 2^{ω}. In this paper we have tried to generalise and consolidate some of these ideas within the context of computability theory.

One of the most basic notions of size is that of cardinality - the two most commonly distinguished cardinalities being those of ω and 2^{ω}. The most famous conjecture in this area is of course the continuum hypothesis (CH), which claims that there is no subclass of 2^{ω} of intermediate cardinality. Although CH has been known to be independent of ZFC for about 50 years, the situation for closed subsets of 2^{ω} is much simpler, as every uncountable closed subclass of 2^{ω} has a perfect subclass (one with no isolated points) and hence continuum many elements.

In this paper we investigate one possible computability theoretic analogue of this situation. Instead of arbitrary closed subclasses of 2^{ω} and perfect subclasses we look at effectively closed classes (so called Π_{1}^{0} classes) and an effective version of perfect classes, which we dub computably perfect classes.

The concept of computable perfection has appeared independently under different names in [2] and [5] (computably growing in [5] and non-uphi in [2]). It is a relatively straightforward and natural computability theoretic notion and we give the formal definition in Section 2, but the idea is that a subclass of 2^{ω} is computably perfect if there is a computable witness to the fact that it has no isolated points. In effect a computably perfect class has a computable witness to the fact that it has continuum many elements. We declare to be diminutive those classes that fail to contain a computably perfect subclass.

Received by the editors October 17, 2007.

1991 Mathematics Subject Classification. Computability Theory, Recursion Theory.

Key words and phrases. Π_{1}^{0} class, complex, randomness, ranked, scattered linear order, computably growing, Muchnik.

Thanks to Joe Miller for helpful conversations on this subject.

In Section 2.1, we make a neat connection between diminutive classes and Kolmogorov complexity. A real X ∈ 2^{ω} is complex if there is a computable lower bound for the Kolmogorov complexity of its initial segments. That is if there is an unbounded computable function f such that for all n

C(X↾n) ⩾ f(n),

where C(X↾n) is the plain Kolmogorov complexity of X↾n.

In our main result, we show that a Π_{1}^{0} class is diminutive if and only if it does not contain a complex element. To the extent that this theorem connects the existence of a particular kind of real (a complex one) in a Π_{1}^{0} class with a global property of the Π_{1}^{0} class (computable perfection), the result is reminiscent of Kučera’s theorem that a Π_{1}^{0} class of reals contains a Martin-Löf random if and only if the class has positive measure.

Diminutive classes are also useful in that they furnish us with the strongest possible generalisation of the Kučera-Gács Theorem. This theorem proved independently by Kučera [7] and Gács [4] states that every real number is wttcomputable from some random real. In fact, it is an easy consequence of other results of Kučera’s that every Π_{1}^{0} class of positive measure contains a wtt-cover for the class of reals (i.e. every real is wtt-computable from some element of any non-null Π_{1}^{0} class). The Kučera-Gács theorem has been generalised in by Hertling in [5] where it is shown that every computably perfect Π_{1}^{0} class contains such a wtt-cover for the reals. In [9] Reimann proves that every Π_{1}^{0} class of positive Hausdorff dimension contains a computably perfect Π_{1}^{0} subclass, and hence a wtt-cover.

Here we establish the converse of Hertling’s result and provide Reimann’s result as an easy corollary of the main theorem in Section 2.1. We prove in Section 2.1 that a Π_{1}^{0} class contains a complex element if and only if it contains a wtt-cover for the reals. So the Π_{1}^{0} classes for which the Kučera-Gács theorem holds are exactly the ones containing complex elements which are exactly the ones that are not diminutive in the above sense. As all Π_{1}^{0} classes of positive Hausdorff dimension have complex elements, Reimann’s result follows.

In Section 3 we show that some commonly studied subclasses of 2^{ω} are diminutive. Countable classes, not having a perfect subclass of any kind, are of course diminutive, but also thin classes, small classes, and classes consisting of pairwise Turing incomparable elements are all diminutive. Classes of positive measure or Hausdorff dimension, and classes consisting of elements of DNR degree, are not diminutive.

In Section 4 we give an example of diminutive classes in the study of scattered linear orders. A linear order is scattered if it does not contain a suborder isomorphic to ℚ. It is well known that if a countable linear order is computable, then the class of (characteristic functions of) initial segments of the order forms a Π_{1}^{0} class of reals. In [8] it is shown that if a computable linear order has a complex initial segment, then the linear order is not scattered. Our theorem extends and sharpens this result, and we give a precise characterisation of computable linear orders that do not have complex initial segments. These we call weakly scattered linear orders. They are related to scattered linear orders in precisely the way that diminutive Π_{1}^{0} classes are related to countable Π_{1}^{0} classes. It is an immediate application of the main theorem of Section 2.1 that wtt-downward closure of the set of wtt-degrees of initial segments of a computable linear order is maximal if and only if the linear order is not weakly scattered.

This method of applying the main result of Section 2.1 should be easily generalisable and give results about the wtt-degree spectra of other computable structures and relations.

1.1. Notation and basic definitions. We first make explicit a few, mostly standard, definitions and notations. Undefined notation follows [11].

Basic notation.

• We use ω to denote the set of natural numbers; 2^{<ω} to denote the set of finite binary strings; and 2^{ω} is the set of infinite binary sequences. ω^{ω} is the collection of all functions from ω to ω. σ and τ will usually denote elements of 2^{<ω} and X and Y elements of 2^{ω}. λ denotes the empty string and if i ∈ {0, 1}, then σi denotes the concatenation of σ with ⟨i⟩. |σ| is the length of σ. σ ⊇ τ implies that σ extends τ and similarly for X ⊃ σ with X ∈ 2^{ω}. If σ ∈ 2^{<ω}, then [σ] = {X ∈ 2^{ω} : X ⊃ σ} and if S ⊆ 2^{<ω}, then [S] is the class ⋃{[σ] : σ ∈ S}.

• The standard topology will be assumed on 2^{ω}, the basic open sets of which are of the form [σ] for σ ∈ 2^{<ω}.

• If C ⊆ 2^{ω}, then the set of extendible nodes of C is the set

Ext(C) = {σ ∈ 2^{<ω} : ∃X ∈ CX ⊃ σ}.

The set of branching nodes of C is the set

Br(C) = {σ ∈ Ext(C) : σ0 ∈ Ext(C) ∧ σ1 ∈ Ext(C)}.

The set of branching levels of C is the set

Brl(C) = {|σ| : σ ∈ Br(C)}

If X ∈ C, then the branching level set along X is the set

Br_{X}(C) = {n ∈ ω : X↾n ∈ Br(C)}.

If σ ∈ Ext(C) then Br_{σ}(C) is defined similarly.

• If C, D ⊆ ω^{ω}, and if

∀X ∈ C∃Y ∈ DX ⩾_{T} Y,

then we say that D is Muchnik reducible to C and write C ⩾_{w} D. Surveys of Muchnik reducibility can be found in [1] and [10].

Definition 1.1. If X ⊆ ω, the principal function of X p_{X} is the function

p_{X}(n) = (n + 1)^{th} least element of X.

Definition 1.2. X ⊆ ω is said to be hyperimmune if p_{X} is not dominated by any computable function.

Definition 1.3. P ⊆ 2^{ω} is a Π_{1}^{0} class if it is the collection of paths through some computable tree of binary strings. Equivalently, P = {X ∈ 2^{ω} : ∀nR(n, X)} where R is a computable predicate on ω × 2^{ω}. Equivalently, P is Π_{1}^{0} if it is of the form 2^{ω} ∖ [S] where S is a c.e. subset of 2^{<ω}. If S_{s} is the enumeration of S at stage s, then P_{s} := 2^{ω} ∖ [S_{s}], and P = ⋂_{s} P_{s}.

Π_{1}^{0} classes can be defined other spaces including ω^{ω} and ℝ, however for the purposes of this paper, they will always be non-empty subsets of 2^{ω}.

§2. Computably perfect classes.

Definition 2.1. C ⊆ 2^{ω} is computably perfect if there is a computable and strictly increasing function f such that for every n ∈ ω and every σ ∈ Ext(C) of length f(n), there exist at least two extensions of σ in Ext(C) of length f(n+1).

Observation 2.2. It is straightforward to show that C is computably perfect if and only if it is closed and there is a computable function g such that for all n and all σ ∈ Ext(C) of length n, there exists at least two extensions of σ of length g(n).

Observation 2.3. It is also straightforward to show that C is computably perfect if and only if there is a computable function f such that for all X ∈ C and for all n ∈ ω

||Br_{X↾f(n)}(C)|| ⩾ n.

Lemma 2.4. If a Π_{1}^{0} class P contains a computably perfect subclass, then P also contains a computably perfect Π_{1}^{0} subclass.

Proof. Let C be any computably perfect subclass of P witnessed by the computable function f. Define the set S to be

{σ : ∃s∃n ⩽ sσ ∈ Ext(P_{s}) ∧ |σ| = f(n) ∧ ∃!τ ∈ Ext(P_{s})[τ ⊇ σ ∧ |τ| = f(n + 1)]}.

Then P ∖ [S] is Π_{1}^{0} , contains C and is computably perfect. ⊣

We will make extensive use of the following idea from algorithmic complexity theory.

Definition 2.5. X ∈ 2^{ω} is complex if there is a computable function f such that for all n

C(X↾f(n)) ⩾ n.

Here C(σ) denotes the plain Kolmogorov complexity of the string σ. Alternatively, we could have used the prefix-free complexity K(σ) as C(σ) and K(σ) differ by at most a multiplicative constant. We may also equivalently define X to be complex if there exists a computable f such that for all n C(X↾n) ⩾ f(n).

The following two definitions are standard.

Definition 2.6. If X, Y ∈ 2^{ω}, then Y is weak truth-table reducible to X (X ⩾_{wtt} Y) if X ⩾_{T} Y and there is a total computable function f such that for all n, the use of X in calculating Y (n) is bounded by f(n).

Definition 2.7. If f ∈ ω^{ω}, then f is DNR if ∀nf(n) ≠ {n}(n), where {n} is the n^{th} partial computable function.

The major result we will be using with regards to complexity is Theorem 6 in [12]:

Lemma 2.8. For A ∈ 2^{ω}, A is complex if and only if A wtt-computes a DNR function.

There are of course many Π_{1}^{0} classes that contain complex elements - 2^{ω} obviously. The following two lemmas give two less trivial examples.

Definition 2.9. The effective Hausdorff dimension of X ∈ 2^{ω} dim_{H}^{1}(X) can be defined to be lim inf_{n} C(X↾n)/n. For a class C ⊆ 2^{ω},

dim_{H}^{1}(C) = sup{dim_{H}^{1}(X) : X ∈ C}.

For a Π_{1}^{0} class P the effective Hausdorff dimension of P is equal to its classical Hausdorff dimension dim_{H}(P). A good survey of Hausdorff dimension, both effective and classical, as it applies to the space 2^{ω} is given in [9].

Lemma 2.10. If P is a Π_{1}^{0} class and if dim_{H}(P) > 0, then P has a complex element.

Proof. If X ∈ 2^{ω} is not complex, then for all rational s > 0 ∃^{∞}nC(X↾n) < sn. Therefore, for all such s, lim inf_{n} C(X↾ n)/n < s and thus dim_{H}^{1}(X) = 0. So, if every element of P is noncomplex,

dim_{H}(P) = dim_{H}^{1}(P) = sup{dim_{H}^{1}(X) : X ∈ P } = 0
⊣

Lemma 2.11. If P is Π_{1}^{0}, and if P ⩾_{w} DNR, then P has a complex element.

Proof. Every Π_{1}^{0} class contains a hyperimmune-free element (see [6]), and for any such element X and any Y ⩽_{T} X, we also have that Y ⩽_{wtt} X. Thus if X computes an element of DNR, it must be complex by Lemma [12].

⊣

2.1. The Main theorem.

Definition 2.12. C ⊆ 2^{ω} is a wtt-cover for 2^{ω} if every element of 2^{ω} is wttreducible to an element of C.

Theorem 2.13. For any Π_{1}^{0} class P the following are equivalent:

1. P contains a wtt-cover for 2^{ω},

2. P contains a complex element X,

3. P contains a computably perfect Π_{1}^{0} subclass containing X.

Proof. 1 ⇒ 2. P must contain an element that wtt-computes an element of a DNR set, and

thus by Lemma [12], must contain a complex element.

2 ⇒ 3. Let f be computable and such that C(X ↾ f(n)) ⩾ n for all n. Define, for

parameter u ∈ ω a function g as follows.

1. g(0) = f(0)

2. g(n + 1) = f(2g(n) + u). We will use u for bookkeeping purposes at the end of the argument.

We have immediately that for all n,

C(X↾g(n + 1)) = C(X↾f(2g(n) + u)) ⩾ 2g(n) + u

and from basic principles that

C(X↾g(n)) < 2g(n) + d

for some fixed constant d.

To get a contradiction, suppose now that X is not contained in any computably perfect Π_{1}^{0} subclass of P. Consider the Π_{1}^{0} class Q ⊆ P constructed in the following way. We let Q_{0} = P_{0} = 2^{ω}, S_{0} = ∅, and for each s let

S_{s+1} = {σ ∈ Ext(Q_{s}) : ∃n < s|σ| = g(n)∧∃!τ ∈ Ext(Q_{s})[τ ⊇ σ∧|τ| = g(n+1)]},

and Q_{s+1} = (P_{s+1} ∩ Q_{s}) ∖ [S_{s+1}].

Q = ⋂_{s} Q_{s} is either computably perfect (witnessed by g) or empty. In either case X ∉ Q and so X must extend some element of S_{s+1} for some least s. Let n < s be such that X↾g(n) ∈ S_{s+1}. There is thus a unique extension of X↾g(n) in Ext(Q_{s}) of length g(n + 1), namely X↾g(n + 1).

Now consider a machine M that acts as follows. Taking input τ ∈ 2^{<ω} of length g(m) for some m, M waits for a stage s such that τ ∈ S_{s+1}. If such a stage exists, then M outputs the unique string on Ext(Q_{s}) extending τ of length g(m + 1). Thus, for n and X as above, M(X ↾ g(n)) = X ↾ g(n + 1) and so C(X↾g(n + 1)) ⩽ C(X↾g(n)) + O(1).

The constant term O(1) depends uniformly on a Π_{1}^{0} index for Q, so there is a computable function k such that, for any Π_{1}^{0} index e for Q,

C(X↾g(n + 1)) ⩽ C(X↾g(n)) + k(e).

Furthermore, there is a computable function φ, that will give such an index for Q uniformly in the parameter u. Using the recursion theorem we choose a u such that the Π_{1}^{0} class with index u is equal to the Π_{1}^{0} class whose index is φ(d + k(u)). Then the Q that is built using parameter d + k(u) is equal to the Π_{1}^{0} class with index u. Thus, if g is defined using the parameter d + k(u),

C(X↾g(n + 1)) ⩽ C(X↾g(n)) + k(u).

Therefore for such a g, u and n,

2g(n) + d + k(u) ⩽ C(X↾g(n + 1)) ⩽ C(X↾g(n)) + k(u) < 2g(n) + d + k(u),

giving the required contradiction.

3 ⇒ 1.

Let P be computably perfect, witnessed by a computable function f. If X ∈ 2^{ω} define a sequence of nodes σ_{i}, as follows: let σ_{0} = λ and let σ_{i+1} be the leftmost extendible node of P of length f(i+1) extending σ_{i} if X(i) = 0, and the rightmost such node of length f(i+1) if X(i) = 1. Such nodes are always distinct as σ_{i} has at least two extensions of length f(i + 1) by assumption. Let Y ∈ P be ⋃_{i} σ_{i}.

To recover X(n) from Y, wait for a stage s such that Y ↾f(n+1) is the leftmost or rightmost node extending Y ↾f(n) in P_{s}. Such a stage will always occur as Q is Π_{1}^{0} . The use of Y in the computation of X(n) is bounded by f(n + 1) and hence Y ⩾_{wtt} X.

⊣

Corollary 2.14. The following classes all contain wtt-covers for 2^{ω}:

1. (Kuc̆era-Gács) the class of Martin-Löf randoms,

2. any Π_{1}^{0} class of positive measure,

3. ([9], Thm 3.25) any Π_{1}^{0} class with positive Hausdorff dimension,

4. any Π_{1}^{0} class P ⩾_{w}DNR.

Proof. 1) The class of Martin-Löf randoms forms a Σ_{2}^{0} class - a union of Π_{1}^{0} classes . Any one of these component Π_{1}^{0} classes contains a wtt-cover for 2^{ω} as every random is complex. 2) Any Π_{1}^{0} class of positive measure contains a random, and hence a complex. 3) and 4) are immediate from Lemmas 2.10 and 2.11. ⊣

§3. Diminutive classes.

Definition 3.1. C ⊆ 2^{ω} is diminutive if it does not contain a computably perfect subclass.

There are many examples of diminutive classes already existing in the literature. The simplest examples are countable Π_{1}^{0} classes (every perfect subclass of 2^{ω} is uncountable) and these have been studied in [13] and elsewhere. We give some more examples now.

Definition 3.2. A Π_{1}^{0} class P is small if Br(P) is hyperimmune. It is observed in [1] that it is equivalent that the branching level set

Brl(P) = {n ∈ ω : ∃σ ∈ Br(P)|σ| = n}

is hyperimmune.

Definition 3.3. A Π_{1}^{0} class P is e.p.h.i. (everywhere pathwise hyperimmune) if for all X ∈ P the set Br_{X}(P) = {n : X↾n ∈ Br(P)} is hyperimmune.

Definition 3.4. A Π_{1}^{0} class P is a Jockusch-Soare class (js-class) if for all distinct X, Y ∈ P X ⩾̸_{T} Y.

Definition 3.5. A Π_{1}^{0} class P is thin if every Π_{1}^{0} subclass of P is the intersection of a clopen subclass of 2^{ω} with P. That is, every Π_{1}^{0} subclass of P is clopen in the relative topology.

Small classes are special instances of e.p.h.i. classes, because if the branching level set is hyperimmune, then certainly the branching set along any path will also be hyperimmune. We prove next that every thin class is e.p.h.i. and that every e.p.h.i. class is diminutive. We then show that every js-class is diminutive.

Lemma 3.6. No thin Π_{1}^{0} class is computably perfect.

Proof. The proof is very similar to Simpson’s proof that all thin Π_{1}^{0} classes have zero measure. We prove the contrapositive. Suppose a Π_{1}^{0} class P is computably perfect, witnessed by the computable function f. Without losing generality we can assume that for all s P_{s} is computably perfect witnessed by f.

Define a computable double sequence of elements of 2^{<ω} as follows: σ_{1,s} = the rightmost string in Ext(P_{s}) of length f(1) σ_{i+1,s} = the rightmost string in Ext(P_{s}) of length f(i + 1)

strictly to the left of σ_{n}

To prove that σ_{i,s} exists for all i and s we use a simple induction to prove that for all i > 0 and s ⩾ 0 there is a τ ∈ Ext(P_{s}) of length f(i) such that τ is strictly to the left of σ_{i,s}. If τ is the rightmost such string, then σ_{i+1} will be the rightmost element in Ext(P) of length f(i + 1) extending τ.

Base case: There are at least two elements of Ext(P) of length f(1), so there must be a τ ∈ Ext(P) of length f(1) strictly to the left of σ_{1}.

Induction: Suppose that τ is the rightmost element in Ext(P_{s}) of length f(i) strictly to the left of σ_{i,s}. There must be at least two extensions of τ in Ext(P_{s}) of length f(i + 1). Therefore there must be a τ′ ∈ Ext(P_{s}) of length f(i + 1) strictly to the left of σ_{i+1}.

If we let σ_{i} = lim_{s} σ_{i,s} for each i, then the strings σ_{i} are pairwise incomparable and form a leftwards monotone sequence. Therefore the class

S = {X ∈ 2^{ω} : ∃i∃sX↾f(i) is to the right of σ_{i,s}}

is not closed (it does not contain its leftmost limit point). However S is Σ_{1}^{0} and hence open by inspection, and so P ∖ S is a non-clopen Π_{1}^{0} subclass of P and P is not thin.

⊣

Corollary 3.7. No thin Π_{1}^{0} class contains a computably perfect subclass.

Proof. By Lemma 2.4, if a thin Π_{1}^{0} class T contained a computably perfect subclass, it would contain a computably perfect Π_{1}^{0} subclass T′. Any Π_{1}^{0} subclass of a thin class is also thin so T′ would be a thin and computably perfect, contradicting the theorem. ⊣

This is enough to show that all thin classes are diminutive, but we can go further:

Theorem 3.8. Every thin Π_{1}^{0} class is e.p.h.i.

Proof. Suppose a Π_{1}^{0} class P is thin and not e.p.h.i. and let f be a computable function such that for some element X of P f dominates Br_{X}(P). Consider the set of all such elements:

P′ = {Y ∈ P : ∀n||Br_{Y ↾n}(P)|| ⩾ f(n)}.

P′ is a then non-empty Π_{1}^{0} subclass of P. As P is thin, P′ is a clopen subclass of P and there is a fixed constant c such that for all X ∈ P′ the sets Br_{X}(P) and Br_{X}(P′) differ by at most c elements. Thus for some finite adjustment f′ of f, and all X ∈ P′

∀n||Br_{X↾n}(P′)|| ⩾ f′(n),

and thus f′ witnesses the fact that P′ is computably perfect. Thus by Lemma 3.6 P′ is not thin and hence neither is P. ⊣

Theorem 3.9. E.p.h.i. classes contain no computably perfect subclass.

Proof. Let P be e.p.h.i. and suppose P′ ⊆ P is computably perfect witnessed by f. Then for all X ∈ P and all n ∈ ω, there is a branching node on P′ between X↾ f(n) and X↾ f(n + 1). As the branching nodes of P′ form a subset of the branching nodes of P, f also witnesses the fact that P is not e.p.h.i., contradiction. ⊣

Finally we show that js-classes are diminutive.

Theorem 3.10. Js-classes are diminutive.

Proof. Let P be a js-class and suppose it is not diminutive. Then by Theorem 2.13 P contains a complex element. Let σ be the shortest branching node on P and consider P^{0} = {X ∈ P : X ⊃ σ0} and P^{1} = {X ∈ P : X ⊃ σ1}. Without losing generality, suppose P^{0} contains a complex element. Then by Theorem 2.13 P^{0} contains a wtt-cover for 2^{ω}, and hence contains elements that compute elements of P^{1}, contradicting the fact that P is a js-class. ⊣

§4. Weakly scattered linear orderings. This section expands on some of the results in [8]. We use Theoerem 2.13 to characterise those computable linear orders whose classes of initial segments contain a wtt-cover for 2^{ω}. We first reproduce the proof that a countable linear order contains a copy of ℚ as a suborder if and only if its class of initial segments contains a perfect subclass. Then we show how this relates to the work in earlier sections.

If L = ⟨ω, <_{L}⟩ is a countable linear order, we will denote the set of (characteristic functions of) initial segments of L by

Seg(L) = {f : ∀n, m[(f(n) = 1 ∧ m <_{L} n) ⇒ f(m) = 1]}.

Definition 4.1. A countable linear order is scattered if it does not contain a suborder isomorphic to ℚ.

Recall that C ⊆ 2^{ω} is perfect if it contains no isolated points. The following is well-known.

Theorem 4.2. A linear order L is scattered if and only if it Seg(L) does not contain a perfect subclass. In fact if Seg(L) contains a perfect subclass C, then the branching level set S := Brl(C) = {|σ| : σ ∈ Br(C)} is isomorphic to ℚ.

Proof. First assume that Seg(L) contains a perfect subclass C. We show that S is a dense linear order with no endpoints.

Let σ be an arbitrary element of Br(C). Let σ^{0}, σ^{1} ∈ Br(C) such that σ^{0} ⊋ σ0 and σ^{1} ⊋ σ1. Both exist as C is perfect. Thus there is an X ∈ Seg(L) such that X(|σ|) = 0 and X(|σ^{0}|) = 1, so |σ^{0}| <_{L} |σ|. Similarly, there is an initial segment Y such that Y (|σ|) = 1 and Y (|σ^{1}|) = 0 and so |σ| <_{L} |σ^{1}|. So S has no endpoints.

To show that S is dense, let σ and τ be arbitrary elements of Br(C) with |σ| <_{L} |τ|. We divide into two cases:

Case 1. σ and τ are incomparable. Let γ be any branching node extended by both σ and τ. By an argument similar to above we must have σ <_{L} γ <_{L} τ.

Case 2. σ and τ are comparable. As |σ| <_{L} |τ|, we must have either σ ⊇ τ0 or τ ⊇ σ1. Assume first that σ ⊇ τ0. Let γ ∈ Br(C) such that γ ⊇ σ1. So there is an X ∈ Seg(C) such that X(|σ|) = X(|γ|) = 1 and X(|τ|) = 0, and a Y ∈ Seg(C) such that Y (|τ|) = Y (|γ|) = 0 and Y (|σ|) = 1. Therefore, |σ| <_{L} |γ| <_{L} |τ|. We argue similarly if τ ⊇ σ1.

Conversely, suppose L contains a suborder M isomorphic to ℚ. Then M has uncountably many initial segments, and hence so does L. As Seg(L) is closed, it contains a perfect subclass.

⊣

We now weaken the notion of scatteredness in a way that allows us to replace perfection in the previous theorem with computable perfection.

Definition 4.3. A countable linear order L = ⟨ω, <_{L}⟩ is weakly scattered if there does not exist an S ⊆ ω and a computable function f such that for all n ∈ ω,

∀a, b ∈ S ∩ [0, n]∃x, y, z ∈ S ∩ [0, f(n)]x <_{L} a <_{L} y <_{L} b <_{L} z.

Notice that such an S is isomorphic to ℚ, and so any scattered linear order is necessarily weakly scattered. Furthermore, if we are given a, b ∈ S, the problem of finding x, y, z such that x <_{L} a <_{L} y <_{L} b <_{L} z is the problem of finding certain branching nodes on Seg(L). This suggests a connection with diminutive Π_{1}^{0} classes and we make this explicit now.

Theorem 4.4. A countable linear order L = ⟨ω, <_{L}⟩ is not weakly scattered if and only if Seg(L) contains a computably perfect subclass.

Proof. Suppose L is not weakly scattered, witnessed by the suborder S = ⟨S, ⩽_{L}⟩ isomorphic to ℚ, and computable function f. Let P = Seg(S), n ∈ ω, and σ ∈ Ext(P) of length n. Let a = max_{L}{c < n : σ(c) = 1} (−∞ if empty) and b = min_{L}{c < n : σ(c) = 0} (∞ if empty). As σ(a) = 1 and σ(b) = 0, and σ ∈ Ext(P), we must have a <_{L} b. As f witnesses the fact that L is not weakly scattered, there is an y ∈ S ∩ [0, f(n)] such that a <_{L} y <_{L} b. So there are two initial segments X, Y of S, both extending σ, such that X(y) = 0 and Y (y) = 1. Thus σ has at least two extensions of length f(n) in Ext(P) and by Observation 2.2, P is computably perfect.

Conversely, suppose Seg(L) contains a computably perfect subclass P. As before, S = {|σ| : σ ∈ Br(P)} will be the domain of the suborder isomorphic to ℚ. Let n ∈ ω and σ, τ ∈ Br(P) be arbitrary and without losing generality suppose |σ| <_{L} |τ|. Arguing as in Theorem 4.2, f allows us to find upper bounds for the minimum lengths of branching nodes extending σ and τ and thus allows us to find an upper bound for some x, y, z such that x <_{L} |σ| <_{L} y <_{L} |τ| <_{L} z. So from f we can easily compute a witness to the fact that Seg(L) is not weakly scattered.

⊣

It is necessary now of course to show that the two concepts are not equivalent.

Theorem 4.5. There is a weakly scattered linear ordering that is not scattered.

Proof. We create such an order L using a priority argument. Let η be the order type of ℚ. L will be an η-order of finite linear orders or blocks B_{i}. Any element of a block may act as an index for the block. We write B_{i} <_{L} B_{j} if every element of B_{i} is <_{L} every element of B_{j} (equivalently if some element of B_{i} is <_{L} some element of B_{j}) .

We enumerate elements of ω in numerical order into L in stages. As usual L_{s} = ⟨L_{s}, <_{L}⟩ is the order at stage s. At each stage, one element of ω is enumerated between each pair of adjacent blocks and at each end of the sequence of blocks. New elements will never be enumerated into blocks. These newly enumerated elements will be singleton blocks.

Notice that if S = ⟨S, <_{L}⟩ is a suborder of L isomorphic to ℚ, then S can contain at most one element from each block. We leverage this fact to create L with the required properties. We build L to ensure that

1. L has a suborder S = ⟨S, <_{L}⟩ isomorphic to ℚ,

2. for every such S, S is hyperimmune.

1 ensures that L is not scattered and 2 is sufficient to ensure that L is weakly scattered. To see this, let S be a suborder of L isomorphic to ℚ and consider P = Seg(S). Then Brl(P) = {|σ| : σ ∈ Br(P)} = S is hyperimmune and so P is small by the observation in Definition 3.2. Therefore P does not contain a computably perfect subclass, and so L is weakly scattered.

During the construction to satisfy a requirement we may merge adjacent blocks into one block. This will change the order relation on the blocks but not on L. Each block will thus be a finite c.e. set. B_{i,s} denotes the set of elements enumerated into B_{i} by stage s. Each block B_{i,s} has associated with it a restraint number r(i, s). No requirement may force the merging of a block unless the index of the requirement is lower than the restraint number of the block. All newly enumerated singleton blocks B_{i,s} have r(i, s) = ∞. We will satisfy the following requirements.

Q: L contains a suborder isomorphic to ℚ.

R_{e}: for any suborder S of L isomorphic to ℚ, then {e} does not

dominate p_{S} the principal function of S. Requirement Q will be satisfied by the enumeration at each stage of singleton

blocks between and at each end of existing blocks, and we need to take no other action to ensure its satisfaction.

In order to satisfy requirement R_{e}, we wait for a stage s at which {e}_{s}(n) ↓ for some 1 ⩽ n ⩽ s. We then attempt to merge a sufficient number of adjacent blocks to ensure that ||{B_{i,s+1} : i ⩽ {e}_{s}(n)}|| ⩽ n. If we succeed in this, then S will contain at most n elements less that or equal to {e}(n) and so p_{S}(n) > {e}(n). Thus {e} will not dominate p_{S}. Merging other blocks to satisfy other requirements later on in the construction will never injure R_{e} (as the merging of blocks can never decrease the principal function of S) and so the requirement is satisfied forever. We thus need to show only that each requirement has an opportunity to act.

We say requirement R_{e} requires attention at stage s if it is not satisfied (see below) and if there is an n ⩽ s such that {e}_{s}(n) ↓ and it is possible to

1. enumerate all unused numbers up to and including {e}(n) onto the righthand end of L_{s}, as singleton blocks,

2. and then merge some number of blocks (respecting the restraint numbers) so that ||{B_{i,s+1} : i ⩽ {e}(n)}|| ⩽ n.

If e is the lowest number such that R_{e} requires attention, we take the following action: we carry out 1 and 2 above, and change the restraint numbers of any newly merged blocks to e. The requirement is then declared to be satisfied.

Lemma 4.6. L contains a copy of ℚ.

Proof. Each requirement R_{e} can act at most once, as once it acts it is declared satisfied and never again requires attention. No block can be merged by a requirement R_{e} if its restraint number is less than e. Thus each block can be merged only a finite number of times, and is thus finite. Let S be a subset of L containing exactly one element from each block. The claim is that ⟨S, <_{L}⟩ is isomorphic to ℚ.

Let a, b ∈ S such that a <_{L} b. Let s be a stage after which neither B_{a} nor B_{b} are merged with any other block. At stage s + 1 elements x, y, z are enumerated so that B_{x} <_{L} B_{a} <_{L} B_{y} <_{L} B_{b} <_{L} B_{z}. Thus ⟨S, <_{L}⟩ is a countable dense linear order without endpoints and hence isomorphic to ℚ. ⊣

Lemma 4.7. If S ⊆ L such that ⟨S, <_{L}⟩ is isomorphic to ℚ, then S is hyperimmune.

Proof. We show that if S contains exactly one element from every block, then S is hyperimmune. This is sufficient as any subset of L that is isomorphic to ℚ contains at most one element from each block, and is thus a subset of such an S and therefore also hyperimmune.

Let {e} be any total computable function and let s be a stage at which no requirement R_{i} requires attention after stage s for any i < e. Let m = ||{B_{i,s} : r(i, s) < e}||. No such B_{i,s} will merge at any later stage, and thus B_{i,s} = B_{i} for all i < e. We wait for a stage t ⩾ s such that {e}_{t}(2m + 1) ↓. We can then enumerate all unused numbers less than and equal to {e}_{t}(2m + 1) at the righthand end of the order and proceed to merge blocks as follows.

Let

B_{i_{1},t} <_{L} B_{i_{2},t} <_{L} ⋯ <_{L} B_{i_{m},t}

be the set of blocks with r(i, t) < e. We then merge all blocks B_{j,t} <_{L} B_{i_{1},t} into one block, and similarly with all blocks B_{j,t} >_{L} B_{i_{m},t}. We also, for each k < m, merge into one block all blocks B_{j,t} with B_{i_{k},t} <_{L} B_{j,t} <_{L} B_{i_{k+1},t}. We are thus left with 2m+1 blocks in the ordering. All numbers less than or equal to {e}(2m + 1) are contained within these blocks so p_{S}(2m + 1) > {e}(2m + 1) and {e} does not dominate p_{S}. As {e} was an arbitrary total computable function, S is hyperimmune. ⊣

⊣

We are primarily concerned here with computable linear orders. If L is a computable linear ordering, then Seg(L) forms a Π_{1}^{0} class by inspection of the above definition . Furthermore,

Theorem 4.8. If a computable linear order L is not weakly scattered, it contains a co-c.e. copy of ℚ.

Proof. If Seg(L) contains a computably perfect subclass, it contains a computably perfect Π_{1}^{0} subclass P by Lemma 2.4. As above, the set Brl(P) = {|σ| : σ ∈ Br(P)} is isomorphic to ℚ. The branching level set of any Π_{1}^{0} class is co-c.e. ⊣

Theorem 4.9. The following are equivalent for a computable linear order L

1. L is not weakly scattered,

2. Seg(L) is not diminutive,

3. Seg(L) contains a complex element,

4. Seg(L) contains a wtt-cover for 2^{ω}.

Proof. This is just Theorem 4.4 and Theorem 2.13.

⊣

Corollary 4.9 in [8] states that if 0′ is wtt-reducible to an element of Seg(L), then there is a Δ_{2}^{0} suborder isomormphic to ℚ. The following improvement is to some degree inherent in their work, and the quasi-converse follows from the above results.

Corollary 4.10. For a computable linear order L, if Seg(L) contains a complex element, then L has a co-c.e. suborder isomorphic to ℚ. Furthermore, the converse holds if L is not weakly scattered.

REFERENCES

[1] Stephen Binns, The Medvedev and Muchnik lattices of Π_{1}^{0} classes, Ph.D. thesis, The Pennsylvania State University, 2003, 80 pages.

[2] , Hyperimmunity in 2^{ω}, Notre Dame Journal of Formal Logic, vol. 48 (2007), no. 2, pp. 293–316.

[3] H.-D. Ebbinghaus, G.H. Müller, and G.E. Sacks (editors), Recursion Theory Week, Lecture Notes in Mathematics, no. 1141, Springer-Verlag, 1985, IX + 418 pages.

[4] P. Gács, Every sequence is reducible to a random one., Information and Control, vol. 70 (1986), pp. 186–192.

[5] Peter Hertling, Surjective functions on computably growing Cantor sets, Journal of Universal Computer Science, vol. 3 (1997), no. 11, pp. 1126–1240.

[6] Carl G. Jockusch, Jr. and Robert I. Soare, Π_{1}^{0} classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 35–56.

[7] Antonín Kučera, Measure, Π_{1}^{0} classes and complete extensions of PA, [3], 1985, pp. 245–259.

[8] John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch Jr., Timothy McNicholl and Sarah Pingrey, Π_{1}^{0} classes and strong degree spectra of relations, Preprint.

[9] Jan Reimann, Computability and fractal dimension, Ph.D. thesis, Ruprecht-Karls-Universität, Heidelberg, 2004, 130 pages.

[10] Stephen G. Simpson, Mass problems and randomness, The Bulletin of Symbolic Logic, pp. 29 pages, to appear.

[11] Robert I. Soare, Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer-Verlag, 1987, XVIII + 437 pages.

[12] Bjørn Kjos-Hanssen, Wolgang Merkle, Frank Stephan, Komolgorov complexity and the recursion theorem, Lecture Notes in Computer Science, 3884, (2006), pp. 149–161.

[13] Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare, Richard A. Shore, Stanley S. Wainer, Members of countable Π_{1}^{0} classes, Annals of Pure and Applied Logic, vol. 31 (1986), no. 2-3, pp. 145–163.

DEPARTMENT OF MATHEMATICS AND STATISTICS

KING FAHD UNIVERSITY OF PETROLEUM AND MINERALS

PO BOX 5046 DHAHRAN 31261, SAUDI ARABIA

E-mail: binns@kfupm.edu.sa