On optimal Scott sentences of finitely generated algebraic structures

2017/02/21 by Matthew Harrison‐Trainor, Harrison-Trainor, Matthew, Meng-Che Ho +1
Computer Science · #03C57 #03D45 #20E06 (Secondary) #20F06 #20F10 (Primary) #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1702.06448

openalex publication_date 2017/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Scott showed that for every countable structure A, there is a sentence of the infinitary logic L_ω1ω, called a Scott sentence for A, whose models are exactly the isomorphic copies of A. Thus, the least quantifier complexity of a Scott sentence of a structure is an invariant that measures the complexity "describing" the structure. Knight et al.~have studied the Scott sentences of many structures. In particular, Knight and Saraph showed that a finitely generated structure always has a Σ⁰₃ Scott sentence. We give a characterization of the finitely generated structures for whom the Σ⁰₃ Scott sentence is optimal. One application of this result is to give a construction of a finitely generated group where the Σ⁰₃ Scott sentence is optimal.

Related

• On the computability of optimal Scott sentences
• An introduction to the Scott complexity of countable structures and a\n survey of recent results
• Scott sentences for certain groups
• Hanf Number for Scott Sentences of Computable Structures
• Scott Spectral Gaps are Bounded for Linear Orderings