Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2505.00893 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917126456999936 |
|---|---|
| author | Chen, Ruiyuan Gonzalez, David Harrison-Trainor, Matthew |
| author_facet | Chen, Ruiyuan Gonzalez, David Harrison-Trainor, Matthew |
| contents | The back-and-forth relations $M\leq_αN$ are central to computable structure theory and countable model theory. It is well-known that the relation $\{(M,N) : M \leq_αN\}$ is (lightface) $Π^0_{2α}$. We show that this is optimal as the set is $\mathbfΠ^0_{2α}$-complete. We are also interested in the one-sided relations $\{ N : M \leq_αN\}$ and $\{ N : M \geq_αN\}$ for a fixed $M$, measuring the $Π_α$ and $Σ_α$ types of $M$. We show that these sets are always $\mathbfΠ^0_{α+ 2}$ and $\mathbfΠ^0_{α+3}$ respectively, and that for most $α$ there are structures $M$ for which these relations are complete at that level. In particular, there are structures $M$ such that there is no $Π_α$ (or even $Π_{α+1})$ sentence $φ$ such that $N \models φ\Longleftrightarrow M \leq_αN$.
This is unfortunate as not all $Π_{α+2}$ sentences are preserved under $\leq_α$. We define a new hierarchy of syntactic complexity closely related to the back-and-forth game, which can both define the back-and-forth types as well as be preserved by them. These hierarchies of formulas have already been useful in certain Henkin constructions, one of which we give in this paper, and another previously used by Gonzalez and Harrison-Trainor to show that every $Π_α$ theory of linear orders has a model with Scott rank at most $α+3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_00893 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Syntactic Definitions of Back-and-Forth Types Chen, Ruiyuan Gonzalez, David Harrison-Trainor, Matthew Logic The back-and-forth relations $M\leq_αN$ are central to computable structure theory and countable model theory. It is well-known that the relation $\{(M,N) : M \leq_αN\}$ is (lightface) $Π^0_{2α}$. We show that this is optimal as the set is $\mathbfΠ^0_{2α}$-complete. We are also interested in the one-sided relations $\{ N : M \leq_αN\}$ and $\{ N : M \geq_αN\}$ for a fixed $M$, measuring the $Π_α$ and $Σ_α$ types of $M$. We show that these sets are always $\mathbfΠ^0_{α+ 2}$ and $\mathbfΠ^0_{α+3}$ respectively, and that for most $α$ there are structures $M$ for which these relations are complete at that level. In particular, there are structures $M$ such that there is no $Π_α$ (or even $Π_{α+1})$ sentence $φ$ such that $N \models φ\Longleftrightarrow M \leq_αN$. This is unfortunate as not all $Π_{α+2}$ sentences are preserved under $\leq_α$. We define a new hierarchy of syntactic complexity closely related to the back-and-forth game, which can both define the back-and-forth types as well as be preserved by them. These hierarchies of formulas have already been useful in certain Henkin constructions, one of which we give in this paper, and another previously used by Gonzalez and Harrison-Trainor to show that every $Π_α$ theory of linear orders has a model with Scott rank at most $α+3$. |
| title | Optimal Syntactic Definitions of Back-and-Forth Types |
| topic | Logic |
| url | https://arxiv.org/abs/2505.00893 |