Optimal Syntactic Definitions of Back-and-Forth Types
Ruiyuan Chen, David Gonzalez, Matthew Harrison-Trainor · 2025
Read Optimal Syntactic Definitions of Back-and-Forth Types by Ruiyuan Chen, David Gonzalez, Matthew Harrison-Trainor (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00893.txt.
Introduction
Chen, Gonzalez, and Harrison-Trainor pin the best clause forms for swap-game types. Swap links twixt forms sit at the heart of count-form work. The set of form pairs at a swap grade is known in rank terms. The team shows that rank is the best that can be had. The set proves full at that rank in their count frame. One-side sets, with one form fixed, get the same care.
Those sets grade the fixed form's two swap types in rank terms. The team shows fixed low ranks for both one-side sets. For most grades, forms exist that fill those ranks in full. A sad twist: low clause forms may fail to catch the type. Not all low forms hold safe when the swap grade shifts. A new rank chain, tied to the swap game, cures that flaw.
Catalog record
| CREATOR | Ruiyuan Chen, David Gonzalez, Matthew Harrison-Trainor |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 132 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-00893
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal Syntactic Definitions of Back-and-Forth Types Thanks: The first author acknowledges support from the National Science Foundation under Grant No. DMS-2224709 . The third author acknowledges support from a Sloan Research Fellowship and from the National Science Foundation under Grant No. DMS-2153823 . Ruiyuan Chen, David Gonzalez, Matthew Harrison-Trainor Abstract . The back-and-forth relations ℳ ≤ α 𝒩 \mathcal{M}\leq_{\alpha}\mathcal{N} are central to computable structure theory and countable model theory. It is well-known that the relation { ( ℳ , 𝒩 ) : ℳ ≤ α 𝒩 } \{(\mathcal{M},\mathcal{N}):\mathcal{M}\leq_{\alpha}\mathcal{N}\} is (lightface) Π 2 α 0 \Pi^{0}_{2\alpha} . We show that this is optimal as the set is 𝚷 2 α 0 \mathbf{\Pi}^{0}_{2\alpha} -complete. We are also interested in the one-sided relations { 𝒩 : ℳ ≤ α 𝒩 } \{\mathcal{N}:\mathcal{M}\leq_{\alpha}\mathcal{N}\} and { 𝒩 : ℳ ≥ α 𝒩 } \{\mathcal{N}:\mathcal{M}\geq_{\alpha}\mathcal{N}\} for a fixed ℳ \mathcal{M} , measuring the Π α \Pi_{\alpha} and Σ α \Sigma_{\alpha} types of ℳ \mathcal{M} . We show that these sets are always 𝚷 α + 2 0 \mathbf{\Pi}^{0}_{\alpha+2} and 𝚷 α + 3 0 \mathbf{\Pi}^{0}_{\alpha+3} respectively, and that for most α \alpha there are structures ℳ \mathcal{M} for which these relations are complete at that level. In particular, there are structures ℳ \mathcal{M} such that there is no Π α \Pi_{\alpha} (or even OPEN Π α + 1 ) \Pi_{\alpha+1}) sentence φ \varphi such that 𝒩 ⊧ φ ⟺ ℳ ≤ α 𝒩 \mathcal{N}\models\varphi\Longleftrightarrow\mathcal{M}\leq_{\alpha}\mathcal{N} . This is unfortunate as not all Π α + 2 \Pi_{\alpha+2} sentences are preserved under ≤ α \leq_{\alpha} . 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 Π α \Pi_{\alpha} theory of linear orders has a model with Scott rank at most α + 3 \alpha+3 . 1991 Mathematics Subject Classification 03C15, 03C57, 03D45, 03E15, 03C75 1. Introduction Originally used to prove that any two countable dense linear orders without endpoints are isomorphic, the back-and-forth method is a classical tool in mathematical logic dating back over one hundred years. A general viewpoint, beginning with Ehrenfeucht [ 8 ] and Fraïssé [ 9 ] , is that by playing back-and-forth games between two first-order structures \mathcal{M} and \mathcal{N} we can capture which sets of formulas they agree on. Generally two players, Spoiler and Duplicator , take turns playing elements from the two structures, with Duplicator trying to maintain atomic facts between the elements in \mathcal{M} and the elements in \mathcal{N} . In the Ehrenfeucht–Fraïssé game most commonly used in model theory, both players play single elements, and (in a finite language) the second player wins the game of length n if and only if the two structures \mathcal{M} and \mathcal{N} satisfy the same sentences with quantifier depth n . Other versions, such as pebble games, can be used for finite variable logics. In this paper, we work with the back-and-forth game that corresponds to infinitary logic, and our main goal is to understand the complexity of deciding which player has a winning strategy. The key features of this particular back-and-forth game are that (a) on their turn, players play tuples of arbitrary size with the size chosen by Spoiler , (b) Spoiler must alternate between playing in \mathcal{M} and playing in \mathcal{N} , with Duplicator alternating between playing in \mathcal{N} and playing in \mathcal{M} , and (c) the games are played over a possibly infinite ordinal clock. This back-and-forth game yields the back-and-forth relations. (For simplicity, we assume that all languages in this paper are relational.) 1.1 . The standard asymmetric back-and-forth relations \leq_{\alpha} , for a countable ordinal \alpha<\omega_{1} , are defined by: item• (\mathcal{M},\bar{a})\leq_{0}(\mathcal{N},\bar{b}) if \bar{a} and \bar{b} satisfy the same quantifier-free formulas from among the first |\bar{a}| -many formulas. item• For \alpha>0 , (\mathcal{M},\bar{a})\leq_{\alpha}(\mathcal{N},\bar{b}) if for each \beta<\alpha and \bar{d}\in\mathcal{N} there is \bar{c}\in\mathcal{M} such that (\mathcal{N},\bar{b}\bar{d})\leq_{\beta}(\mathcal{M},\bar{a}\bar{c}) . We define \bar{a}\equiv_{\alpha}\bar{b} if \bar{a}\leq_{\alpha}\bar{b} and \bar{b}\leq_{\alpha}\bar{a} . The interpretation of (\mathcal{M},\bar{a})\leq_{\alpha}(\mathcal{N},\bar{b}) is that in the back-and-forth game between \mathcal{M} and \mathcal{N} , starting with the partial isomorphism \bar{a}\mapsto\bar{b} and with the first player Spoiler to play next in \mathcal{N} , the second player Duplicator can play without losing along an ordinal clock \alpha . The content of the classical back-and-forth argument is then that if Duplicator can continue playing forever, and \mathcal{M} and \mathcal{N} are countable, then \mathcal{M}\cong\mathcal{N} . The back-and-forth relations are a measure of similarity between (\mathcal{M},\bar{a}) and (\mathcal{N},\bar{b}) . For example, for Boolean algebras A and B : item 1(1) A\leq_{1}B means that A has at least as many elements as B ; item 2(2) A\leq_{2}B means that A and B have the same number of elements and that A has at least as many atoms as B ; item 3(3) A\leq_{n}B for n\geq 3 is determined in general by how A and B split up into atoms, atomless subalgebras, 1 -atoms, and so on. See [ 13 ] . Back-and-forth types have been central in the computability-theoretic study of Boolean algebras and particularly in the study of low n Boolean algebras [ 7 , 30 , 18 , 15 ] . For linear orders, L\leq_{1}M means that M has at least as many elements as L , and L\leq_{2}M is more complicated, but Montalbán [ 25 ] gives a complete description of \equiv_{2} for linear orders. For some particular linear orders the back-and-forth relations are easier to describe, e.g., in [ 6 ] it is shown that for \gamma\geq 1 , \omega^{\beta}\leq_{2\gamma}\omega^{\alpha} if and only if \alpha,\beta\geq\gamma or \alpha=\beta . For algebraic fields \mathbb{Q}\subseteq E,F\subseteq\overline{\mathbb{Q}} , E\leq_{1}F means that every polynomial p(z)\in\mathbb{Q}[x] which as a root in F has a root in E , and E\equiv_{1}F means that E and F are isomorphic which reflects the fact that it is easy to classify algebraic fields up to isomorphism. For general fields E and F the back-and-forth relations are harder to describe, but for example E\leq_{2}F implies that every finitely generated subfield of F is (isomorphic to) a subfield of E . For every \alpha , there are fields E and F such that E\equiv_{\alpha}F but E\ncong F . 1 1 1 This is a consequence of the Borel completeness of fields, see [ 10 ] or [ 21 ] . These back-and-forth relations are related to the infinitary logic \mathcal{L}_{\omega_{1}\omega} which extends the standard finitary first-order logic by allowing countably infinite disjunctions and conjunctions. The formulas of \mathcal{L}_{\omega_{1}\omega} are stratified in terms of their complexity as measured by counting the number of alternations between existential and universal quantifiers. For an ordinal \alpha<\omega_{1} : item – A formula is \Sigma_{0} and \Pi_{0} if it is finitary quantifier-free. item – A formula is \Sigma_{\alpha} if it is of the form \bigdoublevee_{i}\exists\bar{x}_{i}\psi_{i}(\bar{x}_{i}) where each \psi_{i} is \Pi_{\beta} for some \beta<\alpha . item – A formula is \Pi_{\alpha} if it is of the form \bigdoublewedge_{i}\forall\bar{x}_{i}\psi_{i}(\bar{x}_{i}) where each \psi_{i} is \Pi_{\beta} for some \beta<\alpha . The back-and-forth relations \leq_{\alpha} characterize when two structures \mathcal{M} and \mathcal{N} satisfy the