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: learning: questions

Topic: "Unbiased" definition of composition?

Shea Levy (Oct 07 2020 at 23:30):

The nlab page on biased definitions mentions a potential unbiased definition of composition, i.e. one in which we directly define composites of all finite sequences of arrows and appropriate associativity laws. I can't figure out a way to make this work without at some point smuggling in a privileged binary "composability" predicate (i.e. that each arrow composes with the next in the sequence). Is there a way to define this without making 2 special?

Nathanael Arkor (Oct 07 2020 at 23:34):

Biased operations are still ordered: you simply have a family of n-ary operators that are coherent in some sense. The number 2 is only privileged in that every element of a list (that is not the first nor last) has elements immediately to the left and to the right. If you remove the compatibility between the source and target of a morphism, you no longer have a category at all.

Shea Levy (Oct 07 2020 at 23:45):

Hmm maybe it would help to see the details of how the operators are coherent? Is that spelled out anywhere?

John Baez (Oct 07 2020 at 23:46):

There are references at the bottom here:

https://www.epatters.org/wiki/algebra/unbiased-monoidal-categories.html

sarahzrf (Oct 08 2020 at 04:01):

Nathanael Arkor said:

Biased operations are still ordered: you simply have a family of n-ary operators that are coherent in some sense. The number 2 is only privileged in that every element of a list (that is not the first nor last) has elements immediately to the left and to the right. If you remove the compatibility between the source and domain of a morphism, you no longer have a category at all.

...ive actually been vaguely bugged by this before :joy:

sarahzrf (Oct 08 2020 at 04:01):

er, namely that 2 is necessarily privileged in this sense, in a category

sarahzrf (Oct 08 2020 at 04:02):

we have all these shapes for higher categories, what makes us so sure that one domain one codomain a line from the former to the latter is the correct shape for the foundational and most ubiquitous version?

sarahzrf (Oct 08 2020 at 04:02):

(it usually passes after a little while...)

Morgan Rogers (he/him) (Oct 08 2020 at 07:54):

Wouldn't you just have an n-ary predicate for each n? As in $C(f_1,\dotsc,f_n)$ if this sequence is a composable one?

Shea Levy (Oct 08 2020 at 09:50):

John Baez said:

There are references at the bottom here:

https://www.epatters.org/wiki/algebra/unbiased-monoidal-categories.html

Ah, I think this helps! Specifically the second paragraph of this MO question. I think where it seemed like 2 was being privileged is the fact that there's no way to break down 2 into $\sum_{i=1}^{r} k_i$ without either r or some $k_i$ being at least 2.

So here's my first attempt at spelling this out:

1. For all n, we have a partial n-ary operator over arrows $comp_n$
2. If $comp_{r}(comp_{k_1}({f_1}_1, ..., {f_1}_{k_1}), ..., comp_{k_r}({f_r}_1, ..., {f_r}_{k_r}))$ is well-defined for some given $f$ s, then $comp_{\sum_{i=1}^{r} k_i}({f_1}_1, ..., {f_r}_{k_r})$ is well-defined and equal to it.
3. If $comp_{\sum_{i=1}^{r} k_i}({f_1}_1, ..., {f_r}_{k_r})$ is well-defined, then $comp_{r}(comp_{k_1}({f_1}_1, ..., {f_1}_{k_1}), ..., comp_{k_r}({f_r}_1, ..., {f_r}_{k_r}))$ is well-defined (and, by 2, equal to it)

But this can't quite be right, because it would require $comp_0$ to be a nullary function, i.e. the same arrow no matter where it's composed. I can think of a few options for amending this, but I'm now trying to find which one seems the best fit (ideally one that is still "arrows-only").

Nathanael Arkor (Oct 08 2020 at 10:56):

sarahzrf said:

we have all these shapes for higher categories, what makes us so sure that one domain one codomain a line from the former to the latter is the correct shape for the foundational and most ubiquitous version?

Fortunately, if you're skeptical, multicategories (…polycategories, properads, operadic categories, etc.) have you covered.

Nathanael Arkor (Oct 08 2020 at 10:59):

@Shea Levy: there's a explicit definition of an unbiased bicategory in Higher Operads, Higher Categories, which should give you what you need. In particular, composition is defined not for every $n \in \mathbb N$, but instead for every finite nonempty sequence of objects.

Shea Levy (Oct 08 2020 at 11:01):

Nathanael Arkor said:

Shea Levy: there's a explicit definition of an unbiased bicategory in Higher Operads, Higher Categories, which should give you what you need. In particular, composition is defined not for every $n \in \mathbb N$, but instead for every finite sequence of objects.

Thanks! Will take a look. If you happen to know off-hand, what is the arity/meaning of $comp_{[]}$?

Nathanael Arkor (Oct 08 2020 at 11:02):

Sorry, I should have said "finite nonempty sequence of objects". The singleton list referring to the identity morphisms.

Shea Levy (Oct 08 2020 at 11:06):

Nathanael Arkor said:

Sorry, I should have said "finite nonempty sequence of objects". The singleton list referring to the identity morphisms.

Ah, got it! So $comp_l$ has arity $len(l) - 1$ and the $i$'th argument has domain $l[i]$ and codomain $l[i + 1]$ ?

Nathanael Arkor (Oct 08 2020 at 11:12):

You have a composition operation $\mathsf{comp}_{A_0, A_1, \ldots, A_n}$ for $n \in \mathbb N$. So the arities are $\sum_{n \in \mathbb N} \mathrm{List}_{n + 1}(|\mathbb C_0|)$, for $\mathbb C_0$ the class of objects.

Paolo Perrone (Oct 08 2020 at 18:57):

To toot my own horn: in my notes, sections 4.2.2 and 5.5.1, composition of arrows in a category is defined in a fully unbiased way.

Shea Levy (Oct 13 2020 at 14:25):

How does this work in the context of polycategories? Having a hard time generalizing this and still keeping both nullary and unary composition

Nathanael Arkor (Oct 13 2020 at 14:30):

Composition can be seen graphically as contracting certain subgraphs: for a category, we can contract any sequence of consecutive edges; for a multicategory we can contract trees; for polycategories we can contract certain graphs (distinguishing the edges along which we are composing). I believe you can extract a definition of unbiased polycategorical composition in this vein from Garner's Polycategories via pseudo-distributive laws.

Shea Levy (Oct 13 2020 at 16:51):

I've got one form that works assuming exclusively non-empty domains and codomains, and one that works if you have composition along no objects (and an identity arrow from an empty domain to an empty codomain). Trying to get one that works without either of this extra stuff

Shea Levy (Oct 13 2020 at 17:11):

Hmm I think maybe there's not going to be a clean solution. The problem is, if I understand polycategory composition correctly, if you have $f \circ g \circ h \circ \iota \circ j$, $f$ can have empty codomain and $j$ can have empty domain but all the rest have to be non-empty.

Shea Levy (Oct 14 2020 at 21:13):

Shea Levy said:

How does this work in the context of polycategories? Having a hard time generalizing this and still keeping both nullary and unary composition

Figured this out and implemented it in coq for the specific case of sequent calculus treated as a thin polycategory (not necessarily admitting exchange). It's not pretty, but the basic idea is that for every non-empty list of the form $[ \overrightarrow{P}, (\overrightarrow{Q'}, Q, \overrightarrow{Q}), ..., (\overrightarrow{R'}, R, \overrightarrow{R}), \overrightarrow{S}]$ we have an operator comp that takes $f : \overrightarrow{P} \to Q, \overrightarrow{Q'}$, $g : Q, \overrightarrow{Q} \to ...$, $h : ... \to R, \overrightarrow{R'}$, $\iota : R, \overrightarrow{R} \to \overrightarrow{S}$ to the expected composition. All the object vectors, $\overrightarrow{P}$ and $\overrightarrow{S}$ in particular, are allowed to be empty, and we also allow $[R]$ as an index for the identity (this last is less contrived in the implementation, but harder to cover the explanation).