UC Berkeley

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-Σ₂ 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.