Effective descriptive set theory

The Π¹₁ sets behave like c.e. sets enumerated along the computable ordinals. The course compares the stages at which elements enter a Π¹₁ set by comparing ranks of well-founded trees, and deduces the reduction property for Π¹₁ sets, Kleene's separation theorem for Σ¹₁ sets, Kreisel's uniformization theorem and the selection of hyperarithmetic functions. It ends with Harrison's effective perfect set theorem: countable Σ¹₁ classes consist of hyperarithmetic sets.

Contents

1. 1

   Π¹₁ norms and the reduction property

   The rank of the normal-form tree as a stage at which an element enters a Π¹₁ set; comparison of ranks by strictly monotone maps; the stage comparison relations are Π¹₁; the reduction property for Π¹₁ sets and Kleene's separation theorem for Σ¹₁ sets.

   1. 1.1 Ranks and strictly monotone maps
   2. 1.2 Stage comparison
   3. 1.3 Reduction and separation
   4. 1.4 Exercises
   5. 1.5 Notes and references
   35 min
2. 2

   Uniformization and stages

   Kreisel's uniformization theorem for Π¹₁ relations on numbers; total Π¹₁ functions are hyperarithmetic; a Π¹₁ set is the increasing union of hyperarithmetic stages along ω₁ᶜᵏ, and it is Δ¹₁ exactly when its stages are bounded.

   1. 2.1 Uniformization
   2. 2.2 Stages from below
   3. 2.3 Exercises
   4. 2.4 Notes and references
   30 min
3. 3

   Countable Σ¹₁ classes

   Σ¹₁ singletons are hyperarithmetic; the class of hyperarithmetic sets is Π¹₁; by the effective perfect set theorem, a Σ¹₁ class with a non-hyperarithmetic member contains a perfect closed subclass, so countable Σ¹₁ classes consist of hyperarithmetic sets.

   1. 3.1 Σ¹₁ singletons
   2. 3.2 The effective perfect set theorem
   3. 3.3 Exercises
   4. 3.4 Notes and references
   30 min