##### 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

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