Lawvere theories versus classical universal algebra - MathOverflow

Lawvere theories versus classical universal algebra

2011-06-29T02:56:00Z

A Lawvere theory is a small category with finite products such that every object is isomorphic to a finite product of copies of a distinguished object x. A model of the theory in a category with finite products is a product preserving functor from the theory to that category.

This notion is supposed to be the right categorical viewpoint on universal algebra. Given a classical variety of universal algebra, one gets a theory by considering the opposite of the category of finitely generated free algebras.

My question is, what are the advantages/disadvantages of theories versus classical universal algebra?

I believe that theories are more general. What are natural examples of theories that are not covered by classical universal algebra?

Does the classical equational theory of universal algebra have a nice analog for theories?

Answer by Todd Trimble for Lawvere theories versus classical universal algebra

2011-06-29T06:24:07Z

My own experience is that Lawvere theories help one "think outside the box" in ways that I really don't think are too likely with classical universal algebra. Qiaochu has already pointed to what is the key idea: that they enable one to consider models other than in $Set$. Actually, you could put it more strongly. Namely, in Lawvere's formulation, the theory is a model in this extended sense: it is the universal model. For example, the Lawvere theory of groups is the category with finite products where all you know about it is that it has a group object, and nothing more. You could take this philosophy further still: any category with finite products $C$ could be considered an algebraic theory in its own right, where a model of $C$ in a category with finite products $D$ is a product-preserving functor $C \to D$. And this conceptual expansion pays off.

Let me give a concrete example of this: consider the concept of Boolean algebra. Here the Lawvere theory is the category of finite sets of cardinality $2^n$, denoted $Fin_{2^\bullet}$. This is already a neat way to define a Boolean algebra: as a product-preserving functor

$$Fin_{2^\bullet} \to Set.$$

But it's even nicer when you complete $Fin_{2^\bullet}$ to its Karoubi envelope. It's not hard to see that if $C$ is a category with finite products, then the Karoubi envelope $\bar{C}$ also has finite products, and the models of $C$ are equivalent to models of $\bar{C}$. In the present case, the Karoubi envelope of $Fin_{2^\bullet}$ is $Fin_+$, the category of finite nonempty sets. Thus a Boolean algebra is equivalently a product-preserving functor

$$Fin_+ \to Set$$

This not only looks prettier, but it frees us from tendencies of thinking of Boolean algebras as having intrinsically to do with things like power sets and powers of 2: there's no power of 2 sticking out in this description. I call this an unbiased Boolean algebra -- we have removed the bias toward 2.

It also allows one to see that one could be biased in different ways, and see Boolean algebras, if we want, as having to do with powers of 3 instead. In other words, the Lawvere theory $Fin_{3^\bullet}$ has, by the same Karoubi envelope reasoning, the same models as $Fin_+$, so we could just as well think of a Boolean algebra as a product-preserving functor

$$Fin_{3^\bullet} \to Set$$

which gives a totally different way of seeing Boolean algebras as monadic over $Set$ -- here the "underlying sets" of such algebras have a tendency to look like structures on sets of cardinality $3^n$. If you are wondering what good that is for, I might recommend looking at the nLab article on Boolean algebras, and on the multiplicity of different ways of understanding the ultrafilter monad which this suggests. I personally have found this quite eye-opening.

Historically, the heyday of Lawvere theories was in the sixties, when the close connections with monads were ironed out. Lawvere theories are essentially the same things as finitary monads; one advantage of Lawvere theories is that it enabled one to more clearly see this connection, which in turn leads to a clear view of the story about infinitary theories and their equivalence with monads on $Set$ (at least for locally small theories). Nowadays these things are under good control, and they allow us to define things like "compact Hausdorff objects" as models of the infinitary Lawvere theory attached to the ultrafilter monad -- these too are useful. I don't think any of this would have been at all easy to see from the point of view of classical universal algebra.

The connection between theories and monads is worked out in this nLab article. Cf. also this MO answer, which goes into some more detail on the discussion about Boolean algebras.

Edit: In a comment below, Gerhard Paseman very kindly called my attention to the example of $n$-valued Post algebras, which I had not heard of prior to this discussion. Apparently these were introduced by the Polish logician Emil Post based on his studies of $n$-valued logic as an extension of ordinary 2-valued logic; the $n$-valued Post algebras are to $n$-valued logic as Boolean algebras are to 2-valued logic. There are a number of equational presentations of Post algebras; see for example this article by George Epstein from the Transactions of the AMS.

Perhaps I can use this very example to follow Gerhard's advice, and deliver an attempted sales pitch specifically to him. :-) I hope it's not considered off the topic; it is meant to illustrate the basic conceptual simplicity of the Lawvere-theory way of thinking.

If my suspicions are right, the Lawvere theory of $n$-valued Post algebras is nothing but $Fin_{n^\bullet}$, the category of finite sets whose cardinality is a power of $n$. Or, in other words, that such Post algebras can be identified with functors

$$Fin_{n^\bullet} \to Set$$

that preserve finite products. Certainly for anyone used to Lawvere theories, this gives a very tidy description, and this description makes it easy to see the essential equivalence between $n$-valued Post algebras and Boolean algebras, as in the Karoubi envelope analysis above (which uses nothing more complicated than idempotent functions between finite sets).

For those not used to Lawvere theories (and of course this is assuming my suspicions are correct), the more traditional syntactic descriptions given by Post and his followers can be extracted from this categorical description. The rough idea is this. If $X$ is a Boolean algebra, and if $P(n)$ is the power set of a set with $n$ elements, then the elements of the corresponding $n$-valued Post algebra are simply Boolean algebra homomorphisms $P(n) \to X$. Let $X(n)$ denote this set. The $m$-fold cartesian product $X(n)^m$ is naturally identified with $X(n^m)$, the set of Boolean algebra homomorphisms $P(n^m) \to X$. Then, we may describe the clone of Post algebra operations: the $m$-ary operations $X(n)^m \to X(n)$ in the clone are in one-to-one correspondence with functions $f: [n^m] \to [n]$ from an $n^m$-element set to an $n$-element set. Namely, each function $f: [n^m] \to [n]$ induces a Boolean algebra map $f^{-1}: P(n) \to P(n^m)$ (the inverse image $f^{-1}$ takes a subset $S \subseteq [n]$ to $f^{-1}(S) \subseteq [n^m]$); then the corresponding Post algebra operation $X(n^m) \to X(n)$ sends a Boolean algebra map $\phi: P(n^m) \to X$ to the composite

$$P(n) \stackrel{f^{-1}}{\to} P(n^m) \stackrel{\phi}{\to} X.$$

This gives the clone; giving an explicit description of a set of operations and identities for the theory in a universal algebra sense is pretty much the same thing as giving a combinatorial analysis of functions between sets of cardinality a power of $n$, in other words how to generate such functions from a smaller class using cartesian products and composition.

I think with that clue, we can figure out what is going on in Epstein's paper. The constants of the theory are given by functions $[1] \to [n]$, so there are $n$ of them. These are the $e_i$ of his paper. Next, unary operations of the clone are given by functions $[n] \to [n]$; for his purposes, Epstein selects $n$ of them, and calls them $C_i$ ($i = 0, \ldots, n-1$). From our point of view, they are uniquely specified by how they act on the constants, since a function $[n] \to [n]$ is uniquely determined by how it acts on functions $[1] \to [n]$. Epstein's $C_i$ are just the indicator or characteristic functions given by $C_i(e_j) = \delta_{ij}$ (returning the "bottom" constant $e_0 = \bot$ if $i \neq j$, and the "top" constant $e_{n-1} = \top$ if $i = j$). These together with the lattice operations $\wedge: [n]^2 = [n^2] \to [n]$ and $\vee: [n]^2 = [n^2] \to [n]$, which are again uniquely specified by how they act on constants (and defined by the expected rules if the $e_i$ are ordered by $e_i \leq e_j$ iff $i \leq j$), are shown by Epstein to generate the theory of Post algebras, but seems pretty intuitive that they generate the clone as described here by the Lawvere theory $Fin_{n^\bullet}$: it says that any finite function $[n^m] \to [n]$ can be built from a combination of meets and joins applied to the constants $e_i$ and their characteristic functions $C_j$.

Part of my point above was that all the Post algebra theories can be united under a single simple umbrella given by the category of product-preserving functors $Fin_+ \to Set$.

Answer by Sebastian for Lawvere theories versus classical universal algebra

2012-01-08T14:22:06Z

The following point is of course related to the fact that you can use models different from Set, but I think it deserves to be discussed explicitly.

Every clone (in the unverisal algebra sense) can be written as a set of morphisms in a suitable category. Obviously, this category can be chosen to be the category of sets (since the functions in a clone are set-functions), but we might also very well chose another category. For instance, one can write every clone on a finite set as the set of homomorphisms over a relational structure in a variety of relational structures (understood as a category). This works since every clone on a finite set is the set of polymorphisms of a certain set of relations.

To give another example: If the clone in question is a so-called centralizer clone, then it can even be written as the set of homomorphisms in a variety of algebras (understood as a category).

Thus, in terms of Lawvere theories, you look at models in categories different from Set. The advantage of the category-theoretic setting is that you can now apply duality theory. For instance, if we take the centralizer clone of a Boolean algebra, then we can interpret it as a model in the category of Boolean algebras and use the Stone duality to dualize it to a comodel in the category of sets, which are then, if you transfer the scenario back to unviversal algebra, essentially the (well-studied and easy to understand) coclones over sets.

In the last few years, there have been a few papers that studied clones in exactly this way. In particular, this gave many new results for the centralizer clones of Boolean algebras, distributive lattices (which, via Priestley Duality, become comodels in the category of Priestley spaces) and median algebras (which, via a duality by Isbell, become comodels in the category of what I think is often called Isbell spaces). I do not see any (convenient) way to formulate such a connection without using category theory and looking at clones as Lawvere theories.

I believe this is a nice example where shifting to a category theoretic setting has some actual advantages and is not just a question of whether you personally like it or not.

Answer by Akhil Mathew for Lawvere theories versus classical universal algebra

2012-05-02T14:28:03Z

One reason that Lawvere theories might be useful is in homotopy theory: Badzioch has apparently done work on formalizing the notion of a "homotopy algebra" (over a given Lawvere theory). The idea seems to be that an algebra over a Lawvere theory is something you can make homotopyish without recourse to things like operads: given $T$, a homotopy $T$-algebra is a functor $T \to \mathrm{Spaces}$ which preserves products up to homotopy equivalence (rather than on the nose).

In general, it seems that having a categorical language rather than explicit operations is much better for making algebraic structures homotopy invariant. An earlier example is given by the $\Gamma$-spaces of Segal: one writes the axioms of an abelian monoid in terms of a suitable product-preserving functor $\mathrm{Fin}_* \to \mathbf{Sets}$ and replaces those then by weakly product-preserving functors to spaces. It turns out grouplike $\Gamma$-spaces are essentially equivalent to infinite loop spaces.

I don't understand too much of this yet, but what's a little puzzling to me is that homotopy $T$-algebras (according to Badzioch) turn out to be essentially the same as ordinary $T$-algebras. (By contrast, the homotopy-theoretic analog of an abelian group--an infinite loop space--is generally very different from an abelian group.)