×

On effectively closed sets of effective strong measure zero. (English) Zbl 1351.03033

Summary: The strong measure zero sets of reals have been widely studied in the context of set theory of the real line. The notion of strong measure zero is straightforwardly effectivized. A set of reals is said to be of effective strong measure zero if for any computable sequence \(\{\varepsilon_n\}_{n\in\mathbb N}\) of positive rationals, a sequence of intervals \(I_n\) of diameter \(\varepsilon_n\) covers the set. We observe that a set is of effective strong measure zero if and only if it is of measure zero with respect to any outer measure constructed by Monroe’s Method from a computable atomless outer premeasure defined on all open balls. This measure-theoretic restatement permits many characterizations of strong measure zero in terms of semimeasures as well as martingales. We show that for closed subsets of Cantor space, effective strong nullness is equivalent to another well-studied notion called diminutiveness, the property of not having a computably perfect subset. Further, we prove that if \(P\) is a nonempty effective strong measure zero \(\Pi_1^0\) set consisting only of noncomputable elements, then some Martin-Löf random reals compute no element in \(P\), and \(P\) has an element that computes no autocomplex real. Finally, we construct two different special \(\Pi_1^0\) sets, one of which is not of effective strong measure zero, but consists only of infinitely-often K-trivial reals, and the other is perfect and of effective strong measure zero, but contains no anti-complex reals.

MSC:

03D32 Algorithmic randomness and dimension
03D30 Other degrees and reducibilities in computability and recursion theory
03D80 Applications of computability and recursion theory
03E15 Descriptive set theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barmpalias, George; Greenberg, Noam; Montalbán, Antonio; Slaman, Theodore A., \(K\)-trivials are never continuously random, (Proceedings of the 11th Asian Logic Conference (2011), World Scientific), 51-58 · Zbl 1296.03022
[2] Barmpalias, George; Vlek, C. S., Kolmogorov complexity of initial segments of sequences and arithmetical definability, Theoret. Comput. Sci., 412, 41, 5656-5667 (2011) · Zbl 1235.68087
[3] Besicovitch, A. S., Concentrated and rarified sets of points, Acta Math., 62, 289-300 (1933) · Zbl 0009.10504
[4] Bienvenu, Laurent; Porter, Christopher, Strong reductions in effective randomness, Theoret. Comput. Sci., 459, 9, 55-68 (2012) · Zbl 1283.68170
[5] Binns, Stephen, Small \(\Pi_1^0\) classes, Arch. Math. Logic, 45, 4, 393-410 (2006) · Zbl 1147.03024
[6] Binns, Stephen, Hyperimmunity in \(2^N\), Notre Dame J. Form. Log., 48, 2, 293-316 (2007) · Zbl 1139.03029
[7] Binns, Stephen, \( \Pi_1^0\) classes with complex elements, J. Symbolic Logic, 73, 4, 1341-1353 (2008) · Zbl 1155.03032
[8] Binns, Stephen; Kjos-Hanssen, Bjørn, Finding paths through narrow and wide trees, J. Symbolic Logic, 74, 1, 349-360 (2009) · Zbl 1161.03035
[9] Bukovský, Lev, The Structure of the Real Line (2011), Birkhäuser, 554 pages · Zbl 1219.26002
[10] Cenzer, Douglas; Kihara, Takayuki; Weber, Rebecca; Wu, Guohua, Immunity and non-cupping for closed sets, Tbil. Math. J., 2, 77-94 (2009) · Zbl 1208.03047
[11] Demuth, Osvald, A notion of semigenericity, Comment. Math. Univ. Carolin., 28, 71-84 (1987) · Zbl 0645.03040
[12] Demuth, Osvald; Kučera, Antonín, Remarks on 1-genericity, semigenericity and related concepts, Comment. Math. Univ. Carolin., 28, 85-94 (1987) · Zbl 0655.03029
[13] Downey, Rod; Griffiths, Evan J.; LaForte, Geoffrey, On Schnorr and computable randomness, martingales, and machines, MLQ Math. Log. Q., 50, 6, 613-627 (2004) · Zbl 1062.68064
[14] Downey, Rodney G.; Hirschfeldt, Denis R., Algorithmic Randomness and Complexity. Theory and Applications of Computability (2010), Springer, 883 pages · Zbl 1221.68005
[16] Franklin, Johanna N. Y., Schnorr triviality and genericity, J. Symbolic Logic, 75, 1, 191-207 (2010) · Zbl 1184.03040
[17] Franklin, Johanna N. Y.; Stephan, Frank, Schnorr trivial sets and truth-table reducibility, J. Symbolic Logic, 75, 2, 501-521 (2010) · Zbl 1193.03073
[18] Giusto, Mariagnese; Simpson, Stephen G., Located sets and reverse mathematics, J. Symbolic Logic, 65, 3, 1451-1480 (2000) · Zbl 0967.03051
[19] Hertling, Peter, Surjective functions on computably growing Cantor sets, J. UCS, 3, 11, 1226-1240 (1997) · Zbl 0960.68072
[20] Higuchi, Kojiro; Hudelson, Phil; Simpson, Stephen G.; Yokoyama, Keita, Propagation of partial randomness, Ann. Pure Appl. Logic, 165, 2, 742-758 (2014) · Zbl 1329.03078
[21] Higuchi, Kojiro; Kihara, Takayuki, Effective strong nullness and effectively closed sets, (Dawar, A.; Cooper, S. B.; Löwe, B., How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe. How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, Lecture Notes in Comput. Sci., vol. 7318 (2012), Springer), 303-312 · Zbl 1358.03064
[22] Hölzl, Rupert; Merkle, Wolfgang, Traceable sets, (Calude, Cristian S.; Sassone, Vladimiro, IFIP TCS. IFIP TCS, IFIP Adv. Inf. Commun. Technol., vol. 323 (2010), Springer), 301-315 · Zbl 1198.68155
[23] Kanovich, M. I., On the decision complexity of algorithms, Soviet Math. Dokl., 10, 700-701 (1969) · Zbl 0272.02054
[24] Kanovich, M. I., On the decision and enumeration complexity of predicates, Soviet Math. Dokl., 11, 17-20 (1970) · Zbl 0255.02049
[26] Kjos-Hanssen, Bjørn; Merkle, Wolfgang; Stephan, Frank, Kolmogorov complexity and the recursion theorem, Trans. Amer. Math. Soc., 363, 10, 5465-5480 (2011) · Zbl 1236.03032
[27] Laver, Richard, On the consistency of Borel’s conjecture, Acta Math., 137, 1, 151-169 (1976) · Zbl 0357.28003
[28] Levin, L. A., On the notion of a random sequence, Soviet Math. Dokl., 14, 1413-1416 (1973) · Zbl 0312.94006
[29] Miller, Joseph S., Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Adv. Math., 226, 1, 373-384 (2011) · Zbl 1214.03030
[30] Nies, Andre, Computability and Randomness. Oxford Logic Guides (2009), Oxford University Press, 433 pages · Zbl 1169.03034
[31] Reimann, Jan, Computability and fractal dimension (2004), Universität Heidelberg, Ph.D. thesis · Zbl 1080.03031
[33] Rogers, Claude Ambrose, Hausdorff Measures (1998), Cambridge University Press
[34] Simpson, Stephen G., Mass problems and randomness, Bull. Symbolic Logic, 11, 1, 1-27 (2005) · Zbl 1090.03015
[35] Simpson, Stephen G., Mass problems associated with effectively closed sets, Tohoku Math. J., 63, 4, 489-517 (2011) · Zbl 1246.03064
[36] Soare, Robert I., Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic (1987), Springer: Springer Heidelberg, XVIII+437 pages · Zbl 0623.03042
[37] van Lambalgen, Michiel, Von Mises’ definition of random sequences reconsidered, J. Symbolic Logic, 52, 3, 725-755 (1987) · Zbl 0628.60001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.