We provide a survey of results using Weihrauch problems to find analogs between set theory and computability theory. In our treatment, we emphasize the role of morphisms in explaining these coincidences. We end with a discussion of the use of forcing to prove the nonexistence of morphisms.
U.Andrews, M.Cai, D.Diamondstone, C.Jockusch and S.Lempp, Asymptotic density, computable traceability, and 1-randomness, Fund. Math.234(1) (2016), 41–53.
2.
T.Bartoszyński and H.Judah, Set Theory: On the Structure of the Real Line, A K Peters Ltd., Wellesley, MA, 1995.
3.
T.Bartoszyński and S.Shelah, Closed measure zero sets, Ann. Pure Appl. Logic58(2) (1992), 93–110. doi:10.1016/0168-0072(92)90001-G.
4.
A.Blass, Reductions between cardinal characteristics of the continuum, in: Set Theory, Boise, ID, 1992–1994, Contemp. Math., Vol. 192, Amer. Math. Soc., Providence, RI, 1996, pp. 31–49. doi:10.1090/conm/192/02347.
5.
A.Blass, Combinatorial cardinal characteristics of the continuum, in: Handbook of Set Theory. Vols. 1, 2, 3, Springer, Dordrecht, 2010, pp. 395–489. doi:10.1007/978-1-4020-5764-9_7.
6.
V.Brattka, Computability and analysis, a historical approach, in: Pursuit of the Universal, Lecture Notes in Comput. Sci., Vol. 9709, Springer, Cham, 2016, pp. 45–57. doi:10.1007/978-3-319-40189-8_5.
7.
V.Brattka, G.Gherardi and A.Marcone, The Bolzano–Weierstrass theorem is the jump of weak König’s lemma, Ann. Pure Appl. Logic163(6) (2012), 623–655. doi:10.1016/j.apal.2011.10.006.
8.
J.Brendle, A.Brooke-Taylor, K.M.Ng and A.Nies, An analogy between cardinal characteristics and highness properties of oracles, in: Proceedings of the 13th Asian Logic Conference, World Sci. Publ., Hackensack, NJ, 2015, pp. 1–28.
9.
J.Brendle and A.Nies, Up to 2 · 2 · 2ℵ0 cardinal invariants, and their counterparts in computability theory, in: Logic Blog 2015, 2015, available at:http://arxiv.org/abs/1602.04432.
10.
C.T.Chong, A.Nies and L.Yu, Lowness of higher randomness notions, Israel J. Math.166 (2008), 39–60. doi:10.1007/s11856-008-1019-9.
11.
S.Coskey, T.Mátrai and J.Steprāns, Borel Tukey morphisms and combinatorial cardinal invariants of the continuum, Fund. Math.223(1) (2013), 29–48. doi:10.4064/fm223-1-2.
12.
Denis, R.Hirschfeldt, C.G.JockuschJr., T.H.McNicholl and P.E.Schupp, Asymptotic density and the coarse computability bound, Computability5(1) (2016), 13–27. doi:10.3233/COM-150035.
13.
A.M.Donald, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math.12 (1966), 295–310. doi:10.1002/malq.19660120125.
14.
F.G.Dorais, D.D.Dzhafarov, J.L.Hirst, J.R.Mileti and P.Shafer, On uniform relationships between combinatorial problems, Trans. Amer. Math. Soc.368(2) (2016), 1321–1359. doi:10.1090/tran/6465.
15.
R.G.Downey and D.R.Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010.
16.
D.H.Fremlin, Real-valued-measurable cardinals, in: Set Theory of the Reals, Ramat Gan, 1991, Israel Math. Conf. Proc., Vol. 6, Bar-Ilan Univ., Ramat Gan, 1993, pp. 151–304.
17.
G.Gherardi and A.Marcone, How incomputable is the separable Hahn–Banach theorem?, Notre Dame J. Form. Log.50(4) (2009), 393–425. doi:10.1215/00294527-2009-018.
18.
M.Goldstern and S.Shelah, Many simple cardinal invariants, Arch. Math. Logic32(3) (1993), 203–221. doi:10.1007/BF01375552.
19.
N.Greenberg and J.S.Miller, Lowness for Kurtz randomness, J. Symbolic Logic74(2) (2009), 665–678. doi:10.2178/jsl/1243948333.
20.
N.Greenberg and B.Monin, Higher randomness and genericity, Forum Math. Sigma5 (2017), e31, 41 pp.
21.
N.Greenberg and D.Turetsky, Strong jump-traceability, Bulletin of Symbolic Logic, to appear.
22.
J.Kellner, Even more simple cardinal invariants, Arch. Math. Logic47(5) (2008), 503–515. doi:10.1007/s00153-008-0094-2.
T.Kihara, Higher randomness and lim–sup forcing within and beyond hyperarithmetic, in: Sets and Computations, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., Vol. 33, World Sci. Publ., Hackensack, NJ, 2018, pp. 117–155. doi:10.1142/9789813223523_0006.
25.
B.Kjos-Hanssen, W.Merkle and F.Stephan, Kolmogorov complexity and the recursion theorem, in: STACS 2006, Lecture Notes in Comput. Sci., Vol. 3884, Springer, Berlin, 2006, pp. 149–161. doi:10.1007/11672142_11.
26.
B.Kjos-Hanssen, A.Nies and F.Stephan, Lowness for the class of Schnorr random reals, SIAM J. Comput.35(3) (2005), 647–657, (electronic). doi:10.1137/S0097539704446323.
27.
B.Kjos-Hanssen, A.Nies, F.Stephan and L.Yu, Higher Kurtz randomness, Ann. Pure Appl. Logic161(10) (2010), 1280–1290. doi:10.1016/j.apal.2010.04.001.
28.
B.Kjos-Hanssen, F.Stephan and S.A.Terwijn, Covering the recursive sets, Ann. Pure Appl. Logic168(4) (2017), 804–823. doi:10.1016/j.apal.2016.10.017.
29.
K.Kunen, Random and Cohen reals, in: Handbook of Set-Theoretic Topology, North-Holland, Amsterdam, 1984, pp. 887–911. doi:10.1016/B978-0-444-86580-9.50023-9.
30.
A.W.Miller, Some properties of measure and category, Trans. Amer. Math. Soc.266(1) (1981), 93–114. doi:10.1090/S0002-9947-1981-0613787-2.
31.
B.Monin, An answer to the gamma question, in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, ACM, 2018, pp. 730–738.
32.
B.Monin and A.Nies, A unifying approach to the Gamma question, in: 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015), IEEE Computer Soc., Los Alamitos, CA, 2015, pp. 585–596. doi:10.1109/LICS.2015.60.
33.
B.Monin and A.Nies, Muchnik degrees and cardinal characteristics, arXiv:1712.00864.
34.
A.Nies, Computability and Randomness, Oxford Logic Guides, Vol. 51, Oxford University Press, Oxford, 2009.
35.
A.Nies, Lowness, randomness, and computable analysis, in: Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, A.Dayet al., eds, Lecture Notes in Comput. Sci., Vol. 10010, Springer, 2017, pp. 738–754. doi:10.1007/978-3-319-50062-1_42.
36.
N.Osuga and S.Kamo, Many different covering numbers of Yorioka’s ideals, Arch. Math. Logic53(1–2) (2014), 43–56. doi:10.1007/s00153-013-0354-7.
37.
J.Pawlikowski and I.Recław, Parametrized Cichoń’s diagram and small sets, Fund. Math.147(2) (1995), 135–155.
38.
J.Raisonnier and J.Stern, The strength of measurability hypotheses, Israel J. Math.50(4) (1985), 337–349. doi:10.1007/BF02759764.
39.
N.Rupprecht, Effective correspondents to cardinal characteristics in Cichoń’s diagram, PhD thesis, University of Michigan, 2010.
C.-P.Schnorr, A unified approach to the definition of random sequences, Math. Systems Theory5 (1971), 246–258. doi:10.1007/BF01694181.
42.
F.Stephan and L.Yu, Lowness for weakly 1-generic and Kurtz-random, in: Theory and Applications of Models of Computation, Lecture Notes in Comput. Sci., Vol. 3959, Springer, Berlin, 2006, pp. 756–764. doi:10.1007/11750321_72.
43.
S.A.Terwijn and D.Zambella, Computational randomness and lowness, J. Symbolic Logic66(3) (2001), 1199–1205. doi:10.2307/2695101.
44.
B.Tomek, Additivity of measure implies additivity of category, Trans. Amer. Math. Soc.281(1) (1984), 209–213. doi:10.1090/S0002-9947-1984-0719666-7.
45.
B.Tomek, Combinatorial aspects of measure and category, Fund. Math.127(3) (1987), 225–239. doi:10.4064/fm-127-3-225-239.
46.
P.Vojtáš, Topological cardinal invariants and the Galois–Tukey category, in: Recent Developments of General Topology and Its Applications, Berlin, 1992, Math. Res., Vol. 67, Akademie-Verlag, Berlin, 1992, pp. 309–314.
47.
K.Weihrauch, Computable Analysis: An Introduction, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000.
48.
J.Zapletal, Dimension theory and forcing, Topology Appl., 167 (2014), 31–35.
