Positive undecidable numberings in the Ershov hierarchy

M. Manat, A. Sorbi

Research output: Contribution to journalArticle

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
Externally publishedYes

Fingerprint

Ershov Hierarchy
Notation
Family
Sufficient Conditions
Theorem

Keywords

  • Ershov hierarchy
  • positive undecidable numbering

ASJC Scopus subject areas

  • Analysis
  • Logic

Cite this

Positive undecidable numberings in the Ershov hierarchy. / Manat, M.; Sorbi, A.

In: Algebra and Logic, Vol. 50, No. 6, 01.2012, p. 512-525.

Research output: Contribution to journalArticle

Manat, M. ; Sorbi, A. / Positive undecidable numberings in the Ershov hierarchy. In: Algebra and Logic. 2012 ; Vol. 50, No. 6. pp. 512-525.
@article{7fcaf2814f874b01aa621b0dcf59e3c2,
title = "Positive undecidable numberings in the Ershov hierarchy",
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.",
keywords = "Ershov hierarchy, positive undecidable numbering",
author = "M. Manat and A. Sorbi",
year = "2012",
month = "1",
doi = "10.1007/s10469-012-9162-0",
language = "English",
volume = "50",
pages = "512--525",
journal = "Algebra and Logic",
issn = "0002-5232",
publisher = "Springer New York",
number = "6",

}

TY - JOUR

T1 - Positive undecidable numberings in the Ershov hierarchy

AU - Manat, M.

AU - Sorbi, A.

PY - 2012/1

Y1 - 2012/1

N2 - 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.

AB - 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.

KW - Ershov hierarchy

KW - positive undecidable numbering

UR - http://www.scopus.com/inward/record.url?scp=84858746672&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84858746672&partnerID=8YFLogxK

U2 - 10.1007/s10469-012-9162-0

DO - 10.1007/s10469-012-9162-0

M3 - Article

AN - SCOPUS:84858746672

VL - 50

SP - 512

EP - 525

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 6

ER -