## Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

## Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorTodd_Trimble
• CommentTimeNov 9th 2010
• (edited Nov 9th 2010)

There are a few places in the nCommunity where some doubt is cast on the idea that compact Hausdorff spaces can be seen as models of a large Lawvere theory. Since this was something I had in mind in a recent post to the Categories mailing list, I thought I’d take it up here.

In fact, I would like to work more generally with monads on $Set$. My tentative claim is that algebras for an arbitrary monad can be seen as algebras for a large Lawvere theory. Since this may seem set-theoretically dubious, I’ll sketch some things out here and see whether someone can point out a mistake in my thinking.

Let $\beta: Set \to Set$ be a monad. (You can take it to be the ultrafilter monad if you like, but I’ll work more generally.) Take the large Lawvere theory to be $Kl(\beta)^{op}$, the opposite of the Kleisli category. This has small products, and the claim is that the category of $\beta$-algebras is equivalent to the category of functors $Kl(\beta)^{op} \to Set$ that preserve (small) products.

One direction is easy. The inclusion $Kl(\beta) \to Alg(\beta)$ preserves coproducts, so if $X$ is a $\beta$-algebra, the composite

$Kl(\beta)^{op} \to Alg(\beta)^{op} \stackrel{\hom(-, X)}{\to} Set$

preserves products. For $T = Th(\beta) = Kl(\beta)^{op}$, this gives a functor $Alg(\beta) \to Mod(T)$.

In the other direction, given a product-preserving functor $X: Kl(\beta)^{op} \to Set$, the “underlying set” is $X(1)$ [the 1 here is the free algebra on one element], and we would like to produce a $\beta$-algebra structure on $S = X(1)$. This should be the composite

$\beta(S) \cong Set(1, \beta(S)) \cong KL(\beta)^{op}(S, 1) \to Set(X(S), X(1)) \cong Set(S^S, S) \stackrel{\hom([1_S], S)}{\to} Set(1, S) \cong S$

where everything looks set-theoretically respectable to me so far. I will omit the details that this really is a $\beta$-algebra structure, because I think they are tedious but straightforward. So it looks as though we get in this way a functor $Mod(T) \to Alg(\beta)$.

There are further details to check of course. One is that if we start with a model $X$ of $Th(\beta)$, pass to the associated $\beta$-algebra, and pass back to a product-preserving functor as prescribed above, we get the original model $X$ back up to isomorphism. I have in mind a Yoneda-like argument for this. Just to bolster one’s confidence slightly that this won’t run into problems, I’ll note that $Mod(T)$ is locally small because the underlying-set functor is faithful: a natural transformation $X \to Y$ is determined uniquely from its value $X(1) \to Y(1)$ if $X$, $Y$ are product-preserving.

Does anyone see any problems with this? I am not yet claiming that (locally small) large Lawvere theories are essentially the same thing as monads on $Set$ (although I’d like to look into this more carefully as well).

• CommentRowNumber2.
• CommentAuthorFinnLawler
• CommentTimeNov 9th 2010

I didn’t even know that this was controversial. The pages Lawvere theory and infinitary Lawvere theory assert your last claim.

• CommentRowNumber3.
• CommentAuthorAndrew Stacey
• CommentTimeNov 9th 2010

Toby and I (and a few others) had some discussions on this (or at least, it feels as though it’s closely related, if not, I’d like to know why not) back in August: see this discussion.

The page infinitary Lawvere theory was involved in that discussion.

• CommentRowNumber4.
• CommentAuthorAndrew Stacey
• CommentTimeNov 9th 2010

(I’d like it clear that I welcome reopening this discussion, btw - it’s something that’s been on my mind again recently)

• CommentRowNumber5.
• CommentAuthorTodd_Trimble
• CommentTimeNov 9th 2010

Finn, there seems to be some conflict with a statement on the page algebraic theory, which leads to a thread here which also seems to cast some doubt. As Mike has thought more closely and deeply about the interaction between set theory and category theory than I have, I am leaving open the possibility that I am making a subtle error.

• CommentRowNumber6.
• CommentAuthorTodd_Trimble
• CommentTimeNov 9th 2010

Andrew, I didn’t read through the nForum discussion in its entirety, but I did skip ahead to see that Sridhar Ramesh made some statements which are aligning with what I’m thinking here, and which looked agreed upon.

So if we define a large (one-sorted) Lawvere theory as a category with small products in which every object is isomorphic to a small power of $1$, then it would seem that locally small large Lawvere theories are essentially equivalent to monads on $Set$. Let me look again at the page infinitary Lawvere theory

• CommentRowNumber7.
• CommentAuthorTodd_Trimble
• CommentTimeNov 9th 2010

Okay, the section Algebraic Categories in infinitary Lawvere theory looks a bit tentatively written (“conjecture”, not “theorem”). I’ll have to go through the proof carefully, but it looks at a glance (having thought about it a bit already now) like it’s going to hold up.

I think I saw, it was you Finn?, someone make reference to Fred Linton’s old article (which I’ve never read myself) which I am supposing might be where all this is originally found, but it doesn’t seem to be too well-advertised. Stuff should be better known; it’s important.

• CommentRowNumber8.
• CommentAuthorAndrew Stacey
• CommentTimeNov 9th 2010

Looking at the history of the page, I see that I was responsible for the bulk of the “Algebraic Categories” section (see, the edit history is useful - it tells me what I was thinking about all of … three months ago!) which would explain the tentative nature as I’m much less sure of my ground in these matters than the rest of you (I’m a topologist!). I would very much appreciate someone looking over it again (Toby had a look at it back then, but more eyes make better proofs, as the proverb goes).

• CommentRowNumber9.
• CommentAuthorFinnLawler
• CommentTimeNov 9th 2010

Linton’s paper (in LNM 80, TAC reprint here) does go into this, I think, in the context of structure–semantics adjointness. The formulation is quite general, but I think that his idea of semantics is just a functor $U \colon X \to A$, with everything done relative to a subcategory/functor $j \colon A_0 \to A$ of arities (perhaps dense in $A$). The theory corresponding to $U$ (its structure) is then the full image of $A(j,U) \colon A_0^{\mathrm{op}} \to [X,\mathrm{Set}]$. He shows in section 8 that if $U$ has a codensity monad then this theory (where $j = 1$) is equivalent to the opposite of $\mathrm{Kl}(T)$.

As for size issues, what I took from the exchange you linked to between Mike, Sridhar and me was that the problem is not so much with theories as with presentations of theories: Mike said

The case of complete Boolean algebras, for instance, is one where a system of ‘generators and relations’ for a monad fails to actually present one.

• CommentRowNumber10.
• CommentAuthorMike Shulman
• CommentTimeNov 9th 2010

I recall being convinced by that discussion that indeed, monads on Set are the same as (locally small) infinitary Lawvere theories, and the only difference is that, as Finn says, you can’t necessarily “present” an infinitary theory by an infinite number of generators and relations, since it might no longer be locally small.

I think there is a nice abstract viewpoint on this in terms of generalized multicategories. Ordinary Lawvere theories are “categories with virtual finite products”—i.e. normalized multicategories over the monad T for finite products on Prof—which have only one object (otherwise you get multi-sorted Lawvere theories). That is to say, they are monoids in the monoidal category of profunctors $1 ⇸ T 1$, where the monoidal structure is composition of profunctors plus the multiplication of T. But T1 is easily seen to be equivalent to $FinSet^{op}$ (that is, $FinSet$ is the result of freely adding finite coproducts to the terminal category), so the objects in this category are simply functors $FinSet\to Set$, or equivalently finitary functors $Set\to Set$, in which case the monoidal structure can be identified with ordinary composition of finitary endofunctors. This shows that ordinary Lawvere theories are the same as finitary monads on Set.

This whole picture works just as well in the infinitary case. Infinitary Lawvere theories are likewise one-object “categories with virtual small products,” hence normalized multicategories over the monad $\hat{T}$ on Set for small products. Hence they are monoids in the monoidal category of profunctors $1 ⇸ \hat{T} 1$. But now we can easily identify $\hat{T} 1$ with $Set^{op}$ (that is, Set is the result of freely adding small coproducts to the terminal category), so that this category is precisely the category of functors $Set\to Set$, and its monoidal structure is identified with ordinary composition of functors. Thus, an infinitary Lawvere theory is exactly a monad on Set.

Where does size play a role? Well, unlike $T$, the monad $\hat{T}$ doesn’t live on the bicategory Prof of small categories and profunctors, but on the virtual double category of locally small categories and locally small profunctors. In general, the proarrows in that vdc can’t be composed, since the composite of locally small profunctors between large categories may no longer be locally small. That means that a priori, the putative “monoidal category” of profunctors $1 ⇸ \hat{T} 1$ in which an infinitary Lawvere theory is to be a monoid is actually only a multicategory. However, the above argument which identifies it with $[Set,Set]$ shows that in this case, it is actually a monoidal category.

• CommentRowNumber11.
• CommentAuthorSridharRamesh
• CommentTimeNov 12th 2010
• (edited Nov 12th 2010)

Quoth Todd:

Finn, there seems to be some conflict with a statement on the page algebraic theory, which leads to a thread here which also seems to cast some doubt.

A very minor edit to bother announcing, but I’ve gone ahead and rewritten what I suspect was the misleading statement on the algebraic theory page (to note that while there is no small Lawvere theory of compact Hausdorff spaces, there is a large locally small one).

• CommentRowNumber12.
• CommentAuthorTim_Porter
• CommentTimeNov 12th 2010

There is a nice paper by Martin Hyland and John Power here.

I seem to be confused. What are many sorted theories called and where do they sit in all this? Lawvere theories are singly generated. The theories I am using in spherical object are many sorted.

• CommentRowNumber13.
• CommentAuthorSridharRamesh
• CommentTimeNov 12th 2010

I don’t know what anything is to be called, but a locally small category L with small products generated by a K-indexed collection of objects, for small K, amounts to the same thing as a monad M on Set^K (with, as before, Prod[L, Set] being equivalent to the Eilenberg-Moore category of M). This is all in exactly the same way as before; e.g., L is the dual of M’s Kleisli category.

We can push this even further by taking K to not necessarily be small; in that case, L needs more than just small products; it needs specifically the product of any multiclass of the generating objects which includes any particular generating object only a small number of times (i.e., the product of any assignment of small powers to each of the generating objects).

• CommentRowNumber14.
• CommentAuthorFinnLawler
• CommentTimeNov 12th 2010
• (edited Nov 12th 2010)

(Edit: crossed with Sridhar’s response)

I for one would call them just ‘many-sorted Lawvere theories’. You can view them as singly-sorted theories over $Set^k$, where $k$ is the set of sorts.

• CommentRowNumber15.
• CommentAuthorTodd_Trimble
• CommentTimeNov 13th 2010

I’ll probably need to do a little more rewriting of algebraic theory to be satisfied. (I might mention that the Café thread that the article points to needs to be read past the particular branch of the thread it points to, in order to get the full picture.)

Here is a personal gloss on many-sorted theories. A finitary Lawvere theory can be described as a category $T$ with finite products together with an object $X$ for which every object is a product of finitely many copies of $X$. Or, if you prefer, together with a finite-product-preserving functor $Fin^{op} \to T$ which is essentially surjective (the opposite of finite sets $Fin^{op}$ can be identified with the free category-with-finite-products generated by an indeterminate $X$, identified with the set $1$ of $Set^{op}$).

A multi-sorted finitary Lawvere theory on a set of sorts $S$ is similarly a category $T$ with finite products together with a function $f: S \to Ob(T)$ for which every object is a product of finitely many copies of objects of the form $f(s)$. Equivalently, it is a category with finite products $T$ together with an essentially surjective finite-product-preserving functor $Prod(S) \to T$, where $Prod(S)$ is the free category-with-finite-products generated by $S$. Here $Prod(S)$ can be formed explicitly: the free category-with-finite coproducts is a comma category or wreath product construction $Fin \int S$ whose objects are $(m \in Fin, x: m \to S)$, where $S$ is the set of sorts and $m$ is a finite set. A morphism $(m, x) \to (n, y)$ in $Fin \int S$ consists of a function $f: m \to n$ such that $x_i = y_{f(i)}$ for all $i \in m$. Then

$Prod(S) = (Fin \int S)^{op}$

We can even extend this to consider the case where the sorts are conceived as forming a category $S$. Then the free category-with-finite-products on the category $S$ is $Prod(S) = (Fin \int S^{op})^{op}$ where a morphism of the wreath product consists of $f: m \to n$ and together with morphisms $\phi_i: x_i \to y_{f(i)}$ in $S^{op}$. A Lawvere theory over the category $S$ is again a category $T$ with finite products together with an essentially surjective functor $Prod(S) \to T$ which preserves finite products.

We can also extend to the infinitary case, by replacing $Fin$ by $Set$ and considering a similar wreath-product construction $Set \int S$ as the free category-with-small-coproducts on a (set or category) $S$. A multi-sorted infinitary Lawvere theory consists of a category $T$ with small products together with an essentially surjective functor $(Set \int S^{op})^{op} \to T$ which preserves small products.

• CommentRowNumber16.
• CommentAuthorTim_Porter
• CommentTimeNov 13th 2010

@all That helps. My point was that the current entries on algebraic theory and Lawvere theories etc are confusing (not up to the usual high standards of exposition, … blah blah blah :-)) i.e. I could not decide which entry to link that new stuff on spherical objects to as algebraic theories is a bit ’chatty’ and Lawvere theories is definitely single sorted and although I used to have a knowledge of this stuff (and a copy of Kock and Wraith from 1970!) plus hand written notes on lectures of Chris Mulvey on this etc. the theory has passed on, developed and terminology has changed. I did not feel that I was competent to rework the current entries to where I could use them without mucking them up for others who need them for other things.

Adam’s stuff on PROs is also useful and once honed up a bit will be worth linking to. BTW he has a query there whoch is related to my question here.

• CommentRowNumber17.
• CommentAuthorTodd_Trimble
• CommentTimeNov 14th 2010

I have made some changes and rearrangements in algebraic theory where I tried to address my own concerns. Please let me know if you disagree with anything I’ve done. There is more to add in terms of technical details.

• CommentRowNumber18.
• CommentAuthorTim_Porter
• CommentTimeNov 14th 2010

Any chance of (i) a definition of an algebraic theory (as requested at the bottom of the entry), (ii) a mention of the many sorted version, and (iii) a comparison with ideas using sketches.

I like the new structure. It fits better the subject matter.

• CommentRowNumber19.
• CommentAuthorTodd_Trimble
• CommentTimeNov 14th 2010

Excellent suggestions, Tim. I intend to look into this.

• CommentRowNumber20.
• CommentAuthorMike Shulman
• CommentTimeNov 15th 2010

I think the page is very nice now, although more precise details would of course also be nice to have.

• CommentRowNumber21.
• CommentAuthorFinnLawler
• CommentTimeNov 15th 2010

Yes, it’s looking better already.

I don’t have the time to go into it myself at the moment, but it would definitely be worth expanding on Linton’s paper in LNM 80. It doesn’t seem to be widely known, as you said above, Todd, but it seems (to me, prima facie) to be the right stuff to use if we want a definition of algebraic theories that’s agnostic w.r.t. monads vs. Lawvere theories vs. whatever anyone else comes up with.

• CommentRowNumber22.
• CommentAuthorTim_Porter
• CommentTimeNov 15th 2010

Just a thought : there is a link between the categorical shape theory of a functor and the Kleisli category of the codensity monad generated by the functor (as a profunctor). There is also a link with the ’full clone of transformations ’ that Fred Linton uses. This is all in my book with Cordier (although not all originally done by us). I am not sure if that is relevant here or where?

• CommentRowNumber23.
• CommentAuthorzskoda
• CommentTimeNov 15th 2010

I am a bit confused. In the $(\infty,1)$-topos setup, Lurie abstracted the strong shape theory. Is there a $(\infty,1)$-topos-theoretic generalization of the usual shape theory ?

• CommentRowNumber24.
• CommentAuthorTim_Porter
• CommentTimeNov 15th 2010

Perhaps that would be given by Michael Batanin’s paper: Michael Batanin, Categorical strong shape theory, Cahiers Topologie Géom. Différentielle Catég. 38 (1997), no. 1, 3–66. (link on the Shape theory page). I have not completely followed the way the discussion might go, so cannot be sure (and it is n years since I read Michael’s paper.)