This paper analyzes the proof-theoretic strength of an infinite version of several theorems from algorithmic graph theory. In particular, theorems on reachability matrices, shortest path matrices, topological sorting, and minimal spanning trees are considered.
@article{bwmeta1.element.bwnjournal-article-fmv157i1p1bwm,
author = {Peter Clote and Jeffry Hirst},
title = {Reverse mathematics of some topics from algorithmic graph theory},
journal = {Fundamenta Mathematicae},
volume = {158},
year = {1998},
pages = {1-13},
zbl = {0908.03054},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-fmv157i1p1bwm}
}
Clote, Peter; Hirst, Jeffry. Reverse mathematics of some topics from algorithmic graph theory. Fundamenta Mathematicae, Tome 158 (1998) pp. 1-13. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-fmv157i1p1bwm/
[00000] [1] J. Hirst, Combinatorics in subsystems of second order arithmetic, Ph.D. Thesis, The Pennsylvania State University, 1987.
[00001] [2] J. Hirst, Connected components of graphs and reverse mathematics, Arch. Math. Logic 31 (1992), 183-192. | Zbl 0725.03039
[00002] [3] S. Simpson, Which set existence axioms are needed to prove the Cauchy/Peano theorem for ordinary differential equations?, J. Symbolic Logic 49 (1984), 783-802. | Zbl 0584.03039
[00003] [4] S. Simpson, Subsystems of , in: Proof Theory, G. Takeuti (ed.), North-Holland, Amsterdam, New York, 1985, 434-448.
[00004] [5] R. Soare, Recursively Enumerable Sets and Degrees, Springer, Berlin, 1987.