On the existence of a connected component of a graph. (English) Zbl 1337.03086
Summary: 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 \(\mathrm{ACA}_0\) over \(\mathrm{RCA}_0\). 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 \(\mathrm{RCA}_0\) or is equivalent to induction for \(\Sigma_2^0\) formulas, depending on the formulation of the bound on the number of components.
MSC:
| 03F35 | Second- and higher-order arithmetic and fragments |
| 03B30 | Foundations of classical theories (including reverse mathematics) |
Keywords:
reverse mathematics; Weihrauch reducibility; component; graph; connected; partition; parallelizationReferences:
| [1] | Brattka, Effective Borel measurability and reducibility of functions, Mathematical Logic Quarterly 51 (1) pp 19– (2005) · Zbl 1059.03074 · doi:10.1002/malq.200310125 |
| [2] | Brattka, Closed choice and a uniform low basis theorem, Annals of Pure and Applied Logic 163 (8) pp 968– (2012) · Zbl 1251.03082 · doi:10.1016/j.apal.2011.12.020 |
| [3] | Brattka, Effective choice and boundedness principles in computable analysis, Bulletin of Symbolic Logic 1 pp 73– (2011) · Zbl 1226.03062 · doi:10.2178/bsl/1294186663 |
| [4] | Brattka, Weihrauch degrees, omniscience principles and weak computability, J. Symbolic Logic 76 (1) pp 143– (2011) · Zbl 1222.03071 · doi:10.2178/jsl/1294170993 |
| [5] | Dzhafarov, On the strength of the finite intersection principle, Israel J. Math. 196 (1) pp 345– (2013) · Zbl 1302.03035 · doi:10.1007/s11856-012-0150-9 |
| [6] | Friedman, Systems of second order arithmetic with restricted induction, I and II (abstracts), J. Symbolic Logic 41 (2) pp 557– (1976) |
| [7] | Hirst, Connected components of graphs and reverse mathematics, Arch. Math. Logic 31 (3) pp 183– (1992) · Zbl 0725.03039 · doi:10.1007/BF01269946 |
| [8] | Hoyrup, Computability of the Radon–Nikodym derivative, Computability 1 (1) pp 3– (2012) · Zbl 1277.03043 |
| [9] | Pauly, On the (semi)lattices induced by continuous reducibilities, Mathematical Logic Quarterly 56 (5) pp 488– (2010) · Zbl 1200.03028 · doi:10.1002/malq.200910104 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
