Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-16T23:40:47.709Z Has data issue: false hasContentIssue false
  • English
  • Français

NON-SPLITTINGS OF SPEEDABLE SETS

Published online by Cambridge University Press:  22 April 2015

ELLEN S. CHIH
ELLEN S. CHIH*
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CALIFORNIA BERKELEY, 737 EVANS HALL #3840 BERKELEY, CA 94720-3840, USAE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We construct a speedable set that cannot be split into speedable sets. This solves a question of Bäuerle and Remmel.

Keywords

splittingsspeedable sets
Type
Articles
Information
The Journal of Symbolic Logic , Volume 80 , Issue 2 , June 2015 , pp. 609 - 635
Copyright
Copyright © The Association for Symbolic Logic 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Bäuerle, Frank A. and Remmel, Jeffrey B., On speedable and levelable vector spaces. Annals of Pure and Applied Logic, vol. 67 (1994), no. 1–3, pp. 61–112. A selection of papers presented at the symposium “Logic at Tver ’92” (Tver', 1992).Google Scholar
Bennison, Victor L. and Soare, Robert I., Some lowness properties and computational complexity sequences. Theoretical Computer Science, vol. 6 (1978), no. 3, pp. 233–254.Google Scholar
Blum, M. and Marques, I., On complexity properties of recursively enumerable sets, this Journal, vol. 38 (1973), pp. 579–593.Google Scholar
Blum, Manuel, A machine-independent theory of the complexity of recursive functions. Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 322–336.Google Scholar
Barry Cooper, S. and Goncharov, Sergey S. (editors), Computability and models, The University Series in Mathematics, Kluwer Academic/Plenum Publishers, New York, 2003.Google Scholar
Downey, Rod and Stob, Michael, Splitting theorems in recursion theory. Annals of Pure and Applied Logic, vol. 65 (1993), no. 1, p. 106.Google Scholar
Friedberg, Richard M., Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, this Journal, vol. 23 (1958), pp. 309–316.Google Scholar
Jahn, Michael A., Implicit measurements of dynamic complexity properties and splittings of speedable sets, this Journal, vol. 64 (1999), no. 3, pp. 1037–1064.Google Scholar
Lachlan, Alistair H., A recursively enumerable degree which will not split over all lesser ones. Annals of Mathematical Logic, vol. 9 (1976), no. 4, pp. 307–365.Google Scholar
Maass, Wolfgang, Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets. Transactions of the American Mathematical Society, vol. 279 (1983), no. 1, pp. 311–336.Google Scholar
Omanadze, Roland Sh., Splittings of effectively speedable sets and effectively levelable sets, this Journal, vol. 69 (2004), no. 1, pp. 143–158.Google Scholar
Sacks, Gerald E., On the degrees less than 0'. Annals of Mathematics (2), vol. 77 (1963), pp. 211–231.Google Scholar
Soare, Robert I., Computational complexity, speedable and levelable sets, this Journal, vol. 42 (1977), no. 4, pp. 545–563.Google Scholar
Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987.Google Scholar