Maximal order types for sequences with gap condition
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916868906811392 |
|---|---|
| author | Uftring, Patrick |
| author_facet | Uftring, Patrick |
| contents | Higman's lemma states that for any well partial order $X$, the partial order $X^*$ of finite sequences with members from $X$ is also well. By combining results due to Girard as well as Schütte and Simpson, one can show that Higman's lemma is equivalent to arithmetical comprehension over $\textsf{RCA}_0$, the usual base system of reverse mathematics. By incorporating Friedman's gap condition, Schütte and Simpson defined a slightly different order on finite number sequences with fewer comparisons. While it is still true that their definition yields a well partial order, it turns out that arithmetical comprehension is not enough to prove this fact. Gordeev considered a symmetric variation of this gap condition for sequences with members from arbitrary well orders. He could show, over $\textsf{RCA}_0$, that his partial order on sequences is well (for any underlying well order) if and only if arithmetical transfinite recursion is available. We present a new and simpler proof of this fact and extend Gordeev's results to weak and strong gap conditions as well as binary trees with weakly ascending labels. Moreover, we compute the maximal order types of all considered structures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_21877 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximal order types for sequences with gap condition Uftring, Patrick Logic 06A06, 03B30, 03F35, 03E10, 05C05, 03F15 Higman's lemma states that for any well partial order $X$, the partial order $X^*$ of finite sequences with members from $X$ is also well. By combining results due to Girard as well as Schütte and Simpson, one can show that Higman's lemma is equivalent to arithmetical comprehension over $\textsf{RCA}_0$, the usual base system of reverse mathematics. By incorporating Friedman's gap condition, Schütte and Simpson defined a slightly different order on finite number sequences with fewer comparisons. While it is still true that their definition yields a well partial order, it turns out that arithmetical comprehension is not enough to prove this fact. Gordeev considered a symmetric variation of this gap condition for sequences with members from arbitrary well orders. He could show, over $\textsf{RCA}_0$, that his partial order on sequences is well (for any underlying well order) if and only if arithmetical transfinite recursion is available. We present a new and simpler proof of this fact and extend Gordeev's results to weak and strong gap conditions as well as binary trees with weakly ascending labels. Moreover, we compute the maximal order types of all considered structures. |
| title | Maximal order types for sequences with gap condition |
| topic | Logic 06A06, 03B30, 03F35, 03E10, 05C05, 03F15 |
| url | https://arxiv.org/abs/2507.21877 |