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 9, 2017

The 2-Chu Construction

Posted by Mike Shulman

Last time I told you that multivariable adjunctions (“polyvariable adjunctions”?) form a polycategory MVarMVar, a structure like a multicategory but in which codomains as well as domains can involve multiple objects. This time I want to convince you that MVarMVar is actually (a subcategory of) an instance of an exceedingly general notion, called the Chu construction.

As I remarked last time, in defining multivariable adjunctions we used opposite categories. However, we didn’t need to know very much about the opposite of a category AA; essentially all we needed is the existence of a hom-functor hom A:A op×ASethom_A : A^{op}\times A \to Set. This enabled us to define the representable functors corresponding to multivariable morphisms, so that we could then ask them to be isomorphic to obtain a multivariable adjunction. We didn’t need any special properties of the category SetSet or the hom-functor hom Ahom_A, only that each AA comes equipped with a map hom A:A op×ASethom_A : A^{op}\times A \to Set. (Note that this is sort of “half” of a counit for the hoped-for dual pair (A,A op)(A,A^{op}), or it would be if SetSet were the unit object; the other half doesn’t exist in CatCat, but it does once we pass to MVarMVar.)

Furthermore, we didn’t need any cartesian properties of the product ×\times; it could just as well have been any monoidal structure, or even any multicategory structure! Finally, if we’re willing to end up with a somewhat larger category, we can give up the idea that each AA should be equipped with A opA^{op} and hom Ahom_A, and instead allow each objects of our “generalized MVarMVar” to make a free choice of its “opposite” and “hom-functor”.

This leads to the following construction. Let MM be a 2-multicategory, equipped with a chosen object called \bot. (We don’t need to assume anything about \bot.) We define a 2-polycategory Chu(M,)Chu(M,\bot) as follows. Its objects are pairs (A +,A )(A^+,A^-) of objects of MM equipped with a map hom A:(A +,A )\hom_A : (A^+,A^-) \to \bot. I won’t write out the general form of a poly-arrow, but here are a couple special cases to get the idea:

  • A (1,1)-ary morphism ABA\to B consists of morphisms f:A +B +f:A^+ \to B^+ and g:B A g:B^-\to A^- in MM, together with an isomorphism hom B B +fhom A A g\hom_B \circ_{B^+} f \cong \hom_A\circ_{A^-} g of morphisms (A +,B )(A^+,B^-) \to \bot.
  • A (2,1)-ary morphism (A,B)C(A,B) \to C consists of morphisms f:(A +,B +)C +f:(A^+,B^+)\to C^+, g:(A +,C )B g:(A^+,C^-) \to B^-, and h:(C ,B +)A h:(C^-,B^+) \to A^- along with isomorphisms hom C C +fhom B B ghom A A h\hom_C \circ_{C^+} f \cong \hom_B \circ_{B^-} g \cong \hom_A \circ_{A^-} h of morphisms (A +,B +,C )(A^+,B^+,C^-)\to \bot.

In other words, we take the notion of (n,m)(n,m)-variable adjunction, apply () op(-)^{op} to all the left adjoints, then replace each occurrence of an opposite category A opA^{op} with A +A^+ and each occurrence of a non-opposite category AA with A A^-; then write out the representable functors like B(f(a),b)B(f(a),b) and A(a,g(b))A(a,g(b)) as composites of multi-arrows in CatCat with target SetSet and finally interpret them in MM but with SetSet replaced by \bot. Composition is defined just like in MVarMVar. This is the Chu construction Chu(M,)Chu(M,\bot) (or perhaps the “2-Chu construction”, since we’re doing it 2-categorically with isomorphisms instead of equalities).

It should now be clear, by construction, that MVarMVar embeds into Chu(Cat,Set)Chu(Cat,Set) by sending each category AA to its pair (A op,A)(A^{op},A) with its “actual” opposite and its “actual” hom-functor hom A:A op×ASet\hom_A : A^{op}\times A \to Set. (Actually, we have to be a little careful with the directions of the 2-cells; the naive definition with this approach would lead to them pointing in the opposite direction from the usual. One option is to just redefine them by hand; another is to use Chu(Cat,Set op)Chu(Cat,Set^{op}) instead; a third is to define multivariable adjunctions to point in the direction of their right adjoints rather than their left ones.) This embedding is 2-polycategorically fully-faithful, i.e. induces an equivalence on categories of (n,m)(n,m)-ary morphisms for all n,mn,m.

Why is this interesting? Lots of reasons.

Firstly, it means that the notion of multivariable adjunction is not something we just wrote down because we saw it arising in examples. Not that there’s anything wrong with writing down a definition because we have examples of it, but it’s always reassuring if the definition also has a universal property. The Chu construction may seem ad hoc at first, but actually it is the “cofree” way to make a pointed symmetric multicategory into a polycategory with duals and counit (in the representable case, this is due to Dusko Pavlovic). And MVarMVar is (part of) what we get by applying this to CatCat pointed with SetSet; one might say that Chu(Cat,Set)Chu(Cat,Set) is what’s left of the construction of MVarMVar when we take away the mysterious fact that every category has an assigned opposite.

Secondly, if, like me, you never really understood the Chu construction (or maybe never even heard of it), but you are familiar with multivariable adjunctions, then now you have a new way to understand the Chu construction: it’s just an abstract generalization of MVarMVar.

Thirdly, the objects of Chu(Cat,Set)Chu(Cat,Set) that aren’t in MVarMVar are not uninteresting: they are a kind of “polarized category”, with a “specified opposite” that may differ from their honest opposite. Related structures have been studied by Cockett-Seely and Mellies, among others, with semantics of “polarized linear logic” in mind. I haven’t seen anyone define before the exact sort of “polarized adjunction” that arise as the morphisms in Chu(Cat,Set)Chu(Cat,Set); and not really understanding polarized logic myself, I don’t know whether they are directly relevant to it. But they do seem quite suggestive to me. (This connection also explains my perhaps-odd-looking choice of notation A +=A opA^+ = A^{op} and A =AA^- = A rather than the other way around; the objects in A +A^+ are the “positive types” and those in A A^- are the “negative types”.)

Fourthly, Chu constructions are often more than just polycategories. If MM is not just a multicategory but a closed monoidal category, which moreover has pullbacks, then Chu(M,)Chu(M,\bot) is a representable polycategory — the analogue for polycategories of a multicategory that is representable by a tensor product (hence is a monoidal category). Surprisingly (at least, surprisingly if you’re used to thinking about PROPs instead of polycategories), a “representable polycategory” has two tensor products: poly-arrows (A 1,,A n)(B 1,,B m)(A_1,\dots,A_n) \to (B_1,\dots,B_m) correspond to ordinary arrows A 1A nB 1B mA_1\otimes \cdots\otimes A_n \to B_1 \parr \cdots \parr B_m, where \otimes and \parr are two different monoidal structures. The two monoidal structures do have to be related, but the relationship takes the form of some somewhat odd-looking transformations A(BC)(AB)CA\otimes (B\parr C) \to (A\otimes B)\parr C and (AB)CA(BC)(A\parr B) \otimes C \to A \parr (B\otimes C); this is called a linearly distributive category.

A linearly distributive category that also has a dual for every object, in the polycategorical sense I mentioned last time, is called a star-autonomous category. Since Chu(M,)Chu(M,\bot) always has duals (the dual of (A +,A )(A^+,A^-) is (A ,A +)(A^-,A^+)), if it is linearly distributive then it is star-autonomous. In particular, this applies to Chu(Cat,Set)Chu(Cat,Set).

We can figure out what the tensor products in Chu(M,)Chu(M,\bot) look like by inspecting the universal property they would have to have. Recall that a (2,1)-ary morphism (A,B)C(A,B) \to C in Chu(M,)Chu(M,\bot) consists of morphisms f:(A +,B +)C +f:(A^+,B^+)\to C^+, g:(A +,C )B g:(A^+,C^-) \to B^-, and h:(C ,B +)A h:(C^-,B^+) \to A^- in MM along with isomorphisms between the three induced morphisms (A +,B +,C )(A^+,B^+,C^-)\to \bot. A putative factorization ABCA\otimes B \to C, on the other hand, would consist of morphisms k:(AB) +C +k:(A\otimes B)^+ \to C^+ and :C (AB) \ell : C^-\to (A\otimes B)^- and isomorphisms between two induced morphisms ((AB) +,C )((A\otimes B)^+,C^-) \to \bot. It is easy to guess we should take (AB) +=A +B +(A\otimes B)^+ = A^+ \otimes B^+, so that kk is uniquely determined by ff. For the others, note that when MM is closed, gg and hh correspond to maps C [A +,B ]C^- \to [A^+,B^-] and C [B +,A ]C^- \to [B^+,A^-], so (AB) (A\otimes B)^- should involve [A +,B ][A^+,B^-] and [B +,A ][B^+,A^-] somehow. In fact it should be their pseudopullback over [A +B +,][A^+\otimes B^+,\bot]; the isomorphism involved in this pseudopullback encodes one of the two-variable adjunction isomorphisms, with what’s left being the induced ordinary adjunction isomorphism.

A similar, but simpler, argument shows that the unit object of Chu(M,)Chu(M,\bot) is 1 =(1,,id )\mathbf{1}_\bot = (\mathbf{1},\bot,id_\bot), where 1\mathbf{1} is the unit object of MM (if it exists). This has the universal property that it can be inserted anywhere in the domain list without changing the available morphisms, and in particular (0,m)(0,m)-ary morphisms ()Δ() \to \Delta correspond to (1,m)(1,m)-ary morphisms 1 Δ\mathbf{1}_\bot \to \Delta. Its dual 1 =(,1,id )\mathbf{1}_\bot^\bullet = (\bot,\mathbf{1},id_\bot) has the dual property, and so in particular (0,0)-ary morphisms ()()()\to () correspond to morphisms 1 1 \mathbf{1}_\bot \to \mathbf{1}_\bot^\bullet in Chu(M,)Chu(M,\bot), which simplify to just morphisms 1\mathbf{1}\to \bot in MM. This gives another solution to the puzzle at the end of my last post: since the embedding MVarChu(Cat,Set)MVar \to Chu(Cat,Set) is fully faithful on (n,m)(n,m)-ary morphisms for n+m>0n+m\gt 0, we should expect it to be fully faithful on (0,0)(0,0)-ary morphisms too; but the (0,0)(0,0)-ary morphisms in Chu(Cat,Set)Chu(Cat,Set) are morphisms 1Set1\to Set in CatCat.

Personally, I find this explanation of the tensor products in the Chu construction more transparent than any other I’ve heard, since it determines them by a universal property, rather than forcing us to guess what they should be. And it explains the odd condition in the definition of the star-autonomous Chu(M,)Chu(M,\bot) that MM should have pullbacks as well as being closed monoidal; it’s just to ensure that the polycategorical structure is representable. And it makes it much easier to construct the 2-categorical version of the Chu construction: the pseudopullback means that the tensor product in general will be only bicategorical, but by characterizing it by a polycategorical universal property (up to equivalence, rather than isomorphism) we can be guaranteed that it will be sufficiently coherent without having to delve into the definition of monoidal bicategory.

Finally, Chu constructions are interesting for other purposes. In particular, they often provide a “unified home for concrete dualities”. There is a nice explanation of this here for the case of Chu(Set,2)Chu(Set,2). You should read the whole thing, but the short version is that an “ambimorphic set” like 22, which admits the structure of two different concrete categories CC and DD, induces embeddings of CC and DD into Chu(Set,2)Chu(Set,2), and often the self-duality of Chu(Set,2)Chu(Set,2) restricts to a contravariant equivalence between CC and DD. For instance, Stone duality can be represented in this way, while Pontryagin duality similarly arises from Chu(Top,S 1)Chu(Top,S^1).

The 2-Chu construction Chu(Cat,Set)Chu(Cat,Set) exhibits similar behavior, for instance involving Gabriel-Ulmer duality. Now the category SetSet is an ambimorphic object of CatCat: for instance, it carries the structure of both a category with finite limits and a locally finitely presentable category. This induces two embeddings of the 2-categories LexLex of finitely complete categories and LFPLFP of locally finitely presentable categories into Chu(Cat,Set)Chu(Cat,Set), and the self-duality of Chu(Cat,Set)Chu(Cat,Set) restricts to a contravariant equivalence Lex opLFPLex^{op}\simeq LFP.

I’m surprised that I’ve never seen the 2-Chu construction Chu(Cat,Set)Chu(Cat,Set) written down anywhere; it seems like a very natural categorification of Chu(Set,2)Chu(Set,2), and the latter has been studied a lot by many people. The only reference I’ve been able to find is a discussion on the categories mailing list from 2006 involving Vaughan Pratt, Michael Barr, and our own John Baez; you can comb through the archives to follow the thread here and here. Was this ever pursued further by anyone?

Posted at November 9, 2017 12:09 PM UTC

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

4 Comments & 0 Trackbacks

Re: The 2-Chu Construction

Anything to be learned from the homotopification: Chu((,1)Cat,Grpd)Chu((\infty,1)Cat, \infty Grpd)?

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

Re: The 2-Chu Construction

Presumably it will be a home for \infty-Gabriel-Ulmer duality. I don’t know whether there are other new kinds of duality that it might also incorporate.

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

Re: The 2-Chu Construction

Very nice. Especially, I think, the observation about Gabriel-Ulmer duality.

A couple of things. First aren’t relative adjunctions examples of morphisms in Chu(Cat,Set)? I think Paul Levy may have told me this at some point but I am hazy.

Second, in a comment on your last post you talked about “entries-only” polycategories, where there is a (strict) involution on objects and so you need only talk about hom-sets M(A 1,,A n)M(A_1,\dots, A_n) for a list of objects A 1A nA_1\dots A_n. My impression when I thought about Chu a while ago was that these entries-only polycategories were a natural place for it, because the involution in Chu is strict, and because it is quite nice and simple to say that the morphisms in Chu(C,K)((A 1,r 1,X 1),,(A n,r n,X n))Chu(C,K)((A_1,r_1,X_1),\dots ,(A_n,r_n,X_n)) are given by

  • a multimorphism k:(X 1X n)Kk:(X_1\dots X_n)\to K, together with

  • a list of multimorphisms f 1:(X 2,,X n)A 1f n:(X 1,,X n1)A nf_1:(X_2,\dots,X_n)\to A_1\ \dots f_n:(X_1,\dots,X_{n-1})\to A_n such that k(x 1,,x n)=r 1(f 1(x 2,,x n),x 1)==r n(f n(x 1,,x n1),x n)k(x_1,\dots,x_n)=r_1(f_1(x_2,\dots,x_n),x_1)=\dots=r_n(f_n(x_1,\dots,x_{n-1}),x_n).

Since there is some trouble with units in linear logic (here, for example ) the polycategory version of Chu does seem to be potentially relevant in proof theory.

Posted by: Sam S on November 16, 2017 3:56 PM | Permalink | Reply to this

Re: The 2-Chu Construction

aren’t relative adjunctions examples of morphisms in Chu(Cat,Set)Chu(Cat,Set)?

I didn’t think of that, but yes, they are! In the nLab notation, the functor J:BDJ:B\to D induces an object (B op,D,hom D(B,))(B^{op},D, \hom_D(B-,-)) of Chu(Cat,Set)Chu(Cat,Set), and a JJ-relative adjunction is a morphism in Chu(Cat,Set)Chu(Cat,Set) between this and one of the “standardly embedded” objects (C op,C,hom C)(C^{op},C,\hom_C). Very nice.

I think Paul Levy may have told me this at some point but I am hazy.

I would love to find out if this were true. If so, it would at least mean that someone else had thought about Chu(Cat,Set)Chu(Cat,Set) in the past 10 years.

My impression when I thought about Chu a while ago was that these entries-only polycategories were a natural place for it

Yes, I agree. I believe they’re also very similar to Hyland’s *\ast-polycategories; the latter retain a formal division into “domain” and “codomain” but have a permutation action that interchanges the two.

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

Post a New Comment