×

Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions. (English) Zbl 1315.03072

Summary: It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial \(\Pi_1^0\) subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty \(\Pi_1^0\) subsets of Cantor space, we show the existence of a finite-\(\Delta_2^0\)-piecewise degree containing infinitely many finite-\((\Pi_1^0)_2\)-piecewise degrees, and a finite-\((\Pi_2^0)_2\)-piecewise degree containing infinitely many finite-\(\Delta_2^0\)-piecewise degrees (where \((\Pi_n^0)_2\) denotes the difference of two \(\Pi_n^0\) sets), whereas the greatest degrees in these three “finite-\(\Gamma\)-piecewise” degree structures coincide. Moreover, as for nonempty \(\Pi_1^0\) subsets of Cantor space, we also show that every nonzero finite-\((\Pi_1^0)_2\)-piecewise degree includes infinitely many Medvedev (i.e., one-piecewise) degrees, every nonzero countable-\(\Delta_2^0\)-piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite-\((\Pi_2^0)_2\)-countable-\(\Delta_2^0\)-piecewise degree includes infinitely many countable-\(\Delta_2^0\)-piecewise degrees, and every nonzero Muchnik (i.e., countable-\(\Pi_2^0\)-piecewise) degree includes infinitely many finite-\((\Pi_2^0)_2\)-countable-\(\Delta_2^0\)-piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable-\(\Delta^2_0\)-piecewise degree of a nonempty \(\Pi_1^0\) subset of Cantor space have the strong anticupping properties. Finally, we obtain an elementary difference between the Medvedev (Muchnik) degree structure and the finite-\(\Gamma\)-piecewise degree structure of all subsets of Baire space by showing that none of the finite-\(\Gamma\)-piecewise structures is Brouwerian, where \(\Gamma\) is any of the Wadge classes mentioned above.
For Part I see [ibid. 165, No. 5, 1058–1114 (2014; Zbl 1315.03071)].

MSC:

03D30 Other degrees and reducibilities in computability and recursion theory
03E15 Descriptive set theory
26A21 Classification of real functions; Baire classification of sets and functions
68Q32 Computational learning theory

Citations:

Zbl 1315.03071
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alfeld, C. P., Non-branching degrees in the Medvedev lattice of \(\Pi_1^0\) classes, J. Symbolic Logic, 72, 1, 81-97 (2007) · Zbl 1122.03043
[2] Binns, S., A splitting theorem for the Medvedev and Muchnik lattices, Math. Log. Q., 49, 4, 327-335 (2003) · Zbl 1022.03021
[3] Binns, S.; Simpson, S. G., Embeddings into the Medvedev and Muchnik lattices of \(\Pi_1^0\) classes, Arch. Math. Logic, 43, 3, 399-414 (2004) · Zbl 1058.03041
[4] Blum, L.; Blum, M., Toward a mathematical theory of inductive inference, Inf. Control, 28, 2, 125-155 (1975) · Zbl 0375.02028
[5] Brattka, V., Effective Borel measurability and reducibility of functions, Math. Log. Q., 51, 1, 19-44 (2005) · Zbl 1059.03074
[6] Brattka, V.; de Brecht, M.; Pauly, A., Closed choice and a uniform low basis theorem, Ann. Pure Appl. Logic, 163, 8, 986-1008 (2012) · Zbl 1251.03082
[7] Brattka, V.; Gherardi, G., Effective choice and boundedness principles in computable analysis, Bull. Symbolic Logic, 17, 1, 73-117 (2011) · Zbl 1226.03062
[8] Brattka, V.; Gherardi, G., Weihrauch degrees, omniscience principles and weak computability, J. Symbolic Logic, 76, 1, 143-176 (2011) · Zbl 1222.03071
[9] Brattka, V.; Gherardi, G.; Marcone, A., The Bolzano-Weierstrass theorem is the jump of weak König’s lemma, Ann. Pure Appl. Logic, 163, 6, 623-655 (2012) · Zbl 1245.03097
[11] Case, J.; Ngo-Manguelle, S., Refinements of inductive inference by Popperian machines (1979), SUNY Buffalo, Dept. of Computer Science, Tech. Rep. 152 · Zbl 0819.68052
[12] Cenzer, D.; Kihara, T.; Weber, R.; Wu, G., Immunity and non-cupping for closed sets, Tbil. Math. J., 2, 77-94 (2009) · Zbl 1208.03047
[13] Cenzer, D. A.; Hinman, P. G., Density of the Medvedev lattice of \(\Pi_1^0\) classes, Arch. Math. Logic, 42, 6, 583-600 (2003) · Zbl 1037.03040
[14] Cenzer, D. A.; Hinman, P. G., Degrees of difficulty of generalized r.e. separating classes, Arch. Math. Logic, 46, 7-8, 629-647 (2008) · Zbl 1151.03020
[15] Cenzer, D. A.; Remmel, J. B., \( \Pi_1^0\) classes in mathematics, (Handbook of Recursive Mathematics, vol. 2. Handbook of Recursive Mathematics, vol. 2, Stud. Logic Found. Math. (1998), Elsevier), 623-821 · Zbl 0941.03044
[16] Cole, J. A.; Kihara, T., The ∀∃-theory of the effectively closed Medvedev degrees is decidable, Arch. Math. Logic, 49, 1, 1-16 (2010) · Zbl 1184.03038
[17] Cole, J. A.; Simpson, S. G., Mass problems and hyperarithmeticity, J. Math. Log., 7, 2, 125-143 (2007) · Zbl 1150.03013
[18] (Cooper, S. B.; Dawar, A.; Löwe, B., How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, Proceedings CiE 2012. How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, Proceedings CiE 2012, Cambridge, UK, June 18-23. How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, Proceedings CiE 2012. How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, Proceedings CiE 2012, Cambridge, UK, June 18-23, Lecture Notes in Computer Science, vol. 7318 (2012), Springer) · Zbl 1243.68017
[20] Downey, R. G.; Greenberg, N.; J., C. G.; Milans, K. G., Binary subtrees with few labeled paths, Combinatorica, 31, 3, 285-303 (2011) · Zbl 1265.05593
[21] Downey, R. G.; Hirschfeldt, D. R., Algorithmic Randomness and Complexity. Theory and Applications of Computability (2010), Springer, 883 pp · Zbl 1221.68005
[22] Duparc, J., Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank, J. Symbolic Logic, 66, 1, 56-86 (2001) · Zbl 0979.03039
[23] (Ershov, Y. L.; Goncharov, S. S.; Nerode, A.; Remmel, J. B.; Marek, V. W., Handbook of Recursive Mathematics, vol. 2: Recursive Algebra, Analysis and Combinatorics. Handbook of Recursive Mathematics, vol. 2: Recursive Algebra, Analysis and Combinatorics, Studies in Logic and the Foundations of Mathematics (1998), North Holland), 798 pp · Zbl 0905.03001
[24] Gold, E. M., Limiting recursion, J. Symbolic Logic, 30, 1, 28-48 (1965) · Zbl 0203.01201
[25] Greenberg, N.; Miller, J. S., Diagonally non-recursive functions and effective Hausdorff dimension, Bull. Lond. Math. Soc., 43, 4, 636-654 (2011) · Zbl 1225.03055
[26] Hemmerling, A., Hierarchies of function classes defined by the first-value operator, Theor. Inform. Appl., 42, 2, 253-270 (2008) · Zbl 1146.03032
[27] Hertling, P., Topological complexity with continuous operations, J. Complexity, 12, 4, 315-338 (1996) · Zbl 0862.68060
[28] Higuchi, K., Effectively closed mass problems and intuitionism, Ann. Pure Appl. Logic, 163, 6, 693-697 (2012) · Zbl 1241.03052
[30] Hinman, P. G., A survey of Mucnik and Medvedev degrees, Bull. Symbolic Logic, 18, 2, 161-229 (2012) · Zbl 1248.03063
[31] Jain, S.; Osherson, D. N.; Royer, J. S.; Sharma, A., Systems That Learn: An Introduction to Learning Theory (1999), MIT Press, 329 pp
[32] Jayne, J. E.; Rogers, C. A., First level Borel functions and isomorphism, J. Math. Pures Appl., 61, 177-205 (1982) · Zbl 0514.54026
[33] Jockusch, C. G., Degrees of functions with no fixed points, (Logic, Methodology and Philosophy of Science, VIII. Logic, Methodology and Philosophy of Science, VIII, Moscow, 1987. Logic, Methodology and Philosophy of Science, VIII. Logic, Methodology and Philosophy of Science, VIII, Moscow, 1987, Stud. Logic Found. Math. (1989), North-Holland: North-Holland Amsterdam), 191-201
[34] Jockusch, C. G.; Soare, R. I., Degrees of members of \(\Pi_1^0\) classes, Pacific J. Math., 40, 3, 605-616 (1972) · Zbl 0209.02201
[35] Jockusch, C. G.; Soare, R. I., \( \Pi_1^0\) classes and degrees of theories, Trans. Amer. Math. Soc., 173, 33-56 (1972) · Zbl 0262.02041
[36] Kačena, M.; Motto Ros, L.; Semmes, B., Some observations on “a new proof of a theorem of Jayne and Rogers”, Real Anal. Exchange, 38, 1, 121-132 (2012/2013) · Zbl 1272.03149
[39] Le Roux, S.; Pauly, A., Closed choice for finite and for convex sets, (Bonizzoni, P.; Brattka, V.; Löwe, B., CiE.. CiE., Lecture Notes in Computer Science, vol. 7921 (2013), Springer), 294-305 · Zbl 1433.03151
[40] Lewis, A. E.M.; Shore, R. A.; Sorbi, A., Topological aspects of the Medvedev lattice, Arch. Math. Logic, 50, 3-4, 319-340 (2011) · Zbl 1221.03037
[41] Małek, A., A classification of Baire one star functions, Real Anal. Exchange, 32, 205-212 (2006)
[42] Medvedev, Y. T., Degrees of difficulty of the mass problems, Dokl. Akad. Nauk SSSR, 104, 501-504 (1955), (in Russian) · Zbl 0065.00301
[43] Moschovakis, Y. N., Descriptive Set Theory, Mathematical Surveys and Monographs (2009), American Mathematical Society, 502 pp · Zbl 1172.03026
[44] Motto Ros, L., Game representations of classes of piecewise definable functions, Math. Log. Q., 57, 1, 95-112 (2011) · Zbl 1215.03060
[45] Motto Ros, L., On the structure of finite levels and \(ω\)-decomposable Borel functions, J. Symbolic Logic, 78, 4, 1257-1287 (2013) · Zbl 1323.03065
[46] Motto Ros, L.; Semmes, B., A new proof of a theorem of Jayne and Rogers, Real Anal. Exchange, 35, 1, 195-203 (2010) · Zbl 1217.03032
[47] Muchnik, A. A., On strong and weak reducibility of algorithmic problems, Sibirsk. Mat. Zh., 4, 1328-1341 (1963), (in Russian)
[48] Mylatz, U., Vergleich unstetiger funktionen: “principle of omniscience” und vollstandigkeit in der c-hierarchie (2006), Fernuniversität, Gesamthochschule in Hagen, Ph.D. thesis
[49] Nies, A., Computability and Randomness, Oxford Logic Guides (2009), Oxford University Press, 433 pp · Zbl 1169.03034
[50] Pauly, A., A new introduction to the theory of represented spaces, preprint
[51] Pauly, A.; de Brecht, M., Non-deterministic computation and the Jayne Rogers Theorem, (Electronic Proceedings in Theoretical Computer Science (2012)), in press · Zbl 1464.03042
[52] Pawlikowski, J.; Sabok, M., Decomposing Borel functions and structure at finite levels of the Baire hierarchy, Ann. Pure Appl. Logic, 163, 12, 1748-1764 (2012) · Zbl 1259.03061
[53] Rogers, H., The Theory of Recursive Functions and Effective Computability (1987), MIT Press, 504 pp
[54] Sabok, M., \(σ\)-continuity and related forcings, Arch. Math. Logic, 48, 5, 449-464 (2009) · Zbl 1169.03040
[55] Semmes, B., A game for the Borel functions (2009), Universiteit van Amsterdam, Ph.D. thesis
[56] Shafer, P., Coding true arithmetic in the Medvedev and Muchnik degrees, J. Symbolic Logic, 76, 1, 267-288 (2011) · Zbl 1222.03049
[57] Simpson, S. G., Mass problems and randomness, Bull. Symbolic Logic, 11, 1, 1-27 (2005) · Zbl 1090.03015
[58] Simpson, S. G., An extension of the recursively enumerable Turing degrees, J. Lond. Math. Soc., 75, 287-297 (2007) · Zbl 1119.03037
[59] Simpson, S. G., Some fundamental issues concerning degrees of unsolvability, (Computational Prospects of Infinity Part II. Presented Talks. Computational Prospects of Infinity Part II. Presented Talks, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 15 (2007), World Sci. Publ.: World Sci. Publ. Hackensack, NJ), 313-332 · Zbl 1157.03020
[60] Simpson, S. G., Subsystems of Second Order Arithmetic, Perspectives in Logic (2009), Cambridge University Press, 464 pp · Zbl 1181.03001
[61] Simpson, S. G., Mass problems associated with effectively closed sets, Tohoku Math. J., 63, 4, 489-517 (2011) · Zbl 1246.03064
[63] Soare, R. I., Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic (1987), Springer: Springer Heidelberg, xVIII+437 pp · Zbl 0623.03042
[64] Solecki, S., Decomposing Borel sets and functions and the structure of Baire class 1 functions, J. Amer. Math. Soc., 11, 521-550 (1998) · Zbl 0899.03034
[65] Weihrauch, K., Computable Analysis: An Introduction, Texts in Theoretical Computer Science (2000), Springer, 285 pp · Zbl 0956.68056
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.