Post's problem and the priority method

Post's problem asks for a c.e. set that is neither computable nor complete. The course presents Post's simple sets and why they are not many-one complete, then the finite injury priority method in three constructions: two incomparable c.e. sets (Friedberg–Muchnik), a low simple set, and the Sacks splitting theorem with its preservation strategy, with consequences for the structure of the c.e. degrees.

Contents

1. 1

   Simple sets and Post's problem

   Post's problem; simple sets and Post's construction; productive and creative sets; simple sets are not many-one complete.

   1. 1.1 Simple sets
   2. 1.2 Productive and creative sets
   3. 1.3 Exercises
   4. 1.4 Notes and references
   35 min
2. 2

   The Friedberg–Muchnik theorem

   Two Turing incomparable c.e. sets, by the finite injury priority method; requirements, witnesses, priority and initialization.

   1. 2.1 The requirements
   2. 2.2 The construction
   3. 2.3 Verification
   4. 2.4 Exercises
   5. 2.5 Notes and references
   45 min
3. 3

   A low simple set

   A c.e. set that is simple and low, built by finite injury; preservation of computations by restraints; a second solution to Post's problem.

   1. 3.1 The requirements
   2. 3.2 The construction
   3. 3.3 Verification
   4. 3.4 Exercises
   5. 3.5 Notes and references
   40 min
4. 4

   The Sacks splitting theorem

   Splitting a c.e. set into two c.e. sets that avoid the cone above a non-computable c.e. set; the length of agreement and Sacks' preservation strategy; consequences for the c.e. degrees.

   1. 4.1 Length of agreement
   2. 4.2 The construction
   3. 4.3 Verification
   4. 4.4 Consequences
   5. 4.5 Exercises
   6. 4.6 Notes and references
   45 min