Connected components of graphs and reverse mathematics

DOI10.1007/BF01269946MaRDI QIDQ2277258zbMATH OpenFDO

Authors Jeffry L. Hirst

Publication date 1991

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01269946

zbMATH Keywords

arithmetical comprehension schemedecompositions of graphs into connected componentsinduction schemeStatements about infinite graphssubsystems of second-order arithmetic

Mathematics Subject Classification ID

Second- and higher-order arithmetic and fragments (03F35) Connectivity (05C40)

Review text

Statements about infinite graphs can be formalized in the language of Friedman and Simpson's subsystems of second-order arithmetic. Working in \(RCA_ 0\), the following results concerning decompositions of graphs into (maximal) connected components can be proved. The statement ``every graph can be decomposed into its connected components is equivalent to the arithmetical comprehension scheme, \(ACA_ 0\). The statement ``for each \(k\in {\mathbb{N}}\), every graph with at most k connected components can be decomposed into its connected components is equivalent to the induction scheme \(I\Sigma^ 0_ 2\).

Recommendations

• On the existence of a connected component of a graph
• scientific article; zbMATH DE number 1187507
• Reverse mathematics and infinite traceable graphs
• Reverse Mathematics and Recursive Graph Theory
• Reverse mathematics and rank functions for directed graphs

Cites work

• Completeness Theorems, Incompleteness Theorems and Models of Arithmetic
• Countable algebra and set existence axioms
• Degrees of models
• Effective Matchmaking and k-Chromatic Graphs
• scientific article; zbMATH DE number 3825795 (Why is no real title available?)
• scientific article; zbMATH DE number 3700836 (Why is no real title available?)
• scientific article; zbMATH DE number 3536056 (Why is no real title available?)
• scientific article; zbMATH DE number 3566838 (Why is no real title available?)
• scientific article; zbMATH DE number 3316918 (Why is no real title available?)
• Ordinal numbers and the Hilbert basis theorem
• Subsystems of second order arithmetic
• Which set existence axioms are needed to prove the Cauchy/Peano theorem for ordinary differential equations?

Cited in

(5)

• Schmerl decompositions in first order arithmetic
• Reverse mathematics and Isbell's zig-zag theorem
• Reverse mathematics of matroids
• On the existence of a connected component of a graph
• scientific article; zbMATH DE number 1187507 (Why is no real title available?)

This page was built for publication: Connected components of graphs and reverse mathematics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277258)