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 Δ20 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.
Classifying equivalence relations in the Ershov hierarchy
San Mauro L.
;
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 Δ20 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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
