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

Leopold Schlicht (Nov 13 2021 at 14:52):

In Kerodon it says:

Let $S_\bullet$ be a simplicial set. Our proof of Proposition 1.2.5.4 gives a construction of the homotopy category $\mathrm{h} \mathit{S}_{\bullet }$ by generators and relations. The result of this construction is not easy to describe. If [...] are vertices of $S_\bullet$, then every morphism [...] in $\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 $\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:

• Input: a simplicial set $S_\bullet$ and two "formal compositions" of edges of $S_\bullet$.
• Question: do these two formal compositions represent the same morphism in $\mathrm{h} \mathit{S}_{\bullet }$?

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 $S_\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?

Mike Shulman (Nov 13 2021 at 14:55):

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

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.

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.)

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"?

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.

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.

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.

Leopold Schlicht (Nov 13 2021 at 15:45):

Thanks!

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.