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

Fingerprint

Ershov Hierarchy
Semilattice
Notation
Ordinals
Sufficient Conditions
Family
Cardinality

Keywords

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

ASJC Scopus subject areas

  • Logic

Cite this

Rogers semilattices of families of two embedded sets in the Ershov hierarchy. / Badaev, Serikzhan A.; Manat, Mustafa; Sorbi, Andrea.

In: Mathematical Logic Quarterly, Vol. 58, No. 4-5, 08.2012, p. 366-376.

Research output: Contribution to journalArticle

Badaev, Serikzhan A. ; Manat, Mustafa ; Sorbi, Andrea. / Rogers semilattices of families of two embedded sets in the Ershov hierarchy. In: Mathematical Logic Quarterly. 2012 ; Vol. 58, No. 4-5. pp. 366-376.
@article{da54a6cd1cb04e2cb5c0e2b0748011ae,
title = "Rogers semilattices of families of two embedded sets in the Ershov hierarchy",
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.",
keywords = "Computable numbering, Computable ordinal, Ershov's hierarchy, Ordinal notation, Rogers semilattice",
author = "Badaev, {Serikzhan A.} and Mustafa Manat and Andrea Sorbi",
year = "2012",
month = "8",
doi = "10.1002/malq.201100114",
language = "English",
volume = "58",
pages = "366--376",
journal = "Mathematical Logic Quarterly",
issn = "0942-5616",
publisher = "Wiley-VCH Verlag",
number = "4-5",

}

TY - JOUR

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

AU - Badaev, Serikzhan A.

AU - Manat, Mustafa

AU - Sorbi, Andrea

PY - 2012/8

Y1 - 2012/8

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

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

KW - Computable numbering

KW - Computable ordinal

KW - Ershov's hierarchy

KW - Ordinal notation

KW - Rogers semilattice

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

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

U2 - 10.1002/malq.201100114

DO - 10.1002/malq.201100114

M3 - Article

AN - SCOPUS:84864767814

VL - 58

SP - 366

EP - 376

JO - Mathematical Logic Quarterly

JF - Mathematical Logic Quarterly

SN - 0942-5616

IS - 4-5

ER -