The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent

, , &
Annals of Pure and Applied Logic 164 (5):577-588 (2013)
  Copy   BIBTEX

Abstract

We show that, in the partial ordering of the computably enumerable computable Lipschitz degrees, there is a degree a>0a>0 such that the class of the degrees which do not cup to a is not bounded by any degree less than a. Since Ambos-Spies [1] has shown that, in the partial ordering of the c.e. identity-bounded Turing degrees, for any degree a>0a>0 the degrees which do not cup to a are bounded by the 1-shift a+1a+1 of a where a+1

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2012.11.002

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,317

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Undecidability and 1-types in intervals of the computably enumerable degrees.Klaus Ambos-Spies, Denis R. Hirschfeldt & Richard A. Shore - 2000 - Annals of Pure and Applied Logic 106 (1-3):1-47.
Undecidability and 1-types in the recursively enumerable degrees.Klaus Ambos-Spies & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 63 (1):3-37.
The ibT degrees of computably enumerable sets are not dense.George Barmpalias & Andrew E. M. Lewis - 2006 - Annals of Pure and Applied Logic 141 (1):51-60.
1-Generic splittings of computably enumerable degrees.Guohua Wu - 2006 - Annals of Pure and Applied Logic 138 (1):211-219.
Degree spectra of the successor relation of computable linear orderings.Jennifer Chubb, Andrey Frolov & Valentina Harizanov - 2009 - Archive for Mathematical Logic 48 (1):7-13.
The computable Lipschitz degrees of computably enumerable sets are not dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.
Completely mitotic c.e. degrees and non-jump inversion.Evan J. Griffiths - 2005 - Annals of Pure and Applied Logic 132 (2-3):181-207.
Complementing cappable degrees in the difference hierarchy.Rod Downey, Angsheng Li & Guohua Wu - 2004 - Annals of Pure and Applied Logic 125 (1-3):101-118.
Upper bounds on ideals in the computably enumerable Turing degrees.George Barmpalias & André Nies - 2011 - Annals of Pure and Applied Logic 162 (6):465-473.
Lattice embeddings and array noncomputable degrees.Stephen M. Walk - 2004 - Mathematical Logic Quarterly 50 (3):219.

Analytics

Added to PP
2013-12-12

Downloads
26 (#841,117)

6 months
6 (#827,406)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Classical recursion theory: the theory of functions and sets of natural numbers.Piergiorgio Odifreddi - 1989 - New York, N.Y., USA: Sole distributors for the USA and Canada, Elsevier Science Pub. Co..
Computability theory and differential geometry.Robert I. Soare - 2004 - Bulletin of Symbolic Logic 10 (4):457-486.
The computable Lipschitz degrees of computably enumerable sets are not dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.

Add more references