Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-26T00:12:03.241Z Has data issue: false hasContentIssue false
  • English
  • Français

Maximal contiguous degrees

Published online by Cambridge University Press:  12 March 2014

Peter Cholak ,
Rod Downey  and
Stephen Walk
Peter Cholak
Affiliation:
Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556-5683., USA, E-mail: [email protected], URL: http://www.nd.edu/~cholak
Rod Downey
Affiliation:
Department of Mathematics, Victoria University of Wellington, Wellington, New Zealand, E-mail: [email protected], URL: http://www.mcs.vuw.ac.nz/people/Rod-Downey.shtml
Stephen Walk
Affiliation:
Department of Mathematics, Ecc 139, 720 4th Avenue South, St. Cloud State University, St. Cloud, Minnesota 56301-4498, E-mail: [email protected], URL: http://tigger.stcloudstate.edu/~swalk
Get access Rights & Permissions [Opens in a new window]

Abstract

A computably enumerable (c.e.) degree is a maximal contiguous degree if it is contiguous and no c.e. degree strictly above it is contiguous. We show that there are infinitely many maximal contiguous degrees. Since the contiguous degrees are definable, the class of maximal contiguous degrees provides the first example of a definable infinite anti-chain in the c.e. degrees. In addition, we show that the class of maximal contiguous degrees forms an automorphism base for the c.e. degrees and therefore for the Turing degrees in general. Finally we note that the construction of a maximal contiguous degree can be modified to answer a question of Walk about the array computable degrees and a question of Li about isolated formulas.

Keywords

computably enumerablecontiguousautomorphism basearray computable
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 67 , Issue 1 , March 2002 , pp. 409 - 437
Copyright
Copyright © Association for Symbolic Logic 2002

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

Ambos-Spies, K. and Fejer, P. A. [TO appear]. Embedding of N5 and the contiguous degrees, Annals of Pure and Applied Logic, To appear.Google Scholar
Ambos-Spies, Klaus [1984], Contiguous r.e. degrees, Computation and proof theory (Aachen, 1983), Springer, Berlin, pp. 1–37.Google Scholar
Cooper, S. Barry [1996], Discontinuous phenomena and Turing definability, Algebra and analysis (Kazan, 1994), de Gruyter, Berlin, pp. 41–55.Google Scholar
Downey, R. G. [1987], Localization of a theorem of Ambos-Spies and the strong antisplitting property, Archiv für Mathematiscke Logik and Grundlagenforschung, vol. 26, no. 3-4. pp. 127–127.CrossRefGoogle Scholar
Downey, R. G. and Stob, M. [1986], Structural interactions of the recursively enumerable T- and w-degrees, Annals of Pure and Applied Logic, vol. 31, no. 2-3, pp. 205–236, Special issue: second Southeast Asian logic conference (Bangkok, 1984).CrossRefGoogle Scholar
Downey, Rodney G. [1990], Lattice nonembeddings and initial segments of the recursively enumerable degrees, Annals of Pure and Applied Logic, vol. 49, pp. 97–119.CrossRefGoogle Scholar
Downey, Rodney G. [1993], Array nonrecursive sets and lattice embeddings of the diamond, Illinois Journal of Mathematics, vol. 37, pp. 349–374.CrossRefGoogle Scholar
Downey, Rodney G., Jockusch, C. G., and Stob, Michael [1990], Array nonrecursive sets and multiple permitting arguments, Recursion theory week (Proceedings, Oberwolfach 1989) (Ambos-Spies, K., Müller, G. H., and Sacks, G. E., editors). Lecture Notes in Mathematics, no. 1432. Springer-Verlag, pp. 141–173.CrossRefGoogle Scholar
Downey, Rodney G. and Lempp, S. [1997], Contiguity and distributivity in the computably enumerable degrees, this Journal, vol. 62, pp. 1215–1240.Google Scholar
Downey, Rodney G., Lempp, Steffen, and Shore, Richard A. [1993], Highness and bounding minimal pairs, Mathematical Logic Quarterly, vol. 39, no. 4, pp. 475–491.CrossRefGoogle Scholar
Downey, Rodney G. and Shore, R. A. [1996], Lattice embeddings below a nonlowi recursively enumerable degree, Israel Journal of Mathematics, vol. 94, pp. 221–246.CrossRefGoogle Scholar
Downey, Rodney G. and Stob, Michael [1993], Splitting theorems in recursion theory, Annals of Pure and Applied Logic, vol. 65, pp. 1–106.CrossRefGoogle Scholar
Ladner, R. E. and Sasso, L. P. [1975], The weak truth table degrees of recursively enumerable sets, Annals of Mathematical Logic, vol. 8, pp. 429–448.CrossRefGoogle Scholar
Lempp, Steffen and Nies, André [1995], The undecidability of the Π4-theory for the r.e. wit and Turing degrees, this Journal, vol. 60, no. 4, pp. 1118–1136.Google Scholar
Lempp, Steffen, Nies, André, and Slaman, Theodore A. [1998], The Π3-theory of the computably enumerable Turing degrees is undecidable, Transactions of the American Mathematical Society, vol. 350, no. 7, pp. 2719–2736.CrossRefGoogle Scholar
Nies, André [2000], Definability in the c.e. degrees: questions and results, Computability theory and its applications (Boulder, CO, 1999) (Cholak, Peter, Lempp, Steffen, Lerman, Manny, and Shore, Richard, editors). American Mathematical Society, Providence, RI, pp. 207–213.CrossRefGoogle Scholar
Nies, André, Shore, Richard A., and Slaman, Theodore A. [1998], Interpretability and definability in the recursively enumerable degrees, Proceedings of the London Mathematical Society. Third Series, vol. 77, no. 2, pp. 241–291.Google Scholar
Odifreddi, Piergiorgio [1989], Classical recursion theory, North-Holland Publishing Co., Amsterdam, The theory of functions and sets of natural numbers, With a foreword by G. E. Sacks.Google Scholar
Odifreddi, Piergiorgio [1999], Classical recursion theory: Volume II, Elsevier, Amsterdam.Google Scholar
Shore, Richard A. [2000], Natural definability in degree structures, Computability theory and its applications (Boulder, CO, 1999) (Cholak, Peter, Lempp, Steffen, Lerman, Manny, and Shore, Richard, editors), American Mathematical Society, Providence, RI, pp. 255–271.CrossRefGoogle Scholar
Slaman, Theodore [1993], Open questions in recursion theory, Continuely updated since 1993, http://math.berkeley.edu/~slaman.Google Scholar
Slaman, Theodore A. and Woodin, W. Hugh [To appear], Defining the double jump, To appear.Google Scholar
Soare, R. I. [1987], Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Omega Series, Springer-Verlag, New York.CrossRefGoogle Scholar
Stob, Michael [1983], Wtt-degrees and t-degrees of r.e. sets, this Journal, vol. 48, pp. 921–930.Google Scholar
Walk, Stephen M. [1999], Toward the definability of the array noncomputable degrees, Ph.D. thesis, University of Notre Dame.Google Scholar