Reducibilities between problems

A Π¹₂ theorem can be seen as a problem whose instances must be given solutions. The course compares problems by three reducibilities of increasing precision: ω-reducibility, the computational counterpart of implication over RCA₀ in ω-models, with weakness properties and reduction games; computable reducibility, which allows a single application of the stronger problem, with Scott's theorem and cylinders; and Weihrauch reducibility, which requires uniformity, with the omniscience principles and parallelization.

Contents

1. 1

   Problems and ω-reducibility

   Theorems of the form "every instance has a solution" seen as problems; Turing ideals satisfying a problem and ω-reducibility; König's lemma and the jump; weakness properties and their preservation, the standard method for separations; the game characterization of ω-reducibility.

   1. 1.1 Problems
   2. 1.2 Weakness properties and preservation
   3. 1.3 Reduction games
   4. 1.4 Exercises
   5. 1.5 Notes and references
   40 min
2. 2

   Computable reducibility

   Reductions that use a single instance of the stronger problem; computable and strong computable reducibility; König's lemma is ω-reducible but not computably reducible to the jump; Scott's theorem that every PA degree bounds a Scott ideal, and the coincidence of ω-reducibility and computable reducibility to WKL; cylinders.

   1. 2.1 Computable and strong computable reducibility
   2. 2.2 Computable reductions to weak König's lemma
   3. 2.3 Cylinders
   4. 2.4 Exercises
   5. 2.5 Notes and references
   35 min
3. 3

   Weihrauch reducibility

   Uniform computable reductions; uniformly true problems, and the pigeonhole principle as a problem that is computably but not uniformly true; the omniscience principles LPO and LLPO; parallelization, the jump as parallel LPO and weak König's lemma as parallel LLPO.

   1. 3.1 Definitions
   2. 3.2 The omniscience principles
   3. 3.3 Parallelization
   4. 3.4 Exercises
   5. 3.5 Notes and references
   40 min