Large Branches of the E-tree and Jump Pseudo-hierarchies

V. Yu. Shavrukov

Let Σ be the lattice of Σ_{1} sentences modulo provability in Peano arithmetic. Thus the largest element ⊤ of Σ is represented by the sentence 0 = 0.

The E-tree is the collection of proper prime filters on Σ partially ordered by inclusion. As the name suggests, this poset is tree-like in the sense that the predecessors of any element are linearly ordered. {⊤} is the root of the E-tree.

We study branches through the E-tree. It turns out that Turing complexity properties of prime filters hold the key to the structure of maximal branches.

A jump pseudo-hierarchy (j.p.h.) is a triple (P, ≤, (X_{p})_{p∈P}) where P, X_{p} ∈ ω, and ≤ is a linear order on P such that the sets

{ (q, r) ∈ P^{2} | q ≤ r < p } and { (q, m) ∈ P × ω | q < p and m ∈ X′_{q} }

are recursive in X_{p}, uniformly in p. (′ is the Turing jump).

A coloured j.p.h. is a j.p.h. (P, ≤, (X_{p})_{p∈P}) together with a colouring c : P → 5 of P in 5 colours such that the set { (q, c(q)) | q < p } is recursive in X_{p}, uniformly in p.

Our main theorem characterizes the possible order types of branches through the E-tree as those coded by coloured j.p.h.’s satisfying a simple structural condition (or, more precisely, by the coloured order types admitting a j.p.h.).

The coding of order types by pseudo-hierarchies is such that the coded order type “resembles” the order ≤ of the pseudo-hierarchy.

Further, the possible order types of (coloured) j.p.h.’s are described by the formula

( ∑_{ι<γ} λ_{ι} × ϖ_{ι}) + β,

where — × is the lexicographic product,

— (λ_{ι})_{ι<γ} is any strictly increasing countable sequence of countable ordinals > ω such that λ_{ι} is admissible relative to {λ_{κ}}_{κ<ι},

— ϖ_{ι} = \{ \begin{matrix}1 + η & if λ_{ι} > sup_{κ<ι} λ_{κ} \\ η & if λ_{ι} = sup_{κ<ι} λ_{κ}, \end{matrix}

— η is the dense countable order type without end points, and

— β is any countable ordinal.

Address: Department of Mathematics and Computer Science, University of Leicester, Leicester LE1 7RH, U.K.

E-mail: volodya@mcs.le.ac.uk