Reverse mathematics and rank functions for directed graphs
type: Item
instance of: scholarly article
title: Reverse mathematics and rank functions for directed graphs
zbMATH Open document ID: 0968.03070
author: Jeffry L. Hirst
published in: Archive for Mathematical Logic
publication date: 2001-09-11T00:00:00Z
review text: This paper is part of the program of reverse mathematics [see \textit{S. G. Simpson}, Subsystems of second order arithmetic (Springer, Berlin) (1999; Zbl 0909.03048) for an introduction to this subject] and deals with existence and uniqueness of rank functions for directed graphs. Over the weak base theory \(\text{RCA}_0\) the system \(\text{ATR}_0\) is shown to be equivalent to the existence of a rank function for every countable well-founded directed graph. To prove uniqueness of the rank function \(\text{RCA}_0\) suffices. If the notion of rank is extended to non-well-founded graphs by assigning \(\infty\) to the vertices in the non-well-founded part of the graph then \(\Pi^1_1-\text{CA}_0\) turns out to be necessary and sufficient for the proof. Finally, \(\text{ACA}_0\) is the precise measure of the strength of the fact that a path bounded graph has a rank bounded by \(\omega\).
reviewed by: Alberto Marcone
Mathematics Subject Classification ID: 03F35
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1545482
zbMATH Keywords: reverse mathematics
zbMATH Keywords: directed graphs
MaRDI profile type: Publication
full work available at URL: s001530050165
OpenAlex ID: W2088241483
DOI: 10.1007/S001530050165
description: scientific article; zbMATH DE number 1545482