Π⁰₁ classes

The Π⁰₁ classes are the sets of paths through computable binary trees, and describe the solutions of many problems with conditions refutable in finite time. The course studies the topology of Cantor space and weak König's lemma, which members of Π⁰₁ classes must be computable, the basis theorems of Jockusch and Soare, the PA degrees, which compute members of all non-empty Π⁰₁ classes, and the strength of König's lemma for finitely branching trees.

Contents

1. 1

   Trees and Π⁰₁ classes

   Binary trees and their paths, weak König's lemma, open and closed classes of Cantor space, compactness, and the Π⁰₁ classes as sets of paths through computable trees.

   1. 1.1 Binary trees
   2. 1.2 The topology of Cantor space
   3. 1.3 Π⁰₁ classes
   4. 1.4 Exercises
   5. 1.5 Notes and references
   40 min
2. 2

   Computable members

   Isolated members of Π⁰₁ classes are computable; countable Π⁰₁ classes have computable members; a non-empty Π⁰₁ class without computable member is perfect; the class of DNC₂ functions.

   1. 2.1 The leftmost path
   2. 2.2 Isolated members
   3. 2.3 A Π⁰₁ class without computable members
   4. 2.4 Exercises
   5. 2.5 Notes and references
   35 min
3. 3

   Basis theorems

   The low basis theorem, the computably dominated basis theorem and the cone avoidance basis theorem, proved by forcing with Π⁰₁ classes.

   1. 3.1 The low basis theorem
   2. 3.2 The computably dominated basis theorem
   3. 3.3 Cone avoidance
   4. 3.4 Exercises
   5. 3.5 Notes and references
   45 min
4. 4

   PA degrees

   Sets computing a diagonally non-computable {0,1}-valued function; equivalence with computing a member of every non-empty Π⁰₁ class and with separating disjoint c.e. sets; completions of Peano arithmetic.

   1. 4.1 Definition and characterizations
   2. 4.2 Consequences of the basis theorems
   3. 4.3 Completions of Peano arithmetic
   4. 4.4 Exercises
   5. 4.5 Notes and references
   45 min
5. 5

   Finitely branching trees

   Trees of sequences of integers; König's lemma; computably bounded trees behave like binary trees; a computable finitely branching tree whose paths all compute ∅′; the strength needed for König's lemma.

   1. 5.1 Trees of integers
   2. 5.2 Coding into binary trees
   3. 5.3 Unbounded branching
   4. 5.4 Exercises
   5. 5.5 Notes and references
   35 min