nLab
Chu construction

The Chu construction

Context

Monoidal categories

monoidal categories

With symmetry

With duals for objects

With duals for morphisms

With traces

Closed structure

Special sorts of products

Semisimplicity

Morphisms

Internal monoids

Examples

Theorems

In higher category theory

The Chu construction

Idea

In category theory, the Chu construction is a general method for constructing a star-autonomous category from a closed symmetric monoidal category. It is named after Po-Hsiang Chu, a student of Michael Barr, who gave the construction in his master’s thesis at McGill University. It has been extensively developed by Vaughan Pratt for its potential applications in Theoretical Computer Science.

In outline, given a closed symmetric monoidal category CC with pullbacks and an object dd of CC, there is a star-autonomous category Chu(C,d)Chu(C, d) and a strong symmetric monoidal functor

i:CChu(C,d)i: C \to Chu(C, d)

which realizes CC as a coreflective subcategory of Chu(C,d)Chu(C, d). Being star-autonomous, Chu(C,d)Chu(C, d) is self-dual, hence C opC^{op} also embeds as a full subcategory of Chu(C,d)Chu(C, d), this time reflectively.

Many concrete dualities in mathematics can be seen as embedded in a larger ambient self-duality on a Chu construction. This applies in particular to the category of Chu spaces, Chu(Set,2)Chu(Set, 2) (see below).

This construction may be categorified to what might be called a 2-Chu construction, producing for example Chu(Cat,Set)Chu(Cat, Set) (see Shulman17). It also generalizes to a double Chu construction and to operations on multicategories and polycategories.

Definition

As a category with self-duality

Let CC be a closed symmetric monoidal category and dCd\in C an object. The objects of Chu(C,d)Chu(C, d) are triples (a,b;r:abd)(a, b; r: a \otimes b \to d) (called dd-valued pairings between aa and bb), where aa and bb are objects of CC and rr is a morphism of CC. The special triple (d,I;ρ:dId)(d, I; \rho: d \otimes I \cong d), where ρ\rho is an instance of the canonical isomorphism (the right unitor) for the monoidal unit II, will play the role of dualizing object in Chu(C,d)Chu(C, d).

The morphisms of Chu(C,d)Chu(C, d),

(a,b;r:abd)(x,y;s:xyd),(a, b; r: a \otimes b \to d) \to (x, y; s: x \otimes y \to d),

are pairs of morphisms f:axf: a \to x, g:ybg: y \to b which are adjoint with respect to the pairings, that is, making the diagram

ay 1 ag ab f1 x r xy s d\array{ & a \otimes y & \overset{1_a \otimes g}{\to} & a \otimes b\\ f \otimes 1_x & \downarrow & & \downarrow r\\ & x \otimes y & \overset{s}{\to} & d }

commute. There is an evident self-duality

Chu(C,d) opChu(C,d)Chu(C, d)^{op} \to Chu(C, d)

which takes an object (a,b;r:abd)(a, b; r: a \otimes b \to d) to

(b,a;r =[baσabrd])(b, a; r^\dagger = [b \otimes a \overset{\sigma}{\cong} a \otimes b \overset{r}{\to} d])

where σ\sigma is an instance of the symmetry isomorphism, so that r r^\dagger is the evident transpose. On morphisms, it takes a pair (f,g)(f, g) to (g,f)(g, f); note well that the directions of the arrows make the functor contravariant on Chu(C,d)Chu(C, d).

As a *\ast-autonomous category

Armed with just this much knowledge, and knowledge of how star-autonomous categories behave (as categorified versions of Boolean algebras, or perhaps better Boolean rigs), the star-autonomous structure on Chu(C,d)Chu(C, d) can pretty much be deduced (or strongly guessed) by the diligent reader, and this is actually a very good exercise. One could sketch this as follows:

  • The monoidal unit of Chu(C,d)Chu(C, d) should be the dual of the dualizer, and so is (I,d;λ:Idd)(I, d; \lambda: I \otimes d \cong d) where λ\lambda, the transpose of ρ\rho, is a canonical isomorphism for the unit II.

  • The internal hom AXA \multimap X in Chu(C,d)Chu(C, d) should internalize the external hom, i.e., the set of maps from the monoidal unit to AXA \multimap X should be in natural bijection with the set of maps AXA \to X in Chu(C,d)Chu(C, d).

This suggests the first component (AX) 0(A \multimap X)_0 of the triple

AX=((AX) 0,(AX) 1;pairing)A \multimap X = ((A \multimap X)_0, (A \multimap X)_1; pairing)

should be the object of adjoint pairs of maps: given

A=(a,b;r:abd),X=(x,y;s:xyd)A = (a, b; r: a \otimes b \to d), \qquad X = (x, y; s: x \otimes y \to d)

define the first component as pullback:

(AX) 0 x a s˜ b y r˜ d ay\array{ (A \multimap X)_0 & \to & x^a \\ \downarrow & & \downarrow \tilde{s} \\ b^y & \overset{\tilde{r}}{\to} & d^{a \otimes y} }

where exponentials are used to denote internal homs in CC, r˜\tilde{r} is the result of currying rr to bd ab \to d^a and exponentiating, and similarly for s˜\tilde{s}.

The pullback is paired with aya \otimes y, i.e., there is a map

(AX) 0(ay)d(A \multimap X)_0 \otimes (a \otimes y) \to d

obtained by decurrying either leg of the pullback, so one defines (with fingers crossed) (AX) 1(A \multimap X)_1 to be aya \otimes y, and the pairing to be this map into dd.

  • To form the tensor product AXA \otimes X, use the formula AX(AX *) * A \otimes X \cong (A \multimap X^*)^* which holds true in any star-autonomous category (as a categorified analogue of the Boolean algebra equation ax=¬(a¬x)a \wedge x = \neg (a \Rightarrow \neg x)).

With notation as above, this works out to

(ax,y a× d axb x)(a \otimes x, y^a \times_{d^{a \otimes x}} b^x)

where the second component is a pullback, and the pairing omitted but obvious. The main thing to check is the presence of a canonical isomorphism

Chu(C,d)(AX,Y)Chu(C,d)(X,AY)Chu(C, d)(A \otimes X, Y) \cong Chu(C, d)(X, A \multimap Y)

but this is left as an exercise.

Also one should check that if DD is the dualizing object, that A *AD A^* \cong A \multimap D , but this is straightforward.

  • There is a strong symmetric monoidal functor

    i:CChu(C,d)i: C \to Chu(C, d)

    taking cc to (c,d c;eval:cd cd)(c, d^c; eval: c \otimes d^c \to d). (This does not take dd to the dualizing object in Chu(C,d)Chu(C, d), unless of course the canonical map Id dI \to d^d is an isomorphism.) This embedding admits a right adjoint

    p:Chu(C,d)Cp: Chu(C, d) \to C

    given by the obvious projection, that is also strong symmetric monoidal. The unit of the adjunction is an isomorphism, hence CC is a coreflective (full) subcategory of Chu(C,d)Chu(C, d).

  • If CC is complete and cocomplete, then so is Chu(C,d)Chu(C, d). The formula for colimits is the obvious expected one:

    colim i(a i,b i;r i:a ib id)=(colim ia i,lim ib i;r)colim_i (a_i, b_i; r_i: a_i \otimes b_i \to d) = (colim_i a_i, lim_i b_i; r)

    where rr is the decurrying of

    lim i(b id a i)lim ib id colim ia ilim_i (b_i \to d^{a_i}) \cong lim_i b_i \to d^{colim_i a_i}

    and the formula for limits is obtained by dualizing the formula for colimits in Chu(C,d)Chu(C, d).

As a polycategory

We can also deduce the *\ast-autonomous structure of Chu(C,d)Chu(C,d) by constructing it directly as a star-polycategory and then observing that it is representable. This has the additional benefit of giving a universal property to the tensor product, as well as applying to more general inputs CC (and giving a result that may not be representable), and giving a convenient way to phrase the universal property of Chu(C,d)Chu(C,d) itself (see below).

Let CC be a (symmetric) polycategory in which every morphism has codomain arity 0 or 1 (a co-subunary polycategory). For instance, if CC is any symmetric multicategory and dCd\in C an object, we can obtain a co-subunary polycategory by defining C(x 1,,x n;)=C(x 1,,x n;d)C(x_1,\dots,x_n; ) = C(x_1,\dots,x_n; d). (In fact the construction can be generalized even further; see Shulman 18.)

The objects of Chu(C)Chu(C) are now pairings (a,b;r:(a,b)())(a, b; r : (a,b) \to ()) in the appropriate polycategorical sense. A morphism (a,b,r)(x,y,s)(a,b,r) \to (x,y,s) is a pair of morphisms f:axf:a\to x and g:ybg:y\to b that are “adjoint” with respect to the pairings, in the sense that the following square commutes:

More generally, we can directly make Chu(C)Chu(C) into a polycategory by taking the morphisms to be a suitable kind of multivariable adjunctions. For instance, a morphism ((a,b,r),(x,y,s))(u,v,t)((a,b,r),(x,y,s)) \to (u,v,t) consists of three morphisms

f:(a,x)ug:(a,v)yh:(x,v)b f : (a,x) \to u \qquad g : (a,v) \to y \qquad h : (x,v) \to b

such that the following three composites are equal modulo symmetries:

(a,x,v)(f,1)(u,v)t() (a,x,v) \xrightarrow{(f,1)} (u,v) \xrightarrow{t} ()
(x,a,v)(1,g)(x,y)s() (x,a,v) \xrightarrow{(1,g)} (x,y) \xrightarrow{s} ()
(a,x,v)(1,h)(a,b)r(). (a,x,v) \xrightarrow{(1,h)} (a,b) \xrightarrow{r} ().

Similarly, a morphism (a,b,r)((x,y,s),(u,v,t))(a,b,r) \to ((x,y,s),(u,v,t)) consists of three morphisms

f:(a,y)ug:(x,b)uh:(y,v)b f : (a,y) \to u \qquad g : (x,b) \to u \qquad h : (y,v) \to b

such that three composite morphisms (a,y,v)()(a,y,v) \to () are equal. With a suitable extension to mm-nn-ary morphisms we obtain a polycategory, and indeed a *\ast-polycategory: the dual of (a,b,r)(a,b,r) is (b,a,r )(b,a,r^\dagger).

It is then a straightforward exercise to check that if CC is closed, representable, has pullbacks, and a “counit” in the sense that C(Γ;)C(Γ;d)C(\Gamma;) \cong C(\Gamma;d), then Chu(C)Chu(C) is representable on both sides and hence a *\ast-autonomous category, where all the structure coincides with the previous definition.

Chu spaces (General case)

While the Chu construction is worthy of exploration for many types of symmetric monoidal categories CC, a great deal of attention has been focused just on the particular case Chu(Set,2)Chu(Set, 2) (or Chu(Set,TV)Chu(Set,TV), where TVTV is the set of truth values, to be constructive), called the category of Chu spaces, and on relatives like Chu(E,Ω)Chu(E, \Omega) where EE is a topos and Ω\Omega its subobject classifier. The reason is that a great many concrete categories of interest are fully embedded in Chu spaces. Moreover, the 2-element set TVTV carries a panoply of ambimorphic (formerly, schizophrenic) object structures which induce concrete dualities between these categories, and all of these dualities are embedded in (i.e., are restrictions of) the one overarching duality that obtains on Chu spaces.

The way this works is invariably the same: if U:CSetU: C \to Set is a concrete category and 2\mathbf{2} is an object of CC over the 2-element set TVTV, then there is a functor

i:CChu(Set,2):c(Uc,hom(c,2);Uc×hom(c,2)U2=2)i: C \to Chu(Set, 2): c \mapsto (U c, hom(c, \mathbf{2}); U c \times hom(c, \mathbf{2}) \to U\mathbf{2} = 2)

which is faithful by the notion of concrete category.

What is striking is that this functor ii is also full in many cases of interest. This is because the adjointness condition for a pair (f,g):icid(f, g): i c \to i d to be a Chu space morphism, together with faithfulness of UU, forces

g:hom(d,2)monichom(Ud,2)f *hom(Uc,2)g: hom(d, \mathbf{2}) \overset{monic}{\to} hom(U d, 2) \overset{f^*}{\to} hom(U c, 2)

to be a restriction of the preimage function f *f^* – and then the mere additional fact that f *(ϕ)=ϕfhom(c,2)f^*(\phi) = \phi \circ f \in hom(c, \mathbf{2}) whenever ϕhom(d,2)\phi \in hom(d, \mathbf{2}) is often enough to force ff to be (the underlying function of) a morphism of CC. All that is required is that there be sufficiently many morphisms d2d \to \mathbf{2} to detect CC-structure on dd. Some examples follow:

  • As explained above, SetSet fully embeds in Chu(Set,2)Chu(Set, 2) by X(X,2 X;eval:X×2 X2)X \mapsto (X, 2^X; eval: X \times 2^X \to 2).

  • For C=TopC = Top, taking 2\mathbf{2} to be Sierpinski space, we have for each topological space cc an identification Open(c)=hom(c,2)Open(c) = hom(c, \mathbf{2}). Then the adjointness condition on a morphism (f,g):icid(f, g): i c \to i d between the corresponding Chu spaces expresses precisely the continuity condition that the preimage f *f^* takes opens of dd to opens of cc. Hence the functor TopChu(Set,2)Top \to Chu(Set, 2) is full.

  • For C=PosC = Pos, the category of posets, take 2\mathbf{2} to be the partially ordered set of truth values. Here we have that for a partial order cc, hom(c,2)hom(c, \mathbf{2}) is the set of upper sets (upward-closed subsets) of cc. Given a function f:UcUdf: U c \to U d between posets, the condition that the preimage f *(v)f^*(v) of an upper set of dd is an upper set of cc is enough to force ff to be a poset map (consider v={qd:fpq}v = \{q \in d: f p \leq q\}). It follows that the functor PosChu(Set,2)Pos \to Chu(Set, 2) is full.

  • For C=SupC = Sup, the category of sup-lattices (whose morphisms are those functors between the underlying posets that are left adjoints), take 2\mathbf{2} to be the partially ordered set of truth values, but this time as the opposite of the poset TVTV. For a sup-lattice cc, hom(c,2)hom(c, \mathbf{2}) may be identified with the set of representable functors c(,x):c opTVc(-, x): c^{op} \to TV. The Chu condition then is that d(,y)f=d(f,y)d(-, y) \circ f = d(f-, y) is representable for every representable d(,y)d(-, y). But this condition is equivalent ff‘s being a left adjoint. Therefore the functor SupChu(Set,2)Sup \to Chu(Set, 2) is full.

For other examples of concrete categories, the presence of enough elements in hom C(c,2)\hom_C(c, \mathbf{2}) to detect the CC-structure of cc often requires some form of choice principle, such as the axiom of choice or ultrafilter theorem:

  • For C=Vect 𝔽 2C = Vect_{\mathbb{F}_2}, the category of vector spaces over the 2-element field, any object dd has a basis, let us say SS. For each sSs \in S, the characteristic or indicator χ s:S2\chi_{s}: S \to \mathbf{2} extends uniquely to a linear function ϕ s:d2\phi_s: d \to \mathbf{2}. If f:UcUdf: U c \to U d is a function such that ϕ sf:c2\phi_s \circ f: c \to \mathbf{2} is linear for every basis element sSs \in S, then
    f(ax+by)= sSϕ s(f(ax+by))s= s(aϕ s(f(x))+bϕ s(f(y)))s=af(x)+bf(y)f(a x + b y) = \sum_{s \in S} \phi_s(f(a x + b y))s = \sum_s (a\phi_s(f(x)) + b\phi_s(f(y)))s = a f(x) + b f(y)

    It follows that the functor Vect 𝔽 2Chu(Set,2)Vect_{\mathbb{F}_2} \to Chu(Set, 2) is full.

Similar considerations apply to Boolean algebras, Stone Boolean algebras, algebraic lattices, and so on.

In all of these cases, the fullness of these embeddings entitles one to identify a topological space, a Boolean algebra, a vector space over 𝔽 2\mathbb{F}_2, etc. with its corresponding Chu space, and the same consideration applies to the duals (opposites) of these categories.

Now many of these formal categorical duals are themselves concrete categories, as in the famous example of classical Stone duality between Boolean algebras and Stone spaces, i.e., compact Hausdorff totally disconnected topological spaces. In many such Stone duality situations, and certainly wherever Stone duality applies to the categories listed above, a contravariant equivalence between a concrete category CC and an algebraic category DD (i.e., where U:DCU: D \to C is monadic),

C op D hom(,2) U Set, \array{ & C^{op} & \overset{\sim}{\to} & D & \\ hom(-, \mathbf{2}) & \searrow & & \swarrow & U\\ & & Set, & & }

is effected by lifting the object 2\mathbf{2} of CC to a DD-algebra structure in CC (making 2\mathbf{2} an ambimorphic object, carrying CC- and DD-structures compatible with one another); equivalently, seeing hom(,2):C opSethom(-, \mathbf{2}): C^{op} \to Set as an algebra over the monad UFU F for which U:DSetU: D \to Set is monadic. For example, classical Stone duality is the case where CC is the category of Stone spaces, DD is the category of Boolean algebras, and the Boolean operations on 2\mathbf{2} are continuous with respect to its Stone space structure, making 2\mathbf{2} a Boolean algebra object in the category of Stone spaces. (For much more on this, see Johnstone’s classic treatise Stone Spaces, especially the chapter on general concrete dualities.)

The point is that in each of these situations, a Stone duality is a restriction of the more global duality on Chu spaces, in that the diagram

C op hom(,2) D i op i Chu(Set,2) op () * Chu(Set,2)\array{ C^{op} & \overset{hom(-, \mathbf{2})}{\to} & D \\ i^{op} \downarrow & & \downarrow i \\ Chu(Set, 2)^{op} & \overset{(-)^*}{\to} & Chu(Set, 2) }

(where the vertical arrows are full embeddings as described above) commutes up to canonical isomorphism.

The same principle extends to other situations. For example, Pontryagin duality is fully embedded in the larger duality which obtains on Chu(Top,S 1)Chu(Top, S^1), where TopTop is a nice category of spaces.

Similarly, the 2-Chu construction, Chu(Cat,Set)Chu(Cat, Set), exhibits dualities, such as Gabriel-Ulmer duality.

Hi Toby; could I get you to explain the aside about Boolean rigs above? I’m thinking Boolean algebras is appropriate, as we have Ix *x I \to x^* \wp x , xx *D x \otimes x^* \to D [where denotes Girards par and denotes the dualizer], together with appropriate triangular equations, categorifying the inequalities 1(¬x)v1 \leq (\neg x) \vee v and x(¬x)0x \wedge (\neg x) \leq 0 in a Boolean algebra. —Todd

Now that I go to write Boolean rig, I'm not so sure. I just know that Chu(PX,)Chu(P X,\empty) at measurable space is not (even classically) a Boolean algebra. I'll get back to you in a day or less. —Toby

Right, I agree. The Chu construction applied to a complete Heyting algebra is merely a **-autonomous quantale, not a **-autonomous frame (which would be a complete Boolean algebra), as you noted at measurable space. —Todd

Chu spaces (Simple examples)

One of the simplest occurrences of Chu space constructions, and the one explored in Pratt’s notes (see below), leads to examples that although extremely simple have a well developed theory with connections to areas of logic and to formal concept analysis. This will be explored in a separate entry, Chu spaces, simple examples.

Properties

  • Chu spaces give fairly easy to construct examples of closed monoidal categories in which coproduct injections are not necessarily monic; see this MO answer.

Universal property

Recall from the above that Chu(C)Chu(C) is a *\ast-polycategory whenever CC is a co-subunary polycategory. This construction is functorial, and we claim that it defines a right adjoint to the forgetful functor UU from *\ast-polycategories to co-subunary polycategories.

To see this, consider first the *\ast-polycategory F1F 1 freely generated by one object. It has two objects xx and x *x^*, and in addition to identity morphisms it has a dual pair (x *,x)()(x^*,x)\to () and ()(x,x *)() \to (x,x^*). Of these, all but the last are co-subunary. Thus, a morphism UF1CU F 1 \to C consists of two objects aa and bb (plus their identity morphisms) and a morphism (a,b)()(a,b)\to () — in other words, an object of Chu(C)Chu(C).

Now consider the *\ast-polycategory F(1,1)F (1,1) freely generated by two objects xx and yy and a morphism f:xyf:x\to y. It contains two copies of F1F 1 generated by xx and yy, together with f:xyf:x\to y, its dual f *:y *x *f^*: y^* \to x^*, and two other copies of it f :(x,y *)()f^\dagger : (x,y^*) \to () and f:()(x *,y){}^\dagger f : () \to (x^*,y). Of these all but the last are co-subunary, so a morphism UF1CU F 1 \to C is determined by two objects of Chu(C)Chu(C) together with three more morphisms (and some composition laws relating them to the duality morphisms). This yields the two morphisms axa\to x and yby\to b of a morphism in Chu(C)Chu(C), along with their common composite (a,y)()(a,y) \to ().

Similarly, one can characterize all the morphisms in Chu(C)Chu(C) by mapping out of UF(m,n)U F (m,n), where F(m,n)F(m,n) is the *\ast-polycategory freely generated by a mm-ary co-nn-ary morphism.

As a special case of this universal property, if all the *\ast-polycategories are representable and the subunary polycategories are representable, closed, with a counit, and have pullbacks, we obtain an adjunction between a certain category of *\ast-autonomous categories and a certain category of closed symmetric monoidal categories with chosen objects. This is the way it was phrased in Pavlovic 97.

References

For categorifications and generalizations, see

  • Mike Shulman, The 2-Chu Construction, (blog post)

  • Mike Shulman, The 2-Chu-Dialectica construction and the polycategory of multivariable adjunctions, 2018 arxiv

category: category

Last revised on October 13, 2019 at 20:18:32. See the history of this page for a list of all contributions to it.