Rogers Semilattices for Families of Equivalence Relations in the Ershov Hierarchy

N. A. Bazhenov, B. S. Kalmurzaev

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)223-234
Number of pages12
JournalSiberian Mathematical Journal
Volume60
Issue number2
DOIs
Publication statusPublished - 1 Mar 2019

Keywords

  • computable numbering
  • equivalence relation
  • Ershov hierarchy
  • Friedberg numbering
  • minimal numbering
  • principal ideal
  • Rogers semilattice
  • universal numbering

Fingerprint Dive into the research topics of 'Rogers Semilattices for Families of Equivalence Relations in the Ershov Hierarchy'. Together they form a unique fingerprint.

Cite this