An argument due to Leo Harrington

Greg Hjorth

January 28, 2004

1 Introduction

We present a detailed account of the method sketched in [2] and [3]. We also present Harrington’s solution to question 57* from the end notes of Harvey Friedman’s [1].

2 Notation

Notation (φ_{e})_{e∈ω} refers to some standard enumeration of the partial recursive functions φ : ω → ω. If ψ is a partial function, then

ψ ↓ (e)

is used to indicate that e is in the domain on which ψ(e) is defined.

For x ∈ ω^{ω} we let (Φ_{e}(x))_{e∈ω} be some reasonably effective enumeration of the partial recursive in x functions Φ : ω → ω. For s ∈ ω^{<ω} we write

Φ_{e}(s)(m) = n

if for any x ⊃ s we have Φ_{e}(x) ↓ (n) with value m and just using the part of x already in s. Similarly we use (Φ_{e}(x, y))_{e∈ω} to enumerate the functions recursively enumerable in x and y, and there on we adopt the parallel notation of Φ_{e}(s, t) for s, t ∈ ω^{<ω}.

Notation ⊂ refers to not necessarily strict inclusion.

Notation T ⊂ ω^{<ω} × ω^{<ω} is said to be closed downward if whenever (s, t) ∈ T and s′ ⊂ s, t′ ⊂ t we have (s′, t′) ∈ T. For such a T we then let [T] be the set of all (x, y) ∈ ω^{ω} × ω^{ω} which have (x|_{n}, y|_{n}) ∈ T at every n.

We informally say that (s, t) is included in (u, v) if s ⊂ u and t ⊂ v both hold. We say that (s, t) is incompatible with (u, v), written (s, t) ⊥ (u, v), if (s, t) is not included in (u, v) and (u, v) is not included in (s, t).

We write s ⊥ t, for s, t ∈ ω^{<ω} if neither is an initial segment of the other.

Notation Let ρ(·, ·) : ω ×ω → ω be a recursive bijection. For j ∈ ω and s ∈ ω^{<ω}, let p_{j}(s) ∈ ω^{<ω} be defined so that it has the same length as s and (p_{j}(s))(ρ(n, m)) = s(ρ(n, m)) if n ≠ j whilst (p_{j}(s))(ρ(j, m)) = 0 for ρ(j, m) in the domain of s.

In other words, p_{j} is the function which suppresses information on the j^{th} copy of ω.

3 Harrington’s method

The mathematical ideas from this section are all due to Leo Harrington. He however cannot be blamed for the cumbersome definitions and the careless errors, which are all due to the author. Because we will later need to apply ideas of boundedness or overspill to his argument, we need at this stage to describe it as a static set theoretical construction, rather than as a dynamic priority argument.

Definition Fix i, j ∈ ω.

For T ⊂ ω^{<ω} × ω^{<ω} closed downward and recursively enumerable, fix some canonical enumeration of increasing finite subsets, (T^{(n)})_{n∈ω}, with the properties that:-

(i) T^{(n)} ⊂ T^{(n+1)} ⊂ T;

(ii) each T^{(n)} is closed downwards and has size at most n; (iii) n ↦ T^{(n)} is recursive; (iv) T = ⋃_{n} T^{(n)}.

We then let T (n) = {s : ∃t((s, t) ∈ T^{(n)})} be the various respective projections to the first coordinate and let T^{j}(n) = {p_{j}(s) : s ∈ T (n)} be the result of discarding the information on the j^{th} copy of ω.

Then an i-j-step down of T consists of recursively enumerable closed downward U ⊂ ω^{<ω} × ω^{<ω} along with recursive assignments

((A_{s̄,m}^{n})_{s̄∈T ^{j}(n),m≤n})_{n∈ω},

(U_{n})_{n∈ω},

((πn ; s̄)_{s̄∈T ^{j}(n)})_{n∈ω},

satisfying the following 7 conditions:-

(I) If s̄ ∈ T^{j}(n), then πn ; s̄ is a strictly order preserving function from

{(s, t) ∈ T^{(n)} : lh(s) = lh(t); p_{j}(s) ⊂ s̄; s, t ∈ T (n)}

to ω^{<ω}. For n′ ≤ n we have

πn′ ; s̄ ⊂ πn ; s̄.

(II) We let Bn ; s̄ be

{v : ∃w ∈ ran(πn ; s̄)(v ⊂ w)},

the downward closure of the range of πn ; s̄. Then we have first of all that {A_{s̄,m}^{n} : m ≤ n} partitions Bn ; s̄, with v ⊂ v′ implying that for some m ≤ m′ we have v ∈ A_{s̄,m}^{n}, v′ ∈ A_{s̄,m′}^{n} – in other words, sequences in the member of the partition corresponding to larger m′ extend sequences in the member of the partition corresponding to smaller m.

We furthermore have that for n′ ≤ n, A_{s̄,m}^{n′} ⊂ A_{s̄,m}^{n}.

(III) We demand that the πn ; s̄ split apart incompatible elements of T of length greater than i. More precisely: If s̄ ∈ T^{j}(n),

(s_{1}, t_{1}) ⊥ (s_{2}, t_{2}),

(s_{1}, t_{1}), (s_{2}, t_{2}) ∈ dom(πn ; s̄),

lh(s_{1}), lh(s_{2}) > i,

then

πn ; s̄(s_{1}, t_{1}) ⊥ πn ; s̄(s_{2}, t_{2}).

(IV) We demand that πn ; s̄ always chooses new values for πn ; s̄(s^{⌢}p, t^{⌢}q). More precisely: If s̄^{∗} ⊂ s̄ are both in T^{j}(n), (s^{⌢}p_{1}, t^{⌢}q_{1}) ∈ dom(π_{s̄^{∗}}^{n}), (s^{⌢}p_{2}, t^{⌢}q_{2}) ∈ dom(πn ; s̄), (p_{1}, q_{1}) ≠ (p_{2}, q_{2}), and for some v of length ℓ, ℓ ≥ i, we have

v = π_{s̄^{∗}}^{n}(s, t) = πn ; s̄(s, t),

then

(π_{s̄^{∗}}^{n}(s^{⌢}p_{1}, t^{⌢}q_{1}))(ℓ) ≠ (πn ; s̄(s^{⌢}p_{2}, t^{⌢}q_{2}))(ℓ).

(V) We also add some minor bookkeeping conditions to ensure that

U = ⋃ U_{n}

at the first i levels it resembles T, and that in some natural sense it is generated by the values of the p_{j}(s) along with the various πn ; s̄ applied to the elements of T.

(a) πn ; s̄(s, t) = t for all (s, t) in dom(πn ; s̄) with lh(s) = lh(t) ≤ i.

(b) U = ⋃ U_{n}.

(c) U_{n} = {(s̄, u) : s̄ ∈ T^{j}(n), ∃(s, t) ∈ dom(πn ; s̄)(u ⊂ πn ; s̄(s, t))}.

(VI) (The “no injury” case of the construction.) Here we consider some possibly new s̄^{⌢}p̄ ∈ T^{j}(n + 1) and simply build on top of the previously established values for the πn+1 ; s̄(s, t), placing these new values of the form π_{s̄^{⌢}p̄}^{n+1}(s^{⌢}p, t^{⌢}q) into the first element of the partition (A_{s̄^{⌢}p̄,m}^{n+1})_{m≤n} above all the earlier choices along that branch: More precisely:

For all s̄^{⌢}p̄ ∈ T^{j}(n + 1), (s, t) ∈ dom(πn+1 ; s̄) ⊂ dom(π_{s̄^{⌢}p̄}^{n+1}), with πn+1 ; s̄(s, t) = π_{s̄^{⌢}p̄}^{n+1}(s, t), we have for all

m ∈ ω and for all u ⊂ πn+1 ; s̄(s, t)

u ∈ A_{s̄,m}^{n+1} ⇔ u ∈ A_{s̄^{⌢}p̄,m}^{n+1}.

Moreover under these circumstances, if (s^{⌢}p, t^{⌢}q) ∈ dom(π_{s̄^{⌢}p̄}^{n+1})\ dom(πn+1 ; s̄) and π_{s̄^{⌢}p̄}^{n+1}(s, t) ∈ A_{s̄,m_{0}}^{n+1}, then

(s^{⌢}p, t^{⌢}q) ∈ A_{s̄^{⌢}p̄,m_{0}+1}^{n+1},

lh(π_{s̄^{⌢}p̄}^{n+1}(s^{⌢}p, t^{⌢}q)) = lh(πn+1 ; s̄(s, t)) + 1.

(VII) (The “injury” case of the construction) The injury case of the construction arises because we see a place in U_{n} where something valuable happens – either some integer gets placed in the halting set relative to any reals (ȳ, x) extending (s̄, w) or we get the chance to make some calculation diagonalize off ȳ′. In this case we adjust the embedding of T into U so as to make that event happen for a collection of values of the form π_{s̄^{⌢}p̄}^{n+1}(s, t) without damaging any earlier requirements. We do this at some point (ŝ, t̂) ∈ T and all nodes below; the old values of πn+1 ; s̄ for s ⊃ ŝ, t ⊃ t̂ are largely bypassed, and become dead branches on the tree U, which by (IV) above can never be revisited.

Before describing this case we need an extended sequence of definitions.

Notation R_{1}(s̄, w, e) is the statement that Φ_{e}(s̄, w) ↓ (e) in ≤ lh(s̄) steps.

Notation R_{2}(s̄, w, e) is the statement that there is some e′ ≤ lh(s̄)

Φ_{e}(s̄, w) ↓ (e′) = 1

in ≤ lh(s̄) steps, and moreover

Φ_{e′}(s̄) ↓ (e′)

in ≤ lh(s̄) steps.

Notation Given s̄^{⌢}p̄ ∈ T^{j}(n + 1) \ T^{j}(n),

v = πn+1 ; s̄(ŝ, t̂) ∈ A_{s̄,m}^{n+1},

we let

Q(s̄^{⌢}p̄, v, m′)

be the statement that lh(v) > i, lh(ŝ, t̂) > i, lh(s̄) > i, m′ < m, and there is w ∈ Bn+1 ; s̄ with lh(w) ≤ lh(s̄), w ⊃ v, such that either:

(1) m′ = 2^{e} + i, R_{1}(s̄^{⌢}p̄, w, e) holds, but R_{1}(s̄, v, e) fails;

(2) m′ = 3^{e+1} + i, R_{2}(s̄^{⌢}p̄, w, e) holds, but R_{2}(s̄, v, e) fails.

This notation established we describe the injury case.

If s̄^{⌢}p̄ ∈ T^{j}(n + 1) \ T^{j}(n), (s, t) ∈ dom(πn+1 ; s̄), π_{s̄^{⌢}p̄}^{n+1}(s, t) ≠ πn+1 ; s̄(s, t), then there exists ŝ ⊂ s, t̂⊂ t,

v = πn+1 ; s̄(ŝ, t̂) ∈ A_{s̄,m}^{n+1}

(some m) with ⟨ŝ, t̂⟩ least for which there exists m′ with

Q(s̄^{⌢}p̄, v, m′);

moreover there is w ∈ Bn+1 ; s̄, w ⊃ v, lh(w) ≤ lh(s̄) as above with either

R_{1}(s̄^{⌢}p̄, w, e)

or

R_{2}(s̄^{⌢}p̄, w, e)

(depending on whether m′ = 2^{e} + i or m′ = 3^{e+1} + i), such that

π_{s̄^{⌢}p̄}^{n+1}(s′, t′) ⊃ w

all (s′, t′) ∈ dom(π_{s̄^{⌢}p̄}^{n+1}), s′ ⊃ ŝ, t′ ⊃ t̂, and such that

w′ ∈ A_{s̄^{⌢}p̄,m′}^{n+1}

all w′ ⊃ w, w′ ∈ B_{s̄^{⌢}p̄}^{n+1}.

Moreover the conditions above are not only necessary for

π_{s̄^{⌢}p̄}^{n+1}(s, t) ≠ πn+1 ; s̄(s, t)

but sufficient, in that if πn+1 ; s̄(ŝ, t̂) ⊂ πn+1 ; s̄(s, t) with ⟨ŝ, t̂⟩ least such that Q(s̄^{⌢}p̄, πn+1 ; s̄(ŝ, t̂), m′) holding for some m′, then

π_{s̄^{⌢}p̄}^{n+1}(s, t) ≠ πn+1 ; s̄(s, t)

and we define π_{s̄^{⌢}p̄}^{n+1}(ŝ, t̂) according to the least possible such m′.

Lemma 3.1 For T, i, j as above, an i-j-step down of T exists.

Proof It suffices to show that given any choice of

((A_{s̄,m}^{ℓ})_{s̄∈T ^{j}(ℓ),m≤ℓ})_{ℓ≤n}

((πℓ ; s̄)_{s̄∈T ^{j}(ℓ)})_{ℓ≤n},

satisfying (I) to (VII), we can extend to find the various A_{s̄,m}^{n+1} and πn+1 ; s̄ again fulfilling these conditions (I)-(VII). That is to say, it suffices to show existence, since by always choosing the first such choice in some canonical enumeration we obtain recursiveness for free.

But to do this we first define these just for s̄ ∈ T^{j}(n), fixing the various πn+1 ; s̄ according to the non-injury case at (VI) and only after we have first defined the π_{s̄^{∗}}^{n+1} for all s̄^{∗} which form proper initial segments of s̄. The conditions at (I) and (II) represent minor bookkeeping tasks. (III) and (IV) simply require us to move the values of the form (πn+1 ; s̄(s, t))(ℓ) away from some prohibited finite set, and thus can always be achieved.

All the excitement occurs when we consider some new s̄^{⌢}p̄ ∈ T^{j}(n + 1) \ T^{j}(n). But in this case (VII) tells us exactly when an injury must occur, and if an injury takes place then we follow the specifications given there, making sure to avoid values prohibited by (III) and (IV). If no injury takes place, then it as in the previous paragraph. □

Notation From now on we let

πs̄ = ⋃_{n∈ω} πn ; s̄,

A_{s̄,m} = ⋃_{n∈ω} A_{s̄,m}^{n},

B_{s̄,m} = ⋃_{n∈ω} B_{s̄,m}^{n}.

Lemma 3.2 Suppose

ȳ ∈ ω^{ω},
(s, t) ∈ T,
lh(s) = lh(t),
p_{j}(s) ⊂ ȳ.

Then there is an m_{0} ∈ ω, v_{0} ∈ ω^{<ω} such that for all sufficiently large ℓ

π_{ȳ|_{ℓ}}(s, t) = v_{0} ∈ A_{ȳ|_{ℓ},m_{0}}.

Proof By induction on lh(s) = lh(t), with the base case of lh(s) ≤ i being handled by (V)(a) and the absence of any injury at these first few steps of the process.

For the inductive step, passing from (s, t) to (s^{⌢}p, t^{⌢}q), we assume inductively that there is a last ℓ at which π_{ȳ|_{ℓ}}(s, t) is injured, and then argue that the same is true for the various π_{ȳ|_{ℓ}}(s^{⌢}p, t^{⌢}q). The key point here is the upward persistence of Σ_{1}^{0} facts: Once π_{ȳ|_{ℓ}}(s^{⌢}p, t^{⌢}q) has been injured because of some m′ at (VII), we never again can have Q(s̄, π_{ȳ|_{ℓ}}(s^{⌢}p, t^{⌢}q), m′) happening at any s̄ ⊃ π_{ȳ|_{ℓ}}, and any further injury can only come from smaller m′′ < m′. Eventually these smaller m′′ will likewise exhaust themselves, and the value of π_{ȳ|_{ℓ}}(s^{⌢}p, t^{⌢}q) dries into permanence. □

Corollary 3.3 If (y, x) ∈ [T] then there exists (ȳ, x̂) ∈ [U] with ȳ = p_{j}(y) and for all k and for all but finitely many ℓ

π_{ȳ|_{ℓ}}(y|_{k}, x|_{k}) ⊂ x̂.

Proof From the lemma and clause (I) of the construction. □ Lemma 3.4 For (x, y), (ȳ, x̂) as above, there exist arbitrarily large m for which there is some k such that

∀^{∞}ℓ(π_{ȳ|_{ℓ}}(x|_{k}, y|_{k}) ∈ A_{ȳ|_{ℓ},m}).

Proof As in the proof of 3.2. □ Lemma 3.5 If (ȳ, x̂) ∈ [U] then there is (y, x) ∈ [T] such that

p_{j}(y) = ȳ

and at every k

∀^{∞}ℓ(π_{ȳ|_{ℓ}}(y|_{k}, x|_{k}) ⊂ x̂).

Proof Claim(1): There are (ŝ, t̂) ∈ (ω^{i+1})^{2} such that for all but finitely many ℓ

π_{ȳ|_{ℓ}}(ŝ, t̂) ⊂ x̂,

∀s′, t′(π_{ȳ|_{ℓ}}(s′, t′) ⊃ x̂|_{i+1} ⇒ s′ ⊃ ŝ, t′ ⊃ t̂).

Proof of Claim: Go to the first ℓ for which there is ŝ = s^{⌢}p, t̂= t^{⌢}q with

π_{ȳ|_{ℓ}}(ŝ, t̂)|_{i+1} = x̂|_{i+1}.

Since (s, t) ∈ (ω^{i})^{2}, π_{ȳ|_{ℓ}}(s, t) is never injured, it follows from (III) that we get at any ℓ′ ≥ ℓ

∀s′, t′(π_{ȳ|_{ℓ′}} (s′, t′) ⊃ x̂|_{i+1} ⇒ s′ ⊃ ŝ, t′ ⊃ t̂).

After this (ȳ, x̂) ∈ [U] necessitates

π_{ȳ|_{ℓ′}} (ŝ, t̂) ⊂ x̂.
(□Claim)

Now let us assume inductively that there is some (s, t), N, m, and v, with lh(v) > i such that at all ℓ > N we have

π_{ȳ|_{ℓ}}(s, t) = v ⊂ x̂.

Claim(2): If ℓ > N and (s^{⌢}p, t^{⌢}q) ∈ dom(π_{ȳ|_{ℓ}}) has

π_{ȳ|_{ℓ}}(s^{⌢}p, t^{⌢}q) ⊃ x̂|_{lh(v)+1},

then

π_{ȳ|_{ℓ}}(s^{⌢}p, t^{⌢}q) ⊂ x̂.

Proof of claim: Since π_{ȳ|_{ℓ}}(s, t) is never injured, the claim follows from (III) in the same manner as claim(1).

(□Claim)

Now one easily defines (y|_{k}, x|_{k}) by induction on k so as to guarantee that

∀^{∞}ℓ(π_{ȳ|_{ℓ}}(y|_{k}, x|_{k}) ⊂ x̂).

□

Definition Given (y, x) ∈ [T], ȳ = p_{j}(x), and x̂ such that

∀k∀^{∞}ℓ(π_{ȳ|_{ℓ}}(y|_{k}, x|_{k}) ⊂ x̂),

as in 3.3, we let

πȳ(y, x) = x̂.

Thus we have shown that

(y, x) ↦ (p_{j}(y), π_{p_{j}(y)}(x, y))

provides a bijection of [T] with [U]. It follows from the structure of the definition that πȳ(y, x) is always uniformly recursive in (ȳ′, y, x).

Lemma 3.6 (ȳ, πȳ(y, x))′ is uniformly recursive in (ȳ′, y, x).

Proof It follows from the description of the injury step at (VII) for m′ = 2^{e} + i and lemma 3.4 that

Φ_{e}(ȳ, πȳ(y, x)) ↑ (e)

if and only if there is some v ⊂ πȳ(y, x) such that for all w ⊃ v, s̄ ⊂ ȳ with lh(s̄) sufficiently large

Φ_{e}(s̄, w) ↑ (e).

This provides a Σ_{1}^{0}(ȳ′, πȳ(y, x)) characterization of whether e is in the halting set for (ȳ, πȳ(y, x)). □

Lemma 3.7 ȳ′ is never recursive in (ȳ, πȳ(y, x)).

Proof Otherwise suppose there is e with

Φ_{e′}(ȳ) ↑ (e′) ⇔ Φ_{e}(ȳ, πȳ(y, x)) ↓ (e′) = 1.

The following the description of the injury case at m′ = 3^{e+1} + i we have that there is some v ⊂ πȳ(y, x) such that at every w ⊃ v, s̄ ⊂ ȳ

Φ_{e}(s̄, w) ↓ (e′) = 1

entails Φ_{e′}(ȳ) ↑ (e′). Following on from our supposition at the start of the lemma this gives a Σ_{1}^{0}(y) definition of ȳ′, with an absurdity. □

Definition A recursive linear ordering (X, <_{X}) is suitable if (a) X ⊂ ω;

(b) the set of limit points is recursive; we denote this set by lim(X);

(c) the set of predecessors is recursive, and the successor operation is recursive on this set;

(d) the linear ordering comes with a recursive assignment

lim(X) → X^{ω}
λ ↦ (α_{n,λ})_{n∈ω}

such that (i) each (α_{n,λ})_{n} is a strictly increasing sequence converging to λ; (ii) for all β ∈ X there are only finitely many λ >_{X} β which have some

α_{n,λ} <_{X} β,

and moreover this finite set can be located recursively in β;

(iii) for each λ ∈ lim(X) there are cofinally many β <_{X} λ which provide a cut point for the cofinal sequences associated to limits below λ; that is to say, if a limit λ^{∗} has

β <_{X} λ^{∗} <_{X} λ,

then at every n

β <_{X} α_{n,λ^{∗}}.

It is routine to show that for any κ < ω_{1}^{ck} there is a suitable recursive linear order of order type κ. We need to use (iii) later, so it is a good idea now to make clear how it is being used. (iii) says that in particular there is no limit λ and increasing convergent sequence of limits,

λ_{ℓ} → λ,

and integers (n_{ℓ})_{ℓ∈ω} such that at each ℓ

α_{n_{ℓ+1},λ_{ℓ+1}} ≤_{X} λ_{ℓ}.

In the next definition we need an embellishment on the p_{j}(s) notation.

Definition If I ⊂ ω, then we define p_{I}(s) = s̄ by

s̄(ρ(ℓ, m)) = 0

if ℓ ∈ I;

s̄(ρ(ℓ, m)) = s(ρ(ℓ, m))

if ℓ ∉ I; in other words, p_{I}(s) suppresses all values of s on the copies^{1} of ω indexed in I. We are especially interested in this definition in the case that (X, <_{X}) is a recursive linear ordering, β, λ ∈ X, and I equals

(β, λ]_{X} =_{df} {α ∈ X : β <_{X} α ≤_{X} λ}.

At some points later we will be implicitly using that p_{I_{1}} ∘ p_{I_{2}} = p_{I_{1}∪I_{2}}.

Definition Let T ⊂ ω^{<ω} × ω^{<ω} be recursively enumerable and closed downward. Let κ be a recursive ordinal.

T is said to have a κ-unraveling if there is a suitable recursive linear ordering (X, <_{X}) of order type κ+1, and corresponding ((α_{n,λ})_{n})_{λ∈lim(X)} and a recursively enumerable array of trees (T_{j})_{j∈X} such that:

(a) for j_{0} the top most element of X we have T_{j_{0}} = T;

(b) if j ∈ X and j+ is its successor in X, and we let n_{j} be the supremum of all n for which there exists

λ >_{X} j

with

α_{n,λ} ≤_{X} j,

then T_{j} is the n_{j}-j+-step down of T_{j+}; (c) if λ is a limit and α_{n,λ} ≤_{X} j, then for all (s̄, t) ∈ ω^{≤n} × ω^{≤n} we have

(s̄, t) ∈ T_{j}

if and only if there exists some s with p_{(j,λ]_{X}} (s) = s̄ and

(s, t) ∈ T_{λ}.

1Recall that ρ : ω × ω → ω is our recursive bijection which serves for pairing.

Lemma 3.8 Any recursively enumerable downward closed T ⊂ ω^{<ω} × ω^{<ω} has a κ-unraveling at any recursive ordinal κ.

Proof Let (X, <_{X}) be a suitable linear ordering of order type κ + 1 and top most element j_{0}. For any recursive array (T_{j})_{j∈X} having T_{j_{0}} = T we define a new recursive array (T̂_{j})_{j∈X} again having T̂_{j_{0}} = T and defined by the following complicated recipe:

For j ∈ X let j+ be the <_{X} successor of j. Let Λ(j) be the set of limit λ’s which have λ >_{X} j and at some n

α_{n,λ} ≤_{X} j,

and let n(j) be the supremum of all n for which there exists λ ∈ Λ(j) and we have

α_{n,λ} ≤_{X} j.

With this granted we can define the new array (T̂_{j})_{j∈X}:

(i) We let T̂_{j} be some recursively enumerable tree with T̂_{j} ∩ (ω^{≤n(j)} × ω^{≤n(j)}) equal to the set of all

(p_{(j,λ]_{X}} (s), t),

with λ ∈ Λ(j) and for which there exists n ∈ ω, with (s, t) ∈ T_{λ} ∩ (ω^{≤n} × ω^{≤n}) and

α_{n,λ} ≤_{X} j.

(ii) If some canonical choice of an n(j)-j^{+}-step down of T_{j+} intersected with (ω^{≤n(j)} × ω^{≤n(j)}) equals the description from (i), then we further more insist that T̂_{j} be that n(j)-j+-step down of T_{j+}.

It is routine to see that we can do this in a recursive way, obtain a fixed point

(T̂_{j})_{j∈X} = (T_{j})_{j∈X},

by the recursion theorem. The definitions immediately slot in to show that this fixed point is the unraveling we need once the following claim is verified.

Claim: If λ ∈ lim(X) and α_{n,λ} ≤_{X} j <_{X} λ, then at all (s̄, t) ∈ ω^{≤n} × ω^{≤n} we have

(s̄, t) ∈ T_{j}

if and only if there exists some s with p_{(j,λ]_{X}} (s) = s̄ and

(s, t) ∈ T_{λ}.

Proof of claim: We have

T̂_{j} ∩ (ω^{≤n(j)} × ω^{≤n(j)})

equal to the set

{(p_{(j,λ]_{X}} (s), t) : ∃λ ∈ Λ(j)∃n ∈ ω((s, t) ∈ T_{λ} ∩ (ω^{≤n} × ω^{≤n}), α_{n,λ} ≤_{X} j)}.

For a contradiction we consider some (s̄, t) ∈ T_{j} ∩ ω^{≤n} × ω^{≤n} with α_{n,λ} ≤_{X} j <_{X} λ for which there is no associated (s, t) ∈ T_{λ} with p_{(j,λ]}(s) = s̄. Then by the definition of T̂_{j} we go to some λ_{1} ∈ Λ(j) and α_{n_{1},λ} ≤_{X} j <_{X} λ_{1}, n_{1} ≤ lh(s̄) and s_{1} with p_{(j,λ_{1}]_{X}} (s_{1}, t) = s̄, (s_{1}, t) ∈ T_{λ_{1}}.

Subclaim: λ_{1} <_{X} λ.

Proof of subclaim: Otherwise we have to have λ ≤_{X} λ_{1}, and then in fact λ <_{X} λ_{1} since (s_{1}, t) cannot be in T_{λ} = T̂_{λ} by assumption at the start of the claim. But then we would have λ_{1} ∈ Λ(λ) in light of

α_{n_{1},λ} ≤_{X} j <_{X} λ <_{X} λ_{1},

and we would have to have (p_{(λ,λ_{1}]_{X}} (s_{1}), t) ∈ T̂_{λ}, and then

p_{(j,λ]_{X}} (p_{(λ,λ_{1}]_{X}} (s_{1})) = p_{(j,λ_{1}]_{X}} (s_{1}) = s̄

after all. (□Subclaim)

But now we still have λ ∈ Λ(λ_{1}) and hence we repeat the process and find some λ_{2} ∈ Λ(λ_{1}) and α_{n_{2},λ} ≤_{X} j <_{X} λ_{2}, n_{2} ≥ lh(s_{2}), and s_{2} with p_{(j,λ_{2}]_{X}} (s_{2}, t) = s̄. The same reasoning as the last subclaim gives λ_{2} <_{X} λ, and so on.

In the end of all this we have some strictly increasing sequence (λ_{k})_{k∈ω} and corresponding (α_{n_{k},λ_{k}})_{k∈ω} with α_{n_{k+1},λ_{k+1}} <_{X} λ_{k} at each k. If we let λ_{∞} be the limit of these λ_{k}’s then we obtain a contradiction to clause (d)(iii) of (X, <_{X}) being a suitable linear order. □

Lemma 3.9 Let (X, <_{X}) be a suitable recursive well order and let (T_{β})_{β∈X} an unraveling. Then for all α ≤_{X} β we may find a corresponding bijection

[T_{β}] → [T_{α}]
(y, x) ↦ (ȳ, x̂),

such that:

(i) ȳ always equals p_{(α,β]_{X}} (y); (ii) (ȳ, x̂) is uniformly recursive in

((p_{β}(y))′, x, y);

(iii) if β is the <_{X}-successor of α then (ȳ, x̂)′ is uniformly recursive in ((ȳ)′, x, y).

Proof By induction on β we define maps which work at the level of the nodes of the tree,

πα,β ; s̄ : {(s, t) ∈ T_{β} : lh(s) = lh(t) ≤ lh(s̄)} → ω^{<ω}

and in the end let x̂ be the union over k of

lim_{ℓ→∞}π_{ȳ|_{ℓ}}^{α,β}(x|_{k}, y|_{k}).

At successor steps we simply appeal to the definition of β as the n(β)-β-step down of T_{β+}, and define the various πα,β+ ; s̄’s from the corresponding πα,β ; s̄ and π_{s̄′}^{β,β+} for some appropriate choice of s̄′. This will immediately give part (ii) of the lemma in light of 3.6. The heavy lifting occurs at the limit levels.

So if λ ∈ X is a limit and there are α_{n,λ} → λ given by the suitable ordering (X, <_{X}), then for n ≤ m and (s, t) ∈ T_{λ} × (ω^{≤n} × ω^{≤n}), and

s̄ = p_{(α,λ]_{X}} (s),
s̄′ = p_{(α_{n,λ},λ]_{X}} (s),
s̄′′ = p_{(α_{m,λ},λ]_{X}} (s),

and

α ≤_{X} α_{n,λ} ≤_{X} α_{m,λ} ≤_{X} λ

we have

πα,α_{n,λ} ; s̄(s̄′, t) = πα,α_{m,λ} ; s̄(s̄′′, t),

by the inductive assumption and the definition of an unraveling. Thus we obtain a well defined function if we simply go ahead and choose any such n and let

πα,λ ; s̄(s, t) = πα,α_{n,λ} ; s̄(s̄′, t).

This can in fact be carried out in a uniformly recursive way, thereby giving part (i) of the lemma by 3.5 and the comments which follow it. □

Definition For (X, <_{X}) a recursive well order, β ∈ X, y ∈ ω^{ω} or y ⊂ ω, we let

y^{β}

be the result of iterating the jump operation relative to y out along the initial segment of all elements in X which are below β. For any such X we fix a corresponding uniformly recursive in X tree

S_{X} ⊂ ω^{<ω}

such that S_{X} has exactly one infinite branch

y ∈ [S_{X}]

and on the ω^{th} copy^{2} we have that y equals^{3}

0^{β}.

We can and do additionally assume that this is done so that if Y is an initial segment of X then

S_{Y} = {P_{X\Y} (s) : s ∈ S_{X}}.

Lemma 3.10 Let (X, <_{X}) be a suitable recursive well order of order type κ + 1 and let (T_{β})_{β∈X} be an unraveling with top most element T = T_{j_{0}} having the property that its projection to the first coordinate gives back the tree to find 0^{κ} – namely,

{s : ∃t((s, t) ∈ T)} = S_{X}.

Then for all α ≤_{X} β we may find a corresponding bijection

[T_{β}] → [T_{α}]
(y, x) ↦ (ȳ, x̂),

such that if κ̂ is the order type of the interval [α, β)_{X} in X, then (ȳ, x̂)κ̂ is uniformly recursive in (y, x).

Proof By 3.9 and repeated appeals to the definitions. □

2Again, as before, using our recursive pairing function ρ : ω × ω → ω.

3Up to some reasonable definition of the jump operator, as an element of ω^{ω} Turing equivalent to one of the standard definitions from say [4].

4 Application

Definition Let κ < ω_{1}^{ck} be some recursive well order. A recursively enumerable downward closed U ⊂ ω^{<ω} × ω^{<ω} is said to admit a κ-stack if there is a recursively enumerable T ⊂ ω^{<ω} × ω^{<ω} such that

(i) [T] is uncountable;

(ii) there is a (X, <_{X}) be a suitable recursive well order and let (T_{β})_{β∈X} be an unraveling with top most element T = T_{j_{0}} and bottom most element U; (iii)

{s : ∃t((s, t) ∈ T)} = S_{X}.

Lemma 4.1 If κ̂ < κ < ω_{1}^{ck} and U admits a κ-stack, then it admits a κ̂-stack.

Proof Immediate from the definitions. □

Lemma 4.2 The set of U admitting a κ-stack is Σ_{1}^{1}.

Proof It follows from the perfect set theorem that the collection of trees with uncountably many branches is Σ_{1}^{1}. □

Lemma 4.3 For any κ < ω_{1}^{ck} there is a recursively enumerable U admitting a κ-stack.

Proof From 3.8. □

Corollary 4.4 There is a recursively enumerable U which has a κ-stack for every κ < ω_{1}^{ck}.

Proof Otherwise we obtain for every recursively enumerable U a corresponding

κ < ω_{1}^{ck}

with the Π_{1}^{1} property that there is no κ-stack. Thus by Kriesel uniformization^{4} we can obtain a Δ_{1}^{1} function

U ↦ κ(U),

from recursively enumerable downward closed subset of ω^{<ω} × ω^{<ω} to recursive ordinals, such that at each U we have no κ(U)-stack for U. The collection of all such κ(U)’s is a Δ_{1}^{1} subset of ω_{1}^{ck}, and hence by boundedness there is some κ_{0} such that at every U

κ(U) < κ_{0}.

Thus by 4.1 no recursively enumerable U has a κ_{0} stack, with a contradiction to 4.2. □

So let take such a U which has arbitrarily long stacks and consider some arbitrary (ȳ, x̂) ∈ [U]. It follows from the definitions that ȳ is recursive and at each κ < ω_{1}^{ck} there is some κ + 1-stack built over U, with top most element T = T_{j_{0}}, second top element T_{j_{1}}, which arises as the step down of T_{j_{0}}, and

(y_{0}, x_{0}) ∈ T_{j_{0}},
(y_{1}, x_{1}) ∈ T_{j_{1}},
y_{1} = p_{j_{0}}(y_{0}),
x_{1} = π_{y_{1}}(y_{0}, x_{0}),

4Some people also call this Π_{1}^{1} uniformization for integers.

y_{1} ≡_{T} 0^{κ}.

From 3.10 we get

(ȳ, x̂)^{κ} ≤_{T} (x_{1}, y_{1}).

From 3.7 we get that

(y_{1})′ ≡_{T} 0^{κ+1}

is not recursive in (y_{1}, x_{1}), and hence the κ-degree^{5} of (ŷ, x̂) ≡_{T} x̂ is not above 0^{κ+1}.

Thus we have found a recursively enumerable downward closed U ⊂ ω^{<ω} × ω^{<ω} with uncountably many branches, none of them having κ-degree above 0^{κ+1}. It is then routine to reorganize this to obtain a recursive tree Û with exactly the same infinite branches as U.

To summarize, we have an uncountable Π_{1}^{0} subset of ω^{ω} which does not contain reals of arbitrarily high κ-degree for any κ < ω_{1}^{ck}, and thus provides a negative answer to 57* [1].

References

[1] H. Friedman, One hundred and two problems in mathematical logic, Journal of Symbolic Logic, vol. 40(1975), pp. 113–129.

[2] L.A. Harrington, Arithmetically incomparable arithmetical singletons, mimeographed notes, 1976.

[3] L.A. Harrington, McLaughlin’s conjecture, mimeographed notes, 1976.

[4] P.G. Odifreddi, Classical Recursion Theory, vol. I, North-Holland, Amsterdam, 1989.

greg@math.ucla.edu

MSB 6363 UCLA CA 90095-1555

5Here by κ-degree I mean the Turing degree of the corresponding κ^{th} jump.