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

Almost everywhere domination

Published online by Cambridge University Press:  12 March 2014

Natasha L. Dobrinen  and
Stephen G. Simpson
Natasha L. Dobrinen
Affiliation:
Department of Mathematics, Pennsylvania State University, 413 McAllister Bld, University Park, State College, PA 16802, USA, E-mail: [email protected], URL: http://www.math.psu.edu/dobrinen/
Stephen G. Simpson
Affiliation:
Department of Mathematics, Pennsylvania State University, 413 McAllister Bld, University Park, State College, PA 16802, USA, E-mail: [email protected], URL: http://www.math.psu.edu/simpson/
Get access Rights & Permissions [Opens in a new window]

Abstract.

A Turing degree a is said to be almost everywhere dominating if, for almost all X ∈ 2ω with respect to the “fair coin” probability measure on 2ω, and for all g: ω → ω Turing reducible to X, there exists f: ω → ω of Turing degree a which dominates g. We study the problem of characterizing the almost everywhere dominating Turing degrees and other, similarly defined classes of Turing degrees. We relate this problem to some questions in the reverse mathematics of measure theory.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 69 , Issue 3 , September 2004 , pp. 914 - 922
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]Brown, Douglas K., Giusto, Mariagnese, and Simpson, Stephen G., Vitali's theorem and WWKL, Archive for Mathematical Logic, vol. 41 (2002), pp. 191–206.CrossRefGoogle Scholar
[2]Halmos, Paul R., Measure theory, Van Nostrand, 1950.CrossRefGoogle Scholar
[3]Hinman, Peter G., Recursion-theoretic hierarchies, Perspectives in Mathematical Logic, Springer-Verlag, 1978.CrossRefGoogle Scholar
[4]Kautz, Steven M., Degrees of random sets, Ph.D. thesis, Cornell University, 1991.Google Scholar
[5]Kurtz, Stuart A., Randomness and genericity in the degrees of unsolvability, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1981.Google Scholar
[6]Martin, Donald A., Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift för Mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 295–310.CrossRefGoogle Scholar
[7]Martin, Donald A., Measure, category, and degrees of unsolvability, unpublished, typewritten, 16 pages, 1967.Google Scholar
[8]Sacks, Gerald E., Measure-theoretic uniformity in recursion theory and set theory, Transactions of the American Mathematical Society, vol. 142 (1969), pp. 381–420.CrossRefGoogle Scholar
[9]Sieg, W. (editor), Logic and computation, Contemporary Mathematics, American Mathematical Society, 1990.CrossRefGoogle Scholar
[10]Simpson, S. G. (editor), Reverse mathematics 2001, Lecture Notes in Logic, Association for Symbolic Logic, 2004, to appear.Google Scholar
[11]Simpson, Stephen G., sets and models of WKL0, in [10], preprint, 04 2000, 29 pages, to appear.Google Scholar
[12]Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, 1999.CrossRefGoogle Scholar
[13]Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, 1987.CrossRefGoogle Scholar
[14]Yu, Xiaokang, Measure theory in weak subsystems of second order arithmetic, Ph.D. thesis, Pennsylvania State University, 1987.Google Scholar
[15]Yu, Xiaokang, Radon-Nikodym theorem is equivalent to arithmetical comprehension, in [9], 1990, pp. 289–297.CrossRefGoogle Scholar
[16]Yu, Xiaokang, Riesz representation theorem, Borel measures, and subsystems of second order arithmetic, Annals of Pure and Applied Logic, vol. 59 (1993), pp. 65–78.CrossRefGoogle Scholar
[17]Yu, Xiaokang, Lebesgue convergence theorems and reverse mathematics, Mathematical Logic Quarterly, vol. 40 (1994), pp. 1–13.CrossRefGoogle Scholar
[18]Yu, Xiaokang, A study of singular points and supports of measures in reverse mathematics, Annals of Pure and Applied Logic, vol. 79 (1996), pp. 211–219.CrossRefGoogle Scholar
[19]Yu, Xiaokang and Simpson, Stephen G., Measure theory and weak König's lemma, Archive for Mathematical Logic, vol. 30 (1990), pp. 171–180.CrossRefGoogle Scholar