COMPUTABLE $\Pi _2$ SCOTT SENTENCES

Abstract By a result of Scott [16], each countable structure for a countable language L is described up to isomorphism by an $L_{\omega _1\omega }$ -sentence, called a Scott sentence . We consider structures that are countably infinite. By a result of A. Miller [11], no such structure has a $\Sigma _2$ Scott sentence, so having a $\Pi _2$ Scott sentence is as simple as possible. A result of Montalbán [12] yields a nice characterization of the structures that (for a fixed countable language) have a $\Pi _2$ Scott sentence. Computable infinitary formulas involve c.e. disjunctions and conjunctions, so they are in a sense comprehensible. Therefore, we set out to characterize the structures that (for a fixed computable language) have a computable $\Pi _2$ Scott sentence. We found some examples and some partial results. However, it turns out that (for most languages) there is no nice characterization of the class. The index set is $\Pi ^1_1$ -complete.