$Π^0_4$ conservation of the Ordered Variable Word theorem
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910581735292928 |
|---|---|
| author | Houérou, Quentin Le Patey, Ludovic Levy |
| author_facet | Houérou, Quentin Le Patey, Ludovic Levy |
| contents | A left-variable word over an alphabet~$A$ is a word over~$A \cup \{\star\}$ whose first letter is the distinguished symbol~$\star$ standing for a placeholder. The Ordered Variable Word theorem ($\mathsf{OVW}$), also known as Carlson-Simpson's theorem, is a tree partition theorem, stating that for every finite alphabet~$A$ and every finite coloring of the words over~$A$, there exists a word $c_0$ and an infinite sequence of left-variable words $w_1, w_2, \dots$ such that $\{ c_0 \cdot w_1[a_1] \cdot \dots \cdot w_k[a_k] : k \in \mathbb{N}, a_1, \dots, a_k \in A \}$ is monochromatic.
In this article, we prove that $\mathsf{OVW}$ is $Π^0_4$-conservative over~$\mathsf{RCA}_0 + \mathsf{B}Σ^0_2$. This implies in particular that $\mathsf{OVW}$ does not imply $\mathsf{ACA}_0$ over~$\mathsf{RCA}_0$. This is the first principle for which the only known separation from~$\mathsf{ACA}_0$ involves non-standard models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_18749 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | $Π^0_4$ conservation of the Ordered Variable Word theorem Houérou, Quentin Le Patey, Ludovic Levy Logic 03F30, 03B30, 05D10 A left-variable word over an alphabet~$A$ is a word over~$A \cup \{\star\}$ whose first letter is the distinguished symbol~$\star$ standing for a placeholder. The Ordered Variable Word theorem ($\mathsf{OVW}$), also known as Carlson-Simpson's theorem, is a tree partition theorem, stating that for every finite alphabet~$A$ and every finite coloring of the words over~$A$, there exists a word $c_0$ and an infinite sequence of left-variable words $w_1, w_2, \dots$ such that $\{ c_0 \cdot w_1[a_1] \cdot \dots \cdot w_k[a_k] : k \in \mathbb{N}, a_1, \dots, a_k \in A \}$ is monochromatic. In this article, we prove that $\mathsf{OVW}$ is $Π^0_4$-conservative over~$\mathsf{RCA}_0 + \mathsf{B}Σ^0_2$. This implies in particular that $\mathsf{OVW}$ does not imply $\mathsf{ACA}_0$ over~$\mathsf{RCA}_0$. This is the first principle for which the only known separation from~$\mathsf{ACA}_0$ involves non-standard models. |
| title | $Π^0_4$ conservation of the Ordered Variable Word theorem |
| topic | Logic 03F30, 03B30, 05D10 |
| url | https://arxiv.org/abs/2404.18749 |