MATH 784: Recursion Theory (Fall 2005)

Instructor: Richard Shore

Meeting Time & Room

Depending on interest there are two possibilities for 784 this term.

The standard one is a first course in the theory of computability. We will assume some background in logic. MATH 681 or Computer Science 682 should be more than sufficient. We will concentrate on the recursively (computably) enumerable sets and degrees. The text will be Recursively Enumerable Sets and Degrees by R. I. Soare (Springer-Verlag).

We will begin with a brief discussion of the basic properties of a reasonable model of computability: universal machines, the enumeration, s-m-n and recursion theorems, r.e. (effectively or computably enumerable) sets and the halting problem (one week). Next will come the notions of relative computability, the Turing jump operator and the arithmetical hierarchy (two weeks).

There will be some development of construction procedures for non-r.e. sets including the Kleene-Post finite extension method (really Cohen forcing in arithmetic) and perhaps minimal degree constrictions by forcing with trees (perfect set forcing). The heart of the course, however, will be the development of various kinds of priority arguments for the construction of r.e. sets including finite and infinite injury as well as tree arguments. We will use these methods to analyze the structure of the (Turing) degrees of r.e. sets and something of their set theoretic structure as well. Connections between degree theoretic and other properties such as types of approximations, rates of growth and complexity of definition will be considered.

The second possibility is for a much more advanced course on hyperarithmetic theory using Higher Recursion Theory by Gerald Sacks. This begins with the constructive ordinals, effective transfinite recursion and Pi-1-1 sets. Then an analysis of the hyperarithmetic hierarchy based on iterating the Turing jump into the transfinite. Included is the equivalence of HYP and Delta-1-1 (which is the effective analog of Borel = analytic and coanalytic). Next is a deeper analysis of analytic (=Sigma-1-1=projections of Borel) and coanalytic (=Pi-1-1=complements of analytic) sets. Basis theorems, uniformization, selection and the perfect set theorem. If this topic is not covered in 784 it will be the topic for 781.

Last modified: March 31, 2005