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 Δ02 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 ∑-1a∏-1a equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.

Bazhenov, N., Mustafa, M., SAN MAURO, L.F., Sorbi, A., Yamaleev, M. (2020). Classifying equivalence relations in the Ershov hierarchy. ARCHIVE FOR MATHEMATICAL LOGIC, 59(7-8), 835-864 [10.1007/s00153-020-00710-1].

Classifying equivalence relations in the Ershov hierarchy

San Mauro Luca
;
Sorbi Andrea;
2020-01-01

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 Δ02 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 ∑-1a∏-1a equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.
2020
Bazhenov, N., Mustafa, M., SAN MAURO, L.F., Sorbi, A., Yamaleev, M. (2020). Classifying equivalence relations in the Ershov hierarchy. ARCHIVE FOR MATHEMATICAL LOGIC, 59(7-8), 835-864 [10.1007/s00153-020-00710-1].
File in questo prodotto:
File Dimensione Formato  
eqrel-ershov-hierarchy.pdf

accesso aperto

Descrizione: Articolo
Tipologia: PDF editoriale
Licenza: Creative commons
Dimensione 454.96 kB
Formato Adobe PDF
454.96 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1110348