The n-Category Café

Algebraic theories and their algebras

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

For a locally small category $\mathcal{A}$ with finite products, we say that $A\in\mathcal{A}$ is a $\mathbb{T}$-algebra if it admits a $\mathbb{T}$-structure, meaning each operator $f_i\in\mathbb{T}$ has an interpretation $\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 $n$-ary expressions follow the rules:

1. If $g(x_1,x_2,\dots ,x_n)=x_j$, then we interpret $g$ as the $j$-th projection.
2. If $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_i$’s as $\bar{h_i}:\prod_n A\to A$ and $f_i$’s as $\bar{f_i}:\prod_{v_i} A\to A$, then we interpret $g$ as $\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 $L$ with finite products, together with a strict finite-product preserving identity-on-objects functor $I:\aleph_0^{\text{op}}\to L$, and a model for the theory is a finite-product preserving functor $M:L\to C$. In this case, the operators $f_i$ determine the non-basic operations in $L(v_i,1)$ (i.e. maps not coming from the product structure), with the equations corresponding to composition in $L$. As to the algebras/models, an algebra $A\in\mathcal{A}$ with interpretations $\bar{f_i}$ corresponds to the finite-product preserving functor $M:L\to\mathcal{A}$ such that $M(1)=A$ and $M(f_i)=\bar{f_i}$.

Constants and 0’ary operations

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

However, this comes with a problem: setting $\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 $0$‘ary operation: a collection of maps $\{f_B\in (B,A)\}_{B\in\mathcal{A}}$ such that for every map $B\to B'$ the diagram commutes

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

We must be careful though, because it might be the case that $(B,A)=\emptyset$ for some $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 $0$‘ary operations on $A$ and therefore $A$ cannot be a $\mathbb{T}$-algebra for any algebraic theory that has $0$‘ary operations.

Although this treatment of constants and $0$‘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 $0$‘ary operation on $A$ as a map $T\to A$ where $T$ 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)

Co-algebras

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 $X$ is a $\mathbb{T}$-co-group if there exists a co-product $\Delta:X\to X\vee X$, a co-inverse map $\nu: X\to X$ and a co-unit $\epsilon: X\to X$ satisfying diagrams dual to the group diagrams. As a concrete example we have the $n$-spheres $S^n$ for $n \geq 2$, which admit a co-group structure by taking $\Delta:S^n\to S^n\vee S^n$ to be the operation that collapses the equator of $S^n$ to a point, $\epsilon: S^n\to S^n$ that collapses $S^n$ to the basepoint, and where $\nu: S^n\to S^n$ is any orientation-reversing map (they are all homotopic, after all!). We get the necessary commutative diagrams

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

Algebra valued functors

Fix $B\in\mathcal{A}^\mathbb{T}$ and denote by $(-,B):\mathcal{A}^{\text{op}}\to\mathbf{Set}$ the contravariant hom-set functor. For any $A\in\mathcal{A}$, we can give $(A,B)$ a $\mathbb{T}$-algebra structure as follows: given an operator $f_i$ in $\mathbb{T}$, and the interpretation $\bar{f_i}:\prod_{v_i}B\to B$ determined by the algebra structure of $B$, we can take its interpretation to be the composition $$\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,-)$ is a product-preserving functor. Thus, $(-,B)$ is an algebra valued functor and we can write $(-,B):\mathcal{A}^{\text{op}}\to\mathbf{Set}^\mathbb{T}$. Similarly, if $A$ is a $\mathbb{T}$-co-algebra in $\mathcal{A}$, the covariant functor $(A,-):\mathcal{A}\to\mathbf{Set}$ will be algebra valued.

Example: Returning to our example of the $n$-spheres, note that the wedge sum co-product gives $(S^n,B)$ a group structure for any pointed space $B$, 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\in \mathcal{A}$ is a $\mathbb{T}$-co-algebra (resp. $B$ is a $\mathbb{T}$-algebra) if and only if the functor $(A,-)$ (resp. $(-,B)$) is algebra valued.

To show this less evident converse, fix an operator $f_i$ in $\mathbb{T}$; using the $\mathbb{T}$-algebra structure of $(A,B)$ we have, for every $B\in\mathcal{A}$, a map $$(\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 $$(\sum A,-)\Rightarrow (A,-)$$ since then, by Yoneda, it must come from a map $A\to\sum A$ which we take as the co-interpretation of $f_i$.

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

But $(A,-)$ is an algebra valued functor, so $(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:\mathcal{A}\to\mathbf{Set}^\mathbb{T}$ where $\mathcal{A}$ is complete, we have that $F$ 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:\mathbf{Set}^{\mathbb{T}_1}\to\mathbf{Set}^{\mathbb{T}_2}$ is representable by a $\mathbb{T}_1$-algebra with $\kappa$ or less generators (and with a $\mathbb{T}_2$-co-structure) if and only if $F$ preserves products, kernel pairs, and $\kappa$-directed unions.

The canonical co-structure on free algebras

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

First note that $\sum_n F$ is the free $\mathbb{T}$-algebra on $n$ generators $\{x_1,\dots ,x_n\}$, since “free” constructions preserve colimits. Thus, each operator $f_i$ in $\mathbb{T}$ has an interpretation $$\bar{f_i}:\prod_{v_i} (\sum_{v_i} F)\to \sum_{v_i} F$$ The canonical co-interpretation of $f_i$ that gives $F$ a co-algebra structure is $$\tilde{f_i}:F\to \sum_{v_i} F$$ $$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 $F$ (up to isomorphism) which makes $(F,-):\mathbf{Set}^\mathbb{T}\to\mathbf{Set}^\mathbb{T}$ naturally equivalent to the identity functor.

Tensor products of theories

For two algebraic theories $\mathbb{T}_1$ and $\mathbb{T}_2$, we would like to find a theory $\mathbb{T}$ with the property that $\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\in \mathcal{A}$ with a $\mathbb{T}_1$-structure and a $\mathbb{T}_2$ structure and such that every $\mathbb{T}_2$ operation is a $\mathbb{T}_1$ homomorphism. Let’s make this last condition explicit: every pair of operators $f_i\in\mathbb{T}_1$, $g_j\in\mathbb{T}_2$, must satisfy

It’s easy to see that the theory we are looking for has as operators the disjoint union of operators in $\mathbb{T}_1$ and $\mathbb{T}_2$, and as equations all the equations found in $\mathbb{T}_1$ and $\mathbb{T}_2$, along with all possible equations of the form (1). If we denote such a theory by $\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 $$\mathcal{A}^{\mathbb{T}_1\otimes\mathbb{T}_2}\cong (\mathcal{A}^{\mathbb{T}_2})^{\mathbb{T}_1}       \text{ (Freyd)}$$ $$\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 $\mathbb{T}_R$ be the theory of modules over a ring $R$ (this has all the operators and equations found in the theory of abelian groups, with the addition of one unary operator $\lambda_r$ for every $r\in R$ that acts as “multiplication by $r$”, and the diagrams ensuring that these define a ring action).

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

This generalizes to the following impressive result:

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

An application: theories for closed categories

A category $\mathcal{A}$ is autonomous (according to Linton) if there exists a functor $\mathbf{Hom}:\mathcal{A}^{\text{op}}\times\mathcal{A}\to\mathcal{A}$ and a forgetful functor $U:\mathcal{A}\to\mathbf{Set}$ such that $U\mathbf{Hom}(A,B)\simeq (A,B)$. If we restrict ourselves to algebraic theories $\mathbb{T}$ such that their categories of algebras $\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 $(-,-):(\mathbf{Set}^\mathbb{T})^{\text{op}}\times\mathbf{Set}^\mathbb{T}\to\mathbf{Set}^\mathbb{T}$ as algebra valued means that each $B\in\mathbf{Set}^\mathbb{T}$ has a canonical $\mathbb{T}$-structure in $\mathbf{Set}^\mathbb{T}$. This gives us an embedding $\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 $\mathbb{T}_R$ is once again the theory of modules over $R$, then the largest subtheory $\mathbb{T}'\subset\mathbb{T}_R$ such that $\mathbf{Set}^{\mathbb{T}'}$ is closed will be the largest subtheory with commutative operators: the theory of modules over the center of $R$.

Lawvere functors

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

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

We have just built a contravariant functor $\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 $0$‘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 $0$‘ary co-operations that might be of relevance: by dualizing the definitions, we obtain the notions of co-constant map and generalized $0$‘ary co-operation, which will be in one-to-one correspondence with each other except in the case where $(A,B)=\emptyset$ for some $B\in\mathcal{A}$; in this case we say that $A$ doesn’t admit a $\mathbb{T}$-co-algebra structure for any $\mathbb{T}$ with $0$‘ary operations.

  If we consider the case of the free $\mathbb{T}$-algebra on one generator $F\in\mathbf{Set}^\mathbb{T}$, we see that $(F,B)=\emptyset$ only when $B=\emptyset$. Since we are taking $B\in\mathbf{Set}^\mathbb{T}$, that would imply that the theory $\mathbb{T}$ has no $0$‘ary operations itself. This makes sense, of course, because we already know that $F$ 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!