Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\) (Q412061): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
m rollbackEdits.php mass rollback Tag: Rollback |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00153-012-0269-8 / rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1968578038 / rank | |||
Revision as of 16:54, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\) |
scientific article |
Statements
Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\) (English)
0 references
3 May 2012
0 references
The author studies the reverse mathematics of infinitary extensions of Menger's theorem from graph theory. The extension of finite Menger's theorem to countable graphs was proved in 1987 by \textit{R. Aharoni} [J. Comb. Theory, Ser. B 43, 303--313 (1987; Zbl 0631.05032)], but the extension to arbitrary graphs was only recently obtained by \textit{R. Aharoni} and \textit{E. Berger} [Invent. Math. 176, No. 1, 1--62 (2009; Zbl 1216.05092)]. The difficulty of the proof of the general result makes the theorem a natural candidate for reverse mathematics analysis. Previous work established only the lower bound that Menger's theorem for countable graphs implies the subsystem \(\text{ATR}_0\) of second-order arithmetic over the base system \(\text{RCA}_0\). This paper establishes an upper bound by showing that Menger's theorem for countable graphs is provable in the subsystem \(\Pi^1_1\text{-CA}_0\). The author poses the exact strength of Menger's theorem as an open question, but proves that a strengthened version, which the author calls extended Menger's theorem, is equivalent to \(\Pi^1_1\text{-CA}_0\) over \(\text{RCA}_0\). The proofs in \(\Pi^1_1\text{-CA}_0\) proceed via countable coded \(\beta\)-models and countable coded models of \(\Sigma^1_1\text{-DC}_0\).
0 references
reverse mathematics
0 references
graph theory
0 references
matching theory
0 references