×

zbMATH — the first resource for mathematics

The finite intersection principle and genericity. (English) Zbl 1375.03046
A FIP degree is a Turing degree that given any computable sequence of subsets of \(\omega\) computes a maximal subsequence such that the intersection of each finite subcollection is nonempty. Similarly, a 2IP degree computes maximal subsequences such that every pair of sets has nonempty intersection. Suppose that a is a \(\Delta^0_2\) Turing degree. The authors prove that the following are equivalent: (1) a is FIP, (2) a is 2IP, and (3) a computes a 1-generic set.
This theorem is extended to all Turing degrees by a result of P. Cholak et al. [Trans. Am. Math. Soc. 369, No. 8, 5855–5869 (2017; Zbl 1423.03142)]. For more on the proof theoretic and computable strength of principles related to FIP, see the work of D. D. Dzhafarov and C. Mummert [Isr. J. Math. 196, 345–361 (2013; Zbl 1302.03035)].

MSC:
03D28 Other Turing degree structures
03B30 Foundations of classical theories (including reverse mathematics)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Dzhafarov, D. D. and Mummert, C.On the strength of the finite intersection principle. Israel J. Math.196(1) (2013), 345-361. doi:10.1007/s11856-012-0150-93096595 · Zbl 1302.03035
[2] Friedman, H. M. and Hirst, J. L.Weak comparability of well orderings and reverse mathematics. Ann. Pure Appl. Logic47(1) (1990), 11-29. doi:10.1016/0168-0072(90)90014-S1050559 · Zbl 0706.03044
[3] Friedman, H. M., Simpson, S. G. and Smith, R. L.Countable algebra and set existence axioms. Ann. Pure Appl. Logic25(2) (1983), 141-181. doi:10.1016/0168-0072(83)90012-X0725732 · Zbl 0575.03038
[4] Greenberg, N. and Montalbán, A.Embedding and coding below a 1-generic degree. Notre Dame J. Formal Logic44(4) (2003), 200-216. doi:10.1305/ndjfl/10911224982130306 · Zbl 1066.03045
[5] Hochmand, M. and Meyerovitch, T.A characterization of the entropies of multidimensional shifts of finite type. Ann. Math.171(3) (2010), 2011-2038. doi:10.4007/annals.2010.171.2011 · Zbl 1192.37022
[6] Hirschfeldt, D. R., Shore, R. A. and Slaman, T. A.The atomic model theorem and type omitting. Trans. Amer. Math. Soc.361(11) (2009), 5805-5837. doi:10.1090/S0002-9947-09-04847-82529915 · Zbl 1184.03005
[7] Mileti, J. R.The canonical Ramsey theorem and computability theory. Trans. Amer. Math. Soc.360(3) (2008), 1309-1340 (electronic). doi:10.1090/S0002-9947-07-04390-5 · Zbl 1135.03014
[8] Moore, G. H.Zermelo’s axiom of choice. Studies in the History of Mathematics and Physical Sciences, vol. 8 (Springer-Verlag, New York, 1982). · Zbl 0497.01005
[9] Rubin, H. and Rubin, J. E.Equivalents of the axiom of choice. Studies in Logic and the Foundations of Mathematics, vol. 75 (North-Holland Publishing Co., 1973). · Zbl 0129.00601
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.