PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Stephen Simpson.

Title:Mass problems associated with effectively closed sets
Seminar:Logic Seminar
Speaker:Stephen G. Simpson, Pennsylvania State University
We begin with a brief introduction to mass problems in general. After that, the purpose of the talk is to introduce P_w, the lattice of Muchnik degrees of mass problems associated with nonempty effectively closed sets in the Cantor space. We show that P_w is a countable distributive lattice with 0 and 1. We show that the top element of P_w is the Muchnik degree of the problem of finding a complete consistent theory which extends Peano Arithmetic. The G"odel Incompleteness Theorem tells us that this problem is unsolvable. Instead of Peano Arithmetic we could take any theory which, like Peano Arithmetic, is recursively axiomatizable and effectively essentially undecidable. It turns out that the effectively closed sets associated with all such theories are not only Muchnik equivalent but also recursively homeomorphic to each other. As time permits we shall exhibit some other interesting examples of specific, natural Muchnik degrees in P_w.

Room Reservation Information

Room Number:MB106
Date:10 / 23 / 2007
Time:02:30pm - 03:45pm