- Main

## The Complexity of Countable Structures

- Author(s): Harrison-Trainor, Matthew Alexander
- Advisor(s): Montalban, Antonio
- et al.

## Abstract

We prove various results about the complexity of countable structures, both computable and arbitrary.

We begin by investigating descriptions of countable structures in the infinitary logic *L*_{ω1ω}. Given a countable structure *A*, we can find a sentence ϕ, a Scott sentence for *A*, which describes *A* up to isomorphism in the sense that *A* is the unique countable model of ϕ. We can assign a complexity, the Scott rank of *A*, to *A*; this is the quantifier complexity of the simplest Scott sentence. We investigate the Scott ranks of the models of a theory; we produce several new computable models of high Scott rank; we construct a computable group with no d-Σ_{2} Scott sentence; and we produce a first-order theory of Ulm type.

Next, we look at computable structures on a cone. If *A* is a natural structure—by which we mean an informal notion of a structure that might show up in the normal course of mathematics, and which was not constructed explicitly as a computability-theoretic counterexample—then arguments about *A* will generally relativize. So we can study natural structures by studying arbitrary structures relativized "on a cone". This gives us a way of making precise statements about the imprecise notion of a natural structure. We give a complete classification of the degrees of categoricity on a cone, and prove a number of results about degree spectra of relation on a cone.

Third, we investigate the deep connections between infinitary interpretations and functors. An interpretation of one structure *A* in another structure *B* induces a functor which produces copies of *A* from copies of *B*. Moreover, the interpretation induces a homomorphism from the automorphism group of *B* to the automorphism group of *A*. We show that this reverses: given a functor from *B* to *A*, or a homomorphism from the automorphism group of *B* to *A*, we can recover an interpretation. We consider the effective version of this, as well as the corresponding results for bi-interpretations.

Finally, we look at a number of different algebraic structures. We study the effectivization of extending automorphisms of fields to their algebraic closure, extending valuations to a field extension, and embedding valued fields into algebraically closed valued fields. We give a metatheorem for finding computable copies of various algebraic structures with an independence relation, such as differentially closed fields with δ-independence, with a computable basis. We show that there is a computable left-orderable group with no computable copy with a computable ordering.