The n-Category Café

Let me say a bit more about this paper:

• Vadim Kulikov, A non-classification result for wild knots.

As I mentioned, he proved wild knots are harder to classify than any sort of countable structure describable using first-order classical logic with countably many symbols. And it’s interesting how he proved this. He proved it by studying the space of all knots.

So he used logic to prove a topology problem is hard — but he also used topology to study logic!

More precisely:

Kulikov studied the topological space of all knots, which are topological embeddings $K$ of the circle in the 3-sphere. He also studied the equivalence relation on knots saying $K \sim K'$ if there’s a homeomorphism of the 3-sphere mapping $K$ to $K'$.

This is an example of a ‘Borel relation on a Polish space’. A Polish space is a topological space $X$ homeomorphic to a complete separable metric space. A Borel relation is a relation $R \subseteq X \times X$ that’s a Borel set. For more about the definitions, click the links.

A lot of classification problems can be thought of this way: you give a Polish space of things you’re trying to classify, and an equivalence relation saying when two count as ‘the same’, which is a Borel relation. We then say a Borel relation $R \subseteq X \times X$ is Borel reducible to a Borel relation $S \subseteq Y \times Y$ if there’s a Borel function $f: X \to Y$ such that

$R(x,x') \iff S(f(x), f(x'))$ for all $x, x' \in X$

In this situation people say the classification problem $(X,R)$ can be Borel reduced to the classification problem $(Y,S)$.

This is what Kulikov used to state and prove his result. As far as I can tell, he showed:

1) Equivalence of countable models of any first-order theory with countably many symbols can be Borel reduced to equivalence of (possibly wild) knots.

2) Equivalence of knots is not Borel reducible to the equivalence of countable models of any first-order theory with countably many symbols.

At this point you start noticing that the word ‘logical’ is hiding inside the word ‘topological’.

It’s interesting to see how Kulikov proved his result — his paper is so well-written that you can follow the overall logic without sinking into the weeds of detail.

H. Friedman and L. Stanley showed that the space of countable models of any first-order theory with countably many symbols is Borel reducible to a single one of these, coming from the theory of linear orders.

This is pretty surprising to me: I wouldn’t have guessed that classifying countable linear orders was maximally difficult in this sense.

But thanks to this, to prove 1) Kulikov just needs to show:

1$^\prime$) Equivalence of countable linear orders can be Borel reduced to equivalence of (possibly wild) knots.

For 2), he uses a general result due to Hjorth. Suppose that a Polish group $G$ (a group in the category of Polish spaces) acts on a Polish space $X$ in a ‘turbulent’ way — some sort of highly chaotic way, defined in Kulikov’s paper. Then the Borel relation

$x \sim x' \iff \exists g \in G \; g x = x'$

is not Borel reducible to equivalence of countable models of any first-order theory with countably many symbols!

So Kulikov just needs to show

2$^\prime$) The group of homeomorphisms of the 3-sphere acts in a turbulent way on the space of topological embeddings of the circle in the 3-sphere.

Connections to category theory

How do, or could, categorical logicians think about questions like this?

For example, what do categorical logicians think about the problem of classifying countable linear orders? Is there a sense, similar to the one sketched above, in which it’s maximally hard among some class of problems? Or does dropping the axiom of choice dramatically change its status?

Also: what do they think about the topology of the space $X$ of countable models of a first-order theory (which Kulikov says is homeomorphic to the Cantor set)?

I imagine $X$ is the space of objects of a topological groupoid, where the isomorphisms are the usual isomorphisms of models. But Kulikov merely equips $X$ with the relation of “isomorphicness”. That’s how the makes it into a Polish space with a Borel equivalence relation.

Similarly, since we have the Polish group of homeomorphisms of $S^3$ acting on the Polish space of embeddings $K : S^1 \to S^3$, the action groupoid of this groupoid should be a ‘Polish groupoid’. But Kulikov instead treats it as a Polish space with a Borel equivalence relation.