Some questions in computable mathematics. (English) Zbl 1480.03006
Day, Adam (ed.) et al., Computability and complexity. Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 10010, 22-55 (2017).
Summary: In honor of Rod Downey’s 60th birthday, this paper discusses a few open problems connected in one way or another with him.
For the entire collection see [Zbl 1352.03004].
For the entire collection see [Zbl 1352.03004].
MathOverflow Questions:
Do all linear orders in this class have computable copies?Finding limit-nondecreasing sets for certain functions
MSC:
| 03B30 | Foundations of classical theories (including reverse mathematics) |
| 03C57 | Computable structure theory, computable model theory |
| 03Dxx | Computability and recursion theory |
Software:
MathOverflowReferences:
| [1] | Andrews, U.; Cai, M.; Diamondstone, D.; Jockusch, C.; Lempp, S., Asymptotic density, computable traceability, and 1-randomness, Fundam. Math., 234, 41-53, 2016 · Zbl 1401.03074 |
| [2] | Astor, E.P., Hirschfeldt, D.R., Jockusch Jr., C.G.: Dense computability, upper cones, and minimal pairs, in preparation · Zbl 1454.03052 |
| [3] | Bienvenu, L.; Greenberg, N.; Kučera, A.; Nies, A.; Turetsky, D., Coherent randomness tests and computing the \(K\)-trivial sets, J. Eur. Math. Soc., 18, 773-812, 2016 · Zbl 1375.03049 · doi:10.4171/JEMS/602 |
| [4] | Bonnet, R., Stratifications et extension des genres de chaînes dénombrables, C. R. Acad. Sci. Ser. A-B, 269, A880-A882, 1969 · Zbl 0206.28001 |
| [5] | Brattka, V.: Maintainer, Bibliography on Weihrauch complexity, Computability and Complexity in Analysis Network. http://cca-net.de/publications/weibib.php |
| [6] | Cholak, P., McCoy, C.: Effective prime uniqueness (to appear) · Zbl 1377.03033 |
| [7] | Cholak, P., Igusa, G.: Density-1-bounding and quasiminimality in the generic degrees. J. Symbolic Logic (to appear) · Zbl 1406.03056 |
| [8] | Cholak, PA; Jockusch, CG Jr; Slaman, TA, On the strength of Ramsey’s Theorem for pairs, J. Symbolic Logic, 66, 1-55, 2001 · Zbl 0977.03033 · doi:10.2307/2694910 |
| [9] | Chong, CT; Slaman, TA; Yang, Y., The metamathematics of stable Ramsey’s Theorem for pairs, J. Am. Math. Soc., 27, 863-892, 2014 · Zbl 1341.03015 · doi:10.1090/S0894-0347-2014-00789-X |
| [10] | Chong, C.T., Slaman, T.A., Yang, Y.: The inductive strength of Ramsey’s Theorem for pairs (to appear) · Zbl 1423.03047 |
| [11] | Csima, B.F.: Applications of Computability Theory to Prime Models and Differential Geometry. Ph.D. Dissertation, The University of Chicago (2003) |
| [12] | Csima, BF, Degree spectra of prime models, J. Symbolic Logic, 69, 430-442, 2004 · Zbl 1069.03025 · doi:10.2178/jsl/1082418536 |
| [13] | Dorais, FG; Dzhafarov, DD; Hirst, JL; Mileti, JR; Shafer, P., On uniform relationships between combinatorial problems, Trans. Am. Math. Soc., 368, 1321-1359, 2016 · Zbl 1528.03095 · doi:10.1090/tran/6465 |
| [14] | Downey, R.; Sorbi, A., On presentations of algebraic structures, Complexity, Logic, and Recursion Theory, 157-205, 1997, New York: Dekker, New York · Zbl 0915.03039 |
| [15] | Downey, R.G.: Computability theory and linear orderings. In: Ershov, Y.L., Goncharov, S.S., Nerode, A., Remmel, J.B., Marek, V.W. (eds.) Handbook of Recursive Mathematics, vol. II. Studies in Logic and the Foundations of Mathematics, vol. 139, pp. 823-976 (1998) · Zbl 0905.03001 |
| [16] | Downey, R.; Downey, R.; Decheng, D.; Ping, TS; Hui, QY; Yasugi, M., Computability, definability, and algebraic structures, Proceedings of the 7th and 8th Asian Logic Conferences, 63-102, 2003, Singapore: Singapore University Press and World Scientific, Singapore · Zbl 1054.03028 · doi:10.1142/9789812705815_0004 |
| [17] | Downey, RG; Hirschfeldt, DR, Algorithmic Randomness and Complexity, 2010, New York: Springer, New York · Zbl 1221.68005 · doi:10.1007/978-0-387-68441-3 |
| [18] | Downey, RG; Hirschfeldt, DR; LaForte, G., Randomness and reducibility, J. Comput. Syst. Sci., 68, 96-114, 2004 · Zbl 1072.03024 · doi:10.1016/j.jcss.2003.07.004 |
| [19] | Downey, RG; Hirschfeldt, DR; Lempp, S.; Solomon, R., A \(\Delta^0_2\) set with no infinite low subset in either it or its complement, J. Symbolic Logic, 66, 1371-1381, 2001 · Zbl 0990.03046 · doi:10.2307/2695113 |
| [20] | Downey, RG; Hirschfeldt, DR; Lempp, S.; Solomon, R., Computability-theoretic and proof-theoretic aspects of partial and linear orderings, Isr. J. Math., 138, 271-290, 2003 · Zbl 1044.03043 · doi:10.1007/BF02783429 |
| [21] | Downey, R.; Hirschfeldt, DR; Nies, A., Randomness, computability, and density, SIAM J. Comput., 31, 1169-1183, 2002 · Zbl 1052.68060 · doi:10.1137/S0097539700376937 |
| [22] | Downey, RG; Hirschfeldt, DR; Nies, A.; Terwijn, SA, Calibrating randomness, Bull. Symbolic Logic, 12, 411-491, 2006 · Zbl 1113.03037 · doi:10.2178/bsl/1154698741 |
| [23] | Downey, R.; Jockusch, CG, Every low Boolean algebra is isomorphic to a recursive one, Proc. Am. Math. Soc., 122, 871-880, 1994 · Zbl 0820.03019 · doi:10.1090/S0002-9939-1994-1203984-4 |
| [24] | Downey, R.; Jockusch, C.; McNicholl, TH; Schupp, P., Asymptotic density and the Ershov Hierarchy, Math. Logic Q., 61, 189-195, 2015 · Zbl 1361.03037 · doi:10.1002/malq.201300081 |
| [25] | Downey, RG; Jockusch, CG Jr, On self-embeddings of computable linear orderings, Ann. Pure Appl. Logic, 138, 52-76, 2006 · Zbl 1105.03036 · doi:10.1016/j.apal.2005.06.008 |
| [26] | Downey, RG; Jockusch, CG Jr; Schupp, PE, Asymptotic density and computably enumerable sets, J. Math. Logic, 13, 43, 2013 · Zbl 1326.03048 · doi:10.1142/S0219061313500050 |
| [27] | Downey, RG; Kastermans, B.; Lempp, S., On computable self-embeddings of computable linear orderings, J. Symbolic Logic, 74, 1352-1366, 2009 · Zbl 1201.03029 · doi:10.2178/jsl/1254748695 |
| [28] | Downey, RG; Lempp, S.; Arslanov, MM; Lempp, S., The proof-theoretic strength of the Dushnik-Miller theorem for countable linear orders, Recursion Theory and Complexity, 55-57, 1999, Berlin: De Gruyter, Berlin · Zbl 0951.03053 |
| [29] | Downey, R.; Lempp, S.; Wu, G., On the complexity of the successivity relation in computable linear orders, J. Math. Logic, 10, 83-99, 2010 · Zbl 1256.03039 · doi:10.1142/S0219061310000924 |
| [30] | Downey, R., Remmel, J.B.: Questions in computable algebra and combinatorics. In: Cholak, P.A., Lempp, S., Lerman, M., Shore, R.A. (eds.) Computability Theory and its Applications (Boulder, CO, 1999). Contemporary Mathematics, vol. 257, pp. 95-125. American Mathematical Society, Providence (2000) · Zbl 0980.03045 |
| [31] | Dushnik, B.; Miller, EW, Concerning similarity transformations of linearly ordered sets, Bull. Am. Math. Soc., 40, 322-326, 1940 · JFM 66.0199.02 · doi:10.1090/S0002-9904-1940-07213-1 |
| [32] | Dzhafarov, D.D.: Strong reductions between combinatorial principles. J. Symbolic Logic (to appear) |
| [33] | Dzhafarov, D.D., Patey, L., Solomon, R., Westrick, L.B.: Ramsey’s Theorem for singletons and strong computable reducibility. Proc. Am. Math. Soc. (to appear) · Zbl 1423.03159 |
| [34] | Figueira, S.; Hirschfeldt, DR; Miller, JS; Ng, KM; Nies, A., Counting the changes of random \(\Delta^0_2\) sets, J. Logic Comput., 25, 1073-1089, 2015 · Zbl 1338.03081 · doi:10.1093/logcom/exs083 |
| [35] | Fokina, E.B., Harizanov, V., Melnikov, A.G.: Computable model theory. In: Downey, R. (ed.) Turing’s Legacy: Developments from Turing’s Ideas in Logic. Lecture Notes in Logic, vol. 42, pp. 124-194. Association for Symbolic Logic, La Jolla. Cambridge University Press, Cambridge (2014) · Zbl 1341.03002 |
| [36] | Frolov, A.; Harizanov, V.; Kalimullin, I.; Kudinov, O.; Miller, R., Degree spectra of \(high_n\) and \(nonlow_n\) degrees, J. Logic Comput., 22, 755-777, 2012 · Zbl 1260.03068 · doi:10.1093/logcom/exq041 |
| [37] | Gács, P., Every sequence is reducible to a random one, Inf. Control, 70, 186-192, 1986 · Zbl 0628.03024 · doi:10.1016/S0019-9958(86)80004-3 |
| [38] | Goncharov, SS, Problem of the number of non-self-equivalent constructivizations, Algebra Logic, 19, 401-414, 1980 · Zbl 0476.03046 · doi:10.1007/BF01669323 |
| [39] | Goncharov, S.S.: Limit equivalent constructivizations. In: Mathematical Logic and the Theory of Algorithms Trudy Instituta Matematiki, vol. 2, pp. 4-12. “Nauka” Sibirskoe otdelenie, Novosibirsk (1982) · Zbl 0543.03017 |
| [40] | Goncharov, SS, Countable Boolean Algebras and Decidability, 1997, New York: Consultants Bureau, New York · Zbl 0912.03019 |
| [41] | Goncharov, SS; Dzgoev, VD, Autostability of models, Algebra Logic, 19, 28-37, 1980 · Zbl 0468.03023 · doi:10.1007/BF01669102 |
| [42] | Goncharov, SS; Nurtazin, AT, Constructive models of complete decidable theories, Algebra Logic, 12, 67-77, 1973 · Zbl 0282.02018 · doi:10.1007/BF02219289 |
| [43] | Harizanov, VS; Ershov, YL; Goncharov, SS; Nerode, A.; Remmel, JB; Marek, VW, Pure computable model theory, Handbook of Recursive Mathematics, 3-114, 1998, Amsterdam: North-Holland, Amsterdam · Zbl 0952.03037 |
| [44] | Harrington, L., Recursively presentable prime models, J. Symbolic Logic, 39, 305-309, 1974 · Zbl 0332.02055 · doi:10.2307/2272643 |
| [45] | Harrison-Trainor, M., Melnikov, A., Miller, R., Montalbán, A.: Computable functors and effective interpretability. J. Symbolic Logic (to appear) · Zbl 1390.03034 |
| [46] | Hirschfeldt, DR, Computable trees, prime models, and relative decidability, Proc. Am. Math. Soc., 134, 1495-1498, 2006 · Zbl 1099.03024 · doi:10.1090/S0002-9939-05-08097-4 |
| [47] | Hirschfeldt, DR, Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles, 2014, Singapore: World Scientific, Singapore · Zbl 1304.03001 |
| [48] | Hirschfeldt, DR; Jockusch, CG Jr, On notions of computability theoretic reduction between \(\Pi^1_2\) principles, J. Math. Logic, 16, 1650002, 2016 · Zbl 1373.03068 · doi:10.1142/S0219061316500021 |
| [49] | Hirschfeldt, D.R., Jockusch Jr., C.G., Kjos-Hanssen, B., Lempp, S., Slaman, T.A.: The strength of some combinatorial principles related to Ramsey’s Theorem for pairs. In: Chong, C., Feng, Q., Slaman, T.A., Woodin, W.H., Yang, Y. (eds.) Computational Prospects of Infinity, Part II: Presented Talks. Lecture Notes Series, vol. 15, pp. 143-161. World Scientific, Singapore (2008). Institute for Mathematical Sciences, National University of Singapore · Zbl 1167.03009 |
| [50] | Hirschfeldt, D.R., Jockusch Jr., C.G., Kuyper, R., Schupp, P.E.: Coarse reducibility and algorithmic randomness. J. Symbolic Logic (to appear) · Zbl 1403.03069 |
| [51] | Hirschfeldt, DR; Jockusch, CG Jr; McNicholl, T.; Schupp, PE, Asymptotic density and the coarse computability bound, Computability, 5, 13-27, 2016 · Zbl 1522.03158 · doi:10.3233/COM-150035 |
| [52] | Hirschfeldt, DR; Khoussainov, B.; Shore, RA; Slinko, AM, Degree spectra and computable dimensions in algebraic structures, Ann. Pure Appl. Logic, 115, 71-113, 2002 · Zbl 1016.03034 · doi:10.1016/S0168-0072(01)00087-2 |
| [53] | Hirschfeldt, DR; Kramer, K.; Miller, R.; Shlapentokh, A., Categoricity properties for computable algebraic fields, Trans. Am. Math. Soc., 367, 3981-4017, 2015 · Zbl 1347.03082 · doi:10.1090/S0002-9947-2014-06094-7 |
| [54] | Hirschfeldt, DR; Nies, A.; Stephan, F., Using random sets as oracles, J. Lond. Math. Soc., 75, 610-622, 2007 · Zbl 1128.03036 · doi:10.1112/jlms/jdm041 |
| [55] | Hirschfeldt, DR; Shore, RA, Combinatorial principles weaker than Ramsey’s Theorem for pairs, J. Symbolic Logic, 72, 171-206, 2007 · Zbl 1118.03055 · doi:10.2178/jsl/1174668391 |
| [56] | Hirst, J.L.: Combinatorics in Subsystems of Second Order Arithmetic. Ph.D. Dissertation, The Pennsylvania State University (1987) |
| [57] | Igusa, G., Nonexistence of minimal pairs for generic computation, J. Symbolic Logic, 78, 511-522, 2013 · Zbl 1302.03048 · doi:10.2178/jsl.7802090 |
| [58] | Igusa, G., The generic degrees of density-\(1\) sets, and a characterization of the hyperarithmetic reals, J. Symbolic Logic, 80, 1290-1314, 2015 · Zbl 1367.03077 · doi:10.1017/jsl.2014.77 |
| [59] | Jockusch, CG Jr, Ramsey’s Theorem and recursion theory, J. Symbolic Logic, 37, 268-280, 1972 · Zbl 0262.02042 · doi:10.2307/2272972 |
| [60] | Jockusch, CG Jr; Schupp, PE, Generic computability, and asymptotic density, J. Lond. Math. Soc., 85, 472-490, 2012 · Zbl 1247.03076 · doi:10.1112/jlms/jdr051 |
| [61] | Jockusch, CG; Soare, RI, Degrees of orderings not isomorphic to recursive linear orderings, Ann. Pure Appl. Logic, 52, 39-64, 1991 · Zbl 0734.03026 · doi:10.1016/0168-0072(91)90038-N |
| [62] | Jullien, P.: Contribution à L’étude des Types D’ordre Dispersés. Ph.D. Dissertation, Université d’Aix-Marseille (1969) |
| [63] | Kapovich, I.; Myasnikov, A.; Schupp, P.; Shpilrain, V., Generic-case complexity, decision problems in group theory and random walks, J. Algebra, 264, 665-694, 2003 · Zbl 1041.20021 · doi:10.1016/S0021-8693(03)00167-4 |
| [64] | Kastermans, B.; Lempp, S., Comparing notions of randomness, Theoret. Comput. Sci., 411, 602-616, 2010 · Zbl 1184.68274 · doi:10.1016/j.tcs.2009.09.036 |
| [65] | Kalimullin, I.; Khoussainov, B.; Melnikov, A., Limitwise monotonic sequences and degree spectra of structures, Proc. Am. Math. Soc., 141, 3275-3289, 2013 · Zbl 1408.03028 · doi:10.1090/S0002-9939-2013-11586-8 |
| [66] | Kjos-Hanssen, B.; Merkle, W.; Stephan, F., Kolmogorov complexity and the recursion theorem, Trans. Am. Math. Soc., 363, 5465-5480, 2011 · Zbl 1236.03032 · doi:10.1090/S0002-9947-2011-05306-7 |
| [67] | Knight, JF, Degrees coded in jumps of orderings, J. Symbolic Logic, 51, 1034-1042, 1986 · Zbl 0633.03038 · doi:10.2307/2273915 |
| [68] | Knight, JF; Stob, M., Computable Boolean algebras, J. Symbolic Logic, 65, 1605-1623, 2000 · Zbl 0974.03041 · doi:10.2307/2695066 |
| [69] | Kučera, A.; Ebbinghaus, HD; Müller, GH; Sacks, GE, Measure, \( \Pi^0_1\)-classes and complete extensions of PA, Recursion Theory Week, 245-259, 1985, Berlin: Springer-Verlag, Berlin · Zbl 0622.03031 · doi:10.1007/BFb0076224 |
| [70] | LaRoche, P., Recursively represented Boolean algebras, Not. Am. Math. Soc., 24, A-552, 1977 |
| [71] | Lempp, S.; McCoy, C.; Miller, R.; Solomon, R., Computable categoricity for trees of finite height, J. Symbolic Logic, 70, 151-215, 2005 · Zbl 1104.03026 · doi:10.2178/jsl/1107298515 |
| [72] | Lempp, S.; McCoy, C.; Miller, R.; Solomon, R., The computable dimension of trees of infinite height, J. Symbolic Logic, 70, 111-141, 2005 · Zbl 1098.03049 · doi:10.2178/jsl/1107298515 |
| [73] | Lewis, AEM; Barmpalias, G., Random reals and Lipschitz continuity, Math. Struct. Comput. Sci., 16, 737-749, 2006 · Zbl 1117.03053 · doi:10.1017/S0960129506005445 |
| [74] | Lewis, AEM; Barmpalias, G., Randomness and the linear degrees of computability, Ann. Pure Appl. Logic, 145, 252-257, 2007 · Zbl 1109.03037 · doi:10.1016/j.apal.2006.08.001 |
| [75] | Liu, J., \(RT^2_2\) does not imply \(WKL_0\), J. Symbolic Logic, 77, 609-620, 2012 · Zbl 1245.03095 · doi:10.2178/jsl/1333566640 |
| [76] | Liu, L., Cone avoiding closed sets, Trans. Am. Math. Soc., 367, 1609-1630, 2015 · Zbl 1369.03101 · doi:10.1090/S0002-9947-2014-06049-2 |
| [77] | Lynch, N., Approximations to the halting problem, J. Comput. Syst. Sci., 9, 143-150, 1974 · Zbl 0299.02042 · doi:10.1016/S0022-0000(74)80003-6 |
| [78] | Melnikov, AG, Enumerations and completely decomposable torsion-free abelian groups, Theor. Comput. Syst., 45, 897-916, 2009 · Zbl 1204.03039 · doi:10.1007/s00224-009-9175-9 |
| [79] | Merkle, W., The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences, J. Symbolic Logic, 68, 1362-1376, 2003 · Zbl 1065.03024 · doi:10.2178/jsl/1067620192 |
| [80] | Merkle, W.; Mihailović, N., On the construction of effectively random sets, J. Symbolic Logic, 69, 862-878, 2004 · Zbl 1090.03011 · doi:10.2178/jsl/1096901772 |
| [81] | Merkle, W.; Miller, JS; Nies, A.; Reimann, J.; Stephan, F., Kolmogorov-Loveland randomness and stochasticity, Ann. Pure Appl. Logic, 138, 183-210, 2006 · Zbl 1097.03041 · doi:10.1016/j.apal.2005.06.011 |
| [82] | Meyer, AR, An open problem on creative sets, Recursive Funct. Theor. Newsl., 4, 15-16, 1973 |
| [83] | Mileti, J.R., Partition Theorems and Computability Theory. Ph.D. Dissertation, University of Illinois at Urbana-Champaign (2004) |
| [84] | Millar, TS, Foundations of recursive model theory, Ann. Math. Logic, 13, 45-72, 1978 · Zbl 0432.03018 · doi:10.1016/0003-4843(78)90030-X |
| [85] | Millar, TS, Omitting types, type spectrums, and decidability, J. Symbolic Logic, 48, 171-181, 1983 · Zbl 0516.03017 · doi:10.2307/2273331 |
| [86] | Miller, JS; Nies, A., Randomness and computability: open questions, Bull. Symbolic Logic, 12, 390-410, 2006 · Zbl 1169.03033 · doi:10.2178/bsl/1154698740 |
| [87] | Miller, R.G.: Computability, Definability, Categoricity, and Automorphisms. Ph.D. Dissertation, The University of Chicago (2000) |
| [88] | Miller, R., The \(\Delta^0_2\)-spectrum of a linear order, J. Symbolic Logic, 66, 470-486, 2001 · Zbl 0992.03050 · doi:10.2307/2695025 |
| [89] | Miller, R., \({\bf d}\)-computable categoricity for algebraic fields, J. Symbolic Logic, 74, 1325-1351, 2009 · Zbl 1202.03044 · doi:10.2178/jsl/1254748694 |
| [90] | Miller, R., Poonen, B., Schoutens, H., Shlapentokh, A.: A computable functor from graphs to fields (to appear) · Zbl 1447.03005 |
| [91] | Monin, B.: Asymptotic density and error-correcting codes (to appear) |
| [92] | Monin, B., Nies, A.: A unifying approach to the Gamma question. In: 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, pp. 585-596. IEEE Computer Society (2015) · Zbl 1395.03019 |
| [93] | Monin, B., Patey, L.: \( \Pi^0_1\) encodability and omniscient reductions (to appear) |
| [94] | Montalbán, A., Equivalence between Fraïssé’s Conjecture and Jullien’s Theorem, Ann. Pure Appl. Logic, 139, 1-42, 2006 · Zbl 1094.03045 · doi:10.1016/j.apal.2005.03.001 |
| [95] | Muchnik, AA; Semenov, AL; Uspensky, VA, Mathematical metaphysics of randomness, Theoret. Comput. Sci., 207, 263-317, 1998 · Zbl 0922.60014 · doi:10.1016/S0304-3975(98)00069-3 |
| [96] | Patey, L.: The weakness of being cohesive, thin or free in reverse mathematics. Isr. J. Math. (to appear) · Zbl 1368.03018 |
| [97] | Patey, L., Open questions about Ramsey-type statements in reverse mathematics, Bull. Symbolic Logic, 22, 151-169, 2016 · Zbl 1396.03012 · doi:10.1017/bsl.2015.40 |
| [98] | Remmel, JB, Recursively categorical linear orderings, Proc. Am. Math. Soc., 83, 387-391, 1981 · Zbl 0493.03022 · doi:10.1090/S0002-9939-1981-0624937-1 |
| [99] | Richter, LJ, Degrees of structures, J. Symbolic Logic, 46, 723-731, 1981 · Zbl 0512.03024 · doi:10.2307/2273222 |
| [100] | Rosenstein, JG, Linear Orderings, 1982, New York-London: Academic Press Inc., New York-London |
| [101] | Schnorr, C-P, A unified approach to the definition of a random sequence, Math. Syst. Theor., 5, 246-258, 1971 · Zbl 0227.62005 · doi:10.1007/BF01694181 |
| [102] | Schnorr, C.-P.: Zufälligkeit und Wahrscheinlichkeit. Lecture Notes in Mathematics, vol. 218. Springer, Berlin (1971) · Zbl 0232.60001 |
| [103] | Schweber, N.: Do all linear orders in this class have computable copies? (2014). mathoverflow.net/questions/161434 |
| [104] | Schweber, N.: Finding limit-nondecreasing sets for certain functions (2016). mathoverflow.net/questions/227766 |
| [105] | Seetapun, D.; Slaman, TA, On the strength of Ramsey’s Theorem, Notre Dame J. Formal Logic, 36, 570-582, 1995 · Zbl 0843.03034 · doi:10.1305/ndjfl/1040136917 |
| [106] | Simpson, SG, Subsystems of Second Order Arithmetic, 1999, Berlin: Springer, Berlin · Zbl 0909.03048 · doi:10.1007/978-3-642-59971-2 |
| [107] | Simpson, SG, Subsystems of Second Order Arithmetic, 2009, Poughkeepsie: Cambridge University Press, Cambridge and Association for Symbolic Logic, Poughkeepsie · Zbl 1181.03001 · doi:10.1017/CBO9780511581007 |
| [108] | Slaman, TA, Relative to any nonrecursive set, Proc. Am. Math. Soc., 126, 2117-2122, 1998 · Zbl 0894.03017 · doi:10.1090/S0002-9939-98-04307-X |
| [109] | Solovay, RM, Hyperarithmetically encodable sets, Trans. Am. Math. Soc., 239, 99-122, 1978 · Zbl 0411.03039 · doi:10.1090/S0002-9947-1978-0491103-7 |
| [110] | Soskov, I.N.: Degree spectra and co-spectra of structures, Annuaire de l’Université de Sofia “St. Kliment Ohrisdski”, Faculté de Mathématiques et Informatique 96, 45-68(2004) · Zbl 1086.03034 |
| [111] | Specker, E.; Gandy, RO; Yates, CEM, Ramsey’s Theorem does not hold in recursive set theory, Logic Colloquium 1969, 439-442, 1971, Amsterdam: North-Holland, Amsterdam · Zbl 0285.02038 |
| [112] | Szpilrajn, E., Sur l’extension de l’ordre partiel, Fundam. Math., 16, 386-389, 1930 · JFM 56.0843.02 |
| [113] | Terwijn, S.A.: Computability and Measure. Ph.D. Dissertation, University of Amsterdam (1998) |
| [114] | Thurber, J.: Degrees of Boolean Algebras. Ph.D. Dissertation, University of Notre Dame (1994) |
| [115] | Wang, Y.: Randomness and Complexity. Ph.D. Dissertation, University of Heidelberg (1996) · Zbl 0858.03041 |
| [116] | Wang, Y., A separation of two randomness concepts, Inf. Process. Lett., 69, 115-118, 1999 · Zbl 1338.68131 · doi:10.1016/S0020-0190(98)00202-6 |
| [117] | Wehner, S., Enumerations, countable structures, and Turing degrees, Proc. Am. Math. Soc., 126, 2131-2139, 1998 · Zbl 0906.03044 · doi:10.1090/S0002-9939-98-04314-7 |
| [118] | Weihrauch, K.: The degrees of discontinuity of some translators between representations of the real numbers. Technical report TR-92-050. International Computer Science Institute, Berkeley (1992) |
| [119] | Weihrauch, K.: The TTE-interpretation of three hierarchies of omniscience principles. In: Informatik Berichte FernUniversität Hagen, vol. 130. Hagen (1992) |
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.
