Ernest Schimmerling

Mathematical logic seminar - February 19, 2003

Speaker: Stephen Simpson
Department of Mathematics
Pennsylvania State University

Title: An Extension of the Recursively Enumerable Turing Degrees

The recursively enumerable Turing degrees have been studied extensively for more than 50 years. While the methods are intricate, the results have been sterile for foundations of mathematics, and there are no natural examples other than the original ones. In order to overcome these difficulties, we embed the upper semilattice of r. e. Turing degrees into a slightly larger structure which is better behaved and more foundationally relevant. Let $T_1$ and $T_2$ be recursive subtrees of the full binary tree of finite sequences of 0's and 1's. We say that $T_1$ is reducible to $T_2$ if every path through $T_2$ computes a path through $T_1$. The equivalence classes under this reducibility form a countable distributive lattice, the lattice of Muchnik degrees of $\Pi^0_1$ subsets of $2^\omega$. We show that this lattice naturally embeds the upper semilattice of r. e. Turing degrees, via an embedding which preserves top and bottom elements. Within this lattice there are a number of natural examples, including the Muchnik degree of the set of Martin-Lof random reals, and the Muchnik degree of the set of fixed-point-free functions.

Organizer's note:
Professor Simpson will also give the the PAL Colloquium on Thursday, February 20.