Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2409.03199 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910046658494464 |
|---|---|
| author | Altman, Harry |
| author_facet | Altman, Harry |
| contents | Given a well-quasi-order $X$ and an ordinal $α$, the set $s^F_α(X)$ of transfinite sequences on $X$ with length less than $α$ and with finite image is also a well-quasi-order, as proven by Nash-Williams. Before Nash-Williams proved it for general $α$, however, it was proven for $α<ω^ω$ by Erdős and Rado. In this paper, we revisit Erdős and Rado's proof and improve upon it, using it to obtain upper bounds on the maximum linearization of $s^F_{ω^k}(X)$ in terms of $k$ and $o(X)$, where $o(X)$ denotes the maximum linearization of $X$. We show that, for fixed $k$, $o(s^F_{ω^k}(X))$ is bounded above by a function which can roughly be described as $(k+1)$-times exponential in $o(X)$. We also show that, for $k\le 2$, this bound is not far from tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03199 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bounding finite-image sequences of length $ω^k$ Altman, Harry Logic 03E10 Given a well-quasi-order $X$ and an ordinal $α$, the set $s^F_α(X)$ of transfinite sequences on $X$ with length less than $α$ and with finite image is also a well-quasi-order, as proven by Nash-Williams. Before Nash-Williams proved it for general $α$, however, it was proven for $α<ω^ω$ by Erdős and Rado. In this paper, we revisit Erdős and Rado's proof and improve upon it, using it to obtain upper bounds on the maximum linearization of $s^F_{ω^k}(X)$ in terms of $k$ and $o(X)$, where $o(X)$ denotes the maximum linearization of $X$. We show that, for fixed $k$, $o(s^F_{ω^k}(X))$ is bounded above by a function which can roughly be described as $(k+1)$-times exponential in $o(X)$. We also show that, for $k\le 2$, this bound is not far from tight. |
| title | Bounding finite-image sequences of length $ω^k$ |
| topic | Logic 03E10 |
| url | https://arxiv.org/abs/2409.03199 |