On the existence of a connected component of a graph
We study the logical content of several maximality principles related to the finite intersection principle (FIP) 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 ACA0 over RCA0, while others are strictly weaker and incomparable with WKL0. We show that there is a computable instance of FIP every solution of which has hyperimmune degree, and that every computable instance has a solution in every nonzero c.e. degree. In particular, FIP implies the omitting partial types principle (OPT) over RCA0. We also show that, modulo Σ 02 induction, FIP lies strictly below the atomic model theorem (AMT).
Gura, K., Hirst, J. L., & Mummert, C. (2015). On the existence of a connected component of a graph. Computability, 4(2), 103-117.
This is the author's manuscript. The version of record is available from the publisher at http://www.doi.org/10.3233/COM-150039.
Copyright © 2015 IOS Press. All rights reserved.