On the strength of the finite intersection principle

Abstract

We study the logical content of several maximality principles related to the finite intersection principle ($F\IP$) in set theory. Classically, these are all equivalent to the axiom of choice, but in the context of reverse mathematics their strengths vary: some are equivalent to $\ACA$ over $\RCA$, while others are strictly weaker, and incomparable with $\WKL$. We show that there is a computable instance of $F\IP$ all of whose solutions have hyperimmune degree, and that every computable instance has a solution in every nonzero c.e.\ degree. In terms of other weak principles previously studied in the literature, the former result translates to $F\IP$ implying the omitting partial types principle ($\mathsf{OPT}$). We also show that, modulo ${\Sigma }_2^0$ induction, $F\IP$ lies strictly below the atomic model theorem ($\mathsf{AMT}$).

This paper corresponds to section 3 of arXiv:1009.3242, "Reverse mathematics and equivalents of the axiom of choice", which has been abbreviated and divided into two pieces for publication

Cited by in corpus (3)

• On the existence of a connected component of a graph
• On the logical strengths of partial solutions to mathematical problems
• Refining the taming of the Reverse Mathematics zoo