You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
In the real world, the rope in a knot has some nonzero thickness. In math, knots are made of infinitely thin stuff. This allows mathematical knots to be tied in infinitely complicated ways - ways that are impossible for knots with nonzero thickness! These are called 'wild' knots.
See the wild knot in this video by Henry Segerman?
There's just one point where the stuff it's made of needs to have zero thickness. So we say it's wild at just one point. But some knots are wild at many points.
There are even knots that are wild at every point! To build these you need to recursively put in wildness at more and more places, forever.
Wild knots are extremely hard to classify. This is not just a feeling - it's a theorem. Vadim Kulikov showed that wild knots are harder to classify than any sort of countable structure that you can describe using first-order classical logic with just countably many symbols!
Very roughly speaking, this means wild knots are so infinitely complicated that we can't classify them using anything we can write down. This makes them very different from 'tame' knots - knots that aren't wild. Yeah, tame knots are hard to classify, but nowhere near that hard.
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 ∼ 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 homeomorphic to a complete separable metric space, and a Borel relation is a relation 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 is Borel reducible to a Borel relation if there's a Borel function such that
for all
In this situation people say the classification problem can be Borel reduced to the classification problem .
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') 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 (a group in the category of Polish spaces) acts on a Polish space in a 'turbulent' way - some sort of highly chaotic way, defined in Kulikov's paper. Then the Borel relation
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') 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.
All this raises lots of interesting questions about categorical logic: like, 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 of countable models of a first-order theory (which Kulikov says is homeomorphic to the Cantor set)?
I imagine is the space of objects of a topological groupoid, where the isomorphisms are the usual isomorphisms of models. But Kulikov merely equips with the relation of "isomorphicness". That's how the makes it into a Polish a space with a Borel equivalence relation.
Similarly, since we have the Polish group of homeomorphisms of acting on the Polish space of embeddings , 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.
I imagine categorical logicians of some sort would prefer to be working with localic groupoids subject to some countability condition.
This is very interesting!
The result about countable linear orders sounds similar to things that arise in stability theory (in older terminology, classification theory, largely invented by Shelah). Roughly, first-order theories can either be "tame" (their models of given cardinality can be classified up to isomorphism by a smallish number of invariants -- the theory of vector spaces over a given field, or of algebraically closed fields: those are the archetypal examples), or be "wild", meaning that they admit the maximal number of isomorphism types of models allowed on grounds of cardinality alone, at least as soon as the cardinality is big enough -- and there is essentially nothing between the extremes of "tame" and "wild". (I know next to nothing of this, so I might have garbled things somewhat, and I'm certainly not being precise.)
From what I've gathered, it's the theories that have built-in asymmetry, like linear orders, that tend to be wild. Let me quote one of my professors from Rutgers, Gregory Cherlin, from one of his book reviews (Bulletin (New Series) of the AMS, Volume 20, Number 2, April 1989). Imagine you have a model and model extensions , , and you want to amalgamate both extensions into a still larger extension. And let's imagine an element and an element . Enter Cherlin:
The notion of independence used is probably the most subtle aspect of the whole theory, and one which is naturally encountered at the outset. The critical (and early) result was that if a first order class does not allow a reasonable notion of independence, then is a mess. There are two things that are likely to break down in setting up a notion of independence. If for example the structures in carry linear orderings, then the notion is intrinsically asymmetrical: if is to be independent from one must in any case decide whether is less than or greater than . A class is called "stable" if it allows a reasonable, symmetric notion of independence.
And he continues:
This notion of independence may lack finite character over the base (though it is customary to require a weak form of this property in the definition of stability). If the notion of independence does have finite character then the class is called "superstable." Thus one must prove at the outset that unstable, or stable but not superstable classes, fall on the nonstructure side [i.e., they are "wild" -- TT]. The theory continues in this vein: build up a structure theory by steps, proving at each stage that failure of the theory at some point produces a nonstructure theorem.
Here "independence" should be read as extending concepts like linear independence, or algebraic independence. This is connected with things like the Mac Lane-Steinitz exchange axiom in the notion of [[matroid]]; see definitions 2.1 and 2.3 there.
Neat! I wonder if wild classification problems in Shelah's sense correspond to those that are and the problem in of classifying linear orders, where is the concept of Borel reduciblity described above (applied to the Polish space of countable models, together with the equivalence relation given by isomorphicness of models).
Less precisely: I wonder if Kulikov and Shelah are talking about essentially the same concept of "wild classification problem"?
John Baez said:
Neat! I wonder if wild classification problems in Shelah's sense correspond to those that are and the problem in of classifying linear orders, where is the concept of Borel reduciblity described above (applied to the Polish space of countable models, together with the equivalence relation given by isomorphicness of models).
Could be! But surely there are others here better qualified to weigh in on this.
Model theory, and particularly stability theory, is something I'd like to know much better, just because it looks both learnable and insanely powerful.
John Baez said:
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.
The countable models of linear orders include all of the countable ordinals, and even just those are mind-bending..!
Yes, I tried understanding all countable ordinals but I gave up.
Good thing you did! You could go crazy trying to understand them all! (It would be like trying to touch the face of God. Too close to the sun, and all that.)
@Joshua Wrigley and I discussed localic groupoids of subcountable models of geometric theories in this paper. Though once you work with locales the countability restriction doesn't end up really doing anything and the groupoids can actually classify models of any cardinality.
In particular you could consider the localic groupoid corresponding to the theory of linear orders. Though, at least if you work with groupoids instead of equivalence relations, it seems unlikely that these will be maximally 'difficult'. I don't know if something more can be said by restricting to coherent theories concerning infinite decidable objects, but if so, it is not obvious to me.
I haven't thought about constructing a localic groupoid of knots before, but I think it might be possible to do so.
I'll check out your paper, thanks! I'd like to learn about localic groupoids of models.
As for knots, is there a notion of an 'embedding' of one locale in another, and a locale of embeddings of one locale in another?
There is a notion of embedding: just take regular monomorphisms of locales. These correspond to quotient frames. I don't know how to construct a locale of embeddings of one locale in another, but I was thinking of using the locale of all maps from S^1 to S^3 and letting the morphisms of the groupoid identify the maps with the same image. I still need to think through the details. Possibly the original paper also has ideas, since Polish spaces tend to behave similarly to locales.
Well, the space of all maps from to is topologically very different from the space of knots, which are embeddings of into . For example the former space is connected while the latter space has lots of connected components that are [[isotopy classes]] of knots: for example the unknotted circles is in a different isotopy class than the right-handed trefoil, which is in a different isotopy class than the left-handed trefoil.
Classifying isotopy classes of knots is one thing people mean by "classifying knots". Kulikov does something else: he considers a knot to be an equivalence class of images of embeddings of in , where two are equivalent if they differ by a homeomorphism of . The fact that he doesn't require the homeomorphism to be orientation-preserving is a bit unusual, since it means for him the right-handed and left-handed trefoil are equivalent.
Still, if you dropped the embedding requirement in Kulikov's approach you'd be trying to classify not only knots but a vast collection of more singular things, like "knots with self-crossings". Like knots, these can be very wild: for example I can continuously map the circle into the 3-sphere in a way where the map is 2-1 on a Cantor set, 1-1 elsewhere, and the homology of the image is infinitely generated.
You make a good point about the crossings. I overlooked that. I'm not sure how to force things to be one-to-one. (Though for what it's worth, just the fact that the spaces of objects are different doesn't necessarily mean the groupoids aren't equivalent.)
Doesn't the injectivity condition determine a nucleus on the locale of functions?
It's possible, but I don't know exactly how.
Turns out it's easier to do it for tame knots, which I wouldn't necessarily have guessed, but maybe makes sense in hindsight.
The paper isn't much help because the space of wild knots isn't actually (shown to be) Polish after all. It's a Borel subset of a Polish space. This makes me think there probably isn't a natural way to this constructively.
I've seen the idea of Borel reducibility to compare cardinalities of sets in models of set theory compatible with the negation of CH, where everything was argued quite classically, so I don't find it terribly surprising that it's not very constructive.
Why do I believe that?
Graham Manuell said:
The paper isn't much help because the space of wild knots isn't actually (shown to be) Polish after all. It's a Borel subset of a Polish space.
Wikipedia cites Bourbaki as saying that a subspace of a Polish is Polish iff it's an intersection of some sequence of open subsets. (The proof is at Theorem 9 here.)
Let's see if we can use that. To show the space of embeddings is Polish, it'll be enough to show it's a countable intersection of open subsets of , where is the set of continuous maps equipped with its metric
where is the induced metric on the unit 3-sphere . This metric makes into a complete separable metric space, hence its underlying topological space is Polish.
So, what's an "embedding" exactly? It's an injective continuous map such that is homeomorphic to with induced topology.
My gut tells me any injective continuous is an embedding because is compact. Let's see. I see that that any closed injective continuous map is an embedding, where a map is 'closed' if it maps closed subsets to closed sets. If is continuous it maps compact subsets to compact subsets. But since is compact any closed subset of is closed, and since is Hausdorff any compact subset of is closed. So indeed, any continuous map is closed, and thus any continuous injection is an embedding.
So, the subspace consisting of embeddings is the same as the subspace consisting of (continuous) injections, and to show this subspace is Polish with its subspace topology, it's sufficient - and necessary! - to show it's a countable intersection of open subsets.
Let me give it a shot. Let
where I'm using both for the usual metric on and on . This set is open thanks to the .
If is not injective we have some such that . So for some there is no such that . In other words: for some , for all , .
That is,
I hope I didn't screw up - I'm losing my original intuition amidst the mess of quantifiers, intersections and unions. But is closed so is closed so
is a countable union of closed sets.
Darn! I wanted a countable union of open sets. So I haven't yet shown that is a Polish space (nor have I disproved it). But its complement is a countable intersection of open sets, by De Morgan's laws. So if I haven't screwed up, I've shown that the space of nonembeddings is a Polish space. :grumpy:
[EDIT: no, I'm fine - see Todd's comment below.]
Hang on... I think you're saying here that is not injective iff belongs to a certain countable union of closed sets. That means that is injective iff belongs to a certain countable intersection of open sets. And that's the condition you want!
Of course you still have work to do to get to those wild knots...
Looks good! So now we can take the locale of morphisms to be the sublocale cut out by the equation where and and is induced by the map sending (f,p) to . (Here is Sierpinski space and I am actually describing the complement of the image. We can universally quantify open predicates over since it is compact.) This resulting locale is also Polish, so we obtain a Polish groupoid.
Todd Trimble said:
Hang on... I think you're saying here that is not injective iff belongs to a certain countable union of closed sets. That means that is injective iff belongs to a certain countable intersection of open sets. And that's the condition you want!
Yay! I had a clear intuition and then when I started writing it up it got buried under LaTeX, alternating quantifiers, double negatives and DeMorgan duals. :face_with_spiral_eyes: Funny how that can happen.
Of course you still have work to do to get to those wild knots...
Kulikov only considers the space of all knots, including tame ones. He says "wild" to mean "potentially wild, not necessarily tame". So I consider my work finished.
@Todd Trimble also privately pointed out a hole in my proof which can be nicely fixed using another application of compactness. I said
is open but that's not obvious because there's an implicit universal quantifier over here. Spelled out more explicitly,
Luckily, as Todd points out, if is a compact space, is any space, and is compact, then is open where
is the projection to . A quite popular Math Stackexchange post includes a proof of this and also a proof of the converse: if a projection is an open map, needs to be compact.
So, if we think of as the projection from to of the open set , we see is open.
John Baez said:
Luckily, as Todd points out, if is a compact space, is any space, and is compact, then is open where
is the projection to . A quite popular Math Stackexchange post includes a proof of this and also a proof of the converse: if a projection is an open map, needs to be compact.
Wait, what I said (this is in a DM I had sent to John) is that the DeMorgan counterpart of the closed projection property for compact spaces, that for any space and closed subset one has that
is closed, is that for any open one has that
is open. That expression on the left, I don't know what people call it. Not the projection (or image) anyway. It's totally underrated.
Oh, right! That right adjoint thing.
Yes, the right adjoint thing. I think there was a discussion on what to call this thing here in this Zulip some time ago, but my memory is that there wasn't consensus on what to call it (not coimage, maybe someone said "dual image" -- I really don't recall). The mental image I have is that gives the diameter of the biggest "tube" that you can fit inside . But everyone threw tomatoes at "intubation" (quite rightly).
"Dual image" is the least bad terminology that I've heard. I think it's extremely unfortunate that someone stole [[coimage]] for something different.
John Baez said:
Less precisely: I wonder if Kulikov and Shelah are talking about essentially the same concept of "wild classification problem"?
My understanding is that the descriptive-set-theoretic complexity of the class of countable models of a theory is at least partially orthogonal to neostability-theoretic wildness (i.e., wildness in the sense of Shelah).
For starters, for any countable structure , the set of isomorphic copies of in the space of enumerated models is Borel (by the existence of Scott sentences). Therefore any -categorical theory is tame in the Borel sense, but can be arbitrarily wild in the sense of classification theory. The theory of atomless Boolean algebras is -categorical and fairly tame in a lot of ways, but it's extremely wild in Shelah's sense, for instance.
In the other direction, there are some relatively tame theories that have Borel-complete reducts (i.e., reducts in which the isomorphism relation for models is Borel-complete). Laskowski and Ulrich showed here that many relatively tame theories interpret Borel-complete theories. (And note that Shelah-style tameness is usually preserved under interpretations.)
James E Hanson wrote
The theory of atomless Boolean algebras is -categorical [...] but it's extremely wild in Shelah's sense, for instance.
I've heard the same thing for dense linear orders without endpoints, if I remember correctly.
Well so is somewhat wild, but not that wild. It's unstable but o-minimal (and therefore NIP), which you can see on Gabriel Conant's website here. NIP and o-minimality are more or less some of the next best things to stability. You can get vastly improved bounds in Ramsey-like combinatorics for graphs that are definable in o-minimal structures, for instance.
Atomless Boolean algebras on the other hand are in the same bin as and on Conant's map. Now there probably is a bit more that can be said about them, and this is something I know a few model theorists are thinking about (including me), but there's very little hope for the same kind of combinatorial tameness in that context.
is 'unclassifiable' in the sense of Shelah, but a lot of modern model theory is about unclassifiable theories.
James E Hanson said:
Well so is somewhat wild, but not that wild. It's unstable but o-minimal (and therefore NIP), which you can see on Gabriel Conant's website here. NIP and o-minimality are more or less some of the next best things to stability. You can get vastly improved bounds in Ramsey-like combinatorics for graphs that are definable in o-minimal structures, for instance.
Atomless Boolean algebras on the other hand are in the same bin as and on Conant's map. Now there probably is a bit more that can be said about them, and this is something I know a few model theorists are thinking about (including me), but there's very little hope for the same kind of combinatorial tameness in that context.
Thank you James; this is very useful information, and that looks like a helpful website for relative outsiders like me.
(The fact that you seem to identify yourself as a model theorist is also of interest to me!)
Lawvere was very interested in o-minimal geometry, and his enthusiasm was what got me interested in o-minimal geometry as a path to realizing Grothendieck's vision of "tame topology", for which there is a beautiful book by van den Dries. So the idea that o-minimality embodies tameness in many respects is not completely lost on me. :-) Thanks for drawing attention to these distinctions.