Pith. sign in

REVIEW 5 minor 33 references

Information at level 2α can be coded into structures that already differ at level α, and the resulting bounds for Scott sentences and back-and-forth formulas are sharp.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Belligerent jump inversion extends unfriendly coding uniformly through the computable ordinals and yields optimal syntactic-oracle trade-offs for Scott sentences and distinguishing formulas.

T0 review reviewed 2026-07-14 challenge →

load-bearing objection Solid, reusable black-box theorems that cleanly extend finite unfriendly inversion through the computable ordinals and settle the optimal oracle/quantifier trade-offs for Scott sentences.

arxiv 2607.10935 v1 pith:MGPEQ343 submitted 2026-07-12 math.LO

Infinite Belligerent Jump Inversion and Computable Scott Analysis

Uri Andrews , David Gonzalez , Hongyu Zhu This is my paper
classification math.LO MSC 03C5703D45
keywords Scott rankback-and-forth relationsScott complexityjump inversioncomputable infinitary logicbelligerent pairscomputable structures
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

In computable structure theory, many notions that live at Scott level α turn out to have effective complexity roughly twice as high. The paper supplies a uniform coding method, called belligerent pairs and belligerent jump inversion, that compresses 2α-level information into computable structures whose distinguishing features already appear at level α. The method extends the known finite case through all computable ordinals. With it the authors determine the exact oracle needed to produce a Π_α Scott sentence for any computable structure that possesses one, and they show that every such structure also has a fully computable Π_2α Scott sentence; both bounds are optimal. Parallel sharp results hold for formulas that witness the failure of an α-back-and-forth relation. The same machinery settles a question on the complexity of back-and-forth classes and yields hardness results for the index set of structures of given Scott rank.

Core claim

For every computable infinite ordinal α, any computable structure that admits a Π_in_α Scott sentence admits both a 0^(γ(α))-computable Π_in_α Scott sentence and a fully computable Π_in_2α Scott sentence; both bounds are sharp. The same compression of complexity yields matching optimal results for formulas that separate two computable structures under the α-back-and-forth relation.

What carries the argument

Belligerent Pairs Theorem and Belligerent Jump Inversion Theorem: a pair of structures that differ already at level α+1 can still code an arbitrary Σ^0_2α+1 set, so that higher-jump information is reflected in lower-level structural distinctions.

Load-bearing premise

The construction for limit ordinals rests on the classical Ash linear orders being friendly at those levels and carrying exactly the Scott sentences claimed for them; if either property fails for some limit, the reduction from the general case to the finite case collapses.

What would settle it

Exhibit a computable structure of Scott complexity Π_in_α that possesses neither a 0^(γ(α))-computable Π_in_α Scott sentence nor a computable Π_in_2α Scott sentence, or produce two computable structures that differ at level α yet cannot code a complete Σ^0_2α+1 set.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper develops two coding tools—the Belligerent Pairs Theorem (Theorem 2.23) and the Belligerent Jump Inversion Theorem (Theorem 2.24)—that compress 2α-level information into computable structures whose distinguishing features appear already at level α. These extend Harrison-Trainor’s finite unfriendly jump inversion uniformly through the computable ordinals. The main applications determine the optimal oracle and quantifier trade-offs for Scott sentences and for formulas witnessing failure of the α-back-and-forth relation: any computable structure with a Π_in_α Scott sentence has a 0^(γ(α))-computable Π_in_α Scott sentence and a computable Π_in_2α Scott sentence, both bounds sharp (Theorem 1.2); analogous sharp results hold for distinguishing formulas (Theorem 1.3). Further applications resolve a question of Chen–Gonzalez–Harrison-Trainor on the complexity of back-and-forth classes (Theorem 1.6) and give matching hardness for the index set of structures of Scott rank ≤α.

Significance. The work supplies a uniform, black-box complexity-compression mechanism that was previously available only at finite levels. The resulting sharp bounds for lightface Scott sentences and for α-back-and-forth distinctions close long-standing gaps between syntactic and oracle complexity in computable structure theory. The tools themselves (especially the seven-clause Jump Inversion Theorem) are reusable for future constructions that need to encode 2α information at level α. The resolution of the Chen–Gonzalez–Harrison-Trainor question and the matching hardness results for Scott-rank index sets further demonstrate the reach of the method. All constructions are fully explicit and reduce to classical Ash pairs plus the published finite unfriendly inversion, so the results rest on solid, previously verified foundations.

minor comments (5)
  1. Definition 1.1 of γ(α) is clear, but a short parenthetical remark that γ(α)+α is the least ordinal ≥ 2α would help readers who encounter the function for the first time.
  2. In the proof of Theorem 3.3 (limit case) the appeal to Lemma 2.3 is immediate; a one-sentence reminder that 2λ=λ for limit λ would make the reduction fully self-contained.
  3. Proposition 4.1 invokes Ash 1986 for the friendliness and Scott sentences of (ω^λ,<) and (ω^λ·2,<). Adding the precise theorem numbers from Ash would improve traceability.
  4. Several places (e.g., the statement of Theorem 2.24(2) and (4)) contain parenthetical remarks distinguishing the finite and infinite cases; these could be collected into a single remark after the theorem for cleaner reading.
  5. Typographical slips: “sturcture” (p. 9), “furthremore” (p. 17), “prediacte” (p. 21), “sepcific” (p. 29). A final proof-reading pass will catch them.

Circularity Check

0 steps flagged

No significant circularity: constructions are explicit inductive reductions to classical Ash pairs and published finite unfriendly inversion; target bounds are derived, not assumed.

full rationale

The paper's central claims (Theorems 1.2–1.3, 2.23–2.24) are obtained by an explicit two-stage construction: (i) at limit ordinals λ the classical Ash pairs (ω^λ, <) and (ω^λ·2, <) are used (Proposition 4.1, citing Ash 1986) together with the ordinary Pair of Structures Theorem to produce a friendly jump inversion (Proposition 4.2); (ii) the general case α = λ + n is obtained by composing that limit inversion with the already-published finite unfriendly inversion of Harrison-Trainor (Theorem 2.21, cited as [HT25]) relativized to 0^(λ+1). Both base ingredients are external, independently verified results; the paper supplies the full inductive details of the composition (§§4.1–4.2) and the subsequent applications that establish sharpness (Theorems 5.1, 5.5, 5.6 and Corollaries 5.3–5.4). No equation is forced by a fitted parameter, no uniqueness theorem is imported solely from overlapping authors, and no target bound is smuggled into the definition of the coding structures. Self-citations appear only as black-box base cases whose statements are already in the literature. The derivation is therefore self-contained against external benchmarks and exhibits no circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 2 invented entities

The paper works entirely inside classical ZFC + the standard apparatus of computable structure theory. No free parameters are fitted. The only non-standard entities are the deliberately constructed “belligerent” pairs and the inverted graphs G^(-α); both are defined explicitly and their properties are proved rather than postulated. Background results (Ash pairs, Pair of Structures Theorem, Harrison-Trainor finite inversion, Vanden Boom effective Lopez-Escobar) are cited with precise references.

axioms (4)
  • domain assumption Classical Ash pairs (ω^λ,<) and (ω^λ·2,<) are λ-friendly and possess the stated Scott sentences (Ash 1986).
    Invoked in Proposition 4.1 to obtain the limit-case belligerent pairs; if false the inductive reduction fails.
  • domain assumption Harrison-Trainor finite unfriendly jump inversion (Theorems 2.21–2.22) holds for every finite n.
    Used as the base case that is then inverted at limit ordinals; cited as [HT25].
  • standard math Pair of Structures Theorem (Ash–Knight): α-friendly pairs with A ≤_α B are (Σ^{0}_α,Π^{0}_α)-hard.
    Standard black-box tool used both for comparison and inside the limit-case construction.
  • standard math Vanden Boom effective Lopez-Escobar theorem: lightface Π^{0}_α isomorphism-invariant classes are defined by computable Π^c_α formulas.
    Used in the proof of clause (4) of the Jump Inversion Theorem to recover formulas of lower complexity.
invented entities (2)
  • Belligerent pairs (A,B) of Theorem 2.23 independent evidence
    purpose: Encode an arbitrary Σ^{0}_{2α+1} set into the isomorphism type of a computable sequence while differing already at the Π_in_{α+1} level.
    Explicitly constructed by composing finite unfriendly pairs with limit inversion; properties proved rather than assumed.
  • Belligerent jump inversion G ↦ G^(-α) independent evidence
    purpose: Produce a computable graph whose Scott complexity and isomorphism type recover those of an arbitrary 0^(2α+1)-computable graph after exactly α jumps.
    Defined by edge-replacement using the belligerent pairs; all seven listed properties are verified by direct induction.

reviewed 2026-07-14 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Infinite Belligerent Jump Inversion and Computable Scott Analysis." pith.science (2026). https://pith.science/paper/MGPEQ343

@misc{pith2026260710935,
  author       = {Pith},
  title        = {Pith review of: Infinite Belligerent Jump Inversion and Computable Scott Analysis},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MGPEQ343}},
  note         = {Machine review of arXiv:2607.10935}
}
Share X Bluesky LinkedIn Reddit HN
abstract

Scott analysis provides two fundamental tools for studying countable structures: Scott sentences, which characterize structures up to isomorphism, and back-and-forth relations, which measure structural similarity. A recurring phenomenon in computable structure theory is that many notions naturally associated with level $\alpha$ of Scott analysis have effective complexity at approximately $2\alpha$ jumps. This discrepancy appears both in the complexity of the back-and-forth relations and in the passage from arbitrary infinitary formulas to computable infinitary formulas. We develop two new coding tools, the Belligerent Pairs Theorem and Belligerent Jump Inversion Theorem, which allow information at complexity level $2\alpha$ to be reflected in computable structures whose distinguishing features already appear at level $\alpha$. These results extend Harrison-Trainor's finite unfriendly jump inversion uniformly throughout the computable ordinals. As applications, we determine the optimal interaction between syntactic complexity and oracle complexity for computable Scott sentences and for formulas distinguishing computable structures. For every computable infinite ordinal $\alpha$, we determine the oracle needed to compute a $\Pi_\alpha$ Scott sentence for a computable structure which has a $\Pi_\alpha$ Scott sentence. Any computable structure with a $\Pi_\alpha$ Scott sentence has a computable $\Pi_{2\alpha}$ Scott sentence. We show that both of these bounds are sharp. We prove analogous optimal results for formulas witnessing failure of the $\alpha$-back-and-forth relation. We also obtain further applications, including a resolution of a question of Chen, Gonzalez, and Harrison-Trainor concerning the complexity of back-and-forth classes.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 10 canonical work pages

  1. [1]

    Computable structure theory---within the arithmetic , url =

    Montalb\'. Computable structure theory---within the arithmetic , url =. 2021 , bdsk-url-1 =. doi:10.1017/9781108525749 , isbn =

    work page doi:10.1017/9781108525749 2021

  2. [2]

    Lavrov, I. A. , date-added =. The effective non-separability of the set of identically true formulae and the set of finitely refutable formulae for certain elementary theories , volume =. Algebra i Logika Sem. , mrclass =

  3. [3]

    , date-added =

    Miller, Arnold W. , date-added =. On the. Notre Dame J. Formal Logic , mrclass =. 1983 , bdsk-url-1 =

    1983

  4. [4]

    and McCoy CSC, Charles , date-added =

    Alvir, Rachael and Knight, Julia F. and McCoy CSC, Charles , date-added =. Complexity of. Fund. Math. , mrclass =. 2020 , bdsk-url-1 =. doi:10.4064/fm865-6-2020 , fjournal =

    work page doi:10.4064/fm865-6-2020 2020

  5. [5]

    Scott complexity of countable structures , url =

    Alvir, Rachael and Greenberg, Noam and Harrison-Trainor, Matthew and Turetsky, Dan , date-added =. Scott complexity of countable structures , url =. J. Symb. Log. , mrclass =. 2021 , bdsk-url-1 =. doi:10.1017/jsl.2021.4 , fjournal =

    work page doi:10.1017/jsl.2021.4 2021

  6. [6]

    Macintyre, John M. , doi =. Transfinite extensions of Friedberg's completeness criterion , volume =. Journal of Symbolic Logic , number =. 1977 , bdsk-url-1 =

    1977

  7. [7]

    Invariant sets in topology and logic , url =

    Vaught, Robert , date-added =. Invariant sets in topology and logic , url =. Fund. Math. , mrclass =. 1974/75 , bdsk-url-1 =. doi:10.4064/fm-82-3-269-294 , fjournal =

    work page doi:10.4064/fm-82-3-269-294 1974

  8. [8]

    Lopez-Escobar, E. G. K. , date-added =. An interpolation theorem for denumerably long formulas , volume =. Fund. Math. , mrclass =

  9. [9]

    Non _n axiomatizable almost strongly minimal theories , volume =

    David Marker , date-added =. Non _n axiomatizable almost strongly minimal theories , volume =. J. Symb. Log. , number =

  10. [10]

    Antonio Montalb\'an , date-added =

  11. [11]

    Priority arguments via true stages , url =

    Montalb. Priority arguments via true stages , url =. Journal of Symbolic Logic , mrclass =. 2014 , bdsk-url-1 =. doi:10.1017/jsl.2014.11 , fjournal =

    work page doi:10.1017/jsl.2014.11 2014

  12. [12]

    Harrington , date-added =

    L. Harrington , date-added =. McLaughlin's Conjecture , year =

  13. [13]

    , date-added =

    Lachlan, Alistair H. , date-added =. A recursively enumerable degree which will not split over all lesser ones , url =. Ann. Math. Logic , mrclass =. 1976 , bdsk-url-1 =. doi:10.1016/0003-4843(76)90016-4 , fjournal =

    work page doi:10.1016/0003-4843(76)90016-4 1976

  14. [14]

    Sacks , date-added =

    G.E. Sacks , date-added =. Recursive enumerability and the jump operator , url =. Trans. Amer. Math. Soc. , mrclass =. 1963 , bdsk-url-1 =. doi:10.2307/1993604 , fjournal =

    work page doi:10.2307/1993604 1963

  15. [15]

    Shoenfield, J. R. , date-added =. Undecidable and creative theories , url =. Fund. Math. , mrclass =. 1960/61 , bdsk-url-1 =. doi:10.4064/fm-49-2-171-179 , fjournal =

    work page doi:10.4064/fm-49-2-171-179 1960

  16. [16]

    A. A. Muchnik , date-added =. On the unsolvability of the problem of reducibility in the theory of algorithms , volume =. Dokl. Akad. Nauk SSSR, N.S. , pages =

  17. [17]

    , date-added =

    Friedberg, Richard M. , date-added =. Two recursively enumerable sets of incomparable degrees of unsolvability (solution of. Proc. Nat. Acad. Sci. U.S.A. , mrclass =

  18. [18]

    Knight and Karen Lange and Charles McCoy , date-added =

    Julia F. Knight and Karen Lange and Charles McCoy , date-added =

  19. [19]

    , booktitle =

    Karp, Carol R. , booktitle =. Finite-quantifier equivalence , year =

  20. [20]

    A robuster Scott rank , url =

    Montalb. A robuster Scott rank , url =. Proc. Amer. Math. Soc. , mrclass =. 2015 , bdsk-url-1 =. doi:10.1090/proc/12669 , fjournal =

    work page doi:10.1090/proc/12669 2015

  21. [21]

    Logic with denumerably long formulas and finite strings of quantifiers , year =

    Scott, Dana , booktitle =. Logic with denumerably long formulas and finite strings of quantifiers , year =

  22. [22]

    and Knight, J

    Ash, C.J. and Knight, J. , date-added =. Computable Structures and the Hyperarithmetical Hierarchy , year =

  23. [23]

    The structural complexity of models of arithmetic , volume =

    Montalb\'an, Antonio and Rossegger, Dino , date-added =. The structural complexity of models of arithmetic , volume =. Journal of Symbolic Logic , pages =

  24. [24]

    Knight , date-added =

    David Gonzalez and Julia F. Knight , date-added =

  25. [25]

    Computable structure theory: Beyond the arithmetic , year =

    Antonio Montalb\'an , date-added =. Computable structure theory: Beyond the arithmetic , year =

  26. [26]

    Optimal syntactic definitions of back-and-forth types , year =

    Ruiyan Chen and David Gonzalez and Matthew Harrison-Trainor , date-added =. Optimal syntactic definitions of back-and-forth types , year =

  27. [27]

    On the computability of optimal Scott sentences , year =

    Rachael Alvir and Barbara Csima and Matthew Harrison-Trainor , date-added =. On the computability of optimal Scott sentences , year =

  28. [28]

    Relative to any non-arithmetic set , year =

    Matthew Harrison-Trainor , date-added =. Relative to any non-arithmetic set , year =

  29. [29]

    Enumerations in computable structure theory , url =

    Goncharov, Sergey and Harizanov, Valentina and Knight, Julia and McCoy, Charles and Miller, Russell and Solomon, Reed , coden =. Enumerations in computable structure theory , url =. Ann. Pure Appl. Logic , mrclass =. 2005 , bdsk-url-1 =. doi:10.1016/j.apal.2005.02.001 , fjournal =

    work page doi:10.1016/j.apal.2005.02.001 2005

  30. [30]

    Ash, C. J. and Knight, J. F. , coden =. Pairs of recursive structures , volume =. Ann. Pure Appl. Logic , mrclass =

  31. [31]

    Ash, C. J. , coden =. Stability of recursive structures in arithmetical degrees , volume =. Ann. Pure Appl. Logic , mrclass =

  32. [32]

    Miller , issn =

    Uri Andrews and Joseph S. Miller , issn =. SPECTRA OF THEORIES AND STRUCTURES , url =. Proceedings of the American Mathematical Society , number =. 2015 , bdsk-url-1 =

    2015

  33. [33]

    The effective Borel hierarchy , url =

    M. The effective Borel hierarchy , url =. Fundamenta Mathematicae , keywords =. 2007 , bdsk-url-1 =

    2007

This paper was first reviewed by grok-4.5 on July 14, 2026.