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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,202

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

Elementary Differences between the (2p)-C. E. and the (2p + 1)-C. E. Enumeration Degrees.I. Sh Kalimullin - 2007 - Journal of Symbolic Logic 72 (1):277 - 284.
The theory of the recursively enumerable weak truth-table degrees is undecidable.Klaus Ambos-Spies, André Nies & Richard A. Shore - 1992 - Journal of Symbolic Logic 57 (3):864-874.
Bounding cappable degrees.Angsheng Li - 2000 - Archive for Mathematical Logic 39 (5):311-352.
Bounding minimal degrees by computably enumerable degrees.Angsheng Li & Dongping Yang - 1998 - Journal of Symbolic Logic 63 (4):1319-1347.
Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees.Klaus Ambos-Spies & Ding Decheng - 1994 - Mathematical Logic Quarterly 40 (3):287-317.
On a problem of Cooper and Epstein.Shamil Ishmukhametov - 2003 - Journal of Symbolic Logic 68 (1):52-64.
Non‐isolated quasi‐degrees.Ilnur I. Batyrshin - 2009 - Mathematical Logic Quarterly 55 (6):587-597.
A superhigh diamond in the c.e. tt-degrees.Douglas Cenzer, Johanna Ny Franklin, Jiang Liu & Guohua Wu - 2011 - Archive for Mathematical Logic 50 (1-2):33-44.
An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
The computably enumerable degrees are locally non-cappable.Matthew B. Giorgi - 2004 - Archive for Mathematical Logic 43 (1):121-139.
On the definable ideal generated by the plus cupping c.e. degrees.Wei Wang & Decheng Ding - 2007 - Archive for Mathematical Logic 46 (3-4):321-346.
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.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
Maximal contiguous degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
The Isolated D. R. E. Degrees are Dense in the R. E. Degrees.Geoffrey Laforte - 1996 - Mathematical Logic Quarterly 42 (1):83-103.

Analytics

Added to PP
2013-12-12

Downloads
16 (#855,572)

6 months
5 (#544,079)

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.

View all 6 references / Add more references