Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-28T01:12:32.210Z Has data issue: false hasContentIssue false
  • English
  • Français

Comparing DNR and WWKL

Published online by Cambridge University Press:  12 March 2014

Klaus Ambos-Spies ,
Bjørn Kjos-Hanssen ,
Steffen Lempp  and
Theodore A. Slaman
Klaus Ambos-Spies
Affiliation:
Mathematisches Institut, Universität Heidelberg, D-69120 Heidelberg, Germany, E-mail: [email protected]
Bjørn Kjos-Hanssen
Affiliation:
Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269-3009, USA, E-mail: [email protected]
Steffen Lempp
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388, USA, E-mail: [email protected]
Theodore A. Slaman
Affiliation:
Department of Mathematics, The University of California, Berkeley, California 94720-3840, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract.

In Reverse Mathematics, the axiom system DNR. asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0 (weak weak König's Lemma).

Keywords

reverse mathematicsdiagonally non-recursive functionsTuring degrees
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 69 , Issue 4 , December 2004 , pp. 1089 - 1104
Copyright
Copyright © Association for Symbolic Logic 2004

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, Klaus and Kučera, Antonín, Randomness in computability theory, Computability theory and its applications (Boulder, CO, 1999), Contemporary Mathematics, vol. 257, American Mathematical Society, Providence, RI, 2000, pp. 1–14.Google Scholar
[2]Brown, Douglas K., Giusto, Mariagnese, and Simpson, Stephen G., Vitali's theorem and WWKL, Archive for Mathematical Logic, vol. 41 (2002), no. 2, pp. 191–206.CrossRefGoogle Scholar
[3]Friedman, Harvey, Some systems of second order arithmetic and their use, Proceedings of the International Congress of Mathematicians (Vancouver, B. C, 1974), Vol. 1, Canadian Mathematical Congress, Montreal, Quebec, 1975, pp. 235–242.Google Scholar
[4]Giusto, Mariagnese and Simpson, Stephen G., Located sets and reverse mathematics, this Journal, vol. 65 (2000), no. 3, pp. 1451–1480.Google Scholar
[5]Jockusch, Carl G. Jr., Degrees of functions with no fixed points, Logic, methodology and philosophy of science, VIII (Moscow, 1987), Studies in Logic and the Foundations of Mathematics, vol. 126, North-Holland, Amsterdam, 1989, pp. 191–201.Google Scholar
[6]Kučera, Antonín, Measure, -classes and complete extensions of PA, Recursion theory week (Oberwolfach, 1984) (Ebbinghaus, H.D., Müller, G.H., and Sacks, G.E., editors). Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259.Google Scholar
[7]Kumabe, Masahiro, A fixed-point free minimal degree, 51 pages, unpublished, 1996.Google Scholar
[8]Martin-Löf, Per, Notes on constructive mathematics, Almqvist & Wiksell, Stockholm, 1970.Google Scholar
[9]Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999.CrossRefGoogle Scholar
[10]Yu, Xiaokang and Simpson, Stephen G., Measure theory and weak Konig's lemma, Archive for Mathematical Logic, vol. 30 (1990), no. 3, pp. 171–180.CrossRefGoogle Scholar