pith. sign in

arxiv: 2606.27151 · v1 · pith:4M2IQZU5new · submitted 2026-06-25 · 🧮 math.LO

Scott complexity of trees of finite rank via degrees of categoricity

Mohammad Mahmoud This is my paper

Pith reviewed 2026-06-26 02:04 UTC · model grok-4.3

classification 🧮 math.LO
keywords Scott rankScott sentence complexityfinite rank treesdegrees of categoricityautomorphism orbitsL omega1 omega definabilitytransfer principleboldface computability
0
0 comments X

The pith

Uniform degree-of-categoricity lower bounds force trees of rank m+1 to have Scott rank exactly 2m+1.

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

The paper isolates a transfer principle showing that any degree-of-categoricity lower bound holding uniformly relative to every oracle defeats L_{\omega_1\omega}-definability of automorphism orbits. The authors verify that their prior construction of computable trees of rank m+1 satisfies this uniformity property. Applying the principle yields that the isomorphism type A_{m+1} has Scott rank exactly 2m+1 in Montalbán's sense, with Scott sentence complexity falling in one of three classes. For the rank-2 case they complete the analysis, proving the orbit of infinite-degree level-one nodes is \Pi_2 but not \Sigma_2 definable and that SSC(A_2) equals \Pi_4 exactly via a computable \Pi_4 Scott sentence.

Core claim

Our construction of rank-(m+1) trees has the property that its degree-of-categoricity lower bound holds uniformly relative to every oracle. By the transfer principle this uniformity defeats L_{\omega_1\omega}-definability of automorphism orbits outright. Therefore the Scott rank of A_{m+1} is exactly 2m+1 and its Scott sentence complexity is one of \Sigma_{2m+1}, d\Sigma_{2m+1}, or \Pi_{2m+2}. For rank 2 the orbit of the level-one nodes of infinite degree is \Pi_2- but not \Sigma_2-definable and SSC(A_2)=\Pi_4 exactly, witnessed by a computable \Pi_4 Scott sentence. The conjecture that SSC(A_{m+1})=\Pi_{2m+2} for all finite m reduces to a single back-and-forth substitution lemma.

What carries the argument

The transfer principle that a degree-of-categoricity lower bound uniform relative to every oracle defeats L_{\omega_1\omega}-definability of automorphism orbits.

If this is right

  • The isomorphism type A_{m+1} has Scott rank exactly 2m+1.
  • The Scott sentence complexity of A_{m+1} is one of \Sigma_{2m+1}, d\Sigma_{2m+1}, or \Pi_{2m+2}.
  • The orbit of level-one nodes of infinite degree in A_2 is \Pi_2-definable but not \Sigma_2-definable.
  • There exists a computable \Pi_4 Scott sentence for A_2.
  • The conjecture SSC(A_{m+1})=\Pi_{2m+2} reduces to a back-and-forth substitution lemma.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The transfer principle may apply to other structures whose categoricity degrees are known to be uniform, yielding Scott-rank bounds in those classes as well.
  • The results open a route to classifying Scott sentence complexities for all finite-rank trees by extending the rank-2 analysis.
  • The link between the 2\alpha-jump phenomenon and Scott spectral gaps suggests that similar uniformity arguments could bound infinitary definability in broader classes of computable structures.

Load-bearing premise

The construction satisfies the uniformity property that its degree-of-categoricity lower bound holds relative to every oracle.

What would settle it

An L_{\omega_1\omega} formula of complexity below the predicted level that defines the orbit of the infinite-degree level-one nodes in A_2, or a counterexample structure with uniform categoricity lower bound whose orbits remain definable in L_{\omega_1\omega}.

read the original abstract

In earlier work we constructed, for each computable ordinal $\alpha$, a computable tree of rank $\alpha+1$ whose strong degree of categoricity is $\mathbf{0}^{(2\alpha)}$ for finite $\alpha$ (and $\mathbf{0}^{(2\alpha+1)}$ for infinite $\alpha$), and showed these degrees are optimal. Those results are lightface: they concern computable copies and Turing degrees of isomorphisms. In this paper we determine the boldface content of the construction. We isolate a simple transfer principle showing that a degree-of-categoricity lower bound which holds \emph{uniformly relative to every oracle} defeats $L_{\omega_1\omega}$-definability of automorphism orbits outright, and we verify that our construction has this uniformity. Writing $\A_{m+1}$ for the isomorphism type of our rank-$(m+1)$ trees ($m\geq 1$ finite), we conclude that $\A_{m+1}$ has Scott rank exactly $2m+1$ in the sense of Montalb\'an, and that its Scott sentence complexity is one of $\Sin{2m+1}$, $\dSin{2m+1}$, or $\Pin{2m+2}$. For rank $2$ we carry out a complete Scott analysis: the orbit of the level-one nodes of infinite degree is $\Pin{2}$- but not $\Sin{2}$-definable, and $\SSC(\A_2)=\Pin{4}$ exactly, witnessed by a computable $\Pc{4}$ Scott sentence. We conjecture $\SSC(\A_{m+1})=\Pin{2m+2}$ for all finite $m$ and reduce the conjecture to a single back-and-forth substitution lemma. These results begin a classification of the Scott sentence complexities of trees, in analogy with the Gonzalez--Rossegger analysis of linear orders, and connect the $2\alpha$-jump phenomenon in degrees of categoricity to Scott spectral gap questions of Harrison-Trainor and Kim.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper extends prior lightface results on degrees of categoricity for computable trees of finite rank to the boldface setting. It isolates a transfer principle converting a uniform (oracle-relative) lower bound on the degree of categoricity into the non-existence of an L_{\omega_1\omega} definition for the relevant automorphism orbits. Applying this to the earlier construction of trees A_{m+1} of rank m+1 yields that these structures have Scott rank exactly 2m+1 (Montalbán sense) and Scott-sentence complexity in {\Sigma_{2m+1}, d\Sigma_{2m+1}, \Pi_{2m+2}}. A complete analysis is given for rank 2 (orbit of infinite-degree level-1 nodes is \Pi_2 but not \Sigma_2; SSC(A_2)=\Pi_4 exactly, witnessed by a computable \Pi_4 Scott sentence). The paper conjectures SSC(A_{m+1})=\Pi_{2m+2} for all finite m and reduces the conjecture to a single back-and-forth substitution lemma.

Significance. If the uniformity hypothesis is verified as claimed, the transfer principle supplies a general method for converting computability-theoretic lower bounds into infinitary-logic conclusions about Scott rank and sentence complexity. The explicit rank-2 analysis and the reduction of the higher-rank conjecture to a concrete lemma are concrete strengths. The work begins a classification of Scott-sentence complexities for trees parallel to the González-Rossegger analysis of linear orders and links the 2\alpha-jump phenomenon in degrees of categoricity to Harrison-Trainor-Kim spectral-gap questions.

major comments (1)
  1. [Transfer principle and uniformity verification] The transfer principle (isolated after the lightface recall) asserts that a degree-of-categoricity lower bound holding uniformly relative to every oracle X defeats L_{\omega_1\omega}-definability of the automorphism orbits. The verification that the given trees satisfy this uniformity for every X is the single load-bearing step for the Scott-rank claim (exactly 2m+1) and the possible SSC values; any gap in the relativized construction would leave the boldface conclusions unsupported.
minor comments (2)
  1. The notation SSC(A) for Scott-sentence complexity is used before an explicit definition; a short definitional sentence in the introduction would help readers.
  2. [Conjecture reduction] The back-and-forth substitution lemma to which the conjecture is reduced could be stated as a numbered claim with its precise quantifier complexity.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the recommendation of minor revision. The major comment concerns the load-bearing role of the uniformity verification for the transfer principle; we address this directly below.

read point-by-point responses

  1. Referee: The transfer principle (isolated after the lightface recall) asserts that a degree-of-categoricity lower bound holding uniformly relative to every oracle X defeats L_{\omega_1\omega}-definability of the automorphism orbits. The verification that the given trees satisfy this uniformity for every X is the single load-bearing step for the Scott-rank claim (exactly 2m+1) and the possible SSC values; any gap in the relativized construction would leave the boldface conclusions unsupported.

    Authors: We agree that the uniformity verification is the key step supporting the boldface Scott-rank and sentence-complexity conclusions. The manuscript carries out this verification explicitly after isolating the transfer principle: the trees A_{m+1} are constructed so that the lower bound on the degree of categoricity (0^{(2m)}) holds relative to an arbitrary oracle X, by replacing all computable approximations and back-and-forth relations with their X-computable counterparts while preserving the combinatorial structure that forces the required jumps. The proofs are written uniformly in X from the outset, so the relativized construction introduces no gaps and directly licenses application of the transfer principle. revision: no

Circularity Check

0 steps flagged

Self-citation of prior lightface construction supplies input trees but is not load-bearing for the new transfer principle or Scott-rank conclusions

full rationale

The paper explicitly cites its own earlier work only for the existence of the computable trees A_{m+1} and their lightface strong degrees of categoricity 0^{(2m)}. The derivation chain then introduces a new transfer principle (uniform oracle-relative lower bound defeats L_{\omega_1\omega}-definability of orbits) and verifies uniformity on those trees. Because the transfer principle and its application are stated and proved in the present paper, the boldface Scott-rank claim (exactly 2m+1) and sentence-complexity bounds do not reduce by definition or by self-citation chain to the prior lightface results. No self-definitional step, fitted-input prediction, or imported uniqueness theorem appears. This is therefore a normal case of citing one's own construction as background while adding independent analytic content.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no information on free parameters, background axioms, or invented entities; the transfer principle and uniformity are invoked but not detailed.

pith-pipeline@v0.9.1-grok · 5899 in / 1335 out tokens · 31206 ms · 2026-06-26T02:04:27.456604+00:00 · methodology

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

16 extracted references · 4 canonical work pages · 1 internal anchor

  1. [1]

    Alvir, N

    R. Alvir, N. Greenberg, M. Harrison-Trainor, and D. Turetsky,Scott complexity of countable structures, J. Symb. Log.86(2021), no. 4, 1706–1720

    2021

  2. [2]

    Alvir, B

    R. Alvir, B. Csima, and M. Harrison-Trainor,On the computability of optimal Scott sentences, preprint, arXiv:2504.09626

    work page arXiv

  3. [3]

    Complexity of Scott Sentences

    R. Alvir, J. F. Knight, and C. McCoy,Complexity of Scott sentences, Fund. Math.251(2020), 109–129. Also arXiv:1807.02715

    work page internal anchor Pith review Pith/arXiv arXiv 2020

  4. [4]

    C. J. Ash and J. F. Knight,Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland, 2000

    2000

  5. [5]

    C. J. Ash, J. F. Knight, M. Manasse, and T. Slaman,Generic copies of countable structures, Ann. Pure Appl. Logic42(1989), 195–205

    1989

  6. [6]

    Chisholm,Effective model theory vs

    J. Chisholm,Effective model theory vs. recursive model theory, J. Symb. Log.55(1990), 1168–1191

    1990

  7. [7]

    B. F. Csima, J. N. Y. Franklin, and R. A. Shore,Degrees of categoricity and the hyperarithmetic hierarchy, Notre Dame J. Form. Log.54(2013), no. 2, 215–231

    2013

  8. [8]

    E. B. Fokina, I. Kalimullin, and R. Miller,Degrees of categoricity of computable structures, Arch. Math. Logic49(2010), no. 1, 51–67

    2010

  9. [9]

    Gonzalez and D

    D. Gonzalez and D. Rossegger,Scott sentence complexities of linear orderings, preprint, arXiv:2305.07126

    work page arXiv

  10. [10]

    Harrison-Trainor and J

    M. Harrison-Trainor and J. T. Kim,Scott spectral gaps for trees are bounded, preprint, arXiv:2602.07166

    work page arXiv

  11. [11]

    D. R. Hirschfeldt and W. M. White,Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures, Notre Dame J. Form. Log.43(2002), no. 1, 51–64

    2002

  12. [12]

    Lempp, C

    S. Lempp, C. McCoy, R. Miller, and R. Solomon,Computable categoricity of trees of finite height, J. Symb. Log.70(2005), no. 1, 151–215

    2005

  13. [13]

    Assem Mahmoud,Degrees of categoricity of trees and the isomorphism problem, Math

    M. Assem Mahmoud,Degrees of categoricity of trees and the isomorphism problem, Math. Log. Q

  14. [14]

    A. W. Miller,On the Borel classification of the isomorphism class of a countable model, Notre Dame J. Form. Log.24(1983), no. 1, 22–34

    1983

  15. [15]

    Montalb´ an,A robuster Scott rank, Proc

    A. Montalb´ an,A robuster Scott rank, Proc. Amer. Math. Soc.143(2015), no. 12, 5427–5436

    2015

  16. [16]

    Vaught,Invariant sets in topology and logic, Fund

    R. Vaught,Invariant sets in topology and logic, Fund. Math.82(1974/75), 269–294. Department of Math and Computational Sciences, University of Toronto Mississauga, Mis- sissauga, ON, Canada Email address:mo.mahmoud@utoronto.ca

    1974