ON THE COMPUTABILITY OF OPTIMAL SCOTT SENTENCES
Rachael Alvir, Barbara F. Csima, Matthew Harrison‐Trainor · Journal of Symbolic Logic · 2025
Abstract Given a countable mathematical structure, its Scott sentence is a sentence of the infinitary logic $\mathcal {L}_{\omega _1 \omega }$ that characterizes it among all countable structures. We can measure the complexity of a structure by the least complexity of a Scott sentence for that structure. It is known that there can be a difference between the least complexity of a Scott sentence and the least complexity of a computable Scott sentence; for example, Alvir, Knight, and McCoy showed that there is a computable structure with a $\Pi _2$ Scott sentence but no computable $\Pi _2$ Scott sentence. It is well known that a structure with a $\Pi _2$ Scott sentence must have a computable $\Pi _4$ Scott sentence. We show that this is best possible: there is a computable structure with a $\Pi _2$ Scott sentence but no computable $\Sigma _4$ Scott sentence. We also show that there is no reasonable characterization of the computable structures with a computable $\Pi _n$ Scott sentence by showing that the index set of such structures is $\Pi ^1_1$ - m -complete.