Rogers semilattices of families of two embedded sets in the Ershov hierarchy

Serikzhan A. Badaev, Mustafa Manat, Andrea Sorbi

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every -computable family of two embedded sets, i.e., two sets A, B, with A properly contained in B, the Rogers semilattice of the family is infinite. This condition is satisfied by every notation of ω; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On the other hand, we also give a sufficient condition on a, that yields that there is a -computable family of two embedded sets, whose Rogers semilattice consists of exactly one element; this condition is satisfied by all notations of every successor ordinal bigger than 1, and by all notations of the ordinal ω + ω; moreover every computable ordinal that is sum of two smaller ordinals has a notation that satisfies this condition. We also show that for every nonzero n ∈ ω, or n = ω, and every notation a of a nonzero ordinal there exists a -computable family of cardinality n, whose Rogers semilattice consists of exactly one element.

Original languageEnglish
Pages (from-to)366-376
Number of pages11
JournalMathematical Logic Quarterly
Volume58
Issue number4-5
DOIs
Publication statusPublished - Aug 1 2012

Keywords

  • Computable numbering
  • Computable ordinal
  • Ershov's hierarchy
  • Ordinal notation
  • Rogers semilattice

ASJC Scopus subject areas

  • Logic

Fingerprint Dive into the research topics of 'Rogers semilattices of families of two embedded sets in the Ershov hierarchy'. Together they form a unique fingerprint.

  • Cite this