Category Theory
Zulip Server
Archive

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.


Stream: theory: algebraic topology

Topic: Undecidability of morphisms in a homotopy category


view this post on Zulip Leopold Schlicht (Nov 13 2021 at 14:52):

In Kerodon it says:

Let SS_\bullet be a simplicial set. Our proof of Proposition 1.2.5.4 gives a construction of the homotopy category hS\mathrm{h} \mathit{S}_{\bullet } by generators and relations. The result of this construction is not easy to describe. If [...] are vertices of SS_\bullet, then every morphism [...] in hS\mathrm{h} \mathit{S}_{\bullet } can be represented by a composition [...]
In general, it can be difficult to determine whether or not two such compositions represent the same morphism of hS\mathrm{h} \mathit{S}_{\bullet } (even for finite simplicial sets, this question is algorithmically undecidable).

I wonder what is meant by "algorithmically undecidable". It seems he is talking about the following computational decision problem:

But I'm pretty sure that the input to a computational problem needs to be some finite amount of data. I'm not sure how to represent a simplicial set SS_\bullet with a finite amount of data. (Each nonempty simplicial set has infinitely many simplices.)

So what is meant by saying that the computational problem is "algorithmically undecidable", precisely? Also, can somebody provide a reference for that claim which contains a proof?

view this post on Zulip Mike Shulman (Nov 13 2021 at 14:55):

I think that's why the statement specifies finite simplicial sets. (-:

view this post on Zulip Mike Shulman (Nov 13 2021 at 15:08):

For the second question, from any presentation of a group one can write down a finite simplicial set for which hS is the classifying space of that group, so it follows from the undecidability of the word problem for groups.

view this post on Zulip Leopold Schlicht (Nov 13 2021 at 15:30):

Mike Shulman said:

I think that's why the statement specifies finite simplicial sets. (-:

Ah, I didn't recognized that, thanks. But in fact even a finite simplicial set is specified by an infinite amount of data. I guess to be able to specify some finite simplicial sets one uses a trick as in my previous thread, right? (Maybe, to specify arbitrary finite simplicial sets, one can use this.)

view this post on Zulip Leopold Schlicht (Nov 13 2021 at 15:42):

Mike Shulman said:

For the second question, from any presentation of a group one can write down a finite simplicial set for which hS is the classifying space of that group, so it follows from the undecidability of the word problem for groups.

But hS is a category and not a space. Do you mean "for which hS is that group"?

view this post on Zulip Mike Shulman (Nov 13 2021 at 15:43):

It consists of an infinite amount of data, but it can be specified by a finite amount, namely the finite number of nondegenerate simplices and their boundaries.

view this post on Zulip Mike Shulman (Nov 13 2021 at 15:43):

Well, hS is a category and not a group either. By "classifying space" I meant the 1-object groupoid corresponding to a group.

view this post on Zulip Mike Shulman (Nov 13 2021 at 15:44):

Since groupoids are equivalent to homotopy 1-types, sometimes we can blur the distinction and use the terminology of one for the other.

view this post on Zulip Leopold Schlicht (Nov 13 2021 at 15:45):

Thanks!

view this post on Zulip Reid Barton (Nov 13 2021 at 16:22):

Also, the homotopy category hS only depends on the 2-skeleton of S, so if S is a finite simplicial set there are really only finitely many simplices involved even if you include the degenerate ones.