The computable Lipschitz degrees of computably enumerable sets are not dense

Annals of Pure and Applied Logic 161 (12):1588-1602 (2010)
  Copy   BIBTEX


The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense [2]), however the problem for the computable Lipschitz degrees is more complex



    Upload a copy of this work     Papers currently archived: 74,594

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

The Computably Enumerable Degrees Are Locally Non-Cappable.Matthew B. Giorgi - 2004 - Archive for Mathematical Logic 43 (1):121-139.
An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
On a Problem of Cooper and Epstein.Shamil Ishmukhametov - 2003 - Journal of Symbolic Logic 68 (1):52-64.
Generalized Cohesiveness.Tamara Hummel & Carl G. Jockusch - 1999 - Journal of Symbolic Logic 64 (2):489-516.
Differences of Computably Enumerable Sets.A. Nies & S. Lempp - 2000 - Mathematical Logic Quarterly 46 (4):555-562.
Bounding Cappable Degrees.Angsheng Li - 2000 - Archive for Mathematical Logic 39 (5):311-352.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.
Bounding Minimal Degrees by Computably Enumerable Degrees.Angsheng Li & Dongping Yang - 1998 - Journal of Symbolic Logic 63 (4):1319-1347.


Added to PP

23 (#496,189)

6 months
1 (#418,924)

Historical graph of downloads
How can I increase my downloads?