Complexity Classifications in Model Theory and Computable Structures

摘要

We explore various questions of complexity in model theory and computable structures. Part I focuses on computable complexity. In Chapter 2, we show that the theory of the collection of isomorphism classes of at-most countable groups pre-ordered by embedability is 1-reducible to the true theory of second-order arithmetic. In Chapter 3, we show that uncountable categoricity is a 0'-d.c.e. property, work previously published with Uri Andrews. Part II focuses on one specific dividing line in model theory called convex orderability. We show that convexly orderable linear orders can be divided into dense and discrete orders. We show that definable sets in a convexly orderable discrete orders are piecewise periodic, and that convexly orderable dense orders have the nowhere dense graph property.