Peter Koepke: Computations with Ordinals, and Models of Set Theory

Days in Logic '06

Coimbra, 19-21 January 2006

Updated tutorial material

Ordinary computations can be characterised by register machines working with natural numbers. We introduce ordinal register machines where the registers can hold arbitrary ordinal numbers. The class of sets of ordinals which are computable by such machines has strong closure properties. It allows to formalise the usual mathematical notions like relations and functions, numbers, and infinitary recursion. It can thus be used as a foundation of mathematics and it codes Gödel's model of constructible sets.

A tentative course outline is as follows:

  1. Review of the theory of ordinals.
  2. Review of standard register machines.
  3. Definition of ordinal register machines.
  4. Notions of ordinal computability.
  5. A universal ordinal machine.
  6. Closure properties of the class of ordinal computable sets.
  7. The theory of sets of ordinals.
  8. Relations to Gödel's constructible model L
A first introduction to ordinal computations (with Turing rather than register machines) can be found in

P. Koepke, Turing computations on ordinals, The Bulletin of Symbolic Logic 11, No. 3, pp. 377-397.

Further material will be made available during the course.

Reinhard Kahle, 21.01.06