Rogers semilattices for families of equivalence relations in the Ershov hierarchy

DOI10.1134/S0037446619020046zbMath1445.03050OpenAlexW2942253303MaRDI QIDQ2313294

B. S. Kalmurzayev, Nikolay Bazhenov

Publication date: 18 July 2019

Published in: Siberian Mathematical Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0037446619020046

zbMATH Keywords

computable numberingprincipal idealequivalence relationErshov hierarchyFriedberg numberingminimal numberingRogers semilatticeuniversal numbering

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Theory of numerations, effectively presented structures (03D45) Hierarchies of computability and definability (03D55)

Related Items

Minimal generalized computable numberings and families of positive preorders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Positive undecidable numberings in the Ershov hierarchy
• Computable categoricity and the Ershov hierarchy
• Two existence theorems for computable numerations
• Computable structures and the hyperarithmetical hierarchy
• On dark computably enumerable equivalence relations
• Properties of numberings in various levels of the Ershov hierarchy
• Infinite family of \(\Sigma_a^{-1}\)-sets with a unique computable numbering
• On computable enumerations. I
• Families without minimal numberings
• Embeddability of the semilattice \(L_m^0\) in Rogers semilattices
• Rogers semilattices of families of two embedded sets in the Ershov hierarchy
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• A decomposition of the Rogers semilattice of a family of d.c.e. sets
• On the existence of universal numberings for finite families of d.c.e. sets
• Friedberg numberings in the Ershov hierarchy
• Friedberg numberings in the Ershov hierarchy