 Main
The Complexity of Countable Structures
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 firstorder 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 computabilitytheoretic 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 biinterpretations.
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 leftorderable group with no computable copy with a computable ordering.
Main Content
Enter the password to open this PDF file:













