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: smallest common degenerate simplex

Naso (Aug 19 2022 at 03:40):

In a simplicial set, if $x$ and $y$ are degenerate simplices of the same nondegenerate simplex $z$, is there a 'smallest' degenerate simplex $w$ that is a degeneracy of both $x$ and $y$, where $a$ is smaller than $b$ iff $b$ is a degeneracy of $a$? I feel like this is true but I'm struggling to come up with a straightforward proof...

Amar Hadzihasanovic (Aug 19 2022 at 08:55):

I think this is false.

Consider a co-degeneracy map from the n-simplex to the 1-simplex. This is the same as an order-preserving surjective map from (0 < ... < n) to (0 < 1), which must send the first k elements to 0 and the next (n+1-k) to 1; so it is uniquely determined by a string $0^k 1^{n+1-k}$.

Amar Hadzihasanovic (Aug 19 2022 at 08:56):

Now you're asking whether given two co-degeneracy maps f, g: (n) -> (1) we can always find a co-degeneracy e: (m) -> (n) which equalises them, that is e;f = e;g.

Amar Hadzihasanovic (Aug 19 2022 at 08:57):

I claim that we can't in general. Any co-degeneracy map can be factored into a sequence of “elementary collapses” (m+1) -> (m).

Amar Hadzihasanovic (Aug 19 2022 at 08:58):

The way that precomposition with such an “elementary collapse” acts on the representation of a map (n) -> (1) as a bit-string is that it “duplicates” the bit in a certain position.

Amar Hadzihasanovic (Aug 19 2022 at 09:02):

For f: (n) -> (1), you can consider the function p(f) that gives you the parity of (length of the string - number of 0s) in the bit-string representation of f.

Amar Hadzihasanovic (Aug 19 2022 at 09:03):

Now you can see that, for all elementary collapses, you have that p(e;f) is the “negation” of p(f), because e either “adds a 0” or “adds a 1”, changing the parity.

Amar Hadzihasanovic (Aug 19 2022 at 09:05):

By induction on the decomposition of a co-degeneracy into “elementary collapses”, you can see that for all co-degeneracies e: (m) -> (n), you have p(e;f) = p(e;g) if and only if p(f) = p(g).

Amar Hadzihasanovic (Aug 19 2022 at 09:06):

So you just have to start from f, g with different parity and see that they can never be “unified”. For example, have f: (2) -> (1) be 001 and g: (2) -> (1) be 011.

Amar Hadzihasanovic (Aug 19 2022 at 09:07):

So for example if in a simplicial set you have a non-degenerate 1-simplex $z$, then the degenerate 2-simplices $f^*z$ and $g^*z$ do not have any common degeneracy.

Naso (Aug 19 2022 at 09:09):

Amar Hadzihasanovic said:

So you just have to start from f, g with different parity and see that they can never be “unified”. For example, have f: (2) -> (1) be 001 and g: (2) -> (1) be 011.

Isn't $h : (3) \to (1) = 0011$ a degeneracy of both of them?

Amar Hadzihasanovic (Aug 19 2022 at 09:11):

No, you can't get $h$ by pulling back $f$ and $g$ with the same map.

Amar Hadzihasanovic (Aug 19 2022 at 09:11):

Which is what you would need to equalise $f^*z$ and $g^*z$

Amar Hadzihasanovic (Aug 19 2022 at 09:12):

...Ah wait I'm being stupid. That's not what you were actually asking.

Amar Hadzihasanovic (Aug 19 2022 at 09:13):

And probably what I proved to be false can be shown to be false more trivially then what I did :D

Naso (Aug 19 2022 at 09:13):

Sorry if i wasn't clear, i don't think I need them to be degeneracies with the same map, just that like in this case, there exists a common degeneracy $h$ which is minimal, for example $0011111$ would be another common degeneracy but not minimal

Amar Hadzihasanovic (Aug 19 2022 at 09:15):

I proved that there are no equalisers of co-degeneracies in the simplex category while I think what you are asking is essentially whether there are pullbacks of co-degeneracies in the simplex category.

Amar Hadzihasanovic (Aug 19 2022 at 09:15):

I'll think about that later!

Naso (Aug 19 2022 at 09:16):

yes, i think that's what i meant.. alright, thanks Amar! :)

Amar Hadzihasanovic (Aug 19 2022 at 09:21):

Well, I think there may be a simple proof: again see a co-degeneracy $f: (m) \to (n)$ as being represented by a string $0^{f_0} 1^{f_1} \ldots n^{f_n}$, which you can also just see as a list $(f_0, \ldots, f_n)$ of positive numbers, corresponding to “$f$ sends the first $f_0$ elements to 0, the next $f_1$ to 1, etc.”.

Amar Hadzihasanovic (Aug 19 2022 at 09:21):

(Here $\sum_{i=0}^n f_i = m$)

Amar Hadzihasanovic (Aug 19 2022 at 09:23):

Then given $f, g: (m) \to (n)$, I claim the “smallest unifier” is the function given by the list $(max(f_0, g_0), \ldots, max(f_n, g_n))$.

Amar Hadzihasanovic (Aug 19 2022 at 09:26):

I think that it shouldn't be too hard to show that this works...

Naso (Aug 19 2022 at 09:32):

I did not want to assume that the domain of $f$ and $g$ must be the same (should have said that earlier, sorry!)

Amar Hadzihasanovic (Aug 19 2022 at 10:06):

Oh sorry I shouldn't have assumed f and g have the same domain either, I think the solution works the same

Amar Hadzihasanovic (Aug 19 2022 at 10:07):

The only effect of having different domains is that $\sum_i f_i$ and $\sum_i g_i$ will be different!

Naso (Aug 19 2022 at 10:19):

thanks a lot, Amar :)

Naso (Aug 20 2022 at 02:55):

Amar Hadzihasanovic said:

I proved that there are no equalisers of co-degeneracies in the simplex category while I think what you are asking is essentially whether there are pullbacks of co-degeneracies in the simplex category.

what is really the correct way to phrase this? The pullback is actually happening in simplicial sets, but we want the cone point to be in the image of the Yoneda embedding? Or can we say the pullback is happening in the simplex category since the Yoneda embedding preserves & reflects limits?If so, can we prove this in a more abstract way, by just citing that the simplex category has all limits, or at least pullbacks (if that is true?)

Amar Hadzihasanovic (Aug 20 2022 at 07:49):

I guess I was a bit imprecise; I think the statement is that there are pullbacks in the category of simplices & co-degeneracy maps.

Amar Hadzihasanovic (Aug 20 2022 at 07:51):

We can tell that these are not pullbacks in the simplex category (including co-faces) because otherwise they would be preserved by the Yoneda embedding, but they are certainly not pullbacks in the category of simplicial sets.

Amar Hadzihasanovic (Aug 20 2022 at 07:57):

Mmm maybe that's not right either. The “unification” as I described it would not really be unique in general... it's probably something weaker than a pullback...

Amar Hadzihasanovic (Aug 20 2022 at 08:31):

Ok, I think I see what the correct statement is -- it's a bit weaker than the existence of pullbacks

Amar Hadzihasanovic (Aug 20 2022 at 08:33):

Let $\Delta_d$ be the category of simplices and co-degeneracy maps; equivalently, this is the category whose

• objects are finite linear orders $(n) = (0 < \ldots < n)$ for $n \in \mathbb{N}$, and
• morphisms are surjective order-preserving maps.

Amar Hadzihasanovic (Aug 20 2022 at 08:35):

For each $n$, we consider the poset $\mathrm{Deg}_n$ whose

• objects are maps $f: (m) \to (n)$ in $\Delta_d$ with target $(n)$, and
• $f \leq g$ if and only if $f$ factors through $g$ (that is, $f = h;g$ for some co-degeneracy $h$).

This is the poset reflection of the slice category $\Delta_d / (n)$.

Amar Hadzihasanovic (Aug 20 2022 at 08:39):

Claim: for all $n$, the poset $\mathrm{Deg}_n$ has binary meets; that is, for all $f, g$, there is a “greatest” $f \land g$ that factors through $f$ and $g$, in the sense that

• $f \land g$ factors through $f$ and $g$, and
• any $h$ that factors through $f$ and $g$ also factors through $f \land g$.

Amar Hadzihasanovic (Aug 20 2022 at 08:40):

(This would be implied by $\Delta_d$ having pullbacks, which is the same as $\Delta_d / (n)$ having products for all $(n)$, but it is strictly weaker, and in fact the stronger statement does not hold).

Amar Hadzihasanovic (Aug 20 2022 at 08:43):

Proof: given $f: (m_1) \to (n)$ and $g: (m_2) \to (n)$, represent them as sequences $(f_0, \ldots, f_n)$ and $(g_0, \ldots, g_n)$ with $m_1 = \sum_i f_i$ and $m_2 = \sum_i g_i$, with the interpretation that I gave above ($f$ sends the first $f_0$ elements to $0$, the next $f_1$ to $1$, etc).

Amar Hadzihasanovic (Aug 20 2022 at 08:44):

Let $f \land g: (m) \to (n)$ correspond to the sequence $(max(f_0, g_0), \ldots, max(f_n, g_n))$, where $m := \sum_i max(f_i, g_i)$.

Amar Hadzihasanovic (Aug 20 2022 at 08:46):

Then $f \land g$ factors through $f$ (possibly non-uniquely): take any sequence of $n+1$ surjective maps $(max(f_i, g_i)) \to (f_i)$, and concatenate them together to get a surjective map $f_1: (m) \to (m_1)$ such that $f \land g = f_1 ; f$.
Similarly, $f \land g$ factors through $g$ (possibly non-uniquely).

Amar Hadzihasanovic (Aug 20 2022 at 08:49):

Let $h: (m') \to (n)$ be any other map that factors through both $f$ and $g$, and is represented by the sequence $(h_0, \ldots, h_n)$.

Amar Hadzihasanovic (Aug 20 2022 at 08:53):

Then it is straightforward to see that $h_i \geq f_i$ and $h_i \geq g_i$ for all $i$ (this is essentially the fact that the size of inverse images of an element can only increase by precomposition with a surjective map)

Amar Hadzihasanovic (Aug 20 2022 at 08:54):

It follows that $h_i \geq max(f_i, g_i)$ for all $i$. Then taking any sequence of $n+1$ surjective maps $(h_i) \to (max(f_i, g_i))$ and concatenating them together, we get a map $k: (m') \to (m)$ such that $h = k; (f \land g)$, and that completes the proof.

Amar Hadzihasanovic (Aug 20 2022 at 08:58):

So what follows is that if $f^* z$ and $g^* z$ are degenerate simplices coming from the same simplex, $(f \land g)^* z$ is the “smallest unifier” in this sense: if $h^* z$ is a degeneracy of both $f^* z$ and $g^* z$, then it is a degeneracy of $(f \land g)^* z$.

Naso (Aug 20 2022 at 14:12):

Thank you so much, Amar, this is all so helpful. I see your point about nonuniqueness meaning this is not a pullback.

Regarding the sequence notation, should it be that $\sum_{i=0}^n f_i = m_1 + 1$ instead of $m_1$? E.g. in your original example, if $f: (2) \to (1)$ is $001$, then $(f_0,f_1) = (2,1)$ and $2 + 1 = 3$ ?

(If you don't mind I'll acknowledge your support with this in my thesis.)

Amar Hadzihasanovic (Aug 20 2022 at 15:07):

Ah yes, sure, you should increase all those by 1.