Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T13:22:44.276Z Has data issue: false hasContentIssue false
  • English
  • Français

The finite intersection principle and genericity

Published online by Cambridge University Press:  26 November 2015

DAVID DIAMONDSTONE ,
ROD DOWNEY ,
NOAM GREENBERG  and
DAN TURETSKY
DAVID DIAMONDSTONE
Affiliation:
Google San Francisco, San Francisco, California, U.S.A. e-mail: [email protected]
ROD DOWNEY
Affiliation:
Department of Mathematics, Victoria University of Wellington, Wellington, New Zealand. e-mail: [email protected]; [email protected]; [email protected]
NOAM GREENBERG
Affiliation:
Department of Mathematics, Victoria University of Wellington, Wellington, New Zealand. e-mail: [email protected]; [email protected]; [email protected]
DAN TURETSKY
Affiliation:
Department of Mathematics, Victoria University of Wellington, Wellington, New Zealand. e-mail: [email protected]; [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that a Δ02 Turing degree computes solutions to all computable instances of the finite intersection principle if and only if it computes a 1-generic degree. We also investigate finite and infinite variants of the principle.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 160 , Issue 2 , March 2016 , pp. 279 - 297
Copyright
Copyright © Cambridge Philosophical Society 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[DM13]Dzhafarov, D. D. and Mummert, C.On the strength of the finite intersection principle. Israel J. Math. 196 (1) (2013), 345–361.CrossRefGoogle Scholar
[FH90]Friedman, H. M. and Hirst, J. L.Weak comparability of well orderings and reverse mathematics. Ann. Pure Appl. Logic 47 (1) (1990), 11–29.CrossRefGoogle Scholar
[FSS83]Friedman, H. M., Simpson, S. G. and Smith, R. L.Countable algebra and set existence axioms. Ann. Pure Appl. Logic 25 (2) (1983), 141–181.CrossRefGoogle Scholar
[GM03]Greenberg, N. and Montalbán, A.Embedding and coding below a 1-generic degree. Notre Dame J. Formal Logic 44 (4) (2003), 200–216.CrossRefGoogle Scholar
[HM10]Hochmand, M. and Meyerovitch, T.A characterization of the entropies of multidimensional shifts of finite type. Ann. Math. 171 (3) (2010), 2011–2038.CrossRefGoogle Scholar
[HSS09]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.CrossRefGoogle Scholar
[Mil08]Mileti, J. R.The canonical {R}amsey theorem and computability theory. Trans. Amer. Math. Soc. 360 (3) (2008), 1309–1340 (electronic).CrossRefGoogle Scholar
[Moo82]Moore, G. H.Zermelo's axiom of choice. Studies in the History of Mathematics and Physical Sciences, vol. 8 (Springer-Verlag, New York, 1982).Google Scholar
[RR73]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).Google Scholar