PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

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:
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