Well-quasi-orders on finite trees and transfinite sequences
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918331175403520 |
|---|---|
| author | Chopra, Alakh Dhruv Pakhomov, Fedor |
| author_facet | Chopra, Alakh Dhruv Pakhomov, Fedor |
| contents | We study the well-quasi-order (wqo) consisting of the set of finite trees with leaf labels coming from an arbitrary wqo $Q$, ordered by tree homomorphisms which respect the order on the labels. This is a variant of the usual Kruskal tree ordering without infima preservation. We calculate the precise maximal order types of this class of wqos as a function of the maximal order type of the labels $Q$. In the process, we sharpen some recent results of Friedman and Weiermann. Furthermore, we show a correspondence with indecomposable transfinite sequences with finite range, over elements of the wqo $Q$, of length less than $ω^ω$. Nash-Williams proved that arbitrary transfinite sequences with finite range are also well-quasi-ordered, but there are no known methods to extract bounds on the maximal order type from the proof. More concrete proofs for sequences of length less than $α$ for some $α< ω^ω$ were given by Erdős and Rado. Using the correspondence, we obtain precise bounds for the entire collection of transfinite sequences with finite range of length less than $ω^ω$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_09830 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Well-quasi-orders on finite trees and transfinite sequences Chopra, Alakh Dhruv Pakhomov, Fedor Logic Combinatorics 06A07, 03B30, 03F15, 03F35 We study the well-quasi-order (wqo) consisting of the set of finite trees with leaf labels coming from an arbitrary wqo $Q$, ordered by tree homomorphisms which respect the order on the labels. This is a variant of the usual Kruskal tree ordering without infima preservation. We calculate the precise maximal order types of this class of wqos as a function of the maximal order type of the labels $Q$. In the process, we sharpen some recent results of Friedman and Weiermann. Furthermore, we show a correspondence with indecomposable transfinite sequences with finite range, over elements of the wqo $Q$, of length less than $ω^ω$. Nash-Williams proved that arbitrary transfinite sequences with finite range are also well-quasi-ordered, but there are no known methods to extract bounds on the maximal order type from the proof. More concrete proofs for sequences of length less than $α$ for some $α< ω^ω$ were given by Erdős and Rado. Using the correspondence, we obtain precise bounds for the entire collection of transfinite sequences with finite range of length less than $ω^ω$. |
| title | Well-quasi-orders on finite trees and transfinite sequences |
| topic | Logic Combinatorics 06A07, 03B30, 03F15, 03F35 |
| url | https://arxiv.org/abs/2602.09830 |