## November 7, 2017

### The Polycategory of Multivariable Adjunctions

#### Posted by Mike Shulman Adjunctions are well-known and fundamental in category theory. Somewhat less well-known are two-variable adjunctions, consisting of functors $f:A\times B\to C$, $g:A^{op}\times C\to B$, and $h:B^{op}\times C\to A$ and natural isomorphisms

$C(f(a,b),c) \cong B(b,g(a,c)) \cong A(a,h(b,c)).$

These are also ubiquitous in mathematics, for instance in the notion of closed monoidal category, or in the hom-power-copower situation of an enriched category. But it seems that only fairly recently has there been a wider appreciation that it is worth defining and studying them in their own right (rather than simply as a pair of parametrized adjunctions $f(a,-)\dashv g(a,-)$ and $f(-,b) \dashv h(b,-)$).

Now, ordinary adjunctions are the morphisms of a 2-category $Adj$ (with an arbitrary choice of direction, say pointing in the direction of the left adjoint), whose 2-cells are compatible pairs of natural transformations (a fundamental result being that either uniquely determines the other). It’s obvious to guess that two-variable adjunctions should be the binary morphisms in a multicategory of “$n$-ary adjunctions”, and this is indeed the case. In fact, Eugenia, Nick, and Emily showed that multivariable adjunctions form a cyclic multicategory, and indeed even a cyclic double multicategory.

In this post, however, I want to argue that it’s even better to regard multivariable adjunctions as forming a slightly different structure called a polycategory.

What is a polycategory? The first thing to say about it is that it’s like a multicategory, but it allows the codomain of a morphism to contain multiple objects, as well as the domain. Thus we have morphisms like $f: (A,B) \to (C,D)$. However, this description is incomplete, even informally, because it doesn’t tell us how we are allowed to compose such morphisms. Indeed, there are many different structures that admit this same description, but differ in the ways that morphisms can be composed.

One such structure is a prop, which John and his students have been writing a lot about recently. In a prop, we compose by simply matching domains and codomains as lists — given $f: (A,B) \to (C,D)$ and $g:(C,D) \to (E,F)$ we get $g\circ f : (A,B) \to (E,F)$ — and we can also place morphisms side by side — given $f:(A,B) \to (C,D)$ and $f':(A',B') \to (C',D')$ we get $(f,f') : (A,B,A',B') \to (C,D,C',D')$.

A polycategory is different: in a polycategory we can only “compose along single objects”, with the “leftover” objects in the codomain of $f$ and the domain of $g$ surviving into the codomain and domain of $g\circ f$. For instance, given $f: (A,B) \to (C,D)$ and $g:(E,C) \to (F,G)$ we get $g\circ_C f : (E,A,B) \to (F,G,D)$. This may seem a little weird at first, and the usual examples (semantics for two-sided sequents in linear logic) are rather removed from the experience of most mathematicians. But in fact it’s exactly what we need for multivariable adjunctions!

I claim there is a polycategory $MVar$ whose objects are categories and whose “poly-arrows” are multivariable adjunctions. What is a multivariable adjunction $(A,B) \to (C,D)$? There’s really only one possible answer, once you think to ask the question: it consists of four functors

$f:C^{op}\times A\times B \to D \quad g:A \times B \times D^{op} \to C \quad h : A^{op}\times C\times D\to B \quad k : C\times D \times B^{op}\to A$

and natural isomorphisms

$D(f(c,a,b),d) \cong C(g(a,b,d),c) \cong B(b,h(a,c,d)) \cong A(a,k(c,d,b)).$

I find this definition quite illuminating already. One of the odd things about a two-variable adjunction, as usually defined, is the asymmetric placement of opposites. (Indeed, I suspect this oddness may have been a not insignificant inhibitor to their formal study.) The polycategorical perspective reveals that this arises simply from the asymmetry of having a 2-ary domain but a 1-ary codomain: a “$(2,2)$-variable adjunction” as above looks much more symmetrical.

At this point it’s an exercise for the reader to write down the general notion of $(n,m)$-variable adjunction. Of course, a $(1,1)$-variable adjunction is an ordinary adjunction, and a $(2,1)$-variable adjunction is a two-variable adjunction in the usual sense. It’s also a nice exercise to convince yourself that polycategory-style composition “along one object” is also exactly right for multivariable adjunctions. For instance, suppose in addition to $(f,g,h,k) : (A,B) \to (C,D)$ as above, we have a two-variable adjunction $(\ell,m,n) : (D,E)\to Z$ with $Z(\ell(d,e),z) \cong D(d,m(e,z)) \cong E(e,n(d,z))$. Then we have a composite multivariable adjunction $(A,B,E) \to (C,Z)$ defined by $C(g(a,b,m(e,z)),c) \cong Z(\ell(f(c,a,b),e),z) \cong A(a,k(c,m(e,z),b)) \cong \cdots$

It’s also interesting to consider what happens when the domain or codomain is empty. For instance, a $(0,2)$-variable adjunction $() \to (A,B)$ consists of functors $f:A^{op}\to B$ and $g:B^{op}\to A$ and a natural isomorphism $B(b,f(a)) \cong A(a,g(b))$. This is sometimes called a mutual right adjunction or dual adjunction, and such things do arise in plenty of examples. Many Galois connections are mutual right adjunctions between posets, and also for instance the contravariant powerset functor is mutually right adjoint to itself. Similarly, a $(2,0)$-variable adjunction $(A,B) \to ()$ is a mutual left adjunction $B(f(a),b) \cong A(g(b),a)$. Of course a mutual right or left adjunction can also be described as an ordinary adjunction between $A^{op}$ and $B$, or between $A$ and $B^{op}$, but the choice of which category to oppositize is arbitrary; the polycategory $MVar$ respects mutual right and left adjunctions as independent objects rather than forcing them into the mold of ordinary adjunctions.

More generally, a $(0,n)$-variable adjunction $() \to (A_1,\dots,A_n)$ is a “mutual right multivariable adjunction” between $n$ contravariant functors $f_i : A_{i+1}\times \cdots \times A_n \times A_1 \times \cdots \times A_{i-1}\to A_i^{op}.$ Just as a $(0,2)$-variable adjunction can be forced into the mold of a $(1,1)$-variable adjunction by oppositizing one category, an $(n,1)$-variable adjunction can be forced into the mold of a $(0,n)$-variable adjunction by oppositizing all but one of the categories — Eugenia, Nick, and Emily found this helpful in describing the cyclic action. But the polycategory $MVar$ again treats them as independent objects.

What role, then, do opposite categories play in the polycategory $MVar$? Or put differently, what happened to the cyclic action on the multicategory? The answer is once again quite beautiful: opposite categories are duals. The usual notion of dual pair $(A,B)$ in a monoidal category consists of a unit and counit $\eta : I \to A\otimes B$ and $\varepsilon :B \otimes A \to I$ satisfying the triangle identities. This cannot be phrased in a mere multicategory, because $\eta$ involves two objects in its codomain (and $\varepsilon$ involves zero), whereas in a multicategory every morphism has exactly one object in its codomain. But in a polycategory, with this restriction lifted, we can write $\eta : () \to (A, B)$ and $\varepsilon : (B,A)\to ()$, and it turns out that the composition rule of a polycategory is exactly what we need for the triangle identities to make sense: $\varepsilon \circ_A \eta = 1_{B}$ and $\varepsilon \circ_{B} \eta = 1_A$.

What is a dual pair in $MVar$? As we saw above, $\eta$ is a mutual right adjunction $B(b,\eta_1(a)) \cong A(a,\eta_2(b))$, and $\varepsilon$ is a mutual left adjunction $B(\varepsilon_1(a),b) \cong A(\varepsilon_2(b),a)$. The triangle identities (suitably weakened up to isomorphism) say that $\varepsilon_2 \circ \eta_1 \cong 1_A$ and $\eta_2 \circ \varepsilon_1 \cong 1_A$ and $\varepsilon_1 \circ \eta_2 \cong 1_B$ and $\eta_1 \circ \varepsilon_2 \cong 1_B$; thus these two adjunctions are actually both the same dual equivalence $B\simeq A^{op}$. In particular, there is a canonical dual pair $(A,A^{op})$, and any other dual pair is equivalent to this one.

Let me say that again: in the polycategory $MVar$, opposite categories are duals. I find this really exciting: opposite categories are one of the more mysterious parts of category theory to me, largely because they don’t have a universal property in $Cat$; but in $MVar$, they do! To be sure, they also have universal properties in other places. In 1606.05058 I noted that you can give them a universal property as a representing object for contravariant functors; but this is fairly tautological. And it’s also well-known that they are duals in the usual monoidal sense (not our generalized polycategory sense) in the monoidal bicategory Prof; but this characterizes them only up to Morita equivalence, whereas the duality in $MVar$ characterizes them up to ordinary equivalence of categories. Of course, we did already use opposite categories in defining the notion of multivariable adjunction, so it’s not as if this produces them out of thin air; but I do feel that it does give an important insight into what they are.

In particular, the dual pair $(A,A^{op})$ allows us to implement the “cyclic action” on multivariable adjunctions by simple composition. Given a $(2,1)$-variable adjunction $(A,B) \to C$, we can compose it polycategorically with $\eta : () \to (A,A^{op})$ to obtain a $(1,2)$-variable adjunction $B \to (A^{op},C)$. Then we can compose that with $\varepsilon : (C^{op},C)\to ()$ to obtain another $(2,1)$-variable adjunction $(B,C^{op})\to A^{op}$. This is exactly the action of the cyclic structure described by Eugenia, Nick, and Emily on our original multivariable adjunction. (In fact, there’s a precise sense in which a cyclic multicategory is “almost” equivalent to a polycategory with duals; for now I’ll leave that as an exercise for the reader.)

Note the similarity to how dual pairs in a monoidal category shift back and forth: $Hom(A\otimes B, C) \cong Hom(B, A^\ast \otimes C) \cong Hom(B\otimes C^\ast, A^\ast).$ In string diagram notation, the latter is represented by “turning strings around”, regarding the unit and counit of the dual pair $(A,A^\ast)$ as a “cup” and “cap”. Pleasingly, there is also a string diagram notation for polycategories, in which dual pairs behave exactly the same way; we simply restrict the ways that strings are allowed to be connected together — for instance, no two vertices can be joined by more than one string. (More generally, the condition is that the string diagram should be “simply connected”.)

In future posts I’ll explore some other neat things related to the polycategory $MVar$. For now, let me leave you with some negative thinking puzzles:

• What is a $(0,1)$-variable adjunction?
• How about a $(1,0)$-variable adjunction?
• How about a $(0,0)$-variable adjunction?
Posted at November 7, 2017 10:45 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2992

### Re: The polycategory of multivariable adjunctions

I forgot to mention that a one-object (symmetric) polycategory is also known as a dioperad. So if you know what a dioperad is, then you know what a polycategory is: it’s a “colored dioperad”.

Posted by: Mike Shulman on November 7, 2017 6:38 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Very nice! Some time ago I thought about a generalized version of the Chu construction, that takes a (symmetric?) multicategory to a *-polycategory. Perhaps I read it somewhere or perhaps I worked it out for myself, I can’t remember. Anyway, all this resembles an instance of that. But perhaps you were coming to that in a future installment?

Posted by: Sam S on November 7, 2017 10:43 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Yes, it is closely related to a kind of Chu construction — and yes, that’s the subject of the next post in the series!

Posted by: Mike Shulman on November 8, 2017 3:31 AM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Are there any examples of (2,2)-variable (or more) adjunctions in the wild?

Also, one of the fundamental operations on a biadjunction $(A, B) \to C$ is to make it into a biadjunction $(A^{J^{\mathrm{op}}}, B^J) \to C$ by the usual (co)end formulas over some small category $J$ (provided $A$, $B$ and $C$ are sufficiently (co)complete). Just like biadjuctions themselves, this feels rather asymmetric. Does the polycategory framework reveal this as a special case of something more natural?

Posted by: Karol Szumiło on November 8, 2017 12:38 AM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Are there any examples of (2,2)-variable (or more) adjunctions in the wild?

No and yes.

I don’t currently know of any examples of $(n,m)$-variable adjunctions for $n+m\gt 3$ that are “basic”, i.e. not obtained as composites of several $(n,m)$-variable adjunctions with $n+m\le 3$. I don’t find this surprising, since it’s already rare to find $n$-ary morphisms in a multicategory for $n\gt 2$ that aren’t obtained as composites of binary morphisms; they certainly do exist, but they’re harder to come by. So I expect that basic higher-ary adjunctions exist too, but I’m not surprised that I haven’t thought of any yet.

If you drop the “basic” condition, then of course a (2,2)-variable adjunction can be obtained from a (3,1)-variable adjunction by dualizing one of the categories, and a (3,1)-variable adjunction can be obtained by composing two (2,1)-variable adjunctions. For instance, the ternary tensor product in a closed monoidal category gives a (3,1)-variable adjunction $(A,A,A) \to A$:

$A(x\otimes y\otimes z, w) \cong A(x, (w\lhd z)\lhd y) \cong A(y, x \rhd w \lhd z) \cong A(z, y \rhd (x\rhd w))$

which we can turn sideways and regard as a (2,2)-variable adjunction $(A,A) \to (A,A^{op})$. But this isn’t very satisfying either.

I do know of one class of examples of (2,2)-variable adjunctions that are obtained by composing a (2,1)-variable adjunction with a (1,2)-variable adjunction. However, that’s the subject of the third post in this series, so I’m not going to give it away just yet! Feel free to guess however… (-:

one of the fundamental operations on a biadjunction $(A, B) \to C$ is to make it into a biadjunction $(A^{J^{\mathrm{op}}}, B^J) \to C$ by the usual (co)end formulas over some small category $J$ (provided $A$, $B$ and $C$ are sufficiently (co)complete). Just like biadjuctions themselves, this feels rather asymmetric. Does the polycategory framework reveal this as a special case of something more natural?

First a note: the word “biadjunction” is generally used to mean “weak (one-variable) 2-adjunction” (i.e. an adjunction between bicategories), so we ought to avoid using it to mean “two-variable adjunction”.

Now to the question, which is a good one! Note that already in the (2,1)-variable case, this construction can be done on any 2 of the 3 categories involved: in addition to $(A^{J^{\mathrm{op}}}, B^J) \to C$ we can get $(A, B^J) \to C^J$ and $(A^J, B) \to C^J$. I expect that the same is true in the $(n,m)$-variable case: we can choose any two of the categories to exponentiate by $J$, and if they are both in the codomain or both in the domain then one of the exponents has to be $op$‘d, whereas if one is in the domain and one in the codomain then they can get the same exponent. Does that count as more natural?

Posted by: Mike Shulman on November 8, 2017 3:54 AM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

First a note: the word “biadjunction” is generally used to mean “weak (one-variable) 2-adjunction” (i.e. an adjunction between bicategories), so we ought to avoid using it to mean “two-variable adjunction”.

Good point. Unfortunately, I have a tendency to get confused by 2-categorical terminology.

Now to the question, which is a good one! Note that already in the (2,1)-variable case, this construction can be done on any 2 of the 3 categories involved: in addition to $(A^{J^{\mathrm{op}}}, B^J) \to C$ we can get $(A, B^J) \to C^J$ and $(A^J, B) \to C^J$. I expect that the same is true in the $(n,m)$-variable case: we can choose any two of the categories to exponentiate by $J$, and if they are both in the codomain or both in the domain then one of the exponents has to be op‘d, whereas if one is in the domain and one in the codomain then they can get the same exponent. Does that count as more natural?

Yes, this is quite compelling, but I think we can hope for more. The situation feels more symmetric, although it still seems that adjunctions $(A, B^J) \to C^J$ and $(A^J, B) \to C^J$ are closely related while the other one is odd one out. Perhaps there is some 3-fold symmetry in the fact that in each case one of the adjoints is given by a (co)end and the other two are “pointwise”. I don’t know what to make of it, but perhaps there is relation between these adjunctions in terms of duality that you described in the end.

Another similar observation is that for a (2,1)-variable adjunction $(A, B) \to C$ and any functor $I \times J \to K$ there is a Day convolution adjunction $(A^I, B^J) \to C^K$. Maybe this also has an interesting generalization to the $(m,n)$ case.

Posted by: Karol Szumiło on November 8, 2017 7:39 AM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

it still seems that adjunctions $(A, B^J) \to C^J$ and $(A^J, B) \to C^J$ are closely related while the other one is odd one out.

I think that’s an illusion. The point is your next sentence:

Perhaps there is some 3-fold symmetry in the fact that in each case one of the adjoints is given by a (co)end and the other two are “pointwise”.

Here’s another way to describe the same structure as a polycategory with duals or a cyclic multicategory: get rid of the idea that morphisms have a “domain” or “codomain” entirely. Instead each morphism just has a list of objects called its “entries”. There is an involution $(-)^\bullet$ on the objects, and the composition operation is $M(A_1,\dots,A_n) \times M(B_1,\dots, B_m) \to M(A_1,\dots,A_{n-1},B_2,\dots,B_m)$ if $B_1 = A_n^\bullet$ (or equivalently $A_n = B_1^\bullet$). People who work with cyclic operads (one-object cyclic multicategories) are familiar with this, whereas people who think of polycategories as semantics for linear logic are familiar with the syntactic version of it (one-sided sequents $\vdash \Gamma$).

To make a polycategory into an “entries-only polycategory”, define $M(A_1,\dots,A_n)$ to be the arrows $(A_1,\dots,A_n) \to ()$ with empty target. (Or empty source; the involution mediates the difference). Conversely, given an entries-only polycategory, define an arrow $(A_1,\dots,A_n) \to (B_1,\dots,B_m)$ to be a morphism in $M(A_1,\dots,A_n,B_1^\bullet,\dots,B_m^\bullet)$. In the case of $MVar$, this corresponds to forcing all multivariable adjunctions to be “mutual right” (or mutual left).

In the entries-only version, all the exponentiation operations are the same: $M(A_1,\dots ,A_n) \to M(A_1,\dots,A_i^J, \dots ,A_j^{J^{op}},\dots,A_n)$. The apparent difference between $(A, B^J) \to C^J$ and $(A^J, B^{J^{op}})\to C$ is just an artifact of the separation of domain and codomain.

Another similar observation is that for a (2,1)-variable adjunction $(A, B) \to C$ and any functor $I \times J \to K$ there is a Day convolution adjunction $(A^I, B^J) \to C^K$. Maybe this also has an interesting generalization to the $(m,n)$ case.

Yes, I think it does. (Of course, you still need $A,B,C$ to be complete and cocomplete.) In fact, I think your functor $I \times J \to K$ only needs to be a profunctor. And at that level of generality, this observation subsumes the previous one: to get $(A, B^J) \to C^J$ use the functor $1\times J \to J$, while to get $(A^J, B^{J^{op}})\to C$ use the profunctor $J\times J^{op} \to 1$.

I wonder whether this can be regarded as some kind of “action” of $Prof$ on $MVar$.

Posted by: Mike Shulman on November 8, 2017 4:42 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

I wonder whether this can be regarded as some kind of “action” of $Prof$ on $MVar$.

This seems plausible from the perspective of seeing multivariable adjunctions as “representable profunctors” that you mentioned in another comment. Say we have an $(m,n)$-variable adjunction presented as a profunctor $P \colon A_1 \times \ldots \times A_m \nrightarrow B_1 \times \ldots \times B_n$ and a profunctor $U \colon J_1 \times \ldots \times J_m \nrightarrow K_1 \times \ldots \times K_n$. (BTW, does itex have a better arrow than $\nrightarrow$ for profunctors?) Then it seems to me that the “Day convolution of $P$ by $U$” is a profunctor $A_1^{J_1} \times \ldots \times A_m^{J_m} \nrightarrow B_1^{K_1} \times \ldots \times B_n^{K_n}$ given by the end

$\int_{j_1, \ldots, j_m, k_1, \ldots, k_n} P(a_1(j_1), \ldots, a_m(j_m), b_1(k_1), \ldots, b_n(k_n))^{U(j_1, \ldots, j_m, k_1, \ldots, k_n)} \text{.}$

I think I can see that this is an $(m,n)$-variable adjunction again and that this is associative with respect to “cartesian product” of profunctors. It should be also compatible with the polycategorical composition, but I haven’t digested that enough yet.

Posted by: Karol Szumiło on November 10, 2017 1:46 AM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Yes, that’s a good perspective. It seems like we are seeing a restriction to $MVar$ of some kind of action of $Prof$ on itself.

I don’t think iTeX has a better command for profunctors, but I sometimes write the HTML entity &#8696; giving $A ⇸ B$.

Posted by: Mike Shulman on November 10, 2017 8:05 AM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Is there more to be said about the string diagrams for polycategories than what you wrote in the post? (By the way, the link to your stratified surface diagrams mentioned in that earlier post is dead.

No time this morning to work out your negative thinking puzzles. I got about as far as thinking in the (0, 1) and (1, 0) cases that there would only be one functor involved from $\mathbf{1}$ to $A$ or $A^{op}$, and that there would only be one hom set available for an adjunction isomorphism.

Then there was some worry about whether to consider $(A)$ and $(A, \mathbf{1})$ and $(A, \mathbf{1}, \mathbf{1})$, etc. as ‘different’. But time for tasks unfortunately.

Posted by: David Corfield on November 8, 2017 8:55 AM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

super-secret decoder ring here

Va bgure jbeqf, n (0,1)-nqwhapgvba vf na bowrpg va n pngrtbel; juvyr gurer vf rffragvnyyl bar (0,0)-nqwhapgvba.

Posted by: Jesse C. McKeown on November 8, 2017 2:32 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Va bgure jbeqf, n (0,1)-nqwhapgvba vf na bowrpg va n pngrtbel; juvyr gurer vf rffragvnyyl bar (0,0)-nqwhapgvba.

Don’t feel bad, though; I got the (0,0)-case wrong the first time too. It’s a tricky one. If no one gets it after a while I’ll give some hints.

Posted by: Mike Shulman on November 8, 2017 4:55 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Posted by: David Corfield on November 8, 2017 5:34 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Posted by: Mike Shulman on November 8, 2017 5:38 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Is $\mathrm{MVar}$ representable?

If there is a unit object $\mathbf{1}$, because $(0,1)$-adjunctions are just objects, we would need, at least, a bijection between objects of a category $C$ and adjunctions $(f,g): \mathbf{1} \to C$. The closest thing I can think of is the fact that, if $C$ has arbitrary copowers of objects, an adjunction $(f,g): \mathbf{Set} \to C$ is essentially determined by the object $f(1)$, the image of a singleton set: up to isomorphism, $f$ maps the set $X$ to the $X$th copower of $f(1)$, and $g$ is the representable functor $C(f(1),-)$.

I’m not sure how to bypass the “copowers exist” condition, but I’m still going to guess: $(0,0)$-adjunctions are adjunctions $\mathbf{Set} \to \mathbf{Set}^\mathrm{op}$ :)

### Re: The polycategory of multivariable adjunctions

…which of course are all of the form $X \mapsto A^X$ for some set $A$, that is, they are “the same” as sets.

### Re: The polycategory of multivariable adjunctions

Would composing a $(0, 1)$-adjunction with a $(1, 0)$-adjunction be worth trying?

So say we have $f: () \to A$ and $g: A \to ()$, two objects, $p,q$ of $A$, what can result from composition here?

It feels like I should speak about $Hom_A(p, q)$. Could a $(0, 0)$-adjunction just be a set?

Posted by: David Corfield on November 9, 2017 11:11 AM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Congratulations, Amar and David, you both got it right: the category of (0,0)-adjunctions is $Set^{op}$. (If our multivariable adjunctions pointed in the direction of the right adjoints instead of the left adjoints, it would be $Set$.)

There are several ways one can arrive at this answer, and you found two of the ones I was thinking of. Another is that a multivariable adjunction $(A_1,\dots,A_n) \to (B_1,\dots,B_m)$ can equivalently be defined as a profunctor $A_1\times\cdots\times A_n \to B_1 \times\cdots \times B_m$ that is “representable in each variable”, and a profunctor $1\to 1$ is just a set.

It’s worth noting that one isn’t technically forced to define (0,0)-adjunctions in this way; that is, one can make other choices and still get a 2-polycategory $MVar$. Because a (0,0)-ary morphism in a polycategory can’t be composed with anything else, it’s always possible to take a given polycategory and redefine there to be exactly one (0,0)-ary morphism. One can make other choices too, but the choice isn’t totally free, since as David pointed out we have to be able to compose a (0,1)-ary morphism and a (1,0)-ary morphism to get a (0,0)-ary morphism; in particular, as long as we have any of the former two, there has to be at least one (0,0)-ary morphism.

This is the minor difference between a cyclic multicategory and a polycategory with duals. Every symmetric polycategory with duals (at least, strictly involutive duals) has an underlying cyclic symmetric multicategory, this forgetful functor $U$ has both a left adjoint $L$ and a right adjoint $R$, and the adjunctions are almost equivalences: the unit $1 \to U L$ and counit $U R \to 1$ are isomorphisms, so that $L$ and $R$ are fully faithful, and the counit $L U \to 1$ and unit $1 \to R U$ are bijective on objects and act fully-faithfully on all kinds of morphisms except the (0,0)-ary ones. The composite $R U$ redefines there to be exactly one (0,0)-ary morphism as above, while $L U$ defines the (0,0)-ary morphisms to be freely generated by the composites of (1,0)-ary and (0,1)-ary ones subject to associativity.

If a cyclic multicategory happens to have a unit $\mathbf{1}$, then there is another way to make it into a polycategory with duals by taking the (0,0)-ary morphisms to be $\hom(\mathbf{1},\mathbf{1}^\bullet)$. And Amar is exactly right that while $MVar$ itself doesn’t have a unit, its full sub-polycategory on the complete and cocomplete categories does have $Set$ as a unit — at least, a unit up to equivalence of hom-categories.

Annoyingly, this breaks the otherwise completely strict aspect of the definition: except for the (0,0)-ary morphisms, $MVar$ is a strict 2-polycategory, but I haven’t been able to think of a way to define the (0,0)-ary morphisms correctly as (something equivalent to) $Set^{op}$ and retain the strictness of associativity, at least not without doing violence to the whole rest of the construction by applying some general strictification theorem for weak 2-polycategories (which I’m only presuming to exist anyway). Fortunately, since (0,0)-ary morphisms can’t be composed with anything else, for many purposes they can be safely ignored.

Also unfortunately, even the restriction of $MVar$ to complete and cocomplete categories is not representable: it doesn’t (I believe) have binary tensor products. But its further restriction to (small) complete posets does, essentially because the adjoint functor theorem for posets has no annoying solution-set conditions. We can try to categorify that by using locally presentable categories, whose adjoint functor theorem is always true, so that we at least get a multicategory with tensor products, hence a monoidal (2-)category; but since the opposite of a locally presentable category is no longer locally presentable (unless it was a poset to start with), we lose the duals (and the cotensor products) in this way.

This all leads nicely into my next post….

Posted by: Mike Shulman on November 9, 2017 12:09 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

So I thought you were going to do a weakened version of the Chu space construction in $\mathbf{Cat}$ with $K=\mathbf{Set}$, and embed this polycategory in it. And perhaps this is what you are going to do next time! And in Chu spaces, I think the morphisms $I\to I^{\bot}$ usually correspond to elements of $K$.

Posted by: Sam S on November 9, 2017 12:35 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Posted by: Mike Shulman on November 9, 2017 4:39 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Nice! In my thesis I looked at “regular polycategories”, where morphisms with 0-ary inputs or outputs are not allowed. It turns out that there is still a nice way of defining tensor and cotensor units, which induces the correct structure when paired with other representability conditions. Presumably, $\mathbf{Set}$ is a tensor unit in this sense, in the (strict) regular polycategory of complete and cocomplete categories and $(n,m)$-adjunctions, with $n,m \geq 1$.

On the other hand, with this restriction, duals have to be “relativised” to a choice of units, and then, presumably, opposite categories are only characterised up to Morita equivalence, like in $\mathrm{Prof}$

Looking forward to the next post!

### Re: The polycategory of multivariable adjunctions

Interesting, thanks for the pointer. But can you point me to exactly where in your thesis I should be looking? I don’t see any polycategories in the table of contents.

Posted by: Mike Shulman on November 9, 2017 4:15 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Sure: it is Section 3.3, and the definition of tensor units is at the beginning of Subsection 3.3.2.

### Re: The polycategory of multivariable adjunctions

Is there more to be said about the string diagrams for polycategories than what you wrote in the post?

Undoubtedly! (-:

The main reference that I know of for them is

• R. Blute, J.R.B. Cockett, R.A.G. Seely, T. Trimble, Natural deduction and coherence for weakly distributive categories, J. Pure Appl. Algebra, 113 (1996), pp. 229–296. (web)

They describe a “circuit diagram” calculus for not just polycategories but linearly distributive categories (“representable polycategories”). I haven’t really read the whole thing carefully, so I don’t know whether there is a condition like “simply connected” in there (the linearly distributive case is more complicated anyway). I took the “simply connected” condition from the “unbiased” description of polycategories in

• Richard Garner, Polycategories via pseudo-distributive laws, arXiv

I think I’ll have something else to say about these string diagrams in a later post, too.

(By the way, the link to your stratified surface diagrams mentioned in that earlier post is dead.

Yeah, and I don’t think I can do anything about it. My IAS webspace is dead, and I’m not sure what happened to that file. Sorry!

Posted by: Mike Shulman on November 8, 2017 5:04 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Paul-André Melliès has been arguing for a while that “decorrelating” a category from its opposite is a useful perspective in categorical logic. This seems to be a good setting for that idea. His notion of chirality, in particular, is the same as a dual pair $(A,B)$ in $\mathrm{MVar}$.

### Re: The polycategory of multivariable adjunctions

Yes, I’ve encountered that idea. I still haven’t understood the point, though. It seems very non-category-theoretic to distinguish between “a category” and “two categories that are (contravariantly) equivalent”.

Posted by: Mike Shulman on November 8, 2017 4:51 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

I believe the intuition, from game semantics, is that $A$ and $B$ are “player” and “opponent” views, which are a priori uncorrelated, and the equivalence $(A,B) \simeq (C,C^\mathrm{op})$ is a constraint: “the player and the opponent are, in fact, playing the same game”. In the end the structures obtained are equivalent, but I suppose one perspective may give a more direct translation of game semantics ideas.

Perhaps distinguishing between “categories” and “dual pairs in $\mathrm{MVar}$” sounds better, though?

### Re: The polycategory of multivariable adjunctions

You mention linear logic, but I should think we are already used to composing Theorems thus:

( P ) → ( S and T )

( T and W ) → ( X )

( P and W ) → ( S and X )

Posted by: Jesse C. McKeown on November 8, 2017 2:51 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

It’s true that I didn’t need to specify linear logic. But that’s not why!

When a polycategory is regarded as semantics for logic, the comma in the domain denotes “and”, but the comma in the codomain denotes “or”. So the relevant kind of composition of theorems is

( P ) $\to$ ( S or T )

( T and W ) $\to$ ( X )

( P and W ) $\to$ ( S or X )

which is still true. This gets into the notion of “linearly distributive category”, which is to a polycategory the way a monoidal category is to a multicategory, and has two tensor products. Those will come back in the next post too.

So why did I specifically say linear logic? Because to my knowledge, no one has come up with a good notion of “cartesian polycategory” that includes contraction and weakening on both sides and yet has non-posetal examples. The corresponding syntactic statement is that classical logic doesn’t seem to have a good “proof theory” that can distinguish multiple proofs of the same statement in any sensible way. So people who think about polycategories (rather than poly-posets) are usually using them for linear logic rather than classical logic.

Posted by: Mike Shulman on November 8, 2017 4:50 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Just to point out “Categorical Proof Theory of Classical Propositional Calculus”, by Bellin, Hyland, Robinson and Urban, 2006 (pdf), which is based around *-polycategories, but as far as I understand there’s still plenty of room for debate.

Posted by: Sam S on November 8, 2017 7:58 PM | Permalink | Reply to this

### Re: The polycategory of multivariable adjunctions

Intriguing, thanks for the link. But I’ll have a hard time being convinced of any such notion until I see nondegenerate examples that occur naturally in category theory, which I might be interested in even if I didn’t know or care about proof theory. (Ordinary polycategories, linearly distributive categories, and $\ast$-autonomous categories gave me the same problem, until I discovered Sup, $MVar$, and the Chu construction.)

Posted by: Mike Shulman on November 9, 2017 4:09 PM | Permalink | Reply to this

### Re: The Polycategory of Multivariable Adjunctions

I just want to state for the record that I’m totally convinced that the polycategory approach to composition of multivariable adjunctions is exactly the right thing. Kudos! I don’t suppose you could be persuaded to write a short paper about all of this?

One further comment: the problem that I took to Eugenia and Nick that launched our collaboration was to understand multivariate transpositions of composites of parametrized mates: given $n$-variable left adjoints

$f \colon A_1 \times \cdots \times A_n \to A_0$

$g \colon B_1 \times \cdots \times B_n \to B_0$

and functors $h_i \colon A_i \to B_i$, a natural transformation

$\alpha \colon g(h_1,\ldots, h_n) \Rightarrow h_0f$ has $n$ parametrized mates, one for each pair of adjoints to $f$ and $g$. For instance, such natural transformations arise when lifting an $n$-variable adjoint to categories of algebras or coalgebras.

In my PhD thesis, I encountered several diagrams involving composites of natural transformations like this and observed that they were equivalent to dual diagrams involving their parametrized mates, but I had difficulty visualizing the nature of this duality. Now, based on our joint work, I’d describe it as the “cyclic double multicategorical functoriality” of the parametrized mates correspondence.

So, Mike, what I’d really like you to put in your paper is a definition of the double polycategorical with duals MVar. I’ll look forward to reading it ;)

Posted by: Emily Riehl on November 24, 2017 4:14 PM | Permalink | Reply to this

### Re: The Polycategory of Multivariable Adjunctions

Thanks, I’m glad you like it!

There is a somewhat slick way of constructing a double polycategory $MVar$, starting from your construction of the cyclic double multicategory $MVar$. Up here I mentioned that the forgetful functor from polycategories with duals to cyclic multicategories has a left adjoint $L$ and a right adjoint $R$, which are fully faithful and almost equivalences. Since $R$ is a right adjoint, it preserves finite limits, and thus preserves internal categories; so applying it to a cyclic double multicategory produces a double polycategory. This doesn’t have the correct (0,0)-ary morphisms, but other than that it’s the right thing.

However, possibly a better way to construct the double polycategory $MVar$ would be to apply the 2-Chu construction from my next post to some double-categorical structure, since the Chu construction is also a right adjoint when suitably formulated, and then find $MVar$ inside it.

I’ve been waffling back and forth about how to make one or more papers out of the material in these three posts. At first I started writing it all as one paper, but it started feeling too long and unwieldy. Then I tried omitting the 2-Chu construction entirely and constructing $MVar$ in the first way, which is good enough for the Frobenius bits since the (0,0)-ary morphisms never appear there. But now your comment is making me think that perhaps one paper should construct $MVar$ via the 2-Chu construction, and then a second paper should do the Frobenius part.

Of course I don’t actually have time to be writing such a paper right now anyway…

Posted by: Mike Shulman on November 24, 2017 10:36 PM | Permalink | Reply to this

Post a New Comment