Mass problems associated with effectively closed sets

Logic Seminar

Meeting Details

For more information about this meeting, contact Stephen G. Simpson.

Speaker: Stephen G. Simpson, Pennsylvania State University

Abstract: 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: 106 McAllister

Date: 10/23/2007

Time: 2:30pm - 3:45pm