On the Computability of Optimal Scott Sentences

Basic Information

• Paper ID: 2504.09626
• Title: On the Computability of Optimal Scott Sentences
• Authors: Rachael Alvir, Barbara Csima, Matthew Harrison-Trainor
• Classification: math.LO (Mathematical Logic)
• Publication Date: November 7, 2025 (arXiv v2)
• Paper Link: https://arxiv.org/abs/2504.09626

Abstract

This paper investigates the computability of Scott sentences for countable mathematical structures. Scott sentences are sentences in infinitary logic $\mathcal{L}_{\omega_1\omega}$ that characterize isomorphism classes of structures. The paper addresses two core problems: (1) proving that there exist computable structures with $\Pi_2$ Scott sentences but no computable $\Sigma_4$ Scott sentences, demonstrating that the known $\Pi_4$ upper bound is optimal; (2) proving that the index set of computable structures with computable $\Pi_n$ Scott sentences is $\Pi^1_1$-m-complete, showing that no reasonable characterization of such structures exists.

Research Background and Motivation

Core Problems

This paper investigates a fundamental question in Scott analysis theory: the gap between optimal complexity of Scott sentences and their computable versions.

1. Basic Theory of Scott Sentences: For any countable structure $A$, there exists a sentence $\phi$ in infinitary logic $\mathcal{L}_{\omega_1\omega}$ that characterizes the isomorphism class of $A$ among countable structures. The Scott rank is defined as the minimal ordinal $\alpha$ such that $A$ has a $\Pi_{\alpha+1}$ Scott sentence.
2. Computability Gap: Alvir, Knight, McCoy (2020) proved that there exist computable structures with $\Pi_2$ Scott sentences but no computable $\Pi_2$ Scott sentences. This reveals the difference between optimal complexity and computable optimal complexity.

Research Significance

1. Theoretical Importance: Scott analysis plays a central role in research on Vaught's conjecture (e.g., Morley's theorem). Understanding the complexity of Scott sentences for computable structures is crucial for the theory of computable structures.
2. Optimality of Known Upper Bounds: Known results show that computable structures with $\Pi_\alpha$ Scott sentences (where $\alpha$ is computable) must have computable $\Pi_{2\alpha}$ Scott sentences. For $\alpha=2$, this gives a $\Pi_4$ upper bound, but whether this bound is optimal has been an open question.
3. Robustness of Effective Scott Rank: Non-effective Scott rank has multiple equivalent characterizations (Montalbán's theorem), but whether effective Scott rank is equally robust was an open problem in AKMC20.

Limitations of Existing Methods

1. Restricted Construction Techniques: Existing constructions primarily target the $\Pi_2$ level, lacking techniques for generalization to higher complexity levels.
2. Characterization Problem: Lack of effective methods to determine whether computable structures have computable Scott sentences.
3. Theoretical Gaps: Unclear whether the $\Pi_{2n}$ upper bound can be improved to $\Pi_{n+2}$ (recent results by Chen et al. show that $\{B: A \leq_n B\}$ is $\Pi^0_{n+2}$).

Core Contributions

The main contributions of this paper include:

1. Optimal Upper Bound Theorem (Theorem 1.2): Constructs a computable structure with a $\Pi_2$ Scott sentence but no computable $\Sigma_4$ Scott sentence, proving that the known $\Pi_4$ upper bound is optimal.
2. Index Set Complexity (Theorem 1.3): Proves that the index set of computable structures with computable $\Pi_2$ Scott sentences is $\Pi^1_1$-m-complete, showing that no arithmetic characterization of such structures exists.
3. Technical Innovation: Develops new priority tree construction methods through an "expansion stage" mechanism that simultaneously constructs the structure $A$ and its diagonalization structure $B_e$.
4. Generalized Results: Extends results to arbitrary finite levels and hyperarithmetic levels through Marker expansion/jump inversion techniques (Corollaries 5.8, 5.9).
5. Scott Family Complexity: Proves the existence of structures with computable $\Pi_2$ Scott sentences but no enumerable $\Sigma_1$ formula Scott families (Corollary 5.1).

Detailed Methodology

Task Definition

Core Task: Construct a computable structure $A$ satisfying:

• $A$ has a $\Pi_2$ Scott sentence (i.e., $A$ is $\exists$-atomic)
• For all computable $\Pi_3$ sentences $\theta_e$, either $\theta_e$ is not a Scott sentence (there exists $B \models \theta_e$ with $B \not\cong A$), or $A \not\models \theta_e$

Technical Transformation: Through simplification remarks (Section 2), proving the absence of computable $\Pi_3$ Scott sentences is equivalent to proving the absence of computable $\Sigma_4$ Scott sentences.

Model Architecture

1. Structure Design (Bouquet Graph Method)

The structure $A$ is represented as a bouquet graph $G_1(\mathcal{F})$, where:

• Each element is the center of a "flower"
• Different elements are distinguished by adding loops of different lengths (labels)
• Ordering Labels $(u_e)_{e\in\omega}$: partition the domain into disjoint orderings $U_e = \{x \in A: u_e(x)\}$
• Distinguishing Labels $(\ell_i)_{i\in\omega}$ and $(\ell^\dagger_i)_{i\in\omega}$: used to distinguish elements within orderings

2. Diagonalization Strategy

For each $e$, diagonalize $\theta_e$ in the $e$-th ordering:

Dual Structure System:

• Main structure $A = \bigcup_s A_s$ (stage-by-stage approximation)
• Auxiliary structure $B_e = \bigcup_s B_{e,s}$ (differs only in the $e$-th ordering)
• Maintain $B_{e,s} \cong A_s$ (though limits may not be isomorphic)

Key Mechanism:

• Expansion Stages: When discovering $A_s \models \bigwedge_{i\leq k} \forall \bar{x}_{e,i} \phi_{e,i}(\bar{x}_{e,i})$
• Backtracking Mechanism: When requirement $R^e_{i,\bar{b}}$ needs attention (discovering $B_e$ may not satisfy $\theta_e$)

3. Priority System of Requirements

For each $e$ and $\bar{b} \in B_e$, define requirement $R^e_{i,\bar{b}}$:

• Goal: If $B_e \models \bigwedge_j \forall \bar{y}_{i,j} \neg\phi^e_{i,j}(\bar{b}, \bar{y}_{i,j})$, then $A \models \bigwedge_j \forall \bar{y}_{i,j} \neg\phi^e_{i,j}(\bar{a}, \bar{y}_{i,j})$
• Parameters: $t(R^e_{i,\bar{b}})$ (initialization stage), $k(R^e_{i,\bar{b}})$ (number of times attended to)
• Attention Condition: $B_{e,s} \models \bigwedge_{j\leq k} \forall \bar{y}_{i,j} \in B_{e,t+k} \neg\phi^e_{i,j}(\bar{b}, \bar{y}_{i,j})$

Technical Innovation Points

1. Stratified Guessing Mechanism

For $\Pi_3$ sentences $\theta_e = \bigwedge_i \forall \bar{x}_i \bigvee_j \exists \bar{y}_{i,j} \phi_{i,j}(\bar{x}_i, \bar{y}_{i,j})$:

• Do not directly guess $B_e \models \neg\theta_e$ (this is $\Sigma_3$, too complex)
• Instead, separately guess for each $(i, \bar{b})$ that $B_e \models \bigwedge_j \forall \bar{y}_{i,j} \neg\phi_{i,j}(\bar{b}, \bar{y}_{i,j})$ (this is $\Pi_2$)
• Key Observation: If some requirement needs attention infinitely often and is never injured, then $B_e \not\models \theta_e$

2. Active Elements and Copying Mechanism

• Active Elements: $a_1[s], \ldots, a_n[s]$ (each with unique distinguishing label)
• Copies: Elements with identical labels to some active element
• Backtracking Operation: Declare $a_{n^*+1}, \ldots, a_n$ as copies of $a_{n^*}$, unifying their labels

Correspondence:

• Active elements of $A_s$: $a_1, \ldots, a_n$
• Active elements of $B_{e,s}$: $b_1, \ldots, b_{n-1}, c$
• Isomorphism mapping: $a_i \mapsto b_i$ (for $i < n$), $a_n \mapsto c$

3. Fine Control of Expansion Stages

Definition of $k$-small tuples: A tuple $\bar{x}$ is $k$-small if:

• Elements in the $e$-th ordering $a_\sigma \in A$ satisfy $\sigma \in \{0,\ldots,k\}^{\leq k}$
• Elements not in the $e$-th ordering are among the first $k$ elements of $A$

Expansion Condition: For all $i \leq k$ and $k$-small tuples $\bar{x}_i$, $A_s \models \phi_i(\bar{x}_i)$ and existential quantifiers are realized in the first $s$ witnesses.

Key Lemma 3.3: If $R^e_{i,\bar{b}}$ is not injured after some stage, and $B_e \models \bigwedge_j \forall \bar{y}_{i,j} \neg\phi_{i,j}(\bar{b}, \bar{y}_{i,j})$, then $R^e_{i,\bar{b}}$ needs attention infinitely often.

Construction Algorithm Flow

Stage $s+1$:

1. Check Requirement Attention: For all $R^e_{i,\bar{b}}$, check whether $B_{e,s} \models \bigwedge_{j\leq k} \forall \bar{y}_{i,j} \in B_{e,t+k} \neg\phi^e_{i,j}(\bar{b}, \bar{y}_{i,j})$
2. Case A: No Requirement Needs Attention (Normal Expansion)
   • Add new element $a_{n+1}$, inheriting all labels of $a_n$
   • Give $a_n$ and $a_{n+1}$ each a new unique label
   • In $B_{e,s+1}$: add $b_n$ (with same labels as $a_n$), $c$ acquires labels of $a_{n+1}$
   • Initialize next requirement
3. Case B: Highest Priority Requirement $R^e_{i,\bar{b}}$ Needs Attention (Backtracking)
   • Set $t = t(R^e_{i,\bar{b}})$, $n^* = n[t]$
   • Declare $a_{n^*+1}, \ldots, a_n$ all as copies of $a_{n^*}$
   • Unify labels of these elements and $a_{n^*}$
   • In $B_{e,s+1}$ unify labels of $b_{n^*}, \ldots, b_{n-1}, c$
   • Injure all lower priority requirements, increment $k(R^e_{i,\bar{b}})$

Correctness Proof Framework

Lemma 3.2 ($\exists$-Atomicity): Each element $a_i[\infty]$ acquires a distinguishing label upon creation ensuring $A$ is $\exists$-atomic.

Lemma 3.4 (Completeness): If $B_e \models \neg\theta_e$, then there exists a highest priority requirement $R^e_{i,\bar{b}}$ needing attention infinitely often, implying $A \cong B_e$, thus $A \models \neg\theta_e$.

Lemma 3.5 (Diagonalization): If $B_e \models \theta_e$, then each requirement needs attention only finitely often, and there exist infinitely many "true expansion stages," ensuring $A \not\cong B_e$ (since $c \in B_e$ has no corresponding element).

Conclusion: If $A \models \theta_e$, then $B_e \models \theta_e$ and $A \not\cong B_e$, so $\theta_e$ is not a Scott sentence for $A$.

Experimental Setup

This paper is pure mathematical logic research with no traditional experiments. The theoretical results are verified through mathematical proofs.

Proof Structure

1. Proof of Theorem 1.2 (Section 3): Proves existence through explicit construction
2. Proof of Theorem 1.3 (Section 4): Proves $\Pi^1_1$-completeness through reduction
3. Generalized Results (Section 5): Proves through jump inversion techniques

Verification Methods

• Lemma Chain Verification: Establishes main theorems through a series of lemmas
• Case Analysis: Analyzes two possible outcomes of construction (finite/infinite expansion stages)
• Complexity Analysis: Precisely computes complexity bounds of index sets

Experimental Results

Main Results

Theorem 1.2 (Optimal Upper Bound):

• There exists a computable structure $A$ with a $\Pi_2$ Scott sentence but no computable $\Sigma_4$ Scott sentence
• This proves the known $\Pi_4$ upper bound is optimal
• Improves upon AKMC20 (from no computable $\Pi_2$ to no computable $\Sigma_4$)

Theorem 1.3 (Index Set Completeness): The set $\{i \mid A_i \text{ has computable } \Pi_2 \text{ Scott sentence}\}$ is $\Pi^1_1$-m-complete.

Implications:

• No arithmetic characterization exists for determining whether structures have computable $\Pi_2$ Scott sentences
• Effective Scott rank lacks the robustness of non-effective Scott rank

Generalized Results

Corollary 5.8: For each computable ordinal $\alpha$, there exists a computable structure with a $\Pi_{\alpha+2}$ Scott sentence but no computable $\Sigma_{\alpha+4}$ Scott sentence.

Corollary 5.9: For each computable ordinal $\alpha$, the index set of structures with computable $\Pi_{\alpha+2}$ Scott sentences is $\Pi^1_1$-m-complete.

Proof Method: Uses Marker expansion $\Phi_\alpha(A)$, leveraging Proposition 5.10:

• $A$ has $\Pi_\beta$ Scott sentence $\Leftrightarrow$ $\Phi_\alpha(A)$ has $\Pi_{\alpha+\beta}$ Scott sentence
• Computable versions hold similarly

Scott Family Complexity Results

Corollary 5.1: There exists a computable structure with a computable $\Pi_2$ Scott sentence but no enumerable computable $\Sigma_1$ formula Scott family.

Proposition 5.2: Computable structures $A$ with computable $\Pi_{\alpha+1}$ Scott sentences have enumerable computable $\Pi_{\alpha+1}$ formula Scott families.

Proposition 5.3: Computable structures $A$ with computable $\Pi_{\alpha+1}$ Scott sentences have $\Sigma^0_{\alpha+2}$ computable $\Sigma_\alpha$ formula Scott families.

Pseudo-Scott Sentence Results

Corollary 5.5: There exists a computable structure $A$ with a $\Pi_2$ Scott sentence but no computable $\Pi_2$ Scott sentence, yet having a computable $\Pi_2$ sentence $\phi$ such that for all hyperarithmetic structures $B$, $B \models \phi \Leftrightarrow A \cong B$

This significantly strengthens previous results on pseudo-Scott sentences Ho17, Qui20.

Results in Mod(L)

Proposition 5.6: The set of structures with computable $\Pi_2$ Scott sentences:

• Is a Borel set (actually bold $\Sigma^0_3$)
• Is thin $\Pi^1_1$ but not thin $\Sigma^1_1$

Corollary 5.7: The set of structures with $A$-computable $\Pi_2$ Scott sentences is $\Pi^1_1$-Wadge-complete.

Related Work

Historical Development of Scott Analysis

1. Scott (1965): Proved every countable structure has a Scott sentence
2. Nadel (1974): Proved Scott rank of computable structures is at most $\omega_1^A + 1$
3. Montalbán (2015): Established robust Scott rank definitions (equivalent characterizations in Theorem 1.1)

Research on Computable Scott Rank

1. Harrison (1968), Millar-Knight (2010), Makkai (1981): Constructed computable structures with non-computable Scott rank
2. Harrison-Trainor et al. (2018): New examples of high-rank computable structures
3. Alvir et al. (2021): Systematic study of Scott complexity

Computable Scott Sentences

1. Alvir, Knight, McCoy (2020):
   • First proved existence of computable structures with $\Pi_2$ Scott sentences but no computable $\Pi_2$ Scott sentences
   • Posed robustness problem for effective Scott rank
   • Proved enumerable $\Sigma_\alpha$ Scott families imply computable $\Pi_{\alpha+1}$ Scott sentences
2. Knight, Lange, McCoy (Independent Work): Also obtained Theorem 1.3

Index Set Complexity Methods

1. Goncharov-Knight (2002): Proposed using index set complexity to study computable structure theory
2. Harrison-Trainor (2018), Bazhenov et al. (2019):
   • Proved no characterizations exist for decidable presentations and automatic structures
   • Used index set $\Pi^1_1$-completeness techniques

Jump Inversion Techniques

Goncharov et al. (2005): Developed jump inversion methods in structure theory, systematized by Montalbán into effective bi-interpretability and structural jump theory.

Recent Related Progress

Chen, Gonzalez, Harrison-Trainor (Preprint): Proved $\{(A,B): A \leq_n B\}$ is $\Pi^0_{2n}$-complete, but $\{B: A \leq_n B\}$ is $\Pi^0_{n+2}$. This provides context for Problem 1.5.

Conclusions and Discussion

Main Conclusions

1. Determination of Optimal Bounds: The optimal computable upper bound for $\Pi_2$ Scott sentences is $\Pi_4$ (dual of $\Sigma_4$)
2. No Characterization Theorem: No arithmetic method exists to determine whether computable structures have computable $\Pi_n$ Scott sentences
3. Gap Between Effective and Non-Effective: Effective Scott rank lacks the robustness of non-effective Scott rank

Limitations

1. $\Pi_{2n}$ Upper Bound Problem: For $n \geq 3$, whether structures with $\Pi_n$ Scott sentences but no computable $\Sigma_{2n}$ Scott sentences exist remains open (Problem 1.5)
2. Fine Structure of $\Pi_3$ Sentences: Is the index set of structures with $\Pi_2$ Scott sentences and computable $\Pi_3$ Scott sentences $\Pi^1_1$-m-complete? (Problem 1.6)
3. Technical Limitations:
   • Marker expansion only additively increases complexity
   • Current techniques struggle with the gap between $n+2$ and $2n$ (when $n \geq 3$)
4. Decision Complexity: Whether determining if a structure has a $\Pi_2$ Scott sentence is $\Pi^0_4$ is optimal remains unknown

Future Directions

Problem 1.5 (Key Open Problem): For each $n$, do there exist computable structures with $\Pi_n$ Scott sentences but no computable $\Sigma_{2n}$ Scott sentences?

Technical Challenges:

• Chen et al.'s results show $\{B: A \leq_n B\}$ is $\Pi^0_{n+2}$ but the proof is non-effective
• New insights needed to distinguish $n+2$ from $2n$ (when $n \geq 3$)

Problem 1.6: Index set complexity for $\Pi_3$ sentences

Problem 5.4: Are the Scott family complexity bounds in Propositions 5.2 and 5.3 optimal?

Generalization Directions:

• Extension to infinite ordinals
• Study computability of other logical levels
• Explore relationships with other structural invariants

Theoretical Significance

1. Reveals Fundamental Limitations: Demonstrates essential difficulties in effective Scott rank theory
2. Methodological Contributions: Developed priority tree construction techniques potentially applicable to other computability problems
3. Interdisciplinary Connections: Tightly links descriptive set theory (index set complexity), computability theory, and model theory

In-Depth Evaluation

Strengths

1. Theoretical Depth

• Resolves Important Open Problem: Completely settles the optimal bound problem for the $\Pi_2$ case
• Strong Negative Results: $\Pi^1_1$-completeness demonstrates the essential difficulty of the problem
• Unified Framework: Jump inversion extends results across arithmetic and hyperarithmetic levels

2. Technical Innovation

• Elegant Construction: Expansion stage mechanism cleverly handles $\Pi_3$ sentence complexity
• Stratified Guessing: Decomposing $\Sigma_3$ guesses into $\Pi_2$ guesses is creative
• Active Element System: Copying mechanism for backtracking maintains isomorphism relations

3. Proof Completeness

• Detailed Verification: Each key lemma has clear proofs
• Comprehensive Case Analysis: Considers all scenarios for finite/infinite expansion stages
• Rigorous Technical Details: Definitions like $k$-small tuples are carefully handled

4. Result Richness

• Multi-level Corollaries: Main theorem yields corollaries on Scott families, pseudo-Scott sentences, Borel complexity, etc.
• Independent Significance: Each corollary has independent research value

Weaknesses

1. Technical Limitations

• Unresolved $n \geq 3$ Cases: Gap between $\Pi_{2n}$ and $\Pi_{n+2}$ remains undetermined
• Dependence on Marker Expansion: Generalized results rely on existing techniques, lacking direct constructions

2. Presentation Issues

• Construction Complexity: Section 3 construction is quite technical, requiring strong background
• Motivation Explanation: Motivation for certain technical choices (e.g., precise definition of $k$-small tuples) could be clearer

3. Many Open Problems

• Leaves two core open problems (1.5, 1.6)
• Some technical questions (e.g., Problem 5.4) have unclear answers

4. Application Scope

• Results are primarily theoretical, lacking applications to specific mathematical structures
• Connections to practical computable mathematics are not prominent

Impact Assessment

Contribution to the Field

1. Establishes Fundamental Limits: Proves essential difficulties in effective Scott rank theory
2. Methodological Impact: Priority tree construction techniques may inspire other research
3. Opens New Directions: Proposed open problems will guide future research

Practical Value

• Theoretical Tools: Provides theoretical foundation for assessing structure complexity
• Value of Negative Results: Indicates which research directions are infeasible

Reproducibility

• Verifiable Construction: Algorithm is clear, in principle formalizable
• Checkable Proofs: Logical reasoning is rigorous, step-by-step verifiable

Applicable Scenarios

1. Computable Structure Theory Research: Provides foundational tools for studying computably presented mathematical structures
2. Descriptive Set Theory: Exemplary application of index set complexity methods
3. Model Theory and Computability Intersection: Demonstrates deep interactions between the two fields
4. Theoretical Computer Science: Provides examples for understanding fundamental algorithmic limitations

Comparison with Related Work

Technical Evaluation

Construction Techniques: ★★★★★

• Expansion stage mechanism is ingeniously designed
• Backtracking operations preserve invariants

Proof Rigor: ★★★★★

• Lemma chains are complete
• Case analysis is thorough

Readability: ★★★★☆

• Overall structure is clear
• Technical sections are challenging, require careful reading

Originality: ★★★★★

• Resolves important open problems
• Technical methods are novel

Completeness: ★★★★☆

• Main results are complete
• Leaves open problems

Selected References

This paper cites 20 important references, primarily including:

1. Scott (1965): Original paper on Scott sentences
2. Montalbán (2015, 2017, 2021): Systematization of modern Scott rank theory
3. Alvir-Knight-McCoy (2020): Prior work directly improved by this paper
4. Goncharov et al. (2005): Jump inversion techniques
5. Harrison-Trainor et al. (2018, 2021): Latest progress on computable Scott rank

Summary: This paper makes an important contribution to computable structure theory. Through elegant constructions and profound complexity analysis, it reveals fundamental limitations of effective Scott rank theory. While leaving open problems, it establishes a solid foundation for future research in this area. Both the technical innovations (particularly the expansion stage mechanism) and theoretical insights (the gap between effective and non-effective) have lasting value.