Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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×BCf:A\times B\to C, g:A op×CBg:A^{op}\times C\to B, and h:B op×CAh:B^{op}\times C\to A and natural isomorphisms

C(f(a,b),c)B(b,g(a,c))A(a,h(b,c)). 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,)g(a,)f(a,-)\dashv g(a,-) and f(,b)h(b,)f(-,b) \dashv h(b,-)).

Now, ordinary adjunctions are the morphisms of a 2-category AdjAdj (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 “nn-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)(C,D)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)(C,D)f: (A,B) \to (C,D) and g:(C,D)(E,F)g:(C,D) \to (E,F) we get gf:(A,B)(E,F)g\circ f : (A,B) \to (E,F) — and we can also place morphisms side by side — given f:(A,B)(C,D)f:(A,B) \to (C,D) and f:(A,B)(C,D)f':(A',B') \to (C',D') we get (f,f):(A,B,A,B)(C,D,C,D)(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 ff and the domain of gg surviving into the codomain and domain of gfg\circ f. For instance, given f:(A,B)(C,D)f: (A,B) \to (C,D) and g:(E,C)(F,G)g:(E,C) \to (F,G) we get g Cf:(E,A,B)(F,G,D)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 MVarMVar whose objects are categories and whose “poly-arrows” are multivariable adjunctions. What is a multivariable adjunction (A,B)(C,D)(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×A×BDg:A×B×D opCh:A op×C×DBk:C×D×B opA 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)C(g(a,b,d),c)B(b,h(a,c,d))A(a,k(c,d,b)). 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)(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)(n,m)-variable adjunction. Of course, a (1,1)(1,1)-variable adjunction is an ordinary adjunction, and a (2,1)(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)(C,D)(f,g,h,k) : (A,B) \to (C,D) as above, we have a two-variable adjunction (,m,n):(D,E)Z(\ell,m,n) : (D,E)\to Z with Z((d,e),z)D(d,m(e,z))E(e,n(d,z))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)(C,Z)(A,B,E) \to (C,Z) defined by C(g(a,b,m(e,z)),c)Z((f(c,a,b),e),z)A(a,k(c,m(e,z),b)) 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)(0,2)-variable adjunction ()(A,B)() \to (A,B) consists of functors f:A opBf:A^{op}\to B and g:B opAg:B^{op}\to A and a natural isomorphism B(b,f(a))A(a,g(b))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)(2,0)-variable adjunction (A,B)()(A,B) \to () is a mutual left adjunction B(f(a),b)A(g(b),a)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 opA^{op} and BB, or between AA and B opB^{op}, but the choice of which category to oppositize is arbitrary; the polycategory MVarMVar respects mutual right and left adjunctions as independent objects rather than forcing them into the mold of ordinary adjunctions.

More generally, a (0,n)(0,n)-variable adjunction ()(A 1,,A n)() \to (A_1,\dots,A_n) is a “mutual right multivariable adjunction” between nn contravariant functors f i:A i+1××A n×A 1××A i1A i op.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)(0,2)-variable adjunction can be forced into the mold of a (1,1)(1,1)-variable adjunction by oppositizing one category, an (n,1)(n,1)-variable adjunction can be forced into the mold of a (0,n)(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 MVarMVar again treats them as independent objects.

What role, then, do opposite categories play in the polycategory MVarMVar? 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)(A,B) in a monoidal category consists of a unit and counit η:IAB\eta : I \to A\otimes B and ε:BAI\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 η:()(A,B)\eta : () \to (A, B) and ε:(B,A)()\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: ε Aη=1 B\varepsilon \circ_A \eta = 1_{B} and ε Bη=1 A\varepsilon \circ_{B} \eta = 1_A.

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

Let me say that again: in the polycategory MVarMVar, 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 CatCat; but in MVarMVar, 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 MVarMVar 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)(A,A^{op}) allows us to implement the “cyclic action” on multivariable adjunctions by simple composition. Given a (2,1)(2,1)-variable adjunction (A,B)C(A,B) \to C, we can compose it polycategorically with η:()(A,A op)\eta : () \to (A,A^{op}) to obtain a (1,2)(1,2)-variable adjunction B(A op,C)B \to (A^{op},C). Then we can compose that with ε:(C op,C)()\varepsilon : (C^{op},C)\to () to obtain another (2,1)(2,1)-variable adjunction (B,C op)A op(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(AB,C)Hom(B,A *C)Hom(BC *,A *).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 *)(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 MVarMVar. For now, let me leave you with some negative thinking puzzles:

  • What is a (0,1)(0,1)-variable adjunction?
  • How about a (1,0)(1,0)-variable adjunction?
  • How about a (0,0)(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

31 Comments & 0 Trackbacks

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)C(A, B) \to C is to make it into a biadjunction (A J op,B J)C(A^{J^{\mathrm{op}}}, B^J) \to C by the usual (co)end formulas over some small category JJ (provided AA, BB and CC 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)(n,m)-variable adjunctions for n+m>3n+m\gt 3 that are “basic”, i.e. not obtained as composites of several (n,m)(n,m)-variable adjunctions with n+m3n+m\le 3. I don’t find this surprising, since it’s already rare to find nn-ary morphisms in a multicategory for n>2n\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)A(A,A,A) \to A:

A(xyz,w)A(x,(wz)y)A(y,xwz)A(z,y(xw)) 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)(A,A op)(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)C(A, B) \to C is to make it into a biadjunction (A J op,B J)C(A^{J^{\mathrm{op}}}, B^J) \to C by the usual (co)end formulas over some small category JJ (provided AA, BB and CC 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 op,B J)C(A^{J^{\mathrm{op}}}, B^J) \to C we can get (A,B J)C J(A, B^J) \to C^J and (A J,B)C J(A^J, B) \to C^J. I expect that the same is true in the (n,m)(n,m)-variable case: we can choose any two of the categories to exponentiate by JJ, and if they are both in the codomain or both in the domain then one of the exponents has to be opop‘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 op,B J)C(A^{J^{\mathrm{op}}}, B^J) \to C we can get (A,B J)C J(A, B^J) \to C^J and (A J,B)C J(A^J, B) \to C^J. I expect that the same is true in the (n,m)(n,m)-variable case: we can choose any two of the categories to exponentiate by JJ, 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)C J(A, B^J) \to C^J and (A J,B)C J(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)C(A, B) \to C and any functor I×JKI \times J \to K there is a Day convolution adjunction (A I,B J)C K(A^I, B^J) \to C^K. Maybe this also has an interesting generalization to the (m,n)(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)C J(A, B^J) \to C^J and (A J,B)C J(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,,A n)×M(B 1,,B m)M(A 1,,A n1,B 2,,B m)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 B_1 = A_n^\bullet (or equivalently A n=B 1 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,,A n)M(A_1,\dots,A_n) to be the arrows (A 1,,A n)()(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,,A n)(B 1,,B m)(A_1,\dots,A_n) \to (B_1,\dots,B_m) to be a morphism in M(A 1,,A n,B 1 ,,B m )M(A_1,\dots,A_n,B_1^\bullet,\dots,B_m^\bullet). In the case of MVarMVar, 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,,A n)M(A 1,,A i J,,A j J op,,A n)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)C J(A, B^J) \to C^J and (A J,B J op)C(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)C(A, B) \to C and any functor I×JKI \times J \to K there is a Day convolution adjunction (A I,B J)C K(A^I, B^J) \to C^K. Maybe this also has an interesting generalization to the (m,n)(m,n) case.

Yes, I think it does. (Of course, you still need A,B,CA,B,C to be complete and cocomplete.) In fact, I think your functor I×JKI \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)C J(A, B^J) \to C^J use the functor 1×JJ1\times J \to J, while to get (A J,B J op)C(A^J, B^{J^{op}})\to C use the profunctor J×J op1J\times J^{op} \to 1.

I wonder whether this can be regarded as some kind of “action” of ProfProf on MVarMVar.

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 ProfProf on MVarMVar.

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)(m,n)-variable adjunction presented as a profunctor P:A 1××A mB 1××B nP \colon A_1 \times \ldots \times A_m \nrightarrow B_1 \times \ldots \times B_n and a profunctor U:J 1××J mK 1××K nU \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 PP by UU” is a profunctor A 1 J 1××A m J mB 1 K 1××B n K nA_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

j 1,,j m,k 1,,k nP(a 1(j 1),,a m(j m),b 1(k 1),,b n(k n)) U(j 1,,j m,k 1,,k n).\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)(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 MVarMVar of some kind of action of ProfProf on itself.

I don’t think iTeX has a better command for profunctors, but I sometimes write the HTML entity ⇸ giving ABA ⇸ 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 1\mathbf{1} to AA or A opA^{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)(A) and (A,1)(A, \mathbf{1}) and (A,1,1)(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.

Your first answer is correct, but your second answer is wrong!

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

Is it that there aren’t any (0, 0)-adjunctions?

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

Re: The polycategory of multivariable adjunctions

Nope, that’s wrong too! (-:

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

Re: The polycategory of multivariable adjunctions

Is MVar\mathrm{MVar} representable?

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

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

Posted by: Amar Hadzihasanovic on November 9, 2017 8:54 AM | Permalink | Reply to this

Re: The polycategory of multivariable adjunctions

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

Posted by: Amar Hadzihasanovic on November 9, 2017 11:10 AM | Permalink | Reply to this

Re: The polycategory of multivariable adjunctions

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

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

It feels like I should speak about Hom A(p,q)Hom_A(p, q). Could a (0,0)(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 opSet^{op}. (If our multivariable adjunctions pointed in the direction of the right adjoints instead of the left adjoints, it would be SetSet.)

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,,A n)(B 1,,B m)(A_1,\dots,A_n) \to (B_1,\dots,B_m) can equivalently be defined as a profunctor A 1××A nB 1××B mA_1\times\cdots\times A_n \to B_1 \times\cdots \times B_m that is “representable in each variable”, and a profunctor 111\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 MVarMVar. 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 UU has both a left adjoint LL and a right adjoint RR, and the adjunctions are almost equivalences: the unit 1UL1 \to U L and counit UR1U R \to 1 are isomorphisms, so that LL and RR are fully faithful, and the counit LU1L U \to 1 and unit 1RU1 \to R U are bijective on objects and act fully-faithfully on all kinds of morphisms except the (0,0)-ary ones. The composite RUR U redefines there to be exactly one (0,0)-ary morphism as above, while LUL 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 1\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(1,1 )\hom(\mathbf{1},\mathbf{1}^\bullet). And Amar is exactly right that while MVarMVar itself doesn’t have a unit, its full sub-polycategory on the complete and cocomplete categories does have SetSet 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, MVarMVar 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 opSet^{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 MVarMVar 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 Cat\mathbf{Cat} with K=SetK=\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 II I\to I^{\bot} usually correspond to elements of KK.

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

Re: The polycategory of multivariable adjunctions

Yep!

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, Set\mathbf{Set} is a tensor unit in this sense, in the (strict) regular polycategory of complete and cocomplete categories and (n,m)(n,m)-adjunctions, with n,m1n,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 Prof\mathrm{Prof}

Looking forward to the next post!

Posted by: Amar Hadzihasanovic on November 9, 2017 12:51 PM | Permalink | Reply to this

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.

Posted by: Amar Hadzihasanovic on November 9, 2017 4:37 PM | 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?

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)(A,B) in MVar\mathrm{MVar}.
Posted by: Amar Hadzihasanovic on November 8, 2017 12:09 PM | Permalink | Reply to this

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 AA and BB are “player” and “opponent” views, which are a priori uncorrelated, and the equivalence (A,B)(C,C op)(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 MVar\mathrm{MVar}” sounds better, though?

Posted by: Amar Hadzihasanovic on November 9, 2017 10:37 AM | Permalink | Reply to this

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, MVarMVar, and the Chu construction.)

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

Post a New Comment