Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-24T05:24:03.025Z Has data issue: false hasContentIssue false
  • English
  • Français

Uniform almost everywhere domination

Published online by Cambridge University Press:  12 March 2014

Peter Cholak ,
Noam Greenberg  and
Joseph S. Miller
Peter Cholak
Affiliation:
Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556-5683, USA.E-mail:[email protected]
Noam Greenberg
Affiliation:
Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556-5683, USA.E-mail:[email protected]
Joseph S. Miller
Affiliation:
Department of Mathematics, University of Connecticut, U-3009, 196 Auditorium Road, Storrs, CT 06269, USA.E-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We explore the interaction between Lebesgue measure and dominating functions. We show, via both a priority construction and a forcing construction, that there is a function of incomplete degree that dominates almost all degrees. This answers a question of Dobrinen and Simpson, who showed that such functions are related to the proof-theoretic strength of the regularity of Lebesgue measure for Gδ sets. Our constructions essentially settle the reverse mathematical classification of this principle.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 71 , Issue 3 , September 2006 , pp. 1057 - 1072
Copyright
Copyright © Association for Symbolic Logic 2006

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

[I]Ackermann, W., Zum Hilbertschen Aufbau der reellen Zahlen., Mathematische Annalen, vol. 99 (1928), pp. 118–133.CrossRefGoogle Scholar
[2]Binns, Stephen, Kjos-Hanssen, Bjο, Lerman, Manuel, and Solomon, Reed, On a conjecture of Dobrinen and Simpson concerning almost everywhere domination, 2005.CrossRefGoogle Scholar
[3]Dobrinen, Natasha L. and Simpson, Stephen G., Almost everywhere domination, this Journal, vol. 69 (2004), no. 3, pp. 914–922.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]Hausdorff, Felix, Die Graduierung nach dem Endverlauf, Abhandlungen der Königlichen sächsischen Gesellschaft der Wissenschaften (Mathematisch-physische Klasse), vol. 31 (1909), pp. 296–334.Google Scholar
[6]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
[7]Jockusch, Carl G. Jr. and Shore, Richard A., Pseudojump operators. I. The r.e. case, Transactions of the American Mathematical Society, vol. 275 (1983), no. 2, pp. 599–609.Google Scholar
[8]Jockusch, Carl G. Jr. and Soare, Robert I., Degrees of members of classes, Pacific Journal of Mathematics, vol. 40 (1972), pp. 605–616.CrossRefGoogle Scholar
[9]Jockusch, Carl G. Jr. and Soare, Robert I., classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[10]Kučera, Antonín, Measure, -classes and complete extensions of PA, Recursion theory week (Oberwolfach, 1984), Lecture Notes in Mathematics, vol. 1141, Springer, Berlin, 1985, pp. 245–259.CrossRefGoogle Scholar
[11]Kurtz, Stuart, Randomness and genericty in the degrees of unsolvability, Ph.D. thesis, University of Illinios at Urbana-Champaign, 1981.Google Scholar
[12]Martin, D. 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
[13]Nies, André, Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), pp. 274–305.CrossRefGoogle Scholar
[14]Posner, David B. and Robinson, Robert W., Degrees joining to 0', this Journal, vol. 46 (1981), no. 4, pp. 714–722.Google Scholar
[15]Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999.CrossRefGoogle Scholar
[16]Tennenbaum, S., Degree of unsolvability and the rate of growth of functions, Proceedings of the symposium on mathematical theory of automata (New York, 1962), Polytechnic Press of Polytechnic Institute of Brooklyn, Brooklyn, N.Y., 1963, pp. 71–73.Google Scholar
[17]Yates, C. E. M., Three theorems on the degrees of recursively enumerable sets, Duke Mathematical Journal, vol. 32 (1965), pp. 461–468.CrossRefGoogle Scholar
[18]Yu, Xiaokang and Simpson, Stephen G., Measure theory and weak König's lemma, Archive for Mathematical Logic, vol. 30 (1990), no. 3, pp. 171–180.CrossRefGoogle Scholar