Degrees of d. c. e. reals

Mathematical Logic Quarterly 50 (45):345-350 (2004)

A real α is called a c. e. real if it is the halting probability of a prefix free Turing machine. Equivalently, α is c. e. if it is left computable in the sense that L = {q ∈ ℚ : q ≤ α} is a computably enumerable set. The natural field formed by the c. e. reals turns out to be the field formed by the collection of the d. c. e. reals, which are of the form α—β, where α and β are c. e. reals. While c. e. reals can only be found in the c. e. degrees, Zheng has proven that there are Δ02 degrees that are not even n-c. e. for any n and yet contain d. c. e. reals, where a degree is n-c. e. if it contains an n-c. e. set. In this paper we will prove that every ω-c. e. degree contains a d. c. e. real, but there are ω + 1-c. e. degrees and, hence Δ02 degrees, containing no d. c. e. real
Keywords Turing degrees  Ershov hierarchy  Computably enumerable reals
Categories (categorize this paper)
DOI 10.1002/malq.200310103
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 39,711
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.
Schnorr Trivial Reals: A Construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
Regular Reals.Guohua Wu - 2005 - Mathematical Logic Quarterly 51 (2):111-119.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
Recursive Approximability of Real Numbers.Xizhong Zheng - 2002 - Mathematical Logic Quarterly 48 (S1):131-156.
The Kolmogorov Complexity of Random Reals.Liang Yu, Decheng Ding & Rodney Downey - 2004 - Annals of Pure and Applied Logic 129 (1-3):163-180.
Computably Enumerable Reals and Uniformly Presentable Ideals.S. A. Terwijn & R. Downey - 2002 - Mathematical Logic Quarterly 48 (S1):29-40.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Complexity of Reals in Inner Models of Set Theory.Boban Velickovic & W. Hugh Woodin - 1998 - Annals of Pure and Applied Logic 92 (3):283-295.
Lowness for Kurtz Randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Infima of D.R.E. Degrees.Jiang Liu, Shenling Wang & Guohua Wu - 2010 - Archive for Mathematical Logic 49 (1):35-49.
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.
Bi-Isolation in the D.C.E. Degrees.Guohua Wu - 2004 - Journal of Symbolic Logic 69 (2):409 - 420.
Cohen Reals From Small Forcings.Janusz Pawlikowski - 2001 - Journal of Symbolic Logic 66 (1):318-324.


Added to PP index

Total views
24 ( #320,847 of 2,328,397 )

Recent downloads (6 months)
3 ( #548,982 of 2,328,397 )

How can I increase my downloads?


My notes

Sign in to use this feature