MATH 782 — Spring 2000
Logic Seminar

The topic for this semester will be hyperarithmetic sets and recursion theory on admissible ordinals. We will use the book Higher Recursion Theory by Gerald Sacks. The subjects involve generalizing recursion theory on the natural numbers by taking various procedures into the transfinite. The Turing jump is iterated through he recursive ordinals to provide the skeleton of the hyperarithmetic sets. These are proven to be the sets. (This is both an analog and generalization of the theorem of descriptive set theory that the Borel sets are those which are both analytic and co-analytic.) Other theorems that can be seen as results of descriptive set theory will also be proven such as every uncountable (analytic) set contains a perfect subset. The stage is then set for a recursion theory which takes the (Borel) sets as the finite objects and the (co-analytic) sets as the recursively enumerable ones. Equivalently, these are the subsets of which are members and subsets, respectively, of , the constructible hierarchy up to the first nonrecursive ordinal. One more level of generalization replaces by an arbitrary admissible ordinal to arrive at recursion theory on admissible ordinals.

Last modified: April 7, 2003