On the existence of a connected component of a graph

Authors

Kirill Gura
Jeffry L. Hirst
Carl Mummert, Marshall UniversityFollow

Document Type

Article

Publication Date

10-2013

Abstract

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 ACA₀ over RCA₀, while others are strictly weaker and incomparable with WKL₀. 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 RCA₀. We also show that, modulo Σ ⁰₂ induction, FIP lies strictly below the atomic model theorem (AMT).

Comments

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.

Recommended Citation

Gura, K., Hirst, J. L., & Mummert, C. (2015). On the existence of a connected component of a graph. Computability, 4(2), 103-117.