Abstract
Working in subsystems of second order arithmetic, we formulate several representations for hypergraphs. We then prove the equivalence of various vertex coloring theorems to \({\textsf {WKL}}_0\), \({\textsf {ACA}}_0\), and \({\varPi ^1_1 \text {-}}{\textsf {CA}}_0\).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Berge, C.: Hypergraphs, North-Holland Mathematical Library, vol. 45. North-Holland Publishing Co., Amsterdam (1989). (Combinatorics of finite sets, Translated from the French)
Chong, C.T., Slaman, T.A., Yang, Y.: The metamathematics of stable Ramsey’s theorem for pairs. J. Am. Math. Soc. 27(3), 863–892 (2014). https://doi.org/10.1090/S0894-0347-2014-00789-X
Davis, C., Hirschfeldt, D., Hirst, J., Pardo, J., Pauly, A., Yokoyama, K.: Combinatorial principles equivalent to weak induction (2018) (in preparation)
Dorais, F.G., Hirst, J.L., Shafer, P.: Comparing the strength of diagonally nonrecursive functions in the absence of \({\varSigma }_ {2}^{0}\) induction. J. Symb. Log. 80(4), 1211–1235 (2015). https://doi.org/10.1017/jsl.2015.43
Hirst, J.L.: Marriage theorems and reverse mathematics. In: Sieg, W. (ed.) Logic and Computation (Pittsburgh, PA, 1987). Contemporary Mathematics, vol. 106, pp. 181–196. American Mathematical Society, Providence (1990). https://doi.org/10.1090/conm/106/1057822
Hirst, J.L.: Disguising induction: proofs of the pigeonhole principle for trees. In: Tennant, N. (ed.) Foundational Adventures, Tributes, vol. 22, pp. 113–123. College Publications, London (2014)
Kreuzer, A.P., Yokoyama, K.: On principles between \({\varSigma }_{1}\)- and \({\varSigma }_{2}\)-induction, and monotone enumerations. J. Math. Log. 16(1), 1650004 (2016). https://doi.org/10.1142/S0219061316500045
Simpson, S.G.: Subsystems of Second Order Arithmetic. Perspectives in Logic, 2nd edn. Cambridge University Press, Cambridge (2009). https://doi.org/10.1017/CBO9780511581007
Smorodinsky, S.: Conflict-free coloring and its applications. In: Bárány, I., Böröczky, K.J., Táth, G.F., Pach, J. (eds.) Geometry—Intuitive, Discrete, and Convex. Bolyai Society Mathematical Studies, vol. 24, pp. 331–389. János Bolyai Mathematical Society, Budapest (2013). https://doi.org/10.1007/978-3-642-41498-5_12
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Davis, C., Hirst, J., Pardo, J. et al. Reverse mathematics and colorings of hypergraphs. Arch. Math. Logic 58, 575–585 (2019). https://doi.org/10.1007/s00153-018-0654-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-018-0654-z