Positive undecidable numberings in the Ershov hierarchy

M. Manat, A. Sorbi

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

A sufficient condition is given under which an infinite computable family of Σ -1 a -sets has computable positive but undecidable numberings, where a is a notation for a nonzero computable ordinal. This extends a theorem proved for finite levels of the Ershov hierarchy in [1]. As a consequence, it is stated that the family of all Σ -1 a -sets has a computable positive undecidable numbering. In addition, for every ordinal notation a > 1, an infinite family of Σ -1 a-sets is constructed which possesses a computable positive numbering but has no computable Friedberg numberings. This answers the question of whether such families exist at any-finite or infinite-level of the Ershov hierarchy, which was originally raised by Badaev and Goncharov only for the finite levels bigger than 1.

Original languageEnglish
Pages (from-to)512-525
Number of pages14
JournalAlgebra and Logic
Volume50
Issue number6
DOIs
Publication statusPublished - Jan 2012

Keywords

  • Ershov hierarchy
  • positive undecidable numbering

ASJC Scopus subject areas

  • Analysis
  • Logic

Fingerprint Dive into the research topics of 'Positive undecidable numberings in the Ershov hierarchy'. Together they form a unique fingerprint.

Cite this