Any FIP real computes a 1-generic

Cholak, Peter; Downey, Rodney; Igusa, Greg

doi:10.1090/tran/6997

Any FIP real computes a 1-generic
HTML articles powered by AMS MathViewer

by Peter Cholak, Rodney G. Downey and Greg Igusa PDF

Trans. Amer. Math. Soc. 369 (2017), 5855-5869 Request permission

Abstract:

We construct a computable sequence of computable reals $\langle X_i\rangle$ such that any real that can compute a subsequence that is maximal with respect to the finite intersection property can also compute a Cohen 1-generic. This is extended to establish the same result with 2IP in place of FIP. This is the first example of a classical theorem of mathematics that has been found to be equivalent, both proof theoretically and in terms of its effective content, to computing a 1-generic.

References

Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight, and Robert I. Soare, Bounding prime models, J. Symbolic Logic 69 (2004), no. 4, 1117–1142. MR 2135658, DOI 10.2178/jsl/1102022214
David Diamondstone, Rod Downey, Noam Greenberg, and Dan Turetsky, The finite intersection principle and genericity, Math. Proc. Cambridge Philos. Soc. 160 (2016), no. 2, 279–297. MR 3458954, DOI 10.1017/S0305004115000651
Damir D. Dzhafarov and Carl Mummert, Reverse mathematics and properties of finite character, Ann. Pure Appl. Logic 163 (2012), no. 9, 1243–1251. MR 2926282, DOI 10.1016/j.apal.2012.01.007
Damir D. Dzhafarov and Carl Mummert, On the strength of the finite intersection principle, Israel J. Math. 196 (2013), no. 1, 345–361. MR 3096595, DOI 10.1007/s11856-012-0150-9
Denis R. Hirschfeldt, Richard A. Shore, and Theodore A. Slaman, The atomic model theorem and type omitting, Trans. Amer. Math. Soc. 361 (2009), no. 11, 5805–5837. MR 2529915, DOI 10.1090/S0002-9947-09-04847-8
Jeffry Lynn Hirst, COMBINATORICS IN SUBSYSTEMS OF SECOND ORDER ARITHMETIC, ProQuest LLC, Ann Arbor, MI, 1987. Thesis (Ph.D.)–The Pennsylvania State University. MR 2635978
Herman Rubin and Jean E. Rubin, Equivalents of the axiom of choice, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam-London, 1970. MR 0434812
Theodore A. Slaman, $\Sigma _n$-bounding and $\Delta _n$-induction, Proc. Amer. Math. Soc. 132 (2004), no. 8, 2449–2456. MR 2052424, DOI 10.1090/S0002-9939-04-07294-6
Stephen G. Simpson, Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR 2517689, DOI 10.1017/CBO9780511581007
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7