View PDF HTML (experimental)

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án, 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.

Submission history

From: Mohammad Mahmoud [view email]
[v1] Thu, 25 Jun 2026 15:21:12 UTC (24 KB)