|
This article is cited in 3 scientific papers (total in 3 papers)
Weakly precomplete equivalence relations in the Ershov hierarchy
N. A. Bazhenovab, B. S. Kalmurzaevc a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University
c Al-Farabi Kazakh National University
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
Π−1a-universal
equivalence relation and a weakly precomplete
Σ−1a-universal
equivalence relation. We prove that for any
Σ−1a equivalence relation
E, there is a weakly precomplete
Σ−1a equivalence relation
F such
that E≤cF.
For finite levels Σ−1m 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 Σ−1m
equivalence relations.
Keywords:
Ershov hierarchy, equivalence relation,
computable reducibility, universal equivalence relation, weakly
precomplete equivalence relation.
Received: 11.04.2018 Revised: 24.09.2019
Citation:
N. A. Bazhenov, B. S. Kalmurzaev, “Weakly precomplete equivalence relations in the Ershov hierarchy”, Algebra Logika, 58:3 (2019), 297–319; Algebra and Logic, 58:3 (2019), 199–213
Linking options:
https://www.mathnet.ru/eng/al896 https://www.mathnet.ru/eng/al/v58/i3/p297
|
Statistics & downloads: |
Abstract page: | 257 | Full-text PDF : | 27 | References: | 37 | First page: | 3 |
|