Structure of the Turing degrees

The global structure of the Turing degrees as a partial order: the upper semilattice structure and its failure to be a lattice through Spector's exact pairs, the embedding of every countable partial order using independent columns of a 1-generic set, antichains of size continuum, and Spector's construction of minimal degrees by forcing with function trees.

Contents

1. 1

   The partial order of the Turing degrees

   The Turing degrees form an upper semilattice with countable lower cones and no maximal element; every countable ideal has an exact pair; consequently the degrees do not form a lattice, and strictly increasing sequences have no least upper bound.

   1. 1.1 Elementary properties
   2. 1.2 Exact pairs
   3. 1.3 Consequences
   4. 1.4 Exercises
   5. 1.5 Notes and references
   35 min
2. 2

   Embedding partial orders

   The columns of a 1-generic set are computably independent; a computable partial order contains a copy of every countable partial order; hence every countable partial order embeds into the Turing degrees below 0′; there is an antichain of continuum many degrees.

   1. 2.1 Independent sets
   2. 2.2 A universal countable partial order
   3. 2.3 The embedding theorem
   4. 2.4 An antichain of size continuum
   5. 2.5 Exercises
   6. 2.6 Notes and references
   35 min
3. 3

   Minimal degrees

   Splitting trees give a set of minimal Turing degree computable in 0″ (Spector) and a minimal cover of every degree; no c.e. or 1-generic degree is minimal, and no non-empty Π⁰₁ class consists of sets of minimal degree.

   1. 3.1 Splitting trees
   2. 3.2 Spector's theorem
   3. 3.3 Minimal covers
   4. 3.4 Exercises
   5. 3.5 Notes and references
   40 min