Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-25T02:20:42.441Z Has data issue: false hasContentIssue false
  • English
  • Français

Mass Problems and Measure-Theoretic Regularity

Published online by Cambridge University Press:  15 January 2014

Stephen G. Simpson
Stephen G. Simpson*
Affiliation:
Department of Mathematics, Pennsylvania State University, State College, PA 16802, USAURL: http://www.math.psu.edu/simpson/
Get access Rights & Permissions [Opens in a new window]

Abstract

A well known fact is that every Lebesgue measurable set is regular, i.e., it includes an Fσ set of the same measure. We analyze this fact from a metamathematical or foundational standpoint. We study a family of Muchnik degrees corresponding to measuretheoretic regularity at all levels of the effective Borel hierarchy. We prove some new results concerning Nies's notion of LR-reducibility. We build some ω-models of RCA0 which are relevant for the reverse mathematics of measure-theoretic regularity.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 15 , Issue 4 , December 2009 , pp. 385 - 409
Copyright
Copyright © Association for Symbolic Logic 2009

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] Ash, Christopher J. and Knight, Julia, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, no. 144, North-Holland, 2000.Google Scholar
[2] Binns, Stephen, A splitting theorem for the Medvedev and Muchnik lattices, Mathematical Logic Quarterly, vol. 49 (2003), pp. 327–335.Google Scholar
[3] Binns, Stephen, Kjos-Hanssen, Bjørn, Lerman, Manuel, and Solomon, David Reed, On a question of Dobrinen and Simpson concerning almost everywhere domination, The Journal of Symbolic Logic, vol. 71 (2006), pp. 119–136.Google Scholar
[4] Binns, Stephen and Simpson, Stephen G., Embeddings into the Medvedev and Muchnik lattices of classes, Archive for Mathematical Logic, vol. 43 (2004), pp. 399–414.Google Scholar
[5] Brown, Douglas K., Giusto, Mariagnese, and Simpson, Stephen G., Vitali's theorem and WWKL, Archive for Mathematical Logic, vol. 41 (2002), pp. 191–206.Google Scholar
[6] Chatzidakis, Z., Koepke, P., and Pohlers, W. (editors), Logic Colloquium '02: Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic and the Colloquium Logicum, Münster, Germany, August 3–11, 2002, Lecture Notes in Logic, no. 27, Association for Symbolic Logic, 2006.Google Scholar
[7] Cholak, Peter, Greenberg, Noam, and Miller, Joseph S., Uniform almost everywhere domination, The Journal of Symbolic Logic, vol. 71 (2006), pp. 1057–1072.Google Scholar
[8] Chong, C.-T., Feng, Q., Slaman, T. A., Woodin, W. H., and Yang, Y. (editors), Computational prospects of infinity: Proceedings of the Logic Workshop at the Institute for Mathematical Sciences, June 20–August 15, 2005, Part II: Presented talks, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, no. 15, World Scientific, 2008.Google Scholar
[9] Cole, Joshua A. and Simpson, Stephen G., Mass problems and hyperarithmeticity, Journal of Mathematical Logic, vol. 7 (2008), pp. 125–143.Google Scholar
[10] Dobrinen, Natasha L. and Simpson, Stephen G., Almost everywhere domination, The Journal of Symbolic Logic, vol. 69 (2004), pp. 914–922.Google Scholar
[11] Downey, Rod G. and Hirschfeldt, Denis, Algorithmic randomness and complexity, 2010, in press.Google Scholar
[12] Feferman, S., Parsons, C., and Simpson, S. G. (editors), Kurt Gödel: Essays for his centennial, Association for Symbolic Logic, 2009, to appear.Google Scholar
[13] FOM e-mail list, http://www.cs.nyu.edu/mailman/listinfo/fom/, 09 1997 to the present.Google Scholar
[14] Gandy, Robin O., Kreisel, Georg, and Tait, William W., Set existence, Bulletin de l'Academie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques, vol. 8 (1960), pp. 577–582.Google Scholar
[15] Halmos, Paul R., Measure theory, Van Nostrand, 1950.Google Scholar
[16] Kautz, Steven M., Degrees of random sets, Ph.D. thesis, Cornell University, 1991.Google Scholar
[17] Kjos-Hanssen, Bjørn, Low-for-random reals and positive-measure domination, Proceedings of the American Mathematical Society, vol. 135 (2007), pp. 3703–3709.Google Scholar
[18] Kjos-Hanssen, Bjørn, Miller, Joseph S., and Solomon, David Reed, Lowness notions, measure and domination, preprint, 20 pages, in preparation, to appear, 05 2008.Google Scholar
[19] Kleene, Stephen C., Introduction to metamathematics, Van Nostrand, 1952.Google Scholar
[20] Kleene, Stephen C. and Post, Emil L., The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics, vol. 59 (1954), pp. 379–407.Google Scholar
[21] Kolmogoroff, A., Zur Deutung der intuitionistischen Logik, Mathematische Zeitschrift, vol. 35 (1932), pp. 58–65.Google Scholar
[22] Lerman, Manuel, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, 1983.Google Scholar
[23] Martin-Löf, Per, The definition of random sequences, Information and Control, vol. 9 (1966), pp. 602–619.Google Scholar
[24] Medvedev, Yuri T., Degrees of difficulty of mass problems, Doklady Akademii Nauk SSSR, n.s., vol. 104 (1955), pp. 501–504, in Russian.Google Scholar
[25] Muchnik, Albert A., On strong and weak reducibilities of algorithmic problems, Sibirskii Matematicheskii Zhurnal, vol. 4 (1963), pp. 1328–1341, in Russian.Google Scholar
[26] Nies, André, Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), pp. 274–305.Google Scholar
[27] Nies, André, Reals which compute little, In Chatzidakis, et al. [6], pp. 260–274.Google Scholar
[28] Nies, André, Computability and randomness, Oxford University Press, 2009.Google Scholar
[29] Odifreddi, Piergiorgio, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, no. 125, North-Holland, 1989.Google Scholar
[30] Odifreddi, Piergiorgio, Classical recursion theory, Volume 2, Studies in Logic and the Foundations of Mathematics, no. 143, North-Holland, 1999.Google Scholar
[31] Post, Emil L., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.Google Scholar
[32] Rogers, Hartley Jr., Theory of recursive functions and effective computability, McGraw-Hill, 1967.Google Scholar
[33] Sacks, Gerald E., Degrees of unsolvability, 2nd ed., Annals of Mathematics Studies, no. 55, Princeton University Press, 1966.Google Scholar
[34] Sacks, Gerald E., Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, 1990.Google Scholar
[35] Shoenfield, Joseph R., Mathematical logic, Addison-Wesley, 1967.Google Scholar
[36] Shoenfield, Joseph R., Degrees of unsolvability, North-Holland Mathematics Studies, vol. 2, North-Holland, 1971.Google Scholar
[37] Sieg, W. (editor), Logic and computation, Contemporary Mathematics, American Mathematical Society, 1990.Google Scholar
[38] Simpson, Stephen G., FOM: natural r.e. degrees; Pi01 classes, FOM e-mail list [13], 13 08 1999.Google Scholar
[39] Simpson, Stephen G., FOM: priority arguments; Kleene-r.e. degrees; Pi01 classes, FOM e-mail list [13], 16 08 1999.Google Scholar
[40] Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, 1999.Google Scholar
[41] Simpson, Stephen G., Mass problems and randomness, this Bulletin, vol. 11 (2005), pp. 1–27.Google Scholar
[42] Simpson, Stephen G., Almost everywhere domination and superhighness, Mathematical Logic Quarterly, vol. 53 (2007), pp. 462–482.Google Scholar
[43] Simpson, Stephen G., An extension of the recursively enumerable Turing degrees, Journal of the London Mathematical Society, vol. 75 (2007), pp. 287–297.Google Scholar
[44] Simpson, Stephen G., Mass problems and almost everywhere domination, Mathematical Logic Quarterly, vol. 53 (2007), pp. 483–492.Google Scholar
[45] Simpson, Stephen G., Mass problems and intuitionism, Notre Dame Journal of Formal Logic, vol. 49 (2008), pp. 127–136.Google Scholar
[46] Simpson, Stephen G., Some fundamental issues concerning degrees of unsolvability, In Chong, et al. [8], pp. 313–332.Google Scholar
[47] Simpson, Stephen G., The Gödel hierarchy and reverse mathematics, In Feferman, et al. [12], 23 pages, to appear.Google Scholar
[48] Simpson, Stephen G., Medvedev degrees of 2-dimensional subshifts of finite type, Ergodic Theory and Dynamical Systems, (2009), preprint, 8 pages, 1 05 2007, accepted for publication.Google Scholar
[49] Simpson, Stephen G., Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Association for Symbolic Logic and Cambridge University Press, 2009.Google Scholar
[50] Simpson, Stephen G., Computability, unsolvability, and randomness, 2010, in preparation.Google Scholar
[51] Simpson, Stephen G., Degrees of unsolvability, 2010, in preparation.Google Scholar
[52] Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, 1987.Google Scholar
[53] Stephan, Frank, Martin-Löf random and PA-complete sets, In Chatzidakis, et al. [6], pp. 341–347.Google Scholar
[54] Turing, Alan M., On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, vol. 42 (1936), pp. 230–265.Google Scholar
[55] Yu, Xiaokang, Measure theory in weak subsystems of second order arithmetic, Ph.D. thesis, Pennsylvania State University, 1987.Google Scholar
[56] Yu, Xiaokang, Radon-Nikodym theorem is equivalent to arithmetical comprehension, In Sieg, [37], pp. 289–297.Google Scholar
[57] 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.Google Scholar
[58] Yu, Xiaokang, Lebesgue convergence theorems and reverse mathematics, Mathematical Logic Quarterly, vol. 40 (1994), pp. 1–13.Google Scholar
[59] 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.Google Scholar
[60] Yu, Xiaokang and Simpson, Stephen G., Measure theory and weak König's lemma, Archive for Mathematical Logic, vol. 30 (1990), pp. 171–180.Google Scholar