Event Detail

A ceer is a computably enumerable equivalence relation on the natural numbers. Ceers are preordered in a natural way, by saying E is reducible to F iff there is a computable function f such that for all x and y we have x E y ↔ f(x) F f(y). Lots of specific properties of the preorder of ceers have been established; in another direction, however, we could look at the analogues of ceers in appropriate “generalized computability theories” and ask what properties of the ceers are (relatively) setting-independent.

In this talk we will see that the theory of the ceers is “robustly” as complicated as it could possibly be: there is a natural notion of “κ-ceer” for any infinite regular cardinal κ, and the theory of the κ-ceers is always maximally complicated in terms of κ-recursion theory. Interestingly, this seems to require a genuinely different argument once we look at uncountable κ. I will also present a separate argument which applies to a somewhat different class of generalized computability theories.

The first part of this work is joint with Uri Andrews and Andrea Sorbi, and the second part is joint with Uri Andrews, Steffen Lempp, and Manat Mustafa.