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

Mathematical Logic Quarterly 58 (4-5):366-376 (2012)

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 equation image-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 equation image-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 equation image-computable family of cardinality n, whose Rogers semilattice consists of exactly one element
Keywords Rogers semilattice. msc (2010) 03D45  ordinal notation  computable ordinal  Ershov's hierarchy  Computable numbering
Categories (categorize this paper)
DOI 10.1002/malq.201100114
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 43,822
Through your library

References found in this work BETA

Set Theory.Thomas Jech - 1981 - Journal of Symbolic Logic.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Index Sets in Ershov's Hierarchy.Jacques Grassin - 1974 - Journal of Symbolic Logic 39 (1):97-104.
The Iterative Conception of Set.Thomas Forster - 2008 - Review of Symbolic Logic 1 (1):97-110.
Descriptive Set Theory of Families of Small Sets.Étienne Matheron & Miroslav Zelený - 2007 - Bulletin of Symbolic Logic 13 (4):482-537.
Monotone Reducibility and the Family of Infinite Sets.Douglas Cenzer - 1984 - Journal of Symbolic Logic 49 (3):774-782.
Cohen-Stable Families of Subsets of Integers.Miloš S. Kurilić - 2001 - Journal of Symbolic Logic 66 (1):257-270.
Tarskian and Kripkean Truth.Volker Halbach - 1997 - Journal of Philosophical Logic 26 (1):69-80.
A Hierarchy of Families of Recursively Enumerable Degrees.Lawrence V. Welch - 1984 - Journal of Symbolic Logic 49 (4):1160-1170.

Analytics

Added to PP index
2013-10-31

Total views
23 ( #375,749 of 2,265,064 )

Recent downloads (6 months)
1 ( #858,325 of 2,265,064 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature