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.

March 7, 2017

Algebra Valued Functors in General and Tensor Products in Particular

Posted by Emily Riehl

Guest post by Maru Sarazola

The Kan Extension Seminar II continues, and this time we focus on the article “Algebra valued functors in general and tensor products in particular” by Peter Freyd, published in 1966. Its purpose is to present algebraic theories and some related notions in a way that doesn’t make use of elements, so the concepts can later be applied to any category (satisfying some restrictions).

Concerned that the language of categories was not popular enough at the time, he chooses to target a wider audience by taking an “equational” approach in his exposition (in contrast, for example, to Lawvere’s more elegant approach, purely in terms of functors and natural transformations). I must say that this perspective, which nowadays might seem somewhat cumbersome, greatly helped solidify my understanding of some of these notions and constructions.

Before we start, I would like to thank Brendan Fong, Alexander Campbell and Emily Riehl for giving me the opportunity to take part in this great learning experience, and all the other participants for their enlightening comments and discussions. I would also like to thank my advisor, Inna Zakharevich, for her helpful comments and especially for her encouragement throughout this entire process.

Algebraic theories and their algebras

An algebraic theory 𝕋\mathbb{T} is a family of operator symbols {f i}\{ f_i\}, together with non-negative integers {v i}\{ v_i\} and equations relating the f if_i’s, each of which looks in the equations as if it were a function on v iv_i arguments.

For a locally small category 𝒜\mathcal{A} with finite products, we say that A𝒜A\in\mathcal{A} is a 𝕋\mathbb{T}-algebra if it admits a 𝕋\mathbb{T}-structure, meaning each operator f i𝕋f_i\in\mathbb{T} has an interpretation f i¯: v iAA\bar{f_i}:\prod_{v_i}A\to A such that all equations are true when interpreted as maps in 𝒜\mathcal{A}. Interpretations of these nn-ary expressions follow the rules:

  1. If g(x 1,x 2,,x n)=x jg(x_1,x_2,\dots ,x_n)=x_j, then we interpret gg as the jj-th projection.
  2. If g(x 1,,x n)=f i(h 1(x 1,,x n),,h v i(x 1,,x n))g(x_1,\dots ,x_n) =f_i(h_1(x_1,\dots,x_n),\dots,h_{v_i}(x_1,\dots, x_n)) and we have already interpreted the h ih_i’s as h i¯: nAA\bar{h_i}:\prod_n A\to A and f if_i’s as f i¯: v iAA\bar{f_i}:\prod_{v_i} A\to A, then we interpret gg as nAh i¯ v iAf i¯A\prod_n A \xrightarrow{\prod\bar{h_i}} \prod_{v_i} A\xrightarrow{\bar{f_i}} A.

We will denote by 𝒜 𝕋\mathcal{A}^\mathbb{T} the category of 𝕋\mathbb{T}-algebras and homomorphisms in 𝒜\mathcal{A}.

Even though Freyd’s equational approach is (purposefully) quite different, these notions are equivalent to the ones introduced by Lawvere and mentioned previously in Evangelia’s post.

Recall that a Lawvere theory is a small category LL with finite products, together with a strict finite-product preserving identity-on-objects functor I: 0 opLI:\aleph_0^{\text{op}}\to L, and a model for the theory is a finite-product preserving functor M:LCM:L\to C. In this case, the operators f if_i determine the non-basic operations in L(v i,1)L(v_i,1) (i.e. maps not coming from the product structure), with the equations corresponding to composition in LL. As to the algebras/models, an algebra A𝒜A\in\mathcal{A} with interpretations f i¯\bar{f_i} corresponds to the finite-product preserving functor M:L𝒜M:L\to\mathcal{A} such that M(1)=AM(1)=A and M(f i)=f i¯M(f_i)=\bar{f_i}.

Constants and 0’ary operations

It seems necessary to take a moment to discuss 00‘ary operations, since Freyd decides to take a non-conventional approach. It is natural to think of the interpretation of 00‘ary operations as constants, and so we could say that a 00‘ary operation on A𝒜A\in\mathcal{A} is a constant unary operation, i.e. a map AAA\to A where BfAA=BgAAB\xrightarrow{f} A\to A = B\xrightarrow{g} A\to A for every B𝒜B\in\mathcal{A} and all maps ff and gg.

However, this comes with a problem: setting 𝒜=Set\mathcal{A}=\mathbf{Set}, the empty set would be an algebra for every algebraic theory –even those that have constants– and all our algebraic intuition revolts against this! To fix this problem, Freyd defines a generalized 00‘ary operation: a collection of maps {f B(B,A)} B𝒜\{f_B\in (B,A)\}_{B\in\mathcal{A}} such that for every map BBB\to B' the diagram commutes

a commutative diagram

Given such a collection, it’s clear from the definition that f Af_A would be a constant map; reciprocally, given a constant map, we can take that to be f Af_A and then the commutative diagram ensures us that every other f Bf_B is automatically determined by any map BAB\to A. This shows that it is reasonable to consider maps AAA\to A as our 00‘ary operations.

We must be careful though, because it might be the case that (B,A)=(B,A)=\emptyset for some B𝒜B\in\mathcal{A}, which makes it impossible to build such a collection. Whenever this is the case, we will say that there are no 00‘ary operations on AA and therefore AA cannot be a 𝕋\mathbb{T}-algebra for any algebraic theory that has 00‘ary operations.

Although this treatment of constants and 00‘ary operations eliminates the problem of the empty set, it seems terribly unnatural to me. I’m left wondering, why didn’t Freyd define a 00‘ary operation on AA as a map TAT\to A where TT is the terminal object in 𝒜\mathcal{A}? Are there important examples of categories over which we want to consider algebras for certain theories, and that don’t have a terminal object? (I don’t know of any, I’m hoping someone here will)


As usual, we obtain a notion of 𝕋\mathbb{T}-co-algebra by dualizing the definition of 𝕋\mathbb{T}-algebra; in other words, a 𝕋\mathbb{T}-co-algebra in 𝒜\mathcal{A} is precisely a 𝕋\mathbb{T}-algebra in 𝒜 *\mathcal{A}^*. However, as we will soon see, co-algebras will not be relegated to a dualizing afterthought and will instead play a key role in the understanding of algebra valued functors.

Example. Let’s take a look at an example. Let 𝕋\mathbb{T} be the algebraic theory of groups, and 𝒜\mathcal{A} the category of pointed spaces and homotopy classes of maps. In this case the coproduct is the wedge of spaces, and a space XX is a 𝕋\mathbb{T}-co-group if there exists a co-product Δ:XXX\Delta:X\to X\vee X, a co-inverse map ν:XX\nu: X\to X and a co-unit ϵ:XX\epsilon: X\to X satisfying diagrams dual to the group diagrams. As a concrete example we have the nn-spheres S nS^n for n2n \geq 2, which admit a co-group structure by taking Δ:S nS nS n\Delta:S^n\to S^n\vee S^n to be the operation that collapses the equator of S nS^n to a point, ϵ:S nS n\epsilon: S^n\to S^n that collapses S nS^n to the basepoint, and where ν:S nS n\nu: S^n\to S^n is any orientation-reversing map (they are all homotopic, after all!). We get the necessary commutative diagrams

a diagram

where ff –for “fold”– is the operation dual to the diagonal map d:S nS n×S nd:S^n\to S^n\times S^n. Note that this wouldn’t work in Top\mathbf{Top}, since we only have co-associativity up to homotopy.

Algebra valued functors

Fix B𝒜 𝕋B\in\mathcal{A}^\mathbb{T} and denote by (,B):𝒜 opSet(-,B):\mathcal{A}^{\text{op}}\to\mathbf{Set} the contravariant hom-set functor. For any A𝒜A\in\mathcal{A}, we can give (A,B)(A,B) a 𝕋\mathbb{T}-algebra structure as follows: given an operator f if_i in 𝕋\mathbb{T}, and the interpretation f i¯: v iBB\bar{f_i}:\prod_{v_i}B\to B determined by the algebra structure of BB, we can take its interpretation to be the composition v i(A,B)(A, v iB)f i¯(A,B)\prod_{v_i}(A,B)\cong (A,\prod_{v_i} B)\xrightarrow{\bar{f_i}\circ -} (A,B) All equations of the theory will be preserved, since (A,)(A,-) is a product-preserving functor. Thus, (,B)(-,B) is an algebra valued functor and we can write (,B):𝒜 opSet 𝕋(-,B):\mathcal{A}^{\text{op}}\to\mathbf{Set}^\mathbb{T}. Similarly, if AA is a 𝕋\mathbb{T}-co-algebra in 𝒜\mathcal{A}, the covariant functor (A,):𝒜Set(A,-):\mathcal{A}\to\mathbf{Set} will be algebra valued.

Example: Returning to our example of the nn-spheres, note that the wedge sum co-product gives (S n,B)(S^n,B) a group structure for any pointed space BB, which is precisely the usual group structure of the homotopy groups!

Interestingly, the converse of the previous statement is also true! Algebra valued representable functors yield canonical (co)structures on their representatives, so we can actually state the following:

A𝒜A\in \mathcal{A} is a 𝕋\mathbb{T}-co-algebra (resp. BB is a 𝕋\mathbb{T}-algebra) if and only if the functor (A,)(A,-) (resp. (,B)(-,B)) is algebra valued.

To show this less evident converse, fix an operator f if_i in 𝕋\mathbb{T}; using the 𝕋\mathbb{T}-algebra structure of (A,B)(A,B) we have, for every B𝒜B\in\mathcal{A}, a map (A,B)(A,B)f i˜(A,B)(\sum A, B)\simeq \prod(A, B)\xrightarrow{\tilde{f_i}} (A,B) It suffices to show that these maps can be put together to form a natural transformation (A,)(A,)(\sum A,-)\Rightarrow (A,-) since then, by Yoneda, it must come from a map AAA\to\sum A which we take as the co-interpretation of f if_i.

This amounts to showing that, for any g:BBg:B\to B', the following commutes

a commutative diagram

But (A,)(A,-) is an algebra valued functor, so (A,B)(A,B)(A,B)\to (A,B') must be a homomorphism, which by definition translates into that diagram being commutative.

For the case of algebra valued functors F:𝒜Set 𝕋F:\mathcal{A}\to\mathbf{Set}^\mathbb{T} where 𝒜\mathcal{A} is complete, we have that FF is representable if and only if it has a left adjoint (Theorem 2 in the article). This fact, together with a translation of the general adjoint functor theorem to this algebraic context, yields for any infinite cardinal κ\kappa

A functor T:Set 𝕋 1Set 𝕋 2T:\mathbf{Set}^{\mathbb{T}_1}\to\mathbf{Set}^{\mathbb{T}_2} is representable by a 𝕋 1\mathbb{T}_1-algebra with κ\kappa or less generators (and with a 𝕋 2\mathbb{T}_2-co-structure) if and only if FF preserves products, kernel pairs, and κ\kappa-directed unions.

The canonical co-structure on free algebras

Let 𝕋\mathbb{T} be an algebraic theory and let FF in Set 𝕋\mathbf{Set}^\mathbb{T} be the free algebra on one generator xx. Then FF admits a canonical 𝕋\mathbb{T}-co-algebra structure:

First note that nF\sum_n F is the free 𝕋\mathbb{T}-algebra on nn generators {x 1,,x n}\{x_1,\dots ,x_n\}, since “free” constructions preserve colimits. Thus, each operator f if_i in 𝕋\mathbb{T} has an interpretation f i¯: v i( v iF) v iF\bar{f_i}:\prod_{v_i} (\sum_{v_i} F)\to \sum_{v_i} F The canonical co-interpretation of f if_i that gives FF a co-algebra structure is f i˜:F v iF\tilde{f_i}:F\to \sum_{v_i} F xf i¯(x 1,,x v i)x\mapsto \bar{f_i}(x_1,\dots ,x_{v_i}) Chasing the operations around, it’s possible to see that this is the only co-structure on FF (up to isomorphism) which makes (F,):Set 𝕋Set 𝕋(F,-):\mathbf{Set}^\mathbb{T}\to\mathbf{Set}^\mathbb{T} naturally equivalent to the identity functor.

Tensor products of theories

For two algebraic theories 𝕋 1\mathbb{T}_1 and 𝕋 2\mathbb{T}_2, we would like to find a theory 𝕋\mathbb{T} with the property that 𝒜 𝕋(𝒜 𝕋 1) 𝕋 2\mathcal{A}^\mathbb{T}\cong (\mathcal{A}^{\mathbb{T}_1})^{\mathbb{T}_2}, i.e. we want 𝕋\mathbb{T}-algebras to be the objects A𝒜A\in \mathcal{A} with a 𝕋 1\mathbb{T}_1-structure and a 𝕋 2\mathbb{T}_2 structure and such that every 𝕋 2\mathbb{T}_2 operation is a 𝕋 1\mathbb{T}_1 homomorphism. Let’s make this last condition explicit: every pair of operators f i𝕋 1f_i\in\mathbb{T}_1, g j𝕋 2g_j\in\mathbb{T}_2, must satisfy

(1)f i(g j(x 11,,x 1v j),,g j(x v i1,,x v iv j))=g j(f i(x 11,,x v i1),,f i(x 1v j,,x v iv j))f_i\left(g_j(x_{11},\dots,x_{1v_j}),\dots, g_j(x_{v_i1}, \dots,x_{v_i v_j})\right) = g_j\left(f_i(x_{11},\dots,x_{v_i1}),\dots,f_i(x_{1v_j},\dots,x_{v_i v_j})\right)

It’s easy to see that the theory we are looking for has as operators the disjoint union of operators in 𝕋 1\mathbb{T}_1 and 𝕋 2\mathbb{T}_2, and as equations all the equations found in 𝕋 1\mathbb{T}_1 and 𝕋 2\mathbb{T}_2, along with all possible equations of the form (1). If we denote such a theory by 𝕋 1𝕋 2\mathbb{T}_1\otimes \mathbb{T}_2, then the equivalence with the notion of tensor product of Lawvere theories becomes apparent, as they were both defined to satisfy the universal properties 𝒜 𝕋 1𝕋 2(𝒜 𝕋 2) 𝕋 1    (Freyd)\mathcal{A}^{\mathbb{T}_1\otimes\mathbb{T}_2}\cong (\mathcal{A}^{\mathbb{T}_2})^{\mathbb{T}_1}       \text{ (Freyd)} Mod(LL,𝒜)Mod(L,Mod(L,𝒜))    (Lawvere)\mathbf{Mod}(L\otimes L',\mathcal{A})\cong \mathbf{Mod}(L,\mathbf{Mod}(L',\mathcal{A}))       \text{ (Lawvere)}

In contrast to the tensor of Lawvere theories, this explicit formulation makes it simple to compute some basic examples. Let 𝕋 R\mathbb{T}_R be the theory of modules over a ring RR (this has all the operators and equations found in the theory of abelian groups, with the addition of one unary operator λ r\lambda_r for every rRr\in R that acts as “multiplication by rr”, and the diagrams ensuring that these define a ring action).

  • If 𝕋 S\mathbb{T}_S is the theory of modules over SS, then 𝕋 R𝕋 S\mathbb{T}_R\otimes\mathbb{T}_S-algebras on Set\mathbf{Set} will be abelian groups that admit both RR and SS actions. Furthermore, equation (1) imposes commutativity among these actions: λ rλ s=λ sλ r\lambda_r\lambda_s=\lambda_s\lambda_r, and so we find that 𝕋 R𝕋 S\mathbb{T}_R\otimes\mathbb{T}_S is the theory of modules over RSR\otimes S.
  • If 𝕋 U\mathbb{T}_{U} is the theory with one unary operator UU and no equations, then 𝕋 R𝕋 U\mathbb{T}_R\otimes\mathbb{T}_{U} is the theory of modules over the polynomial ring R[U]R[U].
  • If 𝕋 U 1,,U n\mathbb{T}_{U_1,\dots,U_n} is the theory with unary operators U 1,,U nU_1,\dots,U_n and no equations, then 𝕋 R𝕋 U 1,,U n\mathbb{T}_R\otimes\mathbb{T}_{U_1,\dots,U_n} is the theory of modules over R[U 1,,U n]R[U_1,\dots,U_n] where the variables U iU_i don’t commute (recall that equation (1) is only enforced between an operator of 𝕋 1\mathbb{T}_1 and one of 𝕋 2\mathbb{T}_2, not among operators from the same theory).

This generalizes to the following impressive result:

If 𝕋 1\mathbb{T}_1 is the theory of modules over a semi-ring, then for any 𝕋 2\mathbb{T}_2, there exists a semi-ring RR such that 𝕋 1𝕋 2\mathbb{T}_1\otimes\mathbb{T}_2 is the theory of modules over RR.

An application: theories for closed categories

A category 𝒜\mathcal{A} is autonomous (according to Linton) if there exists a functor Hom:𝒜 op×𝒜𝒜\mathbf{Hom}:\mathcal{A}^{\text{op}}\times\mathcal{A}\to\mathcal{A} and a forgetful functor U:𝒜SetU:\mathcal{A}\to\mathbf{Set} such that UHom(A,B)(A,B)U\mathbf{Hom}(A,B)\simeq (A,B). If we restrict ourselves to algebraic theories 𝕋\mathbb{T} such that their categories of algebras Set 𝕋\mathbf{Set}^\mathbb{T} are autonomous, then these theories are also those which have their categories of algebras closed.

If 𝕋\mathbb{T} is such a theory, then the fact that we can see (,):(Set 𝕋) op×Set 𝕋Set 𝕋(-,-):(\mathbf{Set}^\mathbb{T})^{\text{op}}\times\mathbf{Set}^\mathbb{T}\to\mathbf{Set}^\mathbb{T} as algebra valued means that each BSet 𝕋B\in\mathbf{Set}^\mathbb{T} has a canonical 𝕋\mathbb{T}-structure in Set 𝕋\mathbf{Set}^\mathbb{T}. This gives us an embedding Set 𝕋Set 𝕋𝕋\mathbf{Set}^\mathbb{T}\to\mathbf{Set}^{\mathbb{T}\otimes\mathbb{T}}, and therefore * 𝕋\mathbb{T} must be such that every 𝕋\mathbb{T} operator is a 𝕋\mathbb{T} homomorphism*; in other words, all operators in 𝕋\mathbb{T} commute, in the sense of (1).

As an example, if 𝕋 R\mathbb{T}_R is once again the theory of modules over RR, then the largest subtheory 𝕋𝕋 R\mathbb{T}'\subset\mathbb{T}_R such that Set 𝕋\mathbf{Set}^{\mathbb{T}'} is closed will be the largest subtheory with commutative operators: the theory of modules over the center of RR.

Lawvere functors

A Lawvere functor is a functor T:Set 𝕋 1Set 𝕋 2T:\mathbf{Set}^{\mathbb{T}_1}\to\mathbf{Set}^{\mathbb{T}_2} that preserves underlying sets. Since TT trivially preserves products, kernel pairs and directed unions, it must be representable; say T(A,)T\simeq (A,-) for some ASet 𝕋 1A\in\mathbf{Set}^{\mathbb{T}_1} with a 𝕋 2\mathbb{T}_2 co-structure. Then BT(B)(A,B)B\simeq T(B)\simeq (A,B) (as sets) for every BB, so AA must be the free 𝕋 1\mathbb{T}_1 algebra on one generator. We see that Lawvere functors T:Set 𝕋 1Set 𝕋 2T:\mathbf{Set}^{\mathbb{T}_1}\to\mathbf{Set}^{\mathbb{T}_2} are in one-to-one correspondence with the 𝕋 2\mathbb{T}_2-co-structures we can place on the free 𝕋 1\mathbb{T}_1-algebra.

Now, when choosing a 𝕋 2\mathbb{T}_2-co-structure for the free 𝕋 1\mathbb{T}_1-algebra FF we get, for each operator f i𝕋 2f_i\in\mathbb{T}_2, an interpretation f i¯:F v iF\bar{f_i}:F\to\sum_{v_i} F. This will of course be determined by its image on the generator, f i¯(x)\bar{f_i}(x), which is in turn an expression in 𝕋 1\mathbb{T}_1 of the same arity as f if_i. This shows that 𝕋 2\mathbb{T}_2-co-structures on the free 𝕋 1\mathbb{T}_1-algebra are in one-to-one correspondence with theory maps 𝕋 2𝕋 1\mathbb{T}_2\to\mathbb{T}_1.

We have just built a contravariant functor 𝕋Set 𝕋\mathbb{T}\mapsto \mathbf{Set}^\mathbb{T} from the category of algebraic theories to the category of categories, which is no other than Lawvere’s Semantics functor!

Some questions left unanswered

  • Freyd’s way of dealing with 00‘ary operations has been a thorn in my side ever since reading this article. I would love to understand the reason for his choice of definitions, that seems so artificial to me.

    A comment regarding 00‘ary co-operations that might be of relevance: by dualizing the definitions, we obtain the notions of co-constant map and generalized 00‘ary co-operation, which will be in one-to-one correspondence with each other except in the case where (A,B)=(A,B)=\emptyset for some B𝒜B\in\mathcal{A}; in this case we say that AA doesn’t admit a 𝕋\mathbb{T}-co-algebra structure for any 𝕋\mathbb{T} with 00‘ary operations.

    If we consider the case of the free 𝕋\mathbb{T}-algebra on one generator FSet 𝕋F\in\mathbf{Set}^\mathbb{T}, we see that (F,B)=(F,B)=\emptyset only when B=B=\emptyset. Since we are taking BSet 𝕋B\in\mathbf{Set}^\mathbb{T}, that would imply that the theory 𝕋\mathbb{T} has no 00‘ary operations itself. This makes sense, of course, because we already know that FF always has a canonical co-structure.

    Could the co-algebras be the reason behind these definitions? Are we interested in studying algebras over categories with terminal but no initial object, and if so, are we particularly interested in them having co-algebras too?

  • Equation (1) has a taste of a really nice distributive law. Is there a relation between tensors of theories and distributive laws, perhaps asking the latter to satisfy some nice properties? A few clarifying answers have appeared among our reading responses; I look forward to seeing this discussion here!
Posted at March 7, 2017 10:22 AM UTC

TrackBack URL for this Entry:

6 Comments & 0 Trackbacks

Re: Algebra Valued Functors in General and Tensor Products in Particular

I don’t know why Freyd chose to single out 0-ary operations in that way, but there is a more abstract way to describe what he’s doing that applies also to nn-ary operations for all nn. Recall that for any locally small category 𝒜\mathcal{A}, the Yoneda embedding 𝒜P𝒜=[𝒜 op,Set]\mathcal{A} \to P \mathcal{A} = [\mathcal{A}^{op},Set] preserves all limits that exist in 𝒜\mathcal{A}, while the presheaf category P𝒜P \mathcal{A} is complete. Therefore, in any (locally small) category 𝒜\mathcal{A} at all, we can define a 𝕋\mathbb{T}-algebra in 𝒜\mathcal{A} to be a 𝕋\mathbb{T}-algebra in P𝒜P \mathcal{A} (in the naive sense) whose underlying object is representable.

If 𝒜\mathcal{A} has finite products, this agrees with the more direct definition, because the Yoneda embedding preserves products. If 𝒜\mathcal{A} doesn’t necessarily have a terminal object, then the 0-ary operations are interpreted as natural transformations from the terminal presheaf into 𝒜(,A)\mathcal{A}(-,A), which if you unravel it is exactly a “generalized 0-ary operation”. Similarly, if 𝒜\mathcal{A} lacks binary products, then the binary operations are interpreted as natural transformations 𝒜(,A)×𝒜(,A)𝒜(,A)\mathcal{A}(-,A) \times \mathcal{A}(-,A) \to \mathcal{A}(-,A), i.e. operations assigning to each pair of morphisms a 1:BAa_1:B\to A and a 2:BAa_2:B\to A another morphism f(a 1,a 2):BAf(a_1,a_2) : B\to A, in a way that varies naturally with BB.

It’s also worth noting that since limits in P𝒜P \mathcal{A} are objectwise, a 𝕋\mathbb{T}-algebra in P𝒜P \mathcal{A} is the same as a functor from 𝒜\mathcal{A} to the category of 𝕋\mathbb{T}-algebras in SetSet. Thus, to give A𝒜A\in \mathcal{A} a 𝕋\mathbb{T}-algebra structure is equivalently to lift its representable functor 𝒜Set\mathcal{A}\to Set along the forgetful functor Set 𝕋SetSet^{\mathbb{T}}\to Set.

Posted by: Mike Shulman on March 7, 2017 11:42 AM | Permalink | Reply to this

Re: Algebra Valued Functors in General and Tensor Products in Particular

I think when we work “representably” like you lay out, we are ‘really’ working in an equipment of profunctors.

In her paper “Distributive laws for Lawvere theories”, Eugenia Cheng shows that Lawvere theories are equivalently algebras on the terminal category 1 in the Kleisli equipment of the free product monad PP on the equipment of categories, functors, and profunctors. What this all says, ultimately, is that a Lawvere theory is given by a profunctor L:1×P1 opSetL : 1 \times P1^{\text{op}} \to \text{Set}, a functor from opposite category of the free product category on a single generator (which is the category of finite sets) to sets. L(n)L(n) is the set of nn-ary operations of the theory. To tie this in to the usual view, the Kleisli lift of LL to a profunctor P1×P1 opSetP1 \times P1^{\text{op}} \to \text{Set} is the hom-functor of the category of finitely generated free models of LL, or the opposite of the hom-functor of the category which is usually used to define LL.

Now, with any algebra in an equipment, we can take its left and right modules. A left module is a profunctor 1×PC opSet1 \times PC^{\text{op}} \to \text{Set} which is acted on the left by LL. If we let C=1C = 1, then we see that this is a functor P1 opSetP1^{\text{op}} \to \text{Set} which is acted on by LL; I believe this is a model of LL, and the for general CC we get a presheaf of models on CC, but I haven’t quite checked this yet.

If you have a model MM of LL in the usual sense, then the profunctor C(,M)C(-, M-) is a left LL-model. I think this is the same thing you are talking about, with operations being represented as natural transformations.

A right module here is a profunctor C×P1 opSetC \times P1^{\text{op}} \to \text{Set} acted upon by LL, which I believe can be twiddled into a model of LL in Set C\text{Set}^C. If CC has coproducts, and the model is representable, then we get an LL coalgebra. The story Freyd tells about coalgebras in categories of models becomes a story about bimodules of algebras in an equipment!

Posted by: David Jaz Myers on March 7, 2017 8:15 PM | Permalink | Reply to this

Re: Algebra Valued Functors in General and Tensor Products in Particular

While I love profunctors, I don’t believe this is quite correct. For instance, I think the additional dependence on P1 opP1^{op} in a left module prevents it from being an LL-model.

Posted by: Mike Shulman on March 8, 2017 7:23 PM | Permalink | Reply to this

Re: Algebra Valued Functors in General and Tensor Products in Particular

This post really helped cement my understanding of Lawvere theories and their tensor products by making everything very concrete.

I was wondering if there is a similarly concrete description of distributive laws between theories. Mike Stay’s comment on an earlier post says that a `composite’ of theories 𝕋 1\mathbb{T}_1 and 𝕋 2\mathbb{T}_2 is given by

𝕋 1+𝕋 2/~ d \mathbb{T}_1 + \mathbb{T}_2 / ~_d

where ~ d~_d expresses the distributive law, but doesn’t say what ~ d~_d should look like. Maru’s post tells us that tensors are also of the form

𝕋 1+𝕋 2/~ t \mathbb{T}_1 + \mathbb{T}_2 / ~_t

but this time, we know that ~ t~_t takes the form of equation (1) above. This suggests that ~ d~_d should say: for every f i𝕋 1,g j𝕋 2f_i \in \mathbb{T}_1, g_j \in \mathbb{T}_2 there exist f i𝕋 1f'_i \in \mathbb{T}_1 and g j𝕋 2g'_j \in \mathbb{T}_2 such that

(1)f i(g j(x 11,,x 1v j),,g j(x v i1,,x v iv j))=g j(f i(x 11,,x v i1),,f i(x 1v j,,x v iv j)) f_i\left(g_j(x_{11},\dots,x_{1v_j}),\dots, g_j(x_{v_i1}, \dots,x_{v_i v_j})\right) = g'_j\left(f'_i(x_{11},\dots,x_{v_i1}),\dots,f'_i(x_{1v_j},\dots,x_{v_i v_j})\right)

We would need the map (f i,g j)(g j,f i)(f_i,g_j) \mapsto (g'_j, f'_i) to satisfy some conditions akin to those for a distributive law between monads. I’m not sure if this agrees with the abstract definition in Eugenia Cheng’s `Distributive laws between Lawvere theories’.

If this definition works, a tensor product would then be a special case, where f i=f if'_i = f_i and g j=g jg'_j = g_j.

Posted by: Ze on March 8, 2017 9:42 AM | Permalink | Reply to this

Re: Algebra Valued Functors in General and Tensor Products in Particular

The commutativity condition is not quite an instance of a distributive law in the usual sense. A distributive law between monads on Set consists of functions TSSTT S \to S T. An element of TSXT S X is of the form f(y 1,,y u)f(y_1,\dots,y_u) for some uu-ary operation of TT and elements y 1,,y uy_1,\dots,y_u of SXS X. In turn, each y iy_i is of the form g i(x i1,,x iv i)g_i(x_{i1},\dots, x_{i v_i}) for some v iv_i-ary operation of SS and elements x ijx_{i j} of XX, so our element of TSXT S X looks like

f(g 1(x 11,,x 1v i),,g u(x u1,,x uv u)) f(g_1(x_{11}, \dots,x_{1 v_i}), \dots, g_u(x_{u1},\dots,x_{u v_u}))

which is kind of like the LHS of your (1), but involves many different gg’s. A distributive law TSST T S \to S T then has to assign to each such element, a dual element g(f 1(),,f w())g(f_1(\dots),\dots,f_w(\dots)) of STXS T X, in a coherent way.

But instead of a function, I believe equation (1) can be regarded as a relation between TST S and STS T, and presumably as a sort of “relational distributive law”. I don’t know whether anyone has written down a definition of such a thing, but I’ve been looking into them recently for a different reason. Actually, I’ve been looking at a generalization to proarrow equipments: a “horizontal distributive law” between “vertical monads”.

Posted by: Mike Shulman on March 8, 2017 7:32 PM | Permalink | Reply to this

Re: Algebra Valued Functors in General and Tensor Products in Particular

The result of Freyd that you mention, characterising algebra valued functors in terms of coalgebras, naturally leads to a number of fun applications. For instance, that the categories of monoids and groups have no monoidal biclosed structures and that the category of categories has exactly two! See the introduction to Algebraic categories with few monoidal biclosed structures or none by Foltz, Kelly and Lair for a summary of results of that kind and references.

The last chapter of George Bergman’s book An invitation to general algebra and universal constructions is much inspired by Freyd’s paper too.

By the way, a nice categorical variant of the above result of Freyd that you mention is the following:

The category of algebras Alg(T)Alg(T) is the free cocomplete category containing a TT-comodel!

Here the universal TT-comodel in Alg(T)Alg(T) is the restricted Yoneda embedding y:TAlg(T)y:T \to Alg(T). This gives rise to an equivalence Comod(T,C)LAdj(Alg(T),C)Comod(T,C) \simeq LAdj(Alg(T),C).

Posted by: John Bourke on March 8, 2017 11:34 AM | Permalink | Reply to this

Post a New Comment