We study the reverse mathematics and computability of countable graph theory, obtaining the following results. The principle that every countable graph has a connected component is equivalent to over . The problem of decomposing a countable graph into connected components is strongly Weihrauch equivalent to the problem of finding a single component, and each is equivalent to its infinite parallelization. For graphs with finitely many connected components, the existence of a connected component is either provable in or is equivalent to induction for formulas, depending on the formulation of the bound on the number of components.
V.Brattka, Effective Borel measurability and reducibility of functions, Mathematical Logic Quarterly51(1) (2005), 19–44.
2.
V.Brattka, M.de Brecht and A.Pauly, Closed choice and a uniform low basis theorem, Annals of Pure and Applied Logic163(8) (2012), 968–1008.
3.
V.Brattka and G.Gherardi, Effective choice and boundedness principles in computable analysis, Bulletin of Symbolic Logic1 (2011), 73–117, available at: arXiv:0905.4685.
4.
V.Brattka and G.Gherardi, Weihrauch degrees, omniscience principles and weak computability, J. Symbolic Logic76(1) (2011), 143–176.
5.
F.G.Dorais, D.D.Dzhafarov, J.L.Hirst, J.R.Mileti and P.Shafer, On uniform relationships between combinatorial problems, Trans. AMS (2015), to appear.
6.
D.D.Dzhafarov and C.Mummert, On the strength of the finite intersection principle, Israel J. Math.196(1) (2013), 345–361.
7.
H.Friedman, Some systems of second order arithmetic and their use, in: Proceedings of the International Congress of Mathematicians (Vancouver, B.C., 1974), Vol. 1, Canad. Math. Congress, Montreal, Que., 1975, pp. 235–242.
8.
H.Friedman, Systems of second order arithmetic with restricted induction, I and II (abstracts), J. Symbolic Logic41(2) (1976), 557–559.
9.
J.L.Hirst, Connected components of graphs and reverse mathematics, Arch. Math. Logic31(3) (1992), 183–192.
10.
M.Hoyrup, C.Rojas and K.Weihrauch, Computability of the Radon–Nikodym derivative, Computability1(1) (2012), 3–13.
11.
S.Le Roux and A.Pauly, Weihrauch degrees of finding equilibria in sequential games, available at: arXiv:1407.5587.
12.
J.B.Paris and L.A.S.Kirby, Σn-collection schemas in arithmetic, in: Logic Colloquium ’77, Proc. Conf., Wrocław, 1977, Stud. Logic Foundations Math., Vol. 96, North-Holland, Amsterdam–New York, 1978, pp. 199–209.
13.
A.Pauly, On the (semi)lattices induced by continuous reducibilities, Mathematical Logic Quarterly56(5) (2010), 488–502.
14.
A.Pauly and W.Fouché, How constructive is constructing measures? available at: arXiv:1409.3428.
15.
S.G.Simpson, Subsystems of Second Order Arithmetic, 2nd edn, Perspectives in Logic, Cambridge Univ. Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009.
