Finding paths through narrow and wide trees

Stephen Binns Department of Mathematics and Statistics King Fahd University of Petroleum and Minerals Dhahran 31261 Saudi Arabia

Bjørn Kjos-Hanssen ^{∗} Department of Mathematics University of Hawai‘i at Mānoa Honolulu, HI 96822 USA

March 8, 2008

Abstract

We consider two axioms asserting the existence of infinite paths through infinite but “narrow” binary trees. These axioms are shown to be incomparable, in the sense of reverse mathematics, to axioms asserting existence of paths through “wide” trees (WWKL and DNR). In particular, they are strictly weaker than Weak König’s Lemma (WKL), which asserts the existence of paths through arbitrary infinite binary trees.

1 Introduction

We investigate here two new subsystems of second-order arithmetic and compare their logical strengths to those of known systems. We are concerned in particular with subsystems that are strictly weaker than Weak König’s Lemma WKL and, even more specifically, those consisting of axioms that dictate the existence of infinite paths through binary trees. Of course any axiom that implies the existence of at least one path through every infinite binary tree is at least as strong as WKL, but we will apply such path-existence axioms to restricted sets of trees. This direction of inquiry is informed by work done by Simpson [13], Giusto, Brown [3] and others on the axiom WWKL, Weak Weak König’s Lemma. WWKL states that every tree of positive measure (defined in terms of first-order properties of the tree) has a path. This is shown to be strictly weaker than WKL and significant reversals were established to theorems of analysis. The fact that WWKL is weaker than WKL appeals to the intuition as one feels that it should be easier to find a path through a tree that has many paths in some sense. Indeed if one chooses left or right at random one always has a nonvanishing probability of finding a path through such a tree. It is perhaps slightly paradoxical that an opposite heuristic is also applicable. That is, if a tree has few paths (in some sense) then it is also relatively easy to find a path. If one imagines that one is at some (infinitely extendible) node σ on some infinite binary tree and having to make a decision of whether to proceed to the left or right, one can wait until it becomes apparent that the tree above σ0 or the tree above σ1 is finite (we are assuming here that the set of nodes on the tree is known). If σi is finite, we take the path through σ(1 − i). This strategy will work in allowing us to decide on an infinitely extendible extension of σ if and only if there is there is only one such extension - that is if σ is not a branching node of T. The intuition behind our weakening of WKL is that it is easier to find paths through trees that have a small (again in some particular sense of small) set of branching nodes.

∗Partially supported as co-PI by NSF grant DMS-0652669.

This leaves just the question about the appropriate definition of small. There are of course some obvious candidates. One is that the set of branching nodes is finite; another is that the set of branching nodes has a maximal (in the sense of extension) element. In both situations the above strategy of waiting until it becomes clear which direction to take will succeed in finding a path if one starts at this maximal branching node (or at the root of the tree if no branching nodes exist). However these notions of smallness are too strong in the sense that in both cases RCA_{0} proves that every tree with a small set of branching nodes has a path. We thus weaken these notions to give us principles that are strictly stronger than RCA_{0} . We do this with the help of bounding witnesses.

Suppose Φ(n, m) is a formula in second order arithmetic, with free variables n, m. We say f is a strong bounding witness for Φ if

∀n∃m ⩽ f(n)Φ(n, m).

And we say f is a weak bounding witness for Φ if

∃^{∞}n∃m ⩽ f(n)Φ(n, m).

The revised concepts of smallness that we use in the paper are as follows:

1. the set of branching nodes Br(T) is small if there is no weak witness for the predicate

Φ_{1}(n, σ) ≡ [σ ∈ Br(T) ∧ σ ⩾ n];

2. the set of branching nodes is small if there is no strong witness for the predicate

Φ_{2}(σ, τ) ≡ [σ ∈ Ext(T) → (τ ∈ Br(T) ∧ τ ⊇ σ)],

where Ext(T) is the set of nodes on T with infinitely many extensions.

For any infinite binary tree T, ∀n∃σΦ_{1}(n, σ) is true if and only if T has infinitely many branching nodes, and ∀σ∃τΦ_{2}(σ, τ) is true if and only if T is perfect. The two axioms that these give rise to are:

1. VSMALL: If T is an infinite binary tree and there is no weak bounding witness for the predicate Φ_{1}, then T has a path.

2. DIM: If T is an infinite binary tree T and there is no strong bounding witness for the predicate Φ_{2}, then T has a path.

In the next section we give slightly different but equivalent versions of these two axioms. DIM is evidently strong than VSMALL as if a tree has a strong bounding witness for its perfection, the same witness serves as a weak bounding witness for the infinitude of its set of branching nodes. Our main result is that both DIM and VSMALL are independent of WWKL and the DNR axiom.

The DNR axiom is related to the simplest way of producing a non-computable function - diagonalisation. Take a computable enumeration of the partial computable functions ⟨φ_{e}⟩. Let f : ℕ → ℕ be such that f(e) ≠ φ_{e}(e) for all e. DNR is the principle that asserts the existence of such a function.

In [14] it is shown that DNR is a strictly weaker principle than WWKL, but is still non-constructive in the sense that there are models of RCA_{0} in which it fails. In fact it is a general rule that any principle which implies the existence of a non-computable set or function is non-constructive in this sense. This is so because there is a model of RCA_{0} all of whose sets are computable. We show that our axioms are independent of both DNR and WWKL.

We follow standard notation. ℕ is the set of natural numbers, 2^{ℕ} is the powerset of ℕ with standard topology and measure. φ_{e} is the e^{th} partial recursive function, and ⟨., .⟩ is a fixed computable bijection between ℕ and ℕ × ℕ. We will identify subsets of ℕ with their characteristic functions without comment. Lowercase Greek letters σ, τ, γ and so on will be used to denote elements of 2^{<ℕ} and upper case Roman letters X, Y and Z will usually denote elements of 2^{ℕ} or, equivalently, subsets of ℕ. The letters f, g and h will be used for elements of ℕ^{ℕ}. σ ⊂ X or σ ⊆ τ expresses the fact that the infinite binary sequence X or string τ extends σ. σi is the concatenation of σ and ⟨i⟩. A tree will be a subset of 2^{<ℕ}, with ⊆ as its partial order relation. The root of all trees will be the empty string λ. A path through a tree T is (the union of) an infinite maximal linearly ordered subset of T. The set of paths through T is denoted [T]. The cardinality of a set D is denoted ||D||.

2 The axiom systems VSMALL and DIM

It is easy to prove that any infinite binary tree with only finitely many branching nodes must have a path. In fact one can prove, just from the axiom system RCA_{0} , that any infinite binary tree with a maximal branching node must have a path (such a path is Δ_{1}^{0}-definable). In this paper we consider infinite binary trees whose sets of branching nodes are small in some sense. Translating into the language of second order arithmetic we describe axioms which state that if an infinite binary tree has only a small set of branching nodes, then the tree must have a path.

Definition 2.1. If T is a binary tree, then s ∈ T is an extendible node of T if the set {τ ∈ T : τ ⊇ σ} is infinite. The set of extendible nodes of T is denoted Ext(T).If P = [T], then by Ext(P) we mean Ext(T). σ ∈ T is a branching node of T if both σ0 and σ1 are extendible nodes. The set of branching nodes of T is denoted Br(T), and similarly for Br(P) if P = [T].

The two axioms we consider are:

VSMALL: If T is an infinite binary tree with the property that there is no function f : ℕ → ℕ such that

∃^{∞}n∃σ[f(n) ⩽ |σ| < f(n + 1) ∧ σ ∈ Br(T)]

then T has a path.

VSMALL is evidently a strengthening of the statement, provable in RCA_{0} , that every infinite tree with finitely many branching nodes has an infinite path. The second axiom deals with perfect trees. A tree is perfect if every extendible node of T is extended by a branching node. The second axiom we look at captures the notion of a witness to the perfection of a tree.

DIM: If T is an infinite binary tree with the property that there is no function f : ℕ → ℕ such that,

∀σ ∈ Ext(T)∃τ ∈ Br(T)[τ ⊇ σ ∧ |τ| ⩽ f(|σ|)],

then T has a path.

If such an f as referred to in DIM existed, it would also serve to contradict VSMALL. Thus DIM+RCA_{0} is sufficient to prove VSMALL. We show in the following sections that DIM+RCA_{0} is not sufficient to prove DNR, and that WWKL+RCA_{0} is not sufficient to prove VSMALL. Consequently, both DIM and VSMALL are independent of both WWKL and DNR. Finally we prove that VSMALL+RCA_{0} is not sufficient to prove DIM.

3 RCA_{0} +WWKL ⊬ VSMALL

The following four lemmas are well-known or are easy extensions of the cited results.

Definition 3.1. If X = {x_{0} < x_{1} < x_{2} … } ⊆ ℕ, then the principal function of Y p_{Y} is the function n ↦ x_{n}.

Lemma 3.2 ([5] Theorem 1.2). There exists a c.e. set A such that for almost all X ∈ 2^{ℕ}, and for all Y ⩽_{T} X, the principal function of ℕ ∖ A dominates Y.

Lemma 3.3 ([6] Theorem 5.3). A Π_{1}^{0} class is a separating class if it is of the form

{X ∈ 2^{ℕ} : ∀n[(n ∈ A → n ∈ X) ∧ (n ∈ B → n ∉ X)]}

for some disjoint c.e. sets A and B. If S ⊆ 2^{ℕ} is a Π_{1}^{0} separating class with no computable element, then the set {X ∈2^{ℕ} : ∃Y ∈S X ⩾_{T} Y } has measure zero.

Lemma 3.4. [7] The set of 1-random reals has measure 1.

Definition 3.5. f ∈ ℕ^{ℕ} is of hyperimmune-free degree if for all g ∈ ℕ^{ℕ} such that g ⩽_{T} f, g is dominated by a computable function. If h ∈ ℕ^{ℕ}, then f is of hyperimmune-free degree relative to h if for all g ∈ ℕ^{ℕ} such that g ⩽_{T} f, g is dominated by an h-computable function.

Lemma 3.6. [6] If f ∈ ℕ^{ℕ} and if T is an infinite binary f-computable tree, then there is a g ∈ [T] such that g ⊕ f is of hyperimmune-free degree relative to f. If f is of hyperimmune-free degree, then g ⊕ f is of hyperimmune-free degree.

Proof. This is just the hyperimmune basis theorem of [6] relativised to f.

Definition 3.7. An infinite binary tree T is very small if the principal function of its set of branching nodes Br(T) dominates every computable function. P = [T] is very small if T is.

If T is an infinite binary tree, then define the branching level set of T to be the set {|τ| : τ ∈ Br(T)}. The principal function of this set we call the branching level function of T. It is proved in [1] that an infinite computable binary tree is very small if and only if its branching level function dominates every computable function. We use this in the following result.

Theorem 3.8. RCA_{0} +WWKL ⊬ VSMALL

Proof. Let A be as in Lemma 3.2, and let A_{0} and A_{1} be infinite c.e. sets such that A_{0} ∪ A_{1} = A and A_{0} ∩ A_{1} = ∅ and such that no computable X ∈ 2^{ℕ} separates A_{0} and A_{1} (such a partition is possible for any c.e. set - see [11]). Let S be the separating class of A_{0} and A_{1}. Then the principal function of ℕ ∖ A is the branching level function of S.

Now let R ∈ 2^{ℕ} be such that

1. R is 1-random

2. R does not compute any element of S

3. For all g ⩽_{T} R the principal function of ℕ ∖ A dominates g.

Such an R exists as the classes from Lemmas 3.2 3.3 and 3.4 are of measure 1 and hence their intersection is non-empty.

Let R_{i} be the i^{th} column of R (that is let R_{i}(j) = R(⟨i, j⟩) for all j) and let X_{n} = ⨁_{i=0}^{n} R_{i}. We claim that the ω-model 𝔐 whose second order part is given by {Y : ∃n Y ⩽_{T} X_{n}} is a model of WWKL but not of VSMALL.

To see that it is a model of WWKL, let T be a tree of positive measure in 𝔐. T is then computable from some X_{n} and therefore, for every R′ ∈ 2^{ℕ} which is 1-random relative to X_{n}, R′ ⊕ X_{n} computes an element of [T] (see [7]). But R_{n+1} is 1-random relative to X_{n} as every column of a 1-random is random relative to the join of finitely many other columns.

Thus R_{n+1} ⊕ X_{n} computes a path through T and hence 𝔐 is a model of WWKL. That it is not a model of VSMALL is seen in the fact that every set in 𝔐 is computable

from R and hence cannot compute a path through S (by 2 above). So S has no paths in 𝔐. But S is a nonempty Π_{1}^{0} class and is thus the set of paths through some infinite computable tree T_{S} which must be in 𝔐. Furthermore the branching level function of T_{S} is the set ℕ ∖ A which dominates everything computable from R. Thus any function dominating the branching level function of T_{S} is not computable from R and hence not in 𝔐. So T_{S} satisfies the provisions of VSMALL and yet does not have a path. Therefore 𝔐 is not a model of VSMALL.

4 RCA_{0} +DIM ⊬ DNR

We now prove the second half of the main result. Our strategy is to create a model satisfying DIM whose second-order part consists entirely of noncomplex elements of hyperimmune-free degree. Theorem 6 in [16] states that a real wtt-computes a DNR function if and only if it is complex. It is well-known that if X is of hyperimmune-free degree and X ⩾_{T} Y, then X ⩾_{wtt} Y. Thus if every real in the model we construct is hyperimmune and noncomplex, no element in the model computes a DNR function and hence our model will not satisfy the DNR axiom. We make use of the following definitions and lemmas.

Definition 4.1. A tree T is computably perfect if there is no strictly increasing computable function f such that for all n and all σ ∈ Ext(T) of length f(n), there are at least two distinct extensions τ_{1}, τ_{2} of σ in Ext(T) of length f(n + 1). If P = [T], then we say P is computably perfect if T is.

Definition 4.2. An infinite tree T is diminutive if no computable tree T′ with [T′] ⊆ [T] is computably perfect. If f ∈ ℕ^{ℕ}, then T is f-diminutive if no f-computable subtree is computably perfect. P = [T] is (f-)diminutive if T is.

For the rest of the paper we will make extensive use of the concept of the Kolmogorov complexity of a binary string σ, denoted C(σ). For an overview of Kolmogorov complexity see [9]. There will be no need in what follows to distinguish between plain complexity and prefix-free complexity.

Definition 4.3. A real X ∈ 2^{ℕ} is complex if there is no computable function f such that

∀n[C(X ↾ f(n)) ⩾ n].

If g ∈ ℕ^{ℕ}, then X is g-complex if there is no computable function f such that

∀n[C^{g}(X ↾ f(n)) ⩾ n],

where C^{g}(σ) denotes the Kolmogorov complexity relative to g - the shortest description of σ on a universal machine using g as an oracle.

In [2] it is shown that a computable tree contains a computably perfect subtree if and only if it contains a complex path. We relativise this in one direction here.

Lemma 4.4. No path through an infinite f-diminutive f-computable tree is f-complex.

Proof. Suppose T is an f-computable and f-diminutive infinite binary tree, and A is an infinite path through T. Let g(n) be any increasing computable function - a putative witness to the complexity of the A. u ∈ ℕ and define a new computable function h by

1. h(0) = g(0)

2. h(n + 1) = g(2h(n) + u).

Eventually we will use the Recursion Theorem to choose a u that suits our purposes, but until then we treat it as a fixed parameter.

The set of paths through T is a Π_{1}^{f} class P, and we can let P = ⋂_{s} P_{s} where each P_{s} is a clopen subclass of 2^{ℕ} and ⟨P_{s}⟩_{s∈ℕ} is an f-computable sequence. Consider the Π_{1}^{f} class Q ⊆ P defined as follows. Let Q_{0} = 2^{ℕ}. If Q_{s} has been defined, let S_{s} ⊆ 2^{<ℕ} be the set

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

If S_{s}^{∗} = {X ∈ 2^{ℕ} : ∃σ ∈ S_{s}X ⊃ σ}, then define Q_{s+1} = P_{s+1} ∩ Q_{s} ∖ S_{s}^{∗}. Q is then ⋂_{s} Q_{s}.

Q as defined is apparently computably perfect - witnessed by h - and a Π_{1}^{f} class, and thus the paths through some f-computable computably perfect tree. But as P is diminutive, Q must be empty. Thus there is a stage s such that A ∈ S_{s}^{∗}, and there is an n such that A ↾ h(n) ∈ S_{s}.

Now consider a machine M that works as follows. M takes σ ∈ 2^{ℕ} as input and tests to see if it is of length h(n) for some n ⩽ |σ|. If it is, it uses f to search for an t such that σ ∈ S_{t}. If it finds such an t, it outputs the unique extension of σ of length h(n + 1) on Q_{t}. We call this output τ, and we have C^{f}(τ) < |σ| + O(1).

On input A ↾ h(n) M will output the unique string on Q_{s} of length h(n+1) extending A ↾ h(n). That is, it will output A ↾ h(n + 1). So

C^{f}(A ↾ h(n + 1)) < h(n) + O(1),

or

C^{f}(A ↾ g(h(n) + u)) < h(n) + O(1).

The last equation suggests that if we choose u propitiously, we can ensure that g does not witness the fact that A is f-complex. We do this now.

The value of the constant on the right-hand side of the equation depends only on the index for the Π_{1}^{f} class Q (or more precisely on an index for the sequence ⟨S_{s}⟩_{s∈ℕ}), and there is a computable function k such that if e is any index for Q, then C^{f}(τ) ⩽ |σ|+k(e). Furthermore, there is a computable function φ that, given the parameter u, will give an index for Q. Thus

C^{f}(A ↾ g(h(n) + u)) ⩽ h(n) + k(φ(u)).

Using the Recursion Theorem, we fix a value e such that the Π_{1}^{f} class with index φ(k(e)) is equal to the Π_{1}^{f} class with index e. Now we choose the parameter u to be equal to k(e). So we have

C^{f}(A ↾ g(h(n) + k(e))) < h(n) + k(φ(k(e))).

But as φ(k(e)) and e index the same Π_{1}^{f} class,

C^{f}(A ↾ g(h(n) + k(e))) < h(n) + k(e),

and A is not f-complex.

Definition 4.5. A set A ∈ 2^{ℕ} is (f-)hyperimmune if its principal function is not dominated by any (f-)computable function.

In [16] it is shown that a set X is not wtt-reducible to a hyperimmune set if and only if X is complex. We need a limited relativisation of this theorem here and we present just the direction we require. The proof closely follows [16] Theorem 10.

Lemma 4.6. [16] If f is of hyperimmune-free degree and A is not wtt-reducible to an f-hyperimmune set, then A is f-complex.

Proof. Suppose A is not wtt-reducible to any f-hyperimmune set. We identify, without further comment, the binary string σ with the natural number whose binary expansion is 1σ. Suppose C^{f} is calculated using the universal f-oracle machine U^{f} and choose d ∈ ℕ so that C^{f}(σ) ⩽ |σ| + d for all σ. Let g(n) be the least σ such that U^{f}(σ)↓⊇ A ↾ n. Now let

B := {⟨n, σ⟩ : g(n) = σ ∧ ∀k < n[g(k) ≠ σ]},

and observe that A ⩽_{wtt} B. (Given n one finds the maximum σ of length at most n+1+d such that ⟨m, σ⟩ ∈ B for some m ⩽ n + 1. Then U^{f}(σ, n) = A(n) and the queries to B are bounded by (2^{n+d+2} − 1) × (n + 1).) Therefore B is not f-hyperimmune. Let h be an f-computable function such that there are more than 2^{n+1} elements of B in the rectangle

{0, 1, … h(n) − 1} × {0, 1, … 2^{h(n)+d} − 1}.

As h is f-computable and f is of hyperimmune-free degree, there is a computable function h′ such that h′(n) ⩾ h(n) for all n. Therefore there are more than 2^{n+1} elements of B in the rectangle

{0, 1, … h′(n) − 1} × {0, 1, … 2^{h′(n)+d} − 1}.

Then g(h′(n)) ⩾ 2^{n} and C^{f}(A ↾ h′(n)) ⩾ n and so A is f-complex.

Corollary 4.7. If f is of hyperimmune-free degree, then A is complex if and only if it is f-complex.

Proof. The right to left direction is trivial. If f is hyperimmune-free, then it it easy to see that all hyperimmune sets are f-hyperimmune. Lemma 4.6 and Theorem 10 in [16] completes the proof.

Corollary 4.8. If f is of hyperimmune-free degree, then no path of hyperimmune-free degree through an infinite f-computable f-diminutive tree computes a DNR function.

Proof. By Lemma 4.4, any path through such a tree is not f-complex. Hence by the previous lemma, it is not complex and does not wtt-compute a DNR function. As it is of hyperimmune-free degree, it does not Turing compute a DNR function.

Theorem 4.9. RCA_{0} +DIM ⊬ DNR

Proof. To construct a model of DIM that is not a model of DNR, we first define a sequence ℕ = X_{0}, X_{1}, … of elements of 2^{ℕ} such that for all i > 0

1. X_{i} ⩽_{T} X_{i+1},

2. X_{i} is of hyperimmune-free degree,

3. X_{i+1} is a path through some X_{i}-diminutive X_{i}-computable tree.

The second order part of our model will be {Y : ∃iY ⩽_{T} X_{i}}. As usual ⟨., .⟩ is a computable bijection from ℕ × ℕ onto ℕ and we can assume that ⟨m, n⟩ ⩾ m for all n and m. Suppose that X_{i} has properties 1, 2, and 3 for all 0 < i ⩽ ⟨m, n⟩. Now we define X_{⟨m,n⟩+1}. If T = {n}^{X_{m}} is not an infinite binary X_{⟨m,n⟩}-diminutive tree, then let X_{⟨m,n⟩+1} = X_{⟨m,n⟩}. Otherwise, as X_{m} ⩽_{T} X_{⟨m,n⟩}, T is also X_{⟨m,n⟩}-computable and, by Lemma 3.6, there is a Y ∈ [T] such that Y ⊕ X_{⟨m,n⟩} is of hyperimmune-free degree relative to X_{⟨m,n⟩}. As X_{⟨m,n⟩} is of hyperimmune-free degree by 2, Y ⊕ X_{⟨m,n⟩} is also of hyperimmune-free degree by Lemma 3.6. Set X_{⟨m,n⟩+1} = Y ⊕ X_{⟨m,n⟩}. Properties 1 and 2 are satisfied immediately.

To prove property 3, first observe that if X_{⟨m,n⟩} = X_{⟨m,n⟩+1} , then X_{⟨m,n⟩+1} is a path through the nonbranching tree {X_{⟨m,n⟩} ↾ s : s ∈ ℕ}.

Otherwise X_{⟨m,n⟩+1} is a path through the tree T′ consisting of the extendible nodes of

{f ⊕ X_{⟨m,n⟩} : f ∈ [T]},

where [T] is as above. But the branching nodes of T′ are uniformly sparser than the branching nodes of T (each branching node of T′ is exactly twice the length of the corresponding branching node in T), and as T is X_{⟨m,n⟩}-diminutive, so is T′. As X_{⟨m,n⟩+1} is a path through T′, property 3 is satisfied.

The model of DIM will be the ω-model with second order part {f ∈ ℕ^{ℕ} : ∃i f ⩽_{T} X_{i}}. Lemma 4.8 then gives that no X_{i} computes a DNR function for any i. As every

element in the second-order part of the model is computable from some X_{i}, no element in our model computes a DNR function. So our model does not satisfy the DNR axiom.

Theorems 3.8 and 4.9 together show that VSMALL and DIM are independent of both DNR and WWKL.

Finally we show that DIM and VSMALL are distinct.

5 RCA_{0} +VSMALL ⊬ DIM.

In this section we produce a model 𝔐 of VSMALL that is not a model of DIM. To construct the model we use a method very similar to the one used in Section 4 but instead of using diminutive trees, we use very small trees. Recall from Definition 3.7 that a tree T is very small if the principal function of Br(T) dominates every computable function. Equivalently, if the principal function of {|σ| : σ ∈ Br(T)} dominates every computable function. Furthermore, instead of using the concept of f-complexity to distinguish DIM from DNR as in Theorem 4.9, now we use the concept of computable traceability to distinguish VSMALL and DIM.

Definition 5.1. The canonical index of a finite set {x_{1} < x_{2} < ⋯ < x_{n}} ⊆ ℕ is

∏_{i=1}^{n} p_{i}^{x_{i}},

where p_{i} is the i^{th} prime number. We denote by D_{n} the finite set with canonical index n. A (h-)computable array is an infinite sequence of canonically indexed finite sets ⟨D_{r(n)}⟩ with r a (h-)computable function.

Definition 5.2. f ∈ ℕ^{ℕ} is computably traceable (relative to h) if for all nondecreasing unbounded computable functions φ and for all g ⩽_{T} f, there is a (h-)computable array ⟨D_{r(n)}⟩ of finite sets such that

1. ∀n ||D_{r(n)}|| ⩽ φ(n)

2. ∀n g(n) ∈ D_{r(n)}

Lemma 5.3. If f is computably traceable, and g computably traceable relative to f, then g is computably traceable.

Proof. Fix any nondecreasing unbounded computable function φ and any function h ⩽_{T} g. As g is computably traceable relative to f, there is an f-computable index function r(n) satisfying

1. ∀n ||D_{r(n)}|| ⩽ \sqrt{φ(n)}

2. ∀n h(n) ∈ D_{r(n)}.

As r ⩽_{T} f there is a computable index fuction s satisfying

3. ∀n ||D_{s(n)}|| ⩽ \sqrt{φ(n)}

4. ∀n r(n) ∈ D_{s(n)}.

Now we can define a computable function t(n) so that

D_{t(n)} = ⋃\{D_{m} : m ∈ D_{s(n)} and ||D_{m}|| ⩽ \sqrt{φ(n)}\}.

For all n ||D_{t(n)}|| ⩽ \sqrt{φ(n)}·||D_{s(n)}|| ⩽ φ(n) so t(n) satisfies clause 1 of Definition 5.2. Also, r(m) ∈ D_{s(n)} and ||D_{r(m)}|| ⩽ \sqrt{φ(n)} so D_{r(n)} ⊆ D_{t(n)}. Therefore h(n) ∈ D_{t(n)} and the second clause of Definition 5.2 is satisfied. φ and h were arbitrary so g is computably traceable.

Definition 5.4. Let T be a tree and P = [T], the class of paths through T. For convenience we introduce the notation

T [n] = P [n] := {σ ∈ Ext(T) : |σ| = n}

for the set of extendible nodes of T or P of length n.

Lemma 5.5. If f ∈ ℕ^{ℕ} and h is a hyperimmune-free element of a very small Π_{1}^{f} class P, then for all h′ ⩽_{T} h h′ is a hyperimmune-free element of a very small Π_{1}^{f} class.

Proof. As h′ ⩽_{T} h and h is hyperimmune-free, there is a total computable functional Φ on 2^{ℕ} such that Φ(h) = h′ (see [10] Theorem VI.5.5 and Proposition III.3.2). As h is hyperimmune-free, so is h′ and h′ ∈ Φ[P]. A straightforward relativisation of Theorem 4.3.6 in [1], and using the fact that f is of hyperimmune-free degree, gives that Φ[P] is a very small Π_{1}^{f}.

Lemma 5.6. Let f ∈ ℕ^{ℕ} and g be a hyperimmune-free element of a very small Π_{1}^{f} class. Then g is computably traceable relative to f.

Proof. Let φ be any nondecreasing unbounded computable function and suppose h ⩽_{T} g. By Lemma 5.5, h is a element of some very small Π_{1}^{f} class Q. Let ⟨Q_{k}⟩ be an f-computable sequence of nested clopen sets such that Q = ⋂_{k} Q_{k}.

As Q is very small there is an N such that ||Q[n + 1]|| ⩽ φ(n) for all n ⩾ N. And hence for each n ⩾ N there is a k such that ||Q_{k}[n + 1]|| ⩽ φ(n). Let s = s(n) be the least such k for each n. Now define an f-computable function r(n) by

D_{r(n)} = {σ(n) : σ ∈ Q_{s}[n + 1]}.

It is straightforward now to see that clauses 1 and 2 of Definition 5.2 are satisfied for h and r and for cofinitely many n. We can then finitely adjust r to satisfy 1 and 2 for all n. As h and φ were arbitrary, it follows that g is computably traceable relative to f.

The next lemma is based on a theorem by Robinson and Lachlan ([12], [8]). The type of construction is relatively well-known, but for completeness we include sketch of the proof.

Lemma 5.7 (Lachlan, Robinson). There is a co-c.e. hyperimmune set X ⊆ ℕ and a strictly increasing computable function f such that for all co-c.e. Y ⊆ X there exists infinitely many n ∈ ℕ such that ||{m ∈ Y : m < f(n)}|| ⩾ n. That is f dominates the principal function of Y infinitely often.

Proof. (Sketch) We begin by fixing a computable partition of ℕ into intervals ⟨α_{i}⟩ such that ||α_{i}|| = i · 2^{i+1} for each i, and such that max α_{i} + 1 = min α_{i+1}. In the construction we produce a computable double sequence of finite sets ⟨β_{i,s}⟩ such that for each i and each stage s, 1. β_{i,0} = α_{i},

2. β_{i,s+1} ⊆ β_{i,s},

and we let β_{i} = lim_{s} β_{i,s}. We produce concurrently a double sequence of markers ⟨m_{i,s}⟩ such that for all i and s,

1. m_{i,0} = i,

2. m_{i,s} < m_{i+1,s},

3. m_{i,s+1} = m_{j,s} for some j ⩾ i.

4. lim_{t} m_{i,t} exists.

If lim_{t} m_{i,t} is denoted m_{i}, then the set X required by the theorem will be ⋃_{i∈ℕ} β_{m_{i}}.

The values of m_{i,s} are determined to satisfy the requirement that X be hyperimmune - at each stage s if it appears that some approximation to a computable function is going to dominate the principal function of X, then the markers are moved to ensure that this fails to occur (for details on such movable marker arguments see for example [15]).

To determine the value of β_{i,s+1} we find the least j < i such that

1. W_{j,s} ⊉ β_{i,s}

2. ||W_{j,s} ∩ β_{i,s}|| ⩾ \frac{1}{2}||β_{i,s}||

and we let β_{i,s+1} = β_{i,s} ∩ W_{j,s} (where W_{e,s} is some standard enumeration of the c.e. sets). As W_{j,s} is increasing in s and β_{i,s} is decreasing in s, β_{i,t} ⊆ W_{j,t} for all t > s and so for any i, β_{i,s+1} ≠ β_{i,s} at most i times, and for each such s ||β_{i,s+1}|| ⩾ \frac{1}{2}||β_{i,s}||. Therefore, if β_{i} = lim_{s} β_{i,s}, then ||β_{i}|| ⩾ 2i for each i.

To see that X now has the required properties, first recall that the movable-marker construction makes it hyperimmune (the reduction of the β_{i} over time cannot conflict with this requirement, and as β_{i} is nonempty for all i > 0, X is infinite). Suppose now that Y = \overline{W_{e}} is an infinite co-c.e. subset of X. Therefore for infinitely many i, W_{e} ⊉ β_{i}. For each such i > e,

||W_{e} ∩ β_{i}|| < \frac{1}{2}||β_{i}||,

(or else at some stage β_{i} would have been reduced so that β_{i} ⊆ W_{e}). So for infinitely many i

||\overline{W_{e}} ∩ β_{i}|| ⩾ \frac{1}{2}||β_{i}|| ⩾ i.

The function f(n) := max α_{n} (which is independent of e) then dominates the principal function of \overline{W_{e}} infinitely often.

Theorem 5.8. RCA_{0} +VSMALL ⊬ DIM.

Proof. We create a model 𝔐 of VSMALL by the same method as in Theorem 4.9 using very small trees rather than diminutive trees. The lemmas above then give that every element of the second-order part of the model is computably traceable. We then produce using Lemma 5.7 a diminutive Π_{1}^{0} class that has no computably traceable element and hence no element in 𝔐.

Let X and f be as in Lemma 5.7. Let X_{0} and X_{1} be a c.e. partition of \overline{X} and let S = {Y : Y ⊇ X_{0} and Y ∩ X_{1} = ∅} - the separating set of X_{0} and X_{1}. S is a Π_{1}^{0} class and X_{0} and X_{1} can be chosen so that S has no computable element (see [11] Theorem 1). It is straightforward to show that {|σ| : σ ∈ Br(S)} = X and that S is diminutive as X is hyperimmune.

Suppose now that S has a computably traceable element Z and consider the Zcomputable function n ↦ Z ↾ f(n). As Z is computable traceable, there is a computable sequence of canonically indexed sets of binary strings ⟨D_{n}⟩ such that Z ↾ f(n) ∈ D_{n} and ||D_{n}|| < n for all n. Now let

S′ = S ∩ {Y ∈ 2^{ℕ} : ∀nY ↾ f(n) ∈ D_{n}}.

S′ is a Π_{1}^{0} class and contains Z so is non-empty. S′ is perfect as S has no computable element. Furthermore W := {|σ| : σ ∈ Br(S′)} is a co-c.e. subset of X. But ||{σ ∈ Ext(S′) : |σ| = f(n)}|| < n for all n, so ||{m ∈ W : m < f(n)}|| < n, contradicting the assumptions on X and f. Thus S is a diminutive Π_{1}^{0} class with no computably traceable element.

References

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

[2] Stephen Binns. Π_{1}^{0} classes with complex elements. Pre-print, 2007.

[3] Douglas K. Brown, Mariagnese Giusto, and Stephen G. Simpson. Vitali’s theorem and WWKL. Archive for Mathematical Logic, 41:191–206, 2002.

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

[5] Peter Cholak, Noam Greenberg, and Joseph S. Miller. Uniform almost everywhere domination. Journal of Symbolic Logic, 71:1057–1072, 2006.

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

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

[8] A.H. Lachlan. On the lattice of recursively enumerable sets. Transactions of the American Mathematical Society, 130:1–27, 1968.

[9] Ming Li and Paul Vitányi. An Introduction to Kolmogorov Complexity and its Applications. Graduate Texts in Computer Science. Springer-Verlag, 2nd edition, 1997. XX + 637 pages.

[10] P. Odifreddi. Classical Recursion Theory, volume 1. North-Holland, 1950. xvii+ 668 pages.

[11] Kempachiro Ohashi. A stronger form of a theorem of Friedberg. Notre Dame Journal of Formal Logic, V(1):10–12, 1964.

[12] R. W. Robinson. Simplicity of recursively enumerable sets. Journal of Symbolic Logic, 32:162–172, 1967.

[13] Stephen G. Simpson. Subsystems of Second Order Arithmetic. Springer-Verlag, 1999. XIV + 445 pages.

[14] Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, Theodore A. Slaman. Comparing DNR and WWKL. Journal of Symbolic Logic, 69:1089–1104, 2004.

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

[16] Bjørn Kjos-Hanssen, Wolgang Merkle, Frank Stephan. Kolmogorov complexity and the recursion theorem. Lecture Notes in Computer Science, 3884, pages 149–161, 2006.