Blog Archives

Topic Archive: Borel complexity

Set theory seminarFriday, March 4, 201610:00 amGC 6417

Sheila Miller

The Quandary of Quandles: The Borel Completeness of a Knot Invariant

City Tech - CUNY

We show that the isomorphism problems for left distributive algebras, racks, quandles, and keis are as complex as possible in the sense of Borel reducibility. These various kinds of algebraic structure are important for their connections with the theory of knots, links and braids, and in particular, Joyce showed that quandles could be used as complete invariants for tame knots. However, quandles have heuristically seemed to be unsatisfactory invariants. Our result confirms this view, showing that from a set-theoretic perspective, classifying tame knots by quandles replaces one problem with (a special case of) a harder problem.

Model theory seminarFriday, November 21, 201410:45 am

Countable model theory and the complexity of isomorphism

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.