From Symmetric Monoidal Categories to Tensor Products of PROPs
Abstract. A PROP describes operations with finitely many inputs and outputs. We construct the tensor product of symmetric monoidal categories that represents bilinear functors. For PROPs, its interchange law says that applying one operation along rows and the other down columns gives the same composite in either order. The Eckmann–Hilton argument computes the tensor square of the unital magma PROP, giving the PROP for commutative monoids. Tensoring the monoid PROP with its opposite yields the PROP for bimonoids, whose models in vector spaces are bialgebras. Tensoring with the PROP for copying and discarding freely turns the given tensor into a categorical product. This cartesianization is left biadjoint to the inclusion of cartesian categories into symmetric monoidal categories. On Lawvere theories the external tensor recovers the Kronecker tensor.
How can the same compatibility law turn two multiplications into one commutative product and also allow a noncommutative bialgebra? Both calculations start with a rectangle. We apply one operation along its rows and the other down its columns. Reversing the direction of one operation changes the boundary of the rectangle and hence the equation it expresses.
Give four input wires the row order . To operate on the columns, we need the order . The symmetry in a symmetric monoidal category supplies the crossing of the middle two wires. What makes the two ways of composing operations agree? We can trace that equality back to a functor of two variables.
The four factors in a bilinear functor
Write for the tensor inside a symmetric monoidal category, for its unit, and for its symmetry. We suppress associators and unitors and keep the permutations of factors visible. We work with ordinary categories, using small categories as inputs to an external tensor product and small skeleta for categories of finite sets.
Given symmetric monoidal categories and , let be the category of strong symmetric monoidal functors and monoidal natural transformations. Such a functor comes with coherent isomorphisms and . A monoidal natural transformation respects these isomorphisms.
The functor category has a pointwise tensor, given by . To exhibit as a strong monoidal functor we have to exchange the two middle factors. Writing for , its comparison is
Now take a strong symmetric monoidal functor and set . For fixed , the functor has the structure of . For fixed , the functor is strong symmetric monoidal because evaluation at preserves the pointwise tensor and its unit.
There is one more piece of information in . Its comparison is a monoidal natural transformation. To see what that means, arrange the four values of in a square.
Start with the four factors tensored in row order. Combine each row, then combine the two results. Alternatively, exchange the middle two factors, combine each column, and then combine those results. Monoidality of the comparison says that these two maps to agree.
A bilinear functor consists of a bifunctor with these two strong symmetric monoidal structures, natural in all variables, satisfying this mixed square and its unit conditions. In particular and are identified with , compatibly with the other variable's tensor. The two identifications at agree. These conditions let us reconstruct by currying. Gurski, Johnson and Osorno, §§2–3
For a concrete instance, equip finite sets and bijections with disjoint union. The bifunctor is bilinear for this monoidal structure by distributivity in each variable. A pair in belongs to a unique block . The two expansions give precisely the same four blocks. Passing from one order to the other moves past .
The tensor product representing bilinear functors
Write for the tensor between symmetric monoidal categories. The universal bilinear functor sends to and to . Precomposition with this functor and currying give natural equivalences of categories
The arrows in the middle category are natural transformations monoidal in each variable. The right-hand side identifies the internal hom. This gives a closed symmetric monoidal structure in the bicategorical sense. One can work with permutative categories, in which associativity and the unit laws are strict. With strong symmetric monoidal functors as morphisms, their inclusion into symmetric monoidal categories is a biequivalence. Gurski, Johnson and Osorno, Theorem 1.2 and §§4–6
In permutative models we can construct by generators and relations. Every bilinear functor has an underlying bifunctor, so we begin with the free permutative category on . There is one letter for each pair of objects. Its objects are the finite ordered tensor words
Tensoring concatenates words, and the empty word is the unit . Each pair of arrows and gives a one-letter arrow . These arrows already compose as they do in , so and . We can tensor these arrows and permute letters using the symmetry.
Consider the two-letter word and the single letter . Bilinearity gives an isomorphism in the target. We need an arrow in the source that a functor can send to this isomorphism. Doing the same in both variables and for the empty word, we adjoin the following four families of arrows and their inverses. The subscript records the entry held fixed.
Which composites of generators should agree? First, require all four families to be natural in their entries. For example, if , we can apply once after combining a column, or apply it to each letter before combining. Naturality gives
At fixed , impose the associativity, unit and symmetry axioms for . Thus three letters with the same can be combined in either parenthesization to give the same arrow to . The same axioms apply to at fixed .
Now put for . From the row-ordered word we want a map to . Combining the rows first applies . To combine the columns first we must move past , using . Bilinearity imposes the relation
There are also rectangles with an empty direction. For two empty rows, inserting a unit in each row and then combining them gives . Two empty columns give . When both directions are empty, the two arrows agree, so . Two parallel expressions now represent the same arrow of precisely when we can pass from one to the other using the relations inside tensor products and composites.
Given a bilinear with permutative target , send a word to , send to , and send to the corresponding structure maps of . Every defining equation holds under this assignment by the axioms of , so it gives a strict symmetric monoidal functor . These assignments determine the extension uniquely since the generators produce every arrow. Conversely, any strict symmetric monoidal functor out of the quotient gives a bifunctor by and . The images of give its bilinear structure. These two constructions are inverse.
A transformation monoidal in each variable extends by tensoring its components on the letters. For a strong symmetric monoidal functor out of the presentation, its tensor and unit comparisons supply a monoidal isomorphism with the strict extension of its restriction. This gives the first equivalence displayed above. Gurski, Johnson and Osorno, Definition 4.4 and Propositions 5.3 and 6.8
The tensor unit is , the groupoid of finite sets and bijections under disjoint union. It is free symmetric monoidal on one object. A strong symmetric monoidal functor out of it is determined up to monoidal isomorphism by the image of a singleton. It sends an -element set to and a permutation to the corresponding symmetry. Evaluation at the singleton thus gives . Interchanging the two variables of the universal pairing gives symmetry for , and both bracketings of a threefold tensor represent trilinear functors. Gurski, Johnson and Osorno, §§8–12
Reading the universal pairing as a rectangle
For arrows and , bifunctoriality gives two factorizations of .
To read these paths as operations, fix objects and write . Bilinearity identifies with , including . Expanding the -power first gives rows of wires. Expanding the -power first gives columns of wires. Write for the symmetry that puts the row-ordered inputs into column order. For a rectangle it sends the ordered list of wire labels
Suppose and . Their induced operations on are and under the power identifications. What does do? After splitting into rows, naturality of the comparison in identifies it with parallel copies of . Splitting into columns gives the corresponding description for . Using row order to identify the source of with , its two factorizations now read
This is the interchange law. Bifunctoriality supplied the equality. Bilinearity and its mixed square supplied the row and column readings of that equality. Every input wire occurs once on each side.
For the rectangle, give the two rows the labels and . The formula becomes
The letters label the six inputs of an arrow . This use of variables makes sense in any symmetric monoidal category. Forming a tuple from six arrows with a common source would also require a map copying into six factors.
Passing to one-colour PROPs
A one-colour PROP is a strict symmetric monoidal category with objects , tensor on objects given by addition, and chosen generator . An arrow describes an operation with inputs and outputs. A PROP map preserves the generator, tensor and symmetries strictly. A model in a symmetric monoidal category is a strong symmetric monoidal functor to .
Take PROPs and . Every generating object of their external tensor is isomorphic to the tensor power , so choosing these powers again gives a one-colour PROP. For in and in , the two readings both start with an array and end with a array.
Path
First operation
Second operation
Rows first
Apply to the rows to get .
Apply to the columns to get .
Columns first
Apply to the columns to get .
Apply to the rows to get .
At each stage the symmetry puts the factors into the indicated order. For instance, on row-ordered wires the map applying down all columns and returning the output to row order is . Thus both routes give under the chosen power identifications. Juxtaposing the two operations inside one PROP, , has boundary . Multiplication of arities comes from the rectangle, and addition of arities comes from juxtaposition.
This gives a presentation of . Take the coproduct of the two PROPs on the same colour, so they already share the wires and permutations. Impose the rectangle equations for mixed pairs of operations, including empty inputs or outputs. Equivalently, a pair of PROP maps and extends uniquely to precisely when their images satisfy interchange. It suffices to check generating operations in each factor. Tensoring and composing rectangles extends the equations to all operations. Hackney and Robertson, §§3.2–3.3 and Theorem 35
where is the congruence generated by those equations under composition and tensoring.
If denotes the category of models and monoidal natural transformations, the same construction gives
The inner model category carries the pointwise tensor from . An operation of must be a map of -models from the -fold tensor of a model to its -fold tensor. Commuting with is exactly the homomorphism condition for this map. A morphism of the resulting models is a single arrow preserving both structures. We can therefore compute the tensor product by writing out the rectangles for its generators.
Two computations with the same interchange law
The Eckmann–Hilton argument computes the tensor square of the unital magma PROP
Let be the PROP of unital magmas. It is generated by a multiplication and a unit , subject only to the left and right unit laws. What does the tensor square force these generators to satisfy? On its generating wire we have two multiplications . Interchange between the two units identifies them. Write for their common value. Interchange between the two multiplications equates the following two arrows from to .
Label the four input wires in row order. The equality reads . The Eckmann–Hilton argument uses this same rectangle three times, each time inserting in different slots. For example, the first row below precomposes both sides with .
Inputs in row order
Rows first
Columns first
Consequence
A common product
Commutativity
Associativity
Write for the PROP of commutative monoids. Sending its multiplication and unit to and gives a PROP map . Conversely, interpret both copies of in using its generating multiplication and unit. Both paths around the binary rectangle multiply the same four inputs, and the remaining rectangles hold by the unit laws. This gives a map back. The two maps are inverse on generators, so the calculation identifies the PROPs themselves. In particular, it holds for unital magmas satisfying interchange in any symmetric monoidal category. Aguiar and Mahajan, Proposition 6.29 and Remark 6.30
The last description makes the wires explicit. A function between finite sets assigns each input to one output. Multiply the inputs in each fibre, taking the unit for an empty fibre. Associativity and commutativity make this independent of parentheses and fibre order. Composing functions composes these fibrewise products. Baez, Universal Algebra and Diagrammatic Reasoning, p. 42
A monoid and a comonoid give a bimonoid
Take the PROP for associative unital monoids, with and . In the reversed generators are a comultiplication and a counit . What happens to the rectangle when the second operation points outwards?
Start with two input wires. One path multiplies first and comultiplies the result. The other first comultiplies each input, making four wires in the order . To multiply corresponding outputs we need the order . The crossing in the bialgebra axiom is precisely this change of order.
There are three more pairs of generators, and each contributes a familiar axiom.
Pair
Interchange equation
Together these say that and are monoid homomorphisms, with the tensor-product monoid structure on . We have therefore computed , the PROP for bimonoids. Its models in are precisely the unital, counital -bialgebras. Baez, p. 58
For instance, on the group algebra put and on basis elements, then extend linearly. On , both paths give . This calculation allows and to differ. The additional Hopf structure comes from the inverse in , which gives . The same construction on the monoid algebra gives . An antipode would require , which has no solution in .
Free cartesianization by copying and discarding
In the group algebra example we chose a comultiplication on one object. Now suppose we want any two arrows and to be able to use the same input. Their tensor takes two copies of as input. To pair them into an arrow out of we need a way to copy . To project from onto we also need a way to discard . How can we adjoin these operations so that the given tensor becomes a categorical product?
Consider what copying, discarding and permuting wires can do. Each of outputs selects one of the inputs, so the wiring is a function , where and . For example, the constant function with value describes the wiring . Both outputs use the first input and the second input is discarded. These wirings form the PROP . It is the PROP for cocommutative comonoids, generated by a copy and a discard . Coassociativity makes repeated copying independent of parentheses, cocommutativity makes the two copies interchangeable, and the counit laws say that discarding either copy leaves the other wire unchanged.
Tensoring an operation with a wiring
Let be an operation in and a wiring in . Tensoring their sources and their targets gives an arrow in of type
In , is the disjoint union of single wires. Strong monoidality in the second variable gives the identifications
These identifications are natural in the first variable. Thus acts as , one arrow on each copy. For a binary , the arrow applies to three supplied pairs. With the wiring that triples its input, uses a single pair three times.
For the wiring that copies one input times, consider the pair in . We can apply first, passing through , or first, passing through . Since composition is computed coordinate by coordinate, we have
Now apply the functor . It sends to . Since it preserves composition, the path through is sent to . Applying the same rule to the other path gives a second factorization of the very same arrow .
The upper path applies to one bundle and copies the output. The lower path copies the input and then applies to each copy, since the monoidal comparison reads its last arrow as . In the presentation of , this equality is exactly the interchange relation imposed on the coproduct .
At , gives the copy map after identifying with . At , , so gives the discard and acts as . With the same identifications at , interchange gives
Copying a whole bundle puts its factors in the order . Copying each factor separately gives , so we exchange the middle two wires. Discarding the bundle discards both factors. Thus
The wirings themselves satisfy both equations. Copying before or after a wiring selects the same input for each output copy, and there is only one wiring to . Composition and tensoring preserve these equations, so copy and discard are natural for every arrow of .
Why the tensor is a product
Take any . Its output is the empty bundle, whose discard is . The discard equation now gives . Thus every object has exactly one arrow to , which makes terminal.
Now take and . To use the same input for both, copy it and apply one arrow to each copy. This gives the candidate pairing
To read off either component, discard the other factor. The projections are
Projecting the pairing onto discards the output of . The discard equation moves that discard back to , and the counit law cancels it against the copy. Applying this calculation to each projection gives
For uniqueness, take any . The copy equation for moves the copy from its input to its output, giving
In the last step supplies two whole copies. The projections keep from the first and from the second. Discarding one copy of each factor leaves the other unchanged by the counit laws, so . Taking components and forming the pairing are therefore inverse maps in the defining bijection for a product,
For the copy equation also gives , so this bijection is natural in .
Conversely, suppose is a product and is terminal. Take and let be the unique arrow to . For every , both and have components , and and agree by terminality. Both ways of making three copies have components , swapping two copies preserves the diagonal, and discarding one copy gives . The diagonal on a product duplicates both coordinates, giving the formula for above. Thus a symmetric monoidal category is cartesian exactly when its objects carry cocommutative comonoid structures that are natural in every arrow and compatible with the tensor and unit. Di Liberti, Loregian, Nester and Sobociński, Theorem 2.22 and Corollary 2.23
Free cartesianization as a reflection
Let be a category with finite products. Taking its binary product as tensor and its terminal object as unit makes it symmetric monoidal. This defines the inclusion below. In the other direction, we can tensor any small symmetric monoidal category with the wiring PROP .
The arrows in are finite-product-preserving functors, and its 2-cells are natural transformations. In we use strong symmetric monoidal functors and monoidal natural transformations.
Fixing the singleton in the universal pairing gives the unit of cartesianization, a strong symmetric monoidal functor
The product calculation applies to this general just as it did to a PROP. The wirings and copy and discard . Each is canonically a tensor of copies of . Interchange makes copying and discarding natural, and the bilinear comparisons extend them compatibly to tensor words. Hence the tensor in is a product and its unit is terminal. On a strong symmetric monoidal functor , cartesianization acts by .
Why is left adjoint to ? Suppose is strong symmetric monoidal. Its structure maps already identify with and with . We seek a finite-product-preserving functor such that the composite
is monoidally isomorphic to . Once that identification is fixed, must send to and to up to the product comparison. In particular, the copy must go to the diagonal . The discard must go to the unique map .
We can now construct the extension. A wiring selects one input for each of its outputs. Use those same projections to define . For , apply on each coordinate. These two prescriptions commute because at each output both composites apply to the input chosen by . With no outputs the composites agree by terminality. Concatenating the lists of factors gives the monoidal comparison in the wiring variable. The product comparisons of give the comparison in the other variable, coordinate by coordinate. Both orders of comparison have the same projections, so the assignment is bilinear. The universal property of gives , unique up to a unique isomorphism compatible with the chosen identification.
A monoidal natural transformation extends on by taking the product of copies of . Thus restriction along gives an equivalence of hom-categories,
This equivalence is natural in both variables up to coherent isomorphism. That is the meaning of the left biadjunction. Passing to isomorphism classes of functors on both sides gives the ordinary adjunction on hom-sets. Krähmer and Mahaman, Clones from comonoids, §1, on the left adjoint
Why is this a reflection? When already has finite products, take to be the identity of . Its extension is the counit. It sends to . Going back, preserves products because a strong monoidal functor between cartesian tensors preserves the terminal object and the projections obtained by discarding a factor.
The composite on sends to . The other composite and the identity of have the same restriction up to isomorphism along the unit. By uniqueness of extension they too are isomorphic. Thus the counit is an equivalence . This makes a reflective sub-2-category of . For example, disjoint union is already a product in , so .
From commutative monoids to matrices
Take the PROP for commutative monoids from the Eckmann–Hilton calculation. Taking in the universal property shows that the cartesianization has the same set-valued models, namely commutative monoids. In the original PROP the singleton has only its identity endomorphism. After cartesianization, copying a wire and multiplying the copies gives a new unary operation , the square . More generally, an output in variables is a monomial . Copying allows repeated variables, discarding allows exponent zero, and the empty product gives the unit.
An arrow is now a tuple of such monomials. Recording their exponents gives one row per output and one column per input. For example, gives . Every matrix of natural numbers occurs. Evaluating on the free generators of the commutative monoid distinguishes different exponent vectors, and substituting monomials multiplies their exponent matrices. Hence
Tensor products of Lawvere theories
A single-sorted Lawvere theory is a cartesian category whose objects are the finite powers of a chosen object, up to isomorphism. In the PROP presentation, is the th power of the generating wire and an arrow is an -tuple of operations in variables. If and are such theories, associativity and give . Their tensor is thus cartesian. For any cartesian target, product-preserving functors out of correspond to bifunctors on preserving finite products separately in each variable. This is the Kronecker tensor product of Lawvere theories. Hyland and Power, §3
No comments:
Post a Comment