Luke MacLean, Department of Pure Mathematics, University of Waterloo
Notions of Complexity Within Computable Structure Theory
"This talk will broadly cover three notions of measuring complexity within computable structure theory"
The first notion is the degree of categoricity of a structure. This measures the maximum difficulty of computing an isomorphism between two computable isomorphic copies of a structure. We restrict our attention to linear orders, and ask whether it is possible to construct computable copies where the isomorphism between them achieves the degree of categoricity, while avoiding the use of a predetermined set of coding locations in the construction.
The second notion is that of Scott complexity. Every countable structure has a Scott sentence that uniquely describes it up to isomorphism among countable structures. Scott complexity measures the minimal complexity of a Scott sentence for a given structure. We will restrict our attention this time to reduced Abelian p-groups, and provide upper bounds for the Scott complexities of such groups. Towards showing that these bounds are optimal, we provide a partial characterization of the back-and-forth relations for such groups.
The third notion is enumeration reducibility. We study a new class of relations on a structure that we call relatively intrinsically positively enumerable (r.i.p.e.), and provide a syntactic characterization for these relations. We use r.i.p.e. relations to provide a new structural jump within the enumeration degrees. We finally consider two different notions of comparing structures. One being a functorial notion that preserves positive information, and the other a notion of interpretability using the formulas obtained from our previous syntactic characterization.
MC 5501