Tuesday, September 27 from 3 to 4pm
Room: MB 124
Speaker: John Clemens (BSU)
Title: The Recursion Theorem in Set Theory
Abstract: Kleene’s Recursion Theorem is a simple yet powerful result about computable functions, which asserts the existence of functions which “know their own code” in some suitably nice enumeration of the computable functions. It can be used to find fixed points for operations on computable functions. Less well-known is that the Recursion Theorem can be applied to other Polish spaces (instead of the integers) to produce fixed points for set operations. I will give a brief introduction to the theory of computable functions and the original Recursion Theorem, and then discuss the basics of effective descriptive set theory necessary to extend it to more general Polish spaces. As time permits I will sketch some of the consequences in descriptive set theory, such as finding least fixed points of monotone set operations and Moschovakis’s Coding Lemma.