arxiv: 2605.04404 · v1 · submitted 2026-05-06 · 🧮 math.LO

Recognition: unknown

Computable Scott Sentences and the Friedman-Stanley embedding

David Gonzalez, Julia Knight

Pith reviewed 2026-05-08 17:23 UTC · model grok-4.3

classification 🧮 math.LO

keywords Scott sentencesFriedman-Stanley embeddinglabeled treescomputable infinitary logicBorel reducibilityScott rankeffective descriptive set theory

0 comments

The pith

The Friedman-Stanley embedding from graphs to labeled trees preserves the complexity of computable infinitary Scott sentences.

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

The paper examines how a particular embedding turns graphs into labeled trees and shows what this does to the existence and complexity of computable infinitary Scott sentences. It proves that for any X-computable ordinal, a graph has such a sentence of given complexity exactly when its image tree does. This preservation implies that the full class of trees in the image is not Borel, yet each subclass of trees with Scott rank bounded by a fixed alpha is Borel. In fact, when alpha is X-computable, that subclass is complete X-effective Pi_{2alpha+2}. A sympathetic reader would care because the result clarifies the boundary between computable and non-computable classification problems for countable structures.

Core claim

For an X-computable ordinal, if one of A or T_A has a computable infinitary Scott sentence, then so does the other and the complexities match. It follows from results of Gao that T is not Borel. We show that for each alpha, T^alpha is Borel. In fact, if alpha is an X-computable ordinal, then T^alpha is complete X-effective Pi_{2alpha+2}.

What carries the argument

The Harrison-Trainor-Montalban version of the Friedman-Stanley embedding that maps each graph A to a labeled tree T_A while preserving Scott complexity.

If this is right

The embedding transfers the existence of computable infinitary Scott sentences from graphs to trees and back with matching complexity.
The full class T of labeled trees in the range of the embedding is not Borel.
For each ordinal alpha the subclass T^alpha of trees with Scott rank at most alpha is Borel.
When alpha is X-computable, T^alpha is a complete X-effective Pi_{2alpha+2} set.

Where Pith is reading between the lines

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

The preservation may allow results about graph classification to transfer to certain tree classification problems while keeping track of computability.
Similar preservation could hold for the paper's mentioned embedding of graphs into linear orderings.
The effective Borel completeness might extend to other hierarchies or non-X-computable settings.

Load-bearing premise

The specific Harrison-Trainor-Montalban version of the embedding maps graphs to labeled trees in a way that interacts with Scott sentences, and the standard definitions of computable infinitary sentences and X-computable ordinals apply.

What would settle it

A concrete observation that would settle the claim is an X-computable graph A together with its tree T_A whose minimal complexity for a computable infinitary Scott sentence differs, or a non-Borel set inside some T^alpha.

read the original abstract

Friedman and Stanley developed the notion of Borel reducibility and illustrated its use in comparing classification problems for some familiar classes of countable structures. For many embeddings, the fact that the embedding is $1-1$ on isomorphism types is explained by the existence of simple formulas that, uniformly, interpret the input structure in the output structure. For the embeddings of graphs in trees, and in linear orderings, there is no uniform interpretation. We focus on a version of the Friedman-Stanley embedding introduced by Harrison-Trainor and Montalban that takes each structure $A$ for the language of graphs to a labeled tree $T_A$. Gonzalez and Rossegger showed that this embedding preserves Scott complexity. We refine this result, showing that for an $X$-computable ordinal, if one of $A$, $T_A$ has a computable infinitary Scott sentence, then so does the other, and the complexities match. Let $\mathbb{T}$ be the class of labeled trees isomorphic to those in the range of the embedding, and let $\mathbb{T}^\alpha$ be the subclass consisting of structures of Scott rank at most $\alpha$. It follows from results of Gao that $\mathbb{T}$ is not Borel. We show that for each $\alpha$, $\mathbb{T}^\alpha$ is Borel. In fact, if $\alpha$ is an $X$-computable ordinal, then $\mathbb{T}^\alpha$ is complete $X$-effective $\Pi_{2\alpha+2}$.

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.

Desk Editor's Note private letter to a colleague

This refines Gonzalez-Rossegger by extending Scott complexity preservation to computable infinitary sentences under the Harrison-Trainor-Montalban embedding and proving the fixed-rank subclasses of the image are Borel.

read the letter

The main takeaway is that the paper strengthens the earlier preservation result for the Friedman-Stanley embedding of graphs into labeled trees. Gonzalez and Rossegger already showed the embedding preserves ordinary Scott complexity. Here the authors add that it works for computable infinitary Scott sentences as well: if one of A or T_A has such a sentence for an X-computable ordinal, then so does the other and the ordinal complexities match. They also show that each fixed Scott-rank slice T^alpha is Borel, in fact complete X-effective Pi_{2alpha+2} when alpha is X-computable, while the full class T is not Borel by Gao's theorem.

Referee Report

0 major / 2 minor

Summary. The manuscript refines the Gonzalez-Rossegger theorem on the Harrison-Trainor-Montalban embedding of graphs into labeled trees. For an X-computable ordinal, if one of A or T_A has a computable infinitary Scott sentence then so does the other, with matching complexities. While the full class T of labeled trees in the range of the embedding is not Borel (by Gao), each subclass T^α of structures with Scott rank at most α is Borel; when α is X-computable, T^α is complete X-effective Π_{2α+2}.

Significance. If the results hold, the paper supplies a precise effective refinement of preservation under the embedding, with explicit bidirectional formula translations and effective infinitary definitions that bound the complexity by 2α+2. The Borelness of each T^α together with the completeness statement for X-computable α is a notable contribution to the effective descriptive set theory of classes of countable structures. The work credits the independence from the prior Gonzalez-Rossegger theorem and the use of standard notions of X-computable ordinals and computable infinitary Scott sentences.

minor comments (2)

[Abstract] The abstract introduces the classes T and T^α without a forward reference to their formal definition in the body; repeating the definition at the opening of the section on Borelness would improve standalone readability.
The proof sketches for the complexity bound rely on effective translations; a short table summarizing the quantifier complexity increase at each step of the embedding would make the derivation of the 2α+2 bound easier to verify.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation of minor revision. The provided summary accurately reflects the paper's contributions regarding the effective preservation of computable Scott sentences under the Harrison-Trainor-Montalban embedding and the Borelness results for bounded Scott rank subclasses.

Circularity Check

0 steps flagged

No significant circularity; derivation uses explicit translations and external support

full rationale

The paper refines a prior preservation result via explicit bidirectional formula translations between structures A and T_A, and defines membership in T^α by an effective infinitary sentence of bounded complexity 2α+2. The non-Borel claim for the full class T appeals to Gao's external result on uncountable unions. No step reduces a claimed prediction or complexity bound to a fitted parameter, self-definition, or unverified self-citation chain; the Gonzalez-Rossegger citation is acknowledged as prior work being refined rather than load-bearing for the new claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the central claims rest on standard background from computable structure theory and descriptive set theory with no apparent new free parameters or invented entities.

axioms (1)

standard math Standard axioms and definitions of computable infinitary logic, Scott sentences, and X-computable ordinals
Invoked throughout to define the preservation property and effective Borel classes.

pith-pipeline@v0.9.0 · 5564 in / 1252 out tokens · 31063 ms · 2026-05-08T17:23:19.531619+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

27 extracted references · 3 canonical work pages

[1]

On the computability of optimal Scott sentences,

R. Alvir, B. Csima, and M. Harrison-Trainor, “On the computability of optimal Scott sentences,”JSL, published online, 2025

2025
[2]

Complexity of Scott sen- tences,

R. Alvir, J. F. Knight, and C. McCoy CSC, “Complexity of Scott sen- tences,”Fund. Math., vol. 251(2020), pp. 109-129

2020
[3]

Pairs of Recursive Structures,

C. J. Ash, J. F. Knight, “Pairs of Recursive Structures,”APAL, vol. 46(1990), pp. 211-234

1990
[4]

C. J. Ash and J. F. Knight,Computable Structures and the Hyperarith- metical Hierarchy, Elsevier, Amsterdam, 2000

2000
[5]

Recursive labeling systems and stability of recursive structures in hyperarithmetical degrees,

C. J. Ash, “Recursive labeling systems and stability of recursive structures in hyperarithmetical degrees,”TAMS, vol. 298(1986), pp. 497-514

1986
[6]

Comparing classes of finite structures,

W. Calvert, D. Cummins, J. F. Knight, and S. Miller, “Comparing classes of finite structures,”Algebra and Logicvol. 43(2004), pp. 374-392

2004
[7]

Optimal Syn- tactic Definitions of Back-and-Forth Types,

R. Chen, D. Gonzalez and M. Harrison-Trainor, “Optimal Syn- tactic Definitions of Back-and-Forth Types,” To appear inTAMS. https://doi.org/10.1090/tran/9695. 29

work page doi:10.1090/tran/9695
[8]

Cohen,Set Theory and the Continuum Hypothesis, Dover, Garden City, 1966

R. Cohen,Set Theory and the Continuum Hypothesis, Dover, Garden City, 1966

1966
[9]

A Borel reducibility theory for classes of countable structures,

H. Friedman and L. Stanley, “A Borel reducibility theory for classes of countable structures,”JSL, vol. 54(1989), pp. 894-914

1989
[10]

Some dichotomy theorems for isomorphism relations of countable models,

S. Gao, “Some dichotomy theorems for isomorphism relations of countable models,”JSL, vol. 66(2001), pp. 902-922

2001
[11]

Enumerations in computable structure theory,

S. S. Goncharov, V. Harizanov, J. F. Knight, C. McCoy, R. Miller, and R. Solomon, “Enumerations in computable structure theory,”Annals of Pure and Applied Logic, vol. 136(2005), pp. 219-246

2005
[12]

Scott Spectral Gaps are Bounded for Linear Orderings,

D. Gonzalez and M. Harrison-Trainor, “Scott Spectral Gaps are Bounded for Linear Orderings,” preprint at https://arxiv.org/pdf/2411.12084

work page arXiv
[13]

Scott sentence complexities of linear or- derings,

D. Gonzalez and D. Rossegger, “Scott sentence complexities of linear or- derings,”JSL, published online in December 2024

2024
[14]

Complexity of well-ordered sets in an Abelian group,

C. Hall, J. F. Knight, and K. Lange, “Complexity of well-ordered sets in an Abelian group,”Monatshefte f¨ ur Mathematik, vol. 208(2025), pp. 665- 686

2025
[15]

Relative to any non-arithmetic set,

M. Harrison-Trainor, “Relative to any non-arithmetic set,” preprint at https://arxiv.org/abs/2505.23613

work page arXiv
[16]

The tree of tuples of a struc- ture,

M. Harrison-Trainor and A. Montalb´ an, “The tree of tuples of a struc- ture,”JSL, vol. 87(2022), pp. 21-46

2022
[17]

Around non-classifiability for countable torsion-free Abelian groups,

G. Hjorth, “Around non-classifiability for countable torsion-free Abelian groups,” inAbelian Groups and Modules (Dublin, 1998), Trends Math., Birkh¨ auser, Basel,1999, pp. 269-292

1998
[18]

Finite-quantifier equivalence,

C. Karp “Finite-quantifier equivalence,” inTheory of Models (Proc. 1963 Internat. Sympos. Berkeley)ed. by Addison, Henkin, and Tarski, studies in logic and the foundations of mathematics, North-Holland, Amsterdam, 1965, pp. 407-412

1963
[19]

Turing computable em- beddings,

J. F. Knight, S. Miller, and M. Vanden Boom, “Turing computable em- beddings,”JSL, vol. 72(2007), pp. 901-918

2007
[20]

Coding in graphs and linear orderings,

J. F. Knight, A. Soskova, and S. Vatev, “Coding in graphs and linear orderings,”JSL, vol. 85(2020), pp. 673-690

2020
[21]

Maher,On Embeddings of Computable Structures, Classes of Struc- tures, and Computable Isomorphism, PhD Dissertation, University of Notre Dame, 2009

C. Maher,On Embeddings of Computable Structures, Classes of Struc- tures, and Computable Isomorphism, PhD Dissertation, University of Notre Dame, 2009

2009
[22]

A robuster Scott rank,

A. Montalb´ an, “A robuster Scott rank,”PAMS, pp. 407-412, North- Holland, Amsterdam 1965. 30

1965
[23]

Computable Structure Theory: Within the Arithmetic,

A. Montalb´ an, “Computable Structure Theory: Within the Arithmetic,” Perspectives in Logic, Cambridge University Press, Cambridge, 2021

2021
[24]

Computable Structure Theory: Beyond the Arithmetic,

A. Montalb´ an, “Computable Structure Theory: Beyond the Arithmetic,” Perspectives in Logic, Cambridge University Press, Cambridge, 2026

2026
[25]

Torsion-free abelian groups are Borel com- plete,

G. Paolini and S. Shelah, “Torsion-free abelian groups are Borel com- plete,”Annals of Mathematics, vol. 199(2024), pp. 1177-1224

2024
[26]

Logic with denumerably long formulas and finite strings of quantifiers,

D. Scott, “Logic with denumerably long formulas and finite strings of quantifiers,”Theory of Models: Proc. of 1963 Int. Symposium at Berkeley, North-Holland, Amsterdam, 1965, pp. 320-331

1963
[27]

The classification problem for torsion-free Abelian groups of finite rank,

S. Thomas, “The classification problem for torsion-free Abelian groups of finite rank,”JAMS, vol. 16(2002), pp. 233-258. 31

2002