Mass problems and the Goedel Incompleteness Theorem

Logic Seminar

Meeting Details

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

Speaker: Stephen G. Simpson, Pennsylvania State University

Abstract: We focus on P_w, the lattice of degrees of unsolvability (Muchnik degrees) of mass problems associated with nonempty effectively closed sets in the Cantor space. It is known that P_w is a countable distributive lattice with 0 and 1. We show that the top degree in P_w is precisely the degree of unsolvability of the problem of finding a complete consistent theory which extends Peano Arithmetic. The Goedel Incompleteness Theorem tells us that this problem is unsolvable. It turns out that, instead of Peano Arithmetic, we could take any theory which, like Peano Arithmetic, is recursively axiomatizable and effectively essentially undecidable in the sense of Tarski/Mostowski/Robinson. We show 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 degrees in P_w.

Room Reservation Information

Room Number: 106 McAllister

Date: 10/30/2007

Time: 2:30pm - 3:45pm