TY - JOUR

T1 - Weakly Precomplete Equivalence Relations in the Ershov Hierarchy

AU - Bazhenov, N. A.

AU - Kalmurzaev, B. S.

PY - 2019/7/1

Y1 - 2019/7/1

N2 - We study the computable reducibility ≤c for equivalence relations in the Ershov hierarchy. For an arbitrary notation a for a nonzero computable ordinal, it is stated that there exist a Πa−1 -universal equivalence relation and a weakly precomplete Σa−1 - universal equivalence relation. We prove that for any Σa−1 equivalence relation E, there is a weakly precomplete Σa−1 equivalence relation F such that E ≤cF. For finite levels Σm−1 in the Ershov hierarchy at which m = 4k +1 or m = 4k +2, it is shown that there exist infinitely many ≤c-degrees containing weakly precomplete, proper Σm−1 equivalence relations.

AB - We study the computable reducibility ≤c for equivalence relations in the Ershov hierarchy. For an arbitrary notation a for a nonzero computable ordinal, it is stated that there exist a Πa−1 -universal equivalence relation and a weakly precomplete Σa−1 - universal equivalence relation. We prove that for any Σa−1 equivalence relation E, there is a weakly precomplete Σa−1 equivalence relation F such that E ≤cF. For finite levels Σm−1 in the Ershov hierarchy at which m = 4k +1 or m = 4k +2, it is shown that there exist infinitely many ≤c-degrees containing weakly precomplete, proper Σm−1 equivalence relations.

KW - computable reducibility

KW - equivalence relation

KW - Ershov hierarchy

KW - universal equivalence relation

KW - weakly precomplete equivalence relation

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

U2 - 10.1007/s10469-019-09538-y

DO - 10.1007/s10469-019-09538-y

M3 - Article

AN - SCOPUS:85074823099

VL - 58

SP - 199

EP - 213

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 3

ER -