Standard

Weakly Precomplete Equivalence Relations in the Ershov Hierarchy. / Bazhenov, N. A.; Kalmurzaev, B. S.

In: Algebra and Logic, Vol. 58, No. 3, 01.07.2019, p. 199-213.

Research output: Contribution to journal › Article › peer-review

Harvard

Bazhenov, NA & Kalmurzaev, BS 2019, 'Weakly Precomplete Equivalence Relations in the Ershov Hierarchy', Algebra and Logic, vol. 58, no. 3, pp. 199-213. https://doi.org/10.1007/s10469-019-09538-y

APA

Bazhenov, N. A., & Kalmurzaev, B. S. (2019). Weakly Precomplete Equivalence Relations in the Ershov Hierarchy. Algebra and Logic, 58(3), 199-213. https://doi.org/10.1007/s10469-019-09538-y

Vancouver

Bazhenov NA, Kalmurzaev BS. Weakly Precomplete Equivalence Relations in the Ershov Hierarchy. Algebra and Logic. 2019 Jul 1;58(3):199-213. doi: 10.1007/s10469-019-09538-y

Author

Bazhenov, N. A. ; Kalmurzaev, B. S. / Weakly Precomplete Equivalence Relations in the Ershov Hierarchy. In: Algebra and Logic. 2019 ; Vol. 58, No. 3. pp. 199-213.

BibTeX

@article{ddd67161a188409e8319aca348e8d334,
title = "Weakly Precomplete Equivalence Relations in the Ershov Hierarchy",
abstract = "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.",
keywords = "computable reducibility, equivalence relation, Ershov hierarchy, universal equivalence relation, weakly precomplete equivalence relation",
author = "Bazhenov, {N. A.} and Kalmurzaev, {B. S.}",
year = "2019",
month = jul,
day = "1",
doi = "10.1007/s10469-019-09538-y",
language = "English",
volume = "58",
pages = "199--213",
journal = "Algebra and Logic",
issn = "0002-5232",
publisher = "Springer US",
number = "3",

}

RIS

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 -

ID: 22361348