No CrossRef data available.
Article contents
Strengthening prompt simplicity
Published online by Cambridge University Press: 12 March 2014
Abstract
We introduce a natural strengthening of prompt simplicity which we call strong promptness, and study its relationship with existing lowness classes. This notion provides a ≤wtt version of superlow cuppability. We show that every strongly prompt c.e. set is superlow cuppable. Unfortunately, strong promptness is not a Turing degree notion, and so cannot characterize the sets which are superlow cuppable. However, it is a wtt-degree notion, and we show that it characterizes the degrees which satisfy a wtt-degree notion very close to the definition of superlow cuppability.
Further, we study the strongly prompt c.e. sets in the context of other notions related promptness, superlowness, and cupping. In particular, we show that every benign cost function has a strongly prompt set which obeys it, providing an analogue to the known result that every cost function with the limit condition has a prompt set which obeys it. We also study the effect that lowness properties have on the behaviour of a set under the join operator. In particular we construct an array noncomputable c.e. set whose join with every low c.e. set is low.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 2011
References
REFERENCES
[1]Ambos-Spies, K., Jockusch, C., Shore, R., and Soare, R., An algebraic decomposition of recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Transactions of the American Mathematical Society, vol. 281 (1984), pp. 109–128.CrossRefGoogle Scholar
[2]Bickford, M. and Mills, C., Lowness properties of r.e. sets, manuscript, 1982, University of Wisconsin, Madison.Google Scholar
[3]Cholak, P., Downey, R., and Greenberg, N., Strong jump-traceability I: The computably enumerable case, Advances in Mathematics, vol. 217 (2008), no. 5, pp. 2045–2074.CrossRefGoogle Scholar
[4]Cholak, P., Groszek, M., and Slaman, T., An almost deep degree, this Journal, vol. 66 (2001), no. 2, pp. 881–901.Google Scholar
[5]Diamondstone, D., Promptness does not imply superlow cuppability, this Journal, vol. 74 (2009), no. 4, pp. 1264–1272.Google Scholar
[6]Downey, R., Greenberg, N., and Weber, R., Totally ω computably enumerable degrees T. Bounding critical triples, Journal of Mathematical Logic, vol. 7 (2007), no. 2, pp. 145–171.CrossRefGoogle Scholar
[7]Downey, R., Hirschfeldt, D., Nies, A., and Stephan, F., Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences, World Scientific, Singapore, 2003, pp. 103–131.Google Scholar
[8]Downey, Rod, Jockusch, Carl G. Jr., and Stob, Michael, Array nonrecursive sets andgenericity, Computability, enumerability, unsolvability: Directions in recursion theory, London Mathematical Society Lecture Notes Series, vol. 224, Cambridge University Press, 1996, pp. 93–104.CrossRefGoogle Scholar
[9]Figueira, S., Nies, A., and Stephan, F., Lowness properties and approximations of the jump, Proceedings of the twelfth Workshop on Logic, Language, Information and Computation (WoLLIC 2005), Electronic Lecture Notes in Theoretical Computer Science, vol. 143, 2006, pp. 45–57.Google Scholar
[10]Greenberg, N. and Nies, A., Benign cost functions and lowness properties, to appear.Google Scholar
[11]Maass, W., Characterization of the recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets, Transactions of the American Mathematical Society, vol. 279 (1983), pp. 311–336.CrossRefGoogle Scholar
[12]Ng, K. M., Computability, traceability and beyond, Ph.D. Dissertation, Victoria University of Wellington, 2009.Google Scholar
[13]Ng, K. M., Beyond strong jump traceablility, Proceedings of the London Mathematical Society, (to appear).Google Scholar
[14]Nies, A., Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), pp. 274–305.CrossRefGoogle Scholar