Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\) (Q412061): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 6 users not shown) | |||
Property / review text | |||
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\). | |||
Property / review text: 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\). / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Carl Mummert / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03B30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03F35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C63 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C70 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6029798 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
reverse mathematics | |||
Property / zbMATH Keywords: reverse mathematics / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
graph theory | |||
Property / zbMATH Keywords: graph theory / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
matching theory | |||
Property / zbMATH Keywords: matching theory / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00153-012-0269-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1968578038 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Menger's theorem for countable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Menger's theorem for infinite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the strength of König's duality theorem for infinite bipartite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3374865 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4111536 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Injective choice functions for countable families / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the strength of König's duality theorem for countable bipartite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3395521 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 03:56, 5 July 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