Classifying equivalence relations in the Ershov hierarchy.
Arch Math Log
; 59(7): 835-864, 2020.
Article
em En
| MEDLINE
| ID: mdl-33122878
ABSTRACT
Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility ⩽ c . This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the Δ 2 0 case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by ⩽ c on the Σ a - 1 \ Π a - 1 equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.
Texto completo:
1
Coleções:
01-internacional
Base de dados:
MEDLINE
Idioma:
En
Revista:
Arch Math Log
Ano de publicação:
2020
Tipo de documento:
Article