Friday, November 21, 201410:45 amModel theory seminar

Countable model theory and the complexity of isomorphism

Richard Rast

University of Maryland

We discuss the Borel complexity of the isomorphism relation (for countable models of a first order theory) as the “right” generalization of the model counting problem. In this light we present recent results of Dave Sahota and the speaker which completely characterize the complexity of isomorphism for o-minimal theories, as well as recent work of Laskowski and Shelah which give a partial answer for omega-stable theories. Along the way, we introduce a few open problems and barriers to generalizing the existing results.