Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Logic Seminar

Noam Greenberg

Victoria University, Wellington

Capturing the nonhyperarithmetic degrees by an algebraic structure

Abstract:

We show that there is a countable structure M such that for any set X, X computes a copy o M if and only if X is not hyperarithmetic. This gives a strong generalisation of the Slaman-Wehner theorem to the hyperdegrees. On the other hand, the generalization of the Slaman-Wehner theorem to the degrees of constructibility is false. This is related to work of Kalimullin and his co-authors on structures whose degree spectrum has full measure. We show, for example, that there are only countably many such structures. We also touch on the possible form of structures M as above. For example, they can be linear orderings, but not have uncountably categorical theories. Many open questions remain. Among them: can we similarly capture the nonarithmetic degrees? Joint work with Antonio Montalban and Ted Slaman.

Host: Sam Buss

March 17, 2011

3:00 PM

AP&M 6402

****************************