Reverse mathematics of a uniform Kruskal-Friedman theorem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911102485397504 |
|---|---|
| author | Freund, Anton |
| author_facet | Freund, Anton |
| contents | The Kruskal-Friedman theorem asserts: in any infinite sequence of finite trees with ordinal labels, some tree can be embedded into a later one, by an embedding that respects a certain gap condition. This strengthening of the original Kruskal theorem has been proved by I. Kříž (Ann. Math. 1989), in confirmation of a conjecture due to H. Friedman, who had established the result for finitely many labels. It provides one of the strongest mathematical examples for the independence phenomenon from Gödel's theorems. The gap condition is particularly relevant due to its connection with the graph minor theorem of N. Robertson and P. Seymour. In the present paper, we consider a uniform version of the Kruskal-Friedman theorem, which extends the result from trees to general recursive data types. Our main theorem shows that this uniform version is equivalent both to $Π^1_1$-transfinite recursion and to a minimal bad sequence principle of Kříž, over the base theory $\mathsf{RCA_0}$ from reverse mathematics. This sheds new light on the role of infinity in finite combinatorics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2112_08727 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Reverse mathematics of a uniform Kruskal-Friedman theorem Freund, Anton Logic 03B30, 06A07, 05C83, 03F15, 03F35 The Kruskal-Friedman theorem asserts: in any infinite sequence of finite trees with ordinal labels, some tree can be embedded into a later one, by an embedding that respects a certain gap condition. This strengthening of the original Kruskal theorem has been proved by I. Kříž (Ann. Math. 1989), in confirmation of a conjecture due to H. Friedman, who had established the result for finitely many labels. It provides one of the strongest mathematical examples for the independence phenomenon from Gödel's theorems. The gap condition is particularly relevant due to its connection with the graph minor theorem of N. Robertson and P. Seymour. In the present paper, we consider a uniform version of the Kruskal-Friedman theorem, which extends the result from trees to general recursive data types. Our main theorem shows that this uniform version is equivalent both to $Π^1_1$-transfinite recursion and to a minimal bad sequence principle of Kříž, over the base theory $\mathsf{RCA_0}$ from reverse mathematics. This sheds new light on the role of infinity in finite combinatorics. |
| title | Reverse mathematics of a uniform Kruskal-Friedman theorem |
| topic | Logic 03B30, 06A07, 05C83, 03F15, 03F35 |
| url | https://arxiv.org/abs/2112.08727 |