Recursive Structures and Ershov's Hierarchy
Christopher J. Ash, Julia F. Knight · Mathematical logic quarterly · 1996
Abstract Ash and Nerode [2] gave natural definability conditions under which a relation is intrinsically r. e. Here we generalize this to arbitrary levels in Ershov's hierarchy of Δ sets, giving conditions under which a relation is intrinsically α‐r. e. Mathematics Subject Classification: 03C57, 03D55.