Undecidability and 1-types in intervals of the computably enumerable degrees

, &
Annals of Pure and Applied Logic 106 (1-3):1-47 (2000)
  Copy   BIBTEX

Abstract

We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(99)00011-1

Links

PhilArchive



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

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 the recursively enumerable degrees.Klaus Ambos-Spies & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 63 (1):3-37.
An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent.Klaus Ambos-Spies, Philipp Bodewig, Yun Fan & Thorsten Kräling - 2013 - Annals of Pure and Applied Logic 164 (5):577-588.
Bounding cappable degrees.Angsheng Li - 2000 - Archive for Mathematical Logic 39 (5):311-352.
The computably enumerable degrees are locally non-cappable.Matthew B. Giorgi - 2004 - Archive for Mathematical Logic 43 (1):121-139.
Bounding minimal degrees by computably enumerable degrees.Angsheng Li & Dongping Yang - 1998 - Journal of Symbolic Logic 63 (4):1319-1347.
Every incomplete computably enumerable truth-table degree is branching.Peter A. Fejer & Richard A. Shore - 2001 - Archive for Mathematical Logic 40 (2):113-123.
On a problem of Cooper and Epstein.Shamil Ishmukhametov - 2003 - Journal of Symbolic Logic 68 (1):52-64.
Decomposition and infima in the computably enumerable degrees.Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore - 2003 - Journal of Symbolic Logic 68 (2):551-579.
On the filter of computably enumerable supersets of an r-maximal set.Steffen Lempp, André Nies & D. Reed Solomon - 2001 - Archive for Mathematical Logic 40 (6):415-423.
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.
The recursively enumerable degrees have infinitely many one-types.Klaus Ambos-Spies & Robert I. Soare - 1989 - Annals of Pure and Applied Logic 44 (1-2):1-23.
Embedding finite lattices into the ideals of computably enumerable Turing degrees.William C. Calhoun & Manuel Lerman - 2001 - Journal of Symbolic Logic 66 (4):1791-1802.
Relative enumerability and 1-genericity.Wei Wang - 2011 - Journal of Symbolic Logic 76 (3):897 - 913.
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.

Analytics

Added to PP
2014-01-16

Downloads
24 (#639,942)

6 months
8 (#342,364)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

The density of the nonbranching degrees.Peter A. Fejer - 1983 - Annals of Pure and Applied Logic 24 (2):113-130.
The density of infima in the recursively enumerable degrees.Theodore A. Slaman - 1991 - Annals of Pure and Applied Logic 52 (1-2):155-179.

Add more references