Weakly Precomplete Equivalence Relations in the Ershov Hierarchy

N. A. Bazhenov, B. S. Kalmurzaev

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Pages (from-to)199-213
Number of pages15
JournalAlgebra and Logic
Volume58
Issue number3
DOIs
Publication statusPublished - 1 Jul 2019

Keywords

  • computable reducibility
  • equivalence relation
  • Ershov hierarchy
  • universal equivalence relation
  • weakly precomplete equivalence relation

Fingerprint

Dive into the research topics of 'Weakly Precomplete Equivalence Relations in the Ershov Hierarchy'. Together they form a unique fingerprint.

Cite this