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

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,173

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.
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.
1-Generic splittings of computably enumerable degrees.Guohua Wu - 2006 - Annals of Pure and Applied Logic 138 (1):211-219.
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.
Model theory of the computably enumerable many-one degrees.A. Nies - 2000 - Logic Journal of the IGPL 8 (5):701-706.
On definable filters in computably enumerable degrees.Wei Wang & Decheng Ding - 2007 - Annals of Pure and Applied Logic 147 (1):71-83.
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.
A necessary and sufficient condition for embedding ranked finite partial lattices into the computably enumerable degrees.M. Lerman - 1998 - Annals of Pure and Applied Logic 94 (1-3):143-180.
Computably enumerable sets and quasi-reducibility.R. Downey, G. LaForte & A. Nies - 1998 - Annals of Pure and Applied Logic 95 (1-3):1-35.
Interpreting N in the computably enumerable weak truth table degrees.André Nies - 2001 - Annals of Pure and Applied Logic 107 (1-3):35-48.

Analytics

Added to PP
2014-01-16

Downloads
37 (#607,693)

6 months
11 (#338,628)

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