Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T21:52:49.715Z Has data issue: false hasContentIssue false
  • English
  • Français

Strengthening prompt simplicity

Published online by Cambridge University Press:  12 March 2014

David Diamondstone  and
Keng Meng Ng
David Diamondstone
Affiliation:
University of Chicago, 5734 S. University Avenue, Chicago, Illinois 60637, USA, E-mail: [email protected]
Keng Meng Ng
Affiliation:
University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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
The Journal of Symbolic Logic , Volume 76 , Issue 3 , September 2011 , pp. 946 - 972
Copyright
Copyright © Association for Symbolic Logic 2011

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

[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
[15]Nies, A., Computability and randomness, Oxford University Press, 2009.CrossRefGoogle Scholar