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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,745

External links

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

Through your library

Similar books and articles

1-Generic splittings of computably enumerable degrees.Guohua Wu - 2006 - Annals of Pure and Applied Logic 138 (1):211-219.
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.
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
26 (#145,883)

6 months
9 (#1,260,759)

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