Topic Archive: Borel complexity
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.
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.