Ceers higher up

Abstract: Abstract: We examine analogues of ceers (computably enumerable equivalence relations) in generalized recursion theory - specifically, in $\kappa$-recursion theory for $\kappa$ an uncountable regular cardinal. Classically, the degrees of ceers with respect to computable embeddability forms a partial order which is maximally complicated, namely one whose theory is computably isomorphic to that of true arithmetic. We extend this result to the $\kappa$-ceers. Interestingly, this requires a genuinely new argument, and currently no single approach is known which applies both to $\omega$ and to uncountable regular $\kappa$. Moreover, the situation for singular cardinals, let alone admissible ordinals which are not cardinals such as $\omega_1^{CK}$, is completely open. If time permits, we will discuss a second proof of the above result for the special case of $\kappa=\omega_1$ which has the advantage of applying to certain generalized computability theories other than $\kappa$-recursion theories.

This is joint work with Uri Andrews, Steffen Lempp, and Manat Mustafa.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic