For more information about this meeting, contact Stephen Simpson.

Title: | Degrees of unsolvability and the Borel hierarchy |

Seminar: | Logic Seminar |

Speaker: | Stephen G. Simpson, Pennsylvania State University |

Abstract Link: | http://www.math.psu.edu/simpson/papers/massmtr.pdf |

Abstract: |

Given a real number x, let x' be the halting problem relative to x. In other words, x' is the problem of deciding whether a given computer program which uses x as a Turing oracle will or will not eventually halt. By means of Gödel numbering, we may view x' as another real number. Thus we have an operator x |---> x' from real numbers to real numbers, known as the Turing jump operator. By iterating the Turing jump operator along the ordinal numbers which are computable using x as an oracle, we obtain what is known as the hyperarithmetical hierarchy relative to x. In this talk we explore the relationship between the hyperarithmetical hierarchy and the well-known hierarchy of Borel sets in Euclidean space indexed by the countable ordinal numbers. We sketch a proof of the following theorem of Kautz, 1991: If S is a Borel set at level alpha+2 in the effective Borel hierarchy relative to x, then S includes a set whose Lebesgue measure is the same as that of S and which is at level 2 of the effective Borel hierarchy relative to the alpha-th Turing jump of x. As time permits, we discuss recent refinements involving LR-reducibility. |

### Room Reservation Information

Room Number: | MB315 |

Date: | 09 / 15 / 2009 |

Time: | 02:30pm - 03:45pm |