Scott Analysis of Countable Structures

The logic L_ω1ω admits sentences that are infinitely long by allowing countably many conjunctions and disjunctions. In this logic, we can describe countable structures - such as the natural numbers - up to isomorphism among countable structures via a single sentence φ known as the Scott sentence of that structure. The syntactic complexity of a Scott sentence for a structure tells us a host of information about the structure. We consider a finer notion of this complexity than that historically considered in the literature known as the Scott complexity. We also consider an effective analogue of this concept, and prove analogues of known results about Scott complexity.

Next, we compute the Scott complexity for some well-behaved classes of structures. A linear order L is said to be scattered if there is no embedding from the order type of the rationals into L. We give sharp upper bounds on the Scott complexity of an arbitrary scattered linear order in terms of an invariant known as its Hausdorff rank.

Finally, we consider the case when the Scott complexity of a structure is d − Σ_α or Σ_α. Such structures are controlled by a special finite tuple inside the structure similar to the way in which a finitely generated structure is controlled by its generating tuple. We call such structures finitely α-generated and show that several previously known results about the Scott sentences of finitely generated structures can be lifted.