### 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 language | English |
---|---|

Pages (from-to) | 366-376 |

Number of pages | 11 |

Journal | Mathematical Logic Quarterly |

Volume | 58 |

Issue number | 4-5 |

DOIs | |

Publication status | Published - Aug 2012 |

Externally published | Yes |

### Fingerprint

### Keywords

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

### ASJC Scopus subject areas

- Logic

### Cite this

*Mathematical Logic Quarterly*,

*58*(4-5), 366-376. https://doi.org/10.1002/malq.201100114

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

Research output: Contribution to journal › Article

*Mathematical Logic Quarterly*, vol. 58, no. 4-5, pp. 366-376. https://doi.org/10.1002/malq.201100114

}

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 -