Computable ordinals

The ordinals that can be described effectively: well-orderings and ordinals, computable well-orderings and Kleene's system of notations O, the Markwald–Kleene theorem, well-founded trees and the Kleene–Brouwer ordering, the normal form and completeness of Π¹₁ sets, and Spector's boundedness theorem.

Contents

1. 1

   Well-orderings and ordinals

   Well-orderings, order isomorphisms and ordinals; the comparison theorem; transfinite induction and recursion; ordinal arithmetic; countable ordinals and ω₁.

   1. 1.1 Well-orderings
   2. 1.2 Ordinals
   3. 1.3 Countable ordinals
   4. 1.4 Exercises
   5. 1.5 Notes and references
   35 min
2. 2

   Computable ordinals and Kleene's O

   Computable well-orderings and the Church–Kleene ordinal; Kleene's system of notations O; addition of notations by the recursion theorem; the Markwald–Kleene theorem that the constructive ordinals are exactly the computable ones; relativization.

   1. 2.1 Computable well-orderings
   2. 2.2 Kleene's O
   3. 2.3 From notations to well-orderings and back
   4. 2.4 Relativization
   5. 2.5 Exercises
   6. 2.6 Notes and references
   40 min
3. 3

   Well-founded trees and Π¹₁ sets

   Well-founded trees and their ranks; the Kleene–Brouwer ordering; the normal form of Π¹₁ sets as sets of indices of well-founded trees; the Π¹₁-completeness of well-foundedness and well-ordering; Π¹₁ is not Σ¹₁; Spector's boundedness theorem.

   1. 3.1 Trees on ℕ and their ranks
   2. 3.2 Π¹₁ sets and their normal form
   3. 3.3 Π¹₁ is not Σ¹₁
   4. 3.4 Spector's boundedness theorem
   5. 3.5 Exercises
   6. 3.6 Notes and references
   45 min