TY - JOUR

T1 - Rogers Semilattices for Families of Equivalence Relations in the Ershov Hierarchy

AU - Bazhenov, N. A.

AU - Kalmurzaev, B. S.

PY - 2019/3/1

Y1 - 2019/3/1

N2 - The paper studies Rogers semilattices for families of equivalence relations in the Ershov hierarchy. For an arbitrary notation a of a nonzero computable ordinal, we consider ∑a−1-computable numberings of the family of all ∑a−1 equivalence relations. We show that this family has infinitely many pairwise incomparable Friedberg numberings and infinitely many pairwise incomparable positive undecidable numberings. We prove that the family of all c.e. equivalence relations has infinitely many pairwise incomparable minimal nonpositive numberings. Moreover, we show that there are infinitely many principal ideals without minimal numberings.

AB - The paper studies Rogers semilattices for families of equivalence relations in the Ershov hierarchy. For an arbitrary notation a of a nonzero computable ordinal, we consider ∑a−1-computable numberings of the family of all ∑a−1 equivalence relations. We show that this family has infinitely many pairwise incomparable Friedberg numberings and infinitely many pairwise incomparable positive undecidable numberings. We prove that the family of all c.e. equivalence relations has infinitely many pairwise incomparable minimal nonpositive numberings. Moreover, we show that there are infinitely many principal ideals without minimal numberings.

KW - computable numbering

KW - equivalence relation

KW - Ershov hierarchy

KW - Friedberg numbering

KW - minimal numbering

KW - principal ideal

KW - Rogers semilattice

KW - universal numbering

UR - http://www.scopus.com/inward/record.url?scp=85064950874&partnerID=8YFLogxK

U2 - 10.1134/S0037446619020046

DO - 10.1134/S0037446619020046

M3 - Article

AN - SCOPUS:85064950874

VL - 60

SP - 223

EP - 234

JO - Siberian Mathematical Journal

JF - Siberian Mathematical Journal

SN - 0037-4466

IS - 2

ER -