Scott complexity of trees of finite rank via degrees of categoricity
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-06-26 02:04 UTCgrok-4.3pith:4M2IQZU5record.jsonopen to challenge →
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.
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
- 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 \cite{Mah19}, the first author constructed, for each finite $m\geq 1$, a computable tree $\A_{m+1}$ of rank $m+1$ whose strong degree of categoricity is $\mathbf{0}^{(2m)}$, and showed this degree is optimal at each rank. Those results are lightface: they concern Turing degrees of isomorphisms between computable copies. In this paper we determine the boldface content of the construction. We isolate a transfer principle: a degree-of-categoricity lower bound that holds uniformly relative to every oracle defeats $L_{\omega_1\omega}$-definability of automorphism orbits outright. We verify that the construction of \cite{Mah19} has this uniformity, and deduce that $\A_{m+1}$ has Scott rank exactly $2m+1$, with Scott sentence complexity one of $\Sin{2m+1}$, $\dSin{2m+1}$, or $\Pin{2m+2}$. For rank $2$ we carry out a complete, computability-free 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 then prove $\SSC(\A_{m+1})=\Pin{2m+2}$ for all finite $m$: among the three candidates, only $\Pin{2m+2}$ is consistent with the parameterized Scott rank, and a parameter-reservation argument -- naming any finite tuple reserves only finitely many top-level subtrees, and the relativized coding survives on the infinitely many spare subtrees -- pins $\pSR(\A_{m+1})=2m+1$, selecting that candidate. These results begin a classification of the Scott sentence complexities of trees of finite rank, 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 for trees.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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)
- The notation SSC(A) for Scott-sentence complexity is used before an explicit definition; a short definitional sentence in the introduction would help readers.
- [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
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
-
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
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.