Ernest Schimmerling
Mathematical logic seminar - February 19, 2003
| Speaker: | |
Stephen Simpson
Professor
Department of Mathematics
Pennsylvania State University
|
| Title: |
|
An Extension of the Recursively Enumerable Turing Degrees
|
| Abstract: |
|
|
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.