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.

October 17, 2007

Geometric Representation Theory (Lecture 2)

Posted by John Baez

Finally we get to see James Dolan in action, talking about Geometric Representation Theory! While I’ve been focusing on examples, now we’ll start to see the general principles at work in geometric representation theory, starting with this fact:

Every transformation group is the group of something-o-morphisms for an essentially unique something.

To formalize and prove this fact, he introduces the ‘orbi-simplex’. This is a beautiful geometrical method of constructing an axiomatic theory from an action of a finite group GG on a finite set SS, such that this theory has a unique model — a model on SS — and the symmetries of this model are the group GG.

Not many people in the class knew enough mathematical logic to fully appreciate the cunning of this construction — but the whole point is that you don’t need to know all the standard ways of thinking about logic to enjoy the orbi-simplex.

  • Lecture 2 (Oct. 2) - James Dolan on group actions, logic and the orbi-simplex. A ‘transformation group’ is a group acting as transformations of some set SS. Every transformation group is the group of all permutations preserving some structure on SS, and this structure is essentially unique. The bigger the transformation group, the less structure: symmetry and structure are dual, just like ‘entropy’ and ‘information’, or ‘relativity’ and ‘invariance’. To describe structure on sets we can use a logical theory, with types, abstract predicates and axioms. If the theory is ‘complete’ (i.e. all models are isomorphic), then the essentially unique model has a group of symmetries. In this case, how can we recover the theory from this group? For simplicity suppose its model is finite, so we have a subgroup GG of the permutation group S!S! for some finite set SS. Form the simplex Δ S\Delta_S with SS as vertices, and then take the quotient Δ S/G\Delta_S/G: the ‘orbi-simplex’. Δ S/G\Delta_S/G is nicely described as a quotient of the barycentric subdivision of Δ S\Delta_S. A simplex in the barycentric subdivision of Δ S\Delta_S is the same as a DD-flag on some nn-element subset of SS, where DD is any nn-box Young diagram. We can think of this as a ‘DD-ary predicate’ on S: an nn-ary predicate on SS invariant under the ‘Young subgroup’ corresponding to DD (that is, the subgroup of n!n! preserving the partition of nn into rows of DD). A simplex in the barycentric subdivision of Δ S/G\Delta_S/G is the same as an atomic GG-invariant DD-ary predicate on SS. These are the predicates of our logical theory — and we can read off the axioms geometrically, too!
Posted at October 17, 2007 7:03 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1466

57 Comments & 5 Trackbacks

Read the post Klein 2-Geometry IX
Weblog: The n-Category Café
Excerpt: More thoughts on 2-geometry
Tracked: October 18, 2007 1:45 PM

Re: Geometric Representation Theory (Lecture 2)

I hope some people, at least Todd, understand what Jim is up to in this seminar. I feel a bit sad sometimes when we get lots of nice comments on Jeremy Bentham’s head or old Moody Blues songs, but none about a piece of mathematics that’s really quite profound. Of course it’s a lot of work to watch a 1-hour video of a math talk and then figure out that beneath the gentle surface there’s some heavy-duty math that really deserves more explication…

Anyway, something like this seems to be going on. Given a finite set SS and a finite group GG acting on it, we want to completely describe the action in terms of the invariant nn-ary predicates on SS. These are the same as the invariant subsets of S nS^n, and these are just subsets of S n/GS^n/G.

So, to each nn we should keep track of S n/GS^n/G. But, if we think of nn as a finite set rather than just a natural number, we have

S n/G=hom(n,S)/G S^n/G = hom(n,S)/G

Then we see that any function

f:nmf: n \to m

induces a function from hom(m,S)/Ghom(m,S)/G to hom(n,S)/Ghom(n,S)/G, which deserves to be called

hom(f,S)/G:hom(m,S)/Ghom(n,S)/Ghom(f,S)/G : hom(m,S)/G \to hom(n,S)/G

The extra information in these functions is very important since it says how to use a function f:nmf: n \to m to ‘substitute variables’ in an invariant nn-ary predicate to get an invariant mm-ary predicate. (Yes, I think there’s an extra contravariant twist here.)

This is where Lawvere’s work on ‘existential and universal quantifiers as adjoints to substitution’ comes in, but never mind… What we get is a functor

hom(,S)/G:FinSet opSethom(-,S)/G : FinSet^{op} \to Set

Now, a functor from FinSet opFinSet^{op} to SetSet is called a symmetric set — it’s a close relative of a simplicial set, where instead of FinSetFinSet we use Δ\Delta, the category of totally ordered finite sets.

So, we can try to draw a symmetric set as something a bit like a simplicial set, but where the edges of our simplices don’t point in a specific direction.

If we draw the symmetric set hom(,S)/Ghom(-,S)/G as something like a simplicial set, and don’t bother drawing the ‘degeneracies’, and then take its barycentric subdivision, we get Jim’s orbi-simplex. I think. (This is all stuff he explained to me while he was developing the idea.)

What’s really cool is the relation between the orbi-simplex and Young diagrams. This deserves to be worked out quite formally.

To add to the fun, various category theorist have already studied symmetric sets — and this is where Todd might be able to help me out. I seem to recall that the category of symmetric sets is the classifying topos for Boolean algebras, or something like that. And this should have something to do with the ‘logic-flavored’ aspect of what we’re doing here: studying a Boolean algebra of GG-invariant predicates on a set SS. But, I don’t exactly see the connection. My brain still tends to freeze over when my eyes see the word ‘classifying topos’ — that’s part of the problem.

There’s also other work on symmetric sets, which may or may not be relevant.

Posted by: John Baez on October 18, 2007 5:29 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

The topos of all functors F^op -> Sets is the classifier for Boolean algebras in that its points correspond uniquely to such algebras (and the topos itself is not Boolean).

For more see page 2 of this 5 page paper by Lawvere.

One thing I don’t understand is what are symmetric simplicial sets as in this.

Posted by: Charlie Stromeyer Jr on October 18, 2007 6:24 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

I feel a bit sad sometimes when we get lots of nice comments on Jeremy Bentham’s head

Often we have comments over somebody’s head. So it’s nice to have some comments on somebody’s head once in a while.

Seriously, though, I know that sad feeling. I’d be happy to alleviate it a little by commenting myself. While I feel too busy with other stuff right now to learn about orbi-simplices and cassifying topoi, I am eagerly awaiting the point where I see the seminar finally approach groupoidification.

I already made a comment anticipating that event, and feel myself a little sad ;-) about that comment only having received replies concerned with notation.

The more you emphasize how everything you are talking about is related to “groupoidification”, the more likely it becomes that I will send a commend not on (but possibly over) somebody’s head.

Posted by: Urs Schreiber on October 18, 2007 6:25 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

Often we have comments over somebody’s head

Comments and posts as well. I’ll admit I can only follow a lot of the math here, and am left with nothing to add of my own.

Posted by: John Armstrong on October 18, 2007 7:09 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

There’s a hell of a lot math going on in this blog that I don’t follow. Probably most of it. It’s a sad business sometimes…

More in a bit.

Posted by: Todd Trimble on October 18, 2007 7:26 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

Urs, the correct classifying topos which Lawvere discusses above contains as a cartesian closed reflective subcategory the category of all groupoids.

Would this be part of “groupoidification”? I am asking because I know what some groupoids are but I don’t understand what is meant by the term “groupoidification”.

Posted by: Charlie Stromeyer Jr on October 18, 2007 7:13 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

“Would this be part of “groupoidification”?

What I meant was the particular meaning that John has given the term: in my words:

Groupoidification is the study of group representations in terms of action groupoids and their generalization.

By some cosmic coincidence, when John began spreading vague hints about how things beautify once we pass from reps to the corresponding action groupoids, thereby lifting the categorical dimension a bit, I happened to be thinking day and night about another strange lift in categoricaal dimension, and suddenly it occurred to me that both might actually be the same kind of shifts, or at least closely related.

At the moment I am thinking that JohnJimTodd’s “groupoidification” is to obstruction theory like associated bundles are to principal bundles. (That’s not supposed to be intelligible without further details. If it was, we need to talk ;-)

But I must say, as I did early on when John mentioned this the very first time: I find the term “groupoidification” rather unsuggestive of what it actually refers to.

If I were in any position to do so, I would urge its inventors to change that term to something else. It’s not too late yet, so far “groupoidification” is mainly media hype for a product that you cannot yet buy.

My suggestion: let’s think about what the concept of “action groupoid” really means (let’s think about action 2-groupoids to lift some accidental degeneracies of low dimension).

When we have figured out that action groupoids really mean XYZ, then we rename “groupoidification” to “XYZified representation theory”.

Posted by: Urs Schreiber on October 18, 2007 8:14 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

Urs wrote:

Often we have comments over somebody’s head. So it’s nice to have some comments on somebody’s head once in a while.

Auf seinen Kopf, über seinen Kopf… prepositions are so confusing.

Seriously, though, I know that sad feeling.

Yes, I’m sure you do. You come up with so many ideas that nobody can possibly keep up with them! I could easily spend all my research time just reading your posts and trying to understand them and make comments.

It’s sort of ironic, actually. I was interested in higher gauge theory for a long time. For a long time it wasn’t working very well — I was stuck on all sorts of basic problems. Then you got interested in it, and progess instantly sped up. But now you’re doing so much work on it, making such great progress, that I don’t feel it’s urgent for me to think about higher gauge theory anymore: it’s in capable hands! And without that feeling of urgency, I can’t possibly keep up with what you’re doing — doing that would require a lot of energy! There are lots of other things to think about, that don’t have an energetic nn-category theorist already working on them… so I tend to think about those.

As a result, I often neglect your posts — but I always feel a tinge of guilt about this, mixed with admiration at how well you’re doing, and maybe a bit of jealousy, and other complex murky feelings.

(There’s point in hiding it. I don’t think there’s anything to do about it, either.)

While I feel too busy with other stuff right now to learn about orbi-simplices and classifying topoi, I am eagerly awaiting the point where I see the seminar finally approach groupoidification.

Whoops! Now I can’t resist telling you about those ideas you said you don’t have time to learn about.

Classifying topoi are a bit tricky for me. They’re just like Lawvere’s ‘algebraic theories’, but instead of describing some sort of mathematical gadget using a category with finite products, we use a full-fledged topos. So, for example, the classifying topos for groups is ‘the free topos on a group object’, just as the algebraic theory for groups is ‘the free category with finite products on a group object’. It’s just a more elaborate version of the same idea.

Of course this is overkill, at least in this example, since we can already describe groups using an algebraic theory. But, we can describe lots more mathematical structures using classifying topoi, many more than with algebraic theories, because topoi are so powerful.

But while I roughly get the general idea, I still don’t have a good intuition for classifying topoi. I only mentioned them to lure Todd and other hotshots into posting some comments on this thread.

The orbi-simplex, on the other hand, is a pathetically simple idea! Take a group acting on a set. Form the simplex whose vertices are the elements of the set. The group acts on that simplex. Mod out by the group action. Voilà! The orbi-simplex.

Everything about the group action is encoded in the orbi-simplex — and if you stare at it carefully, you can read off an ‘axiomatic theory’ of precisely all the structure the group action preserves!

Jim shows how to do this in this lecture and the next one (coming soon).

Hmm. I suppose I should have tried to get people to make comments by explaining how simple the idea is, instead of how impressively technical one can make it.

But I know it’s not you, Urs, who should think about these things. It’s all those people who aren’t as productive as you — i.e., everyone else on the planet.

I already made a comment anticipating that event, and feel myself a little sad ;-) about that comment only having received replies concerned with notation.

I’m sorry — I didn’t understand that comment very well, and like you I’m busy running around doing a million things.

Hmm… let me look at that comment again. Among other things, you said:

Once could say that the action groupoid V//G has precisely the right morphisms in order to make all group element actions homotopic.

That’s basically true: the weak quotient is really a special case of a ‘weak coequalizer’. The thing you’re saying is basically the universal property of the weak coequalizer.

However, technically you should be a bit careful: you should really say

The action groupoid V//G has precisely the right morphisms in order to make all group element actions coherently homotopic.

In other words, the homotopy you get for the action of ghg h should be related in a nice way to the homotopies you get for gg and for hh. I explained this starting on page 4 of the notes for week 8 of the Winter 2004 quantum gravity seminar, and continue in week 9.

Of course, I only mention this to make you less sad at not getting replies — not to nitpick! You seem to be doing fun stuff with weak cokernels now; those are other examples of weak coequalizers.

(By the way, if you want to see me being scolded for using the word ‘weak’ in this sort of context, see this, where I was informed that my so-called ‘weak pullback’ was really an ‘iso-comma object’.)

The more you emphasize how everything you are talking about is related to “groupoidification”, the more likely it becomes that I will send a commend not on (but possibly over) somebody’s head.

Okay. I’ve been deliberately avoiding the groupoidification theme in the lectures so far, because I want the students (the actual ones in the classroom!) to get a good solid grasp of some classic pieces of linear algebra — the representation theory of symmetric groups and GL(n,F q)GL(n,F_q)’s — before I start groupoidifying them.

In other words, I want the kids to take a good look at some examples before I hit these examples with a powerful sledgehammer. You may be more interested in the sledgehammer for its own sake.

Posted by: John Baez on October 18, 2007 7:50 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

Auf seinen Kopf, über seinen Kopf… prepositions are so confusing.

Yes. For instance in German “ein Kommentar über seinen Kopf” is both “a comment on his head” and “a comment over his head” – only that the second version doesn’t have the standard metaphorical meaning, in German, of “beyond his grasp”.

Poor Danny is now trying to learn this mess they call German grammar. I am glad I don’t have to, anymore. But maybe Danny can soon tell me the names of all these rules – since I don’t know them…

Danny and I had lots of fun when we had to get all this paperwork done the days after he arrived. The first words he learned were Einwohnermeldeamt, Bezirksamt and, watch out, Gebühreneinzugszentrale (the latter one is that institution which guarantees that one can here switch on the TV without being reduced to an intellectual ameba within seconds. Instead it still takes minutes…)

Posted by: Urs Schreiber on October 18, 2007 8:35 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

I often neglect your posts — but I always feel a tinge of guilt about this

Don’t worry, I wasn’t complaining. We are all best when we do what we feel like at the moment. I literally just meant to say that I know the feeling of waiting eagerly for technical comments on blog entries.

If I had five grad students at my disposal to delegate to them finishing the 3/4-done things I have, I’d be probably switching to other things. Personal interest probably gauges itself somewhere in between the poles of felt necessity and felt fascination

And of felt need for sleep. Right now I need to call it quits. But thanks a lot for the detailed comment on classifying topoi and orbi-simplices. I’ll get back to you on that tomorrow.

Posted by: Urs Schreiber on October 18, 2007 9:22 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

If I had five grad students at my disposal to delegate to them finishing the 3/4-done things I have

Oh, for a graduate student to code up algorithms, crank out verifications, and find a way of rendering commutative diagrams in 3-D…

Posted by: John Armstrong on October 18, 2007 11:13 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

1st and 3rd of those could use a good undergrad

jim

Posted by: jim stasheff on October 19, 2007 2:10 AM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

This is true, but I’ve yet to be entrusted with enough power to bend even one of them to my will.

Posted by: John Armstrong on October 19, 2007 5:31 AM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

Getting grad students to do your work is like having kids to make life easier. I can imagine a naive young married couple thinking let’s have kids: then we can relax while they wash the dishes, vacuum the floor and do the laundry! Yeah, right. Before long, they’ll be busy changing diapers.

If you want something done quick, it’s easier do it yourself — unless it’s incredibly easy to explain how to do it, and incredibly tedious to actually do it. So, grad students are a great labor-saving convenience if you’re a chemist and you need someone to repeat the same experiment on 500 different chemicals. But in math — especially my kind of math, which isn’t supposed to be tedious — they make everything take longer.

So for me, the main advantage of having grad students is to make it impossible to quit certain projects, even when those projects bog down in annoying difficulties.

Left to my own devices, I work on lots of projects simultaneously. When one gets stuck I just switch to another for a while. Some take decades; some I’ll never finish. But a grad student can’t take this approach — they can’t afford the luxury of tackling lots of different problems and hoping one of them works out eventually! So, if I have a grad student who is close to finishing their PhD thesis, but finishing it requires surmounting a certain obstacle, I can’t just say “Oh, that’s too tough, switch to a different thesis topic.” It’s too late by then! I have to help them fight their way through it — and they’re motivated to work their butt off to finish the job. So, together we accomplish interesting things that I’d be too lazy to do on my own.

But, it’s a lot of work, and it eats up a lot of time.

Posted by: John Baez on October 19, 2007 2:30 AM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

I wrote:

I want the students (the actual ones in the classroom!) to get a good solid grasp of some classic pieces of linear algebra — the representation theory of symmetric groups and GL(n,F q)GL(n,F_q)’s — before I start groupoidifying them.

In other words, I want the kids to take a good look at some examples before I hit these examples with a powerful sledgehammer.

And why do I want them to see these examples? It’s because amazing things happen when we groupoidify them!

It’s the usual story: take the most beautiful mathematics, categorify it, and it gets even better.

Posted by: John Baez on October 19, 2007 6:40 AM | Permalink | Reply to this

action groupoids

I explained this starting on page 4 of the notes for week 8 of the Winter 2004 quantum gravity seminar, and continue in week 9.

Ah, thanks. See, I wasn’t aware of these particular notes on weak quotients.

For those not having read them: therein John talks about how to conceive the weak quotient of an action

ρ:ΣGΣAut C(V) \rho : \Sigma G \to \Sigma \mathrm{Aut}_C(V)

of a group GG on object VV in a category CC as the weak colimit

V//G:=colim ΣGρ V//G := \mathrm{colim}_{\Sigma G} \rho

(or rather, he spells out what this means in order to save his student’s nerves).

What I had in mind was a related but different way to think of this: we might define V//GV//G by looking at the weak cokernel of ρ\rho

ΣGρΣAut C(V)wcoker(ρ) \Sigma G \stackrel{\rho}{\to} \Sigma \mathrm{Aut}_C(V) \to \mathrm{wcoker}(\rho)

and then identify, somewhat more indirectly, V//GV//G as any object in a 2-category CC' such that

wcoker(ρ)ΣAut (C)(V//G) \mathrm{wcoker}(\rho) \simeq \Sigma \mathrm{Aut}_{(C')}(V//G)

I have an application in mind where we don’t care so much about the objects but rather about their automorphism nn-groups.

More precisely, I have an application here where to every rep of GG we also want a rep of INN 0(G):=wcoker(Id G)\mathrm{INN}_0(G) := \mathrm{wcoker}(\mathrm{Id}_G) “in a compatible way”.

So I am interested in the situation

G wcoker(Id G) ρ Aut C(V). \array{ G &\to& \mathrm{wcoker}(\mathrm{Id}_G) \\ \downarrow^\rho \\ \mathrm{Aut}_C(V) } \,.

With the above considerations I can complete this cone as

G wcoker(Id G) ρ 0 Aut C(V) Aut C(V//G) \array{ G &\to& \mathrm{wcoker}(\mathrm{Id}_G) \\ \downarrow^\rho & \searrow^0 & \downarrow \\ \mathrm{Aut}_C(V) &\to& \mathrm{Aut}_{C'}(V//G) }

with tranformations filling the triangles.

Posted by: Urs Schreiber on October 19, 2007 10:24 AM | Permalink | Reply to this

Classifying toposes

John wrote (confessionally)

My brain still tends to freeze over when my eyes see the word ‘classifying topos’

and (helpfully)

Classifying topoi are a bit tricky for me. They’re just like Lawvere’s ‘algebraic theories’, but instead of describing some sort of mathematical gadget using a category with finite products, we use a full-fledged topos. So, for example, the classifying topos for groups is ‘the free topos on a group object’, just as the algebraic theory for groups is ‘the free category with finite products on a group object’. It’s just a more elaborate version of the same idea.

and (hopefully)

I only mentioned them to lure Todd and other hotshots into posting some comments on this thread.

While I’m certainly not a topos hotshot, and it’s clear that the right person to explain Topos Theory is someone with initials TT, I’ll have a go at explaining classifying toposes.

Preamble

First, I agree with the paragraph of John’s quoted above. Saying that some topos is the classifying topos for Boolean algebras is very similar in spirit to saying that some finite product category is the Lawvere theory of groups, or saying that the monoidal category of 1-manifolds and cobordisms is the free monoidal category on a commutative Frobenius algebra.

Certain kinds of theory (e.g. the theory of monoids) can be interpreted in a monoidal category. In other words, if \mathcal{E} is a monoidal category, it makes sense to talk about models of such a theory in \mathcal{E}. For more general kinds of theory you have to restrict to finite product categories. For more general kinds still, you have to restrict to toposes.

However, when you get to the topos level, there are two small wrinkles. In a way I don’t want to mention them, because they don’t really matter for the explanation I’m going to give. On the other hand, they were a source of confusion to me when I first learned this stuff, so I’ll go ahead. Skip to the definition of classifying topos if you like.

One wrinkle concerns maps of toposes. If you take the definition of topos (a cartesian closed category with finite limits and a subobject classifier) and write down what seems to be the obvious notion of a map of toposes (a functor that preserves all this structure, up to isomorphism), that’s not actually a very useful notion. It turns out that the best notion of a map of toposes is that of geometric morphism: an adjunction with a certain property (that the left adjoint preserves finite limits). I can’t give a good conceptual explanation for this. A practical explanation is that a continuous map XYX \to Y of topological spaces induces a geometric morphism Sh(X)Sh(Y)Sh(X) \to Sh(Y) between toposes of sheaves, but doesn’t in general induce a map of toposes in the ‘obvious’ sense.

This brings us to the other wrinkle. Because a map of toposes is an adjunction, we have a choice of orientation. The custom is to write geometric morphisms in the direction of the right adjoint. As we’ve just seen, this convention fits with the view of toposes as generalized spaces. But — perhaps because of the usual geometry/algebra duality? — it also means that when we come to do classifying toposes of algebraic theories, things go ‘back-to-front’. So while the Lawvere theory of groups is the finite product category T\mathbf{T} with the property that for any finite product category \mathcal{E}, groups in \mathcal{E} are the same as finite-product-preserving functors T, \mathbf{T} \to \mathcal{E}, the classifying topos for groups is the topos U\mathbf{U} with the property that for any topos \mathcal{E}, groups in \mathcal{E} are the same as geometric morphisms U. \mathcal{E} \to \mathbf{U}.

What presheaves classify

The simplest toposes are the presheaf toposes. For a small category C\mathbf{C}, the presheaf topos on C\mathbf{C} is by definition the category [C op,Set][\mathbf{C}^op, Set] of contravariant set-valued functors on C\mathbf{C}. Simplicial sets (where C=Δ\mathbf{C} = \Delta) and symmetric sets (where C=FinSet\mathbf{C} = FinSet) are examples.

So, what do presheaf toposes classify? In other words, given a topos \mathcal{E}, what’s a geometric morphism [C op,Set]? \mathcal{E} \to [\mathbf{C}^op, Set] ? Of course, it could be that it just is what it is. But in fact there’s a nice theorem: a geometric morphism of this form is the same thing as a flat functor C\mathbf{C} \to \mathcal{E}. So, [C op,Set][\mathbf{C}^op, Set] classifies flat functors out of C\mathbf{C}.

OK… but what’s a flat functor? I won’t give the definition, but to a first approximation, a flat functor is a functor that preserves finite limits. This is actually true when C\mathbf{C} has finite limits. It’s also true that flat functors preserve all finite limits that exist in C\mathbf{C}. It’s somehow a bit daft to think about finite-limit-preserving functors on a category that doesn’t have all finite limits; flatness is the righteous concept.

Let’s look at the two presheaf toposes that John mentioned: simplicial and symmetric sets.

By the theorem above, [Δ op,Set][\Delta^op, Set] classifies flat functors out of Δ\Delta. Since Δ\Delta doesn’t have all finite limits (e.g. it doesn’t have binary products), it’s not terribly easy to see what a flat functor out of Δ\Delta is.

Similarly, the topos [FinSet op,Set][FinSet^op, Set] of symmetric sets classifies flat functors out of FinSetFinSet. This time we’re in luck: FinSetFinSet has finite limits, so flat == finite-limit-preserving. But it’s not so easy to see what a finite-limit-preserving functor out of FinSetFinSet is, either!

So it would be good to have some heavier artillery, and that’s what we come to next.

The classifying topos of a finitary algebraic theory

Finitary algebraic theories can be interpreted in any finite product category: for instance, you can talk about a group in any finite product category. Toposes are rather special finite product categories, so we can interpret a rather wider class of theories in them (the ‘geometric theories’). But in particular, we can still interpret finitary algebraic theories.

We can therefore ask: what is the classifying topos of a finitary algebraic theory? For instance — taking the standard example — what topos G\mathbf{G} has the property that for any topos \mathcal{E}, geometric morphisms G \mathcal{E} \to \mathbf{G} are the same thing as groups in \mathcal{E}?

The answer turns out to be wonderfully simple:

The classifying topos of the theory of groups is [Gp fp,Set][Gp_fp, Set], where Gp fpGp_fp is the category of finitely presentable groups

… and the same is true if you replace ‘the theory of groups’ by any other finitary algebraic theory.

Example  The simplest of all algebraic theories is the theory of sets. This is the theory with no operations and no equations. A true categorical logician sees nothing special about taking models in the category of sets (boring!), so would call this ‘the theory of objects’.

A finitely presentable set is simply a finite set. So the classifying topos for the theory of objects is [FinSet,Set][FinSet, Set]. In other words, for any topos \mathcal{E}, a geometric morphism [FinSet,Set] \mathcal{E} \to [FinSet, Set] is the same thing as an object of \mathcal{E}.

These are covariant functors on FinSetFinSet, so they’re not symmetric sets.

Example  The classifying topos for the theory of Boolean algebras is [Bool fp,Set][Bool_fp, Set], where Bool fpBool_fp is the category of finitely presented Boolean algebras.

Stone duality says that the category of Boolean algebras is dual to the category of Stone spaces (== compact Hausdorff totally disconnected spaces). Finite presentability of a Boolean algebra is equivalent to finiteness of the corresponding space. But a finite Stone space is just a set, so Bool fpFinSet opBool_fp \simeq FinSet^op. Hence (aha!) the classifying topos for Boolean algebras is [FinSet op,Set][FinSet^op, Set], symmetric sets.

Example  This one’s a bit of a cheat, because we’re going to consider the theory of totally ordered sets with top and bottom (intervals, let’s say), and that’s not quite an algebraic theory. Regardless, the theory of intervals does have a classifying topos, namely [Intvl f,Set][Intvl_f, Set], where Intvl fIntvl_f is the category of finite intervals.

A nice little duality says that Intvl fIntvl_f is dual to the category D\mathbf{D} of finite totally ordered sets. (Hint: think about homming into the two-element totally ordered set.) So intervals are classified by the topos [D op,Set][\mathbf{D}^op, Set] of augmented simplicial sets.

Example  If you want actual simplicial sets — that is, presheaves on the category Δ\Delta of nonempty finite totally ordered sets — then you can take the theory of nontrivial intervals, i.e. those in which the top and bottom are distinct. Thus, the topos of simplicial sets classifies the theory of strict intervals.

Similarly, presheaves on the category of nonempty finite sets classify nontrivial Boolean algebras.

Help, Todd

One thing puzzles me. According to p.2 of the paper of Lawvere mentioned by Charles Stromeyer, Boolean algebras are classified by presheaves on the category of nonempty finite sets. But according to what I’ve written above, they’re classified by presheaves on the category of all finite sets (which isn’t Morita equivalent). Either one of us is wrong (and I don’t fancy my chances against Lawvere on topos theory) or Lawvere takes Boolean algebras to be nontrivial by definition (which seems unlikely). Help!

Posted by: Tom Leinster on October 19, 2007 2:42 AM | Permalink | Reply to this

Re: Classifying toposes

Hi, Tom. Don’t worry, your answer is right, and Lawvere must have meant nondegenerate Boolean algebras (i.e., where ‘true’ and ‘false’ are distinct). I don’t think that’s quite as unlikely as you seem to think!

Thanks for explaining classifying toposes – now I can just link back to what you wrote when I post my next screed!

Posted by: Todd Trimble on October 19, 2007 12:17 PM | Permalink | Reply to this

Re: Classifying toposes

Tom, thanks for explaining classifying topoi.

Todd, at the bottom of page 3 to page 4 (also pages 166-167) of the Lawvere paper he writes “generic Boolean algebra 2^( ) (in the usual 2-valued notation)”

Can you please figure out what Lawvere is saying here, e.g., I understand what a Boolean algebra with 2^n elements is but I don’t know what Lawvere means by his notation? Thanks.

Posted by: Charlie Stromeyer Jr on October 19, 2007 1:52 PM | Permalink | Reply to this

Re: Classifying toposes

Right. It’s what you probably were already guessing: 2 ()2^{(-)} is alternate notation for the contravariant functor

hom(,2):Fin opSet.hom(-, 2): Fin^{op} \to Set.

But an interesting question is why this is called the “generic Boolean algebra”, and this enters into what Tom was explaining.

As Tom said, whenever you have a finitary algebraic theory, like the theory of groups or the theory of Boolean algebras, it is very easy to build the corresponding classifying topos: it is the topos of presheaves of the form

Alg fpSetAlg_{fp} \to Set

where Alg fpAlg_{fp} is the category of finitely presentable algebras of the theory and their homomorphisms (i.e., algebras which arise from taking coequalizers of maps between finitely generated free algebras). Now, what we mean by the classifying topos is that it is universal in some sense among pairs

(E,M)(E, M)

where EE is a Grothendieck topos and MM is an internal model of the theory as interpreted in EE. In the case of the theory of Boolean algebras, the classifying topos is the topos of functors

[Bool fin,Set][Bool_{fin}, Set]

equipped with a certain model, a universal model, which we are calling the “generic Boolean algebra”. In this case, the generic model is the underlying set functor

U:Bool finSet;U: Bool_{fin} \to Set;

it means that UU comes equipped with internal Boolean algebra operations :U×UU\wedge: U \times U \to U, ¬:UU\neg: U \to U, etc. The universal property says that given a topos-model pair (E,M)(E, M), there exists a left exact left adjoint

χ M:[Bool fin,Set]E\chi_M: [Bool_{fin}, Set] \to E

and an isomorphism ϕ:χ M(U)M\phi: \chi_M(U) \to M, and this pair (χ M,ϕ)(\chi_M, \phi) is unique up to natural isomorphism.

This recipe works the same way for any finitary algebraic theory: the classifying topos is [Alg fp,Set][Alg_{fp}, Set], and its generic model is the underlying-set functor U:Alg fpSetU: Alg_{fp} \to Set (which carries a structure of internal model of the theory), and there is this universal property as above. (If you want to view the theory of Boolean algebras as a finitary algebraic theory, one is obliged to include the terminal or degenerate Boolean algebra as a model, as Tom was doing. If you wish to restrict to non-degenerate Boolean algebras, you can do that as Lawvere was doing, but the technical details are slightly less smooth and simple.)

Finally, Lawvere is invoking the equivalence

P:Fin opBool finP: Fin^{op} \to Bool_{fin}

between the opposite of (nonempty) finite sets and (nondegenerate) Boolean algebras, where PP takes SS to the Boolean algebra 2 S2^S. Because of this equivalence, you can just as well say that [Fin op,Set][Fin^{op}, Set], equipped with the functor 2 ()2^{(-)} as model, is the classifying topos for Boolean algebras, and that’s what Lawvere was saying.

Posted by: Todd Trimble on October 19, 2007 4:29 PM | Permalink | Reply to this

Re: Classifying toposes

If you want to view the theory of Boolean algebras as a finitary algebraic theory, one is obliged to include the terminal or degenerate Boolean algebra as a model, as Tom was doing.

That didn’t come out quite right; what I meant was that if you wanted to construe the category of Boolean algebras as the category of algebras of a finitary algebraic theory, then you are obliged to include the terminal Boolean algebra as well. (You would need that for Bool finBool_{fin} to be finitely cocomplete; in that case flat functors Bool fin opEBool_{fin}^{op} \to E are easy to understand, as being nothing other than functors which preserve finite limits.)

Posted by: Todd Trimble on October 19, 2007 7:31 PM | Permalink | Reply to this

Re: Classifying toposes

Charlie writes:

Lawvere writes:

“generic Boolean algebra 2 ()2^{( )} (in the usual 2-valued notation)”

Can you please figure out what Lawvere is saying here, e.g., I understand what a Boolean algebra with 2 n2^n elements is but I don’t know what Lawvere means by his notation?

X YX^Y is a standard notation for the set of functions from a set YY to a set XX. So, 2 X2^X is the set of functions from the set XX to the set 2={0,1}2 = \{0,1\}.

Since subsets of XX are described by their characteristic functions

χ:X2\chi: X \to 2

we can also think of 2 X2^X as the set of subsets of XX. This is often called the ‘power set’ of XX — and now it should be clear why!

2 X2^X is a finite Boolean algebra: we can take unions, intersections and complements of subsets of XX, and they satisfy the usual rules of classical logic.

Moreoever, all finite Boolean algebras are of this sort. In fact, we get a contravariant equivalence of categories

2 ():FinSet opFinBool2^{(-)} : FinSet^{op} \to FinBool

sending each finite set XX to the finite Boolean algebra 2 X2^X. It’s contravariant, since a function f:XYf: X \to Y lets us take the inverse image of any subset of YY and get a subset of XX, giving a function going backwards from 2 Y2^Y to 2 X2^X.

Note: taking inverse images preserves all the Boolean algebra operations: union, intersection and complement. One can easily get confused here, since a function f:XYf: X \to Y also lets us take the image of any subset of XX and get a subset of YY. However, the image of the complement of a subset isn’t always the complement of the image! Intersections aren’t preserved either. So, we don’t get a Boolean algebra homomorphism by taking images.

There’s much more to say but I hope this helps.

Posted by: John Baez on October 19, 2007 7:08 PM | Permalink | Reply to this

Re: Classifying toposes

Thanks, Todd!

Posted by: Tom Leinster on October 19, 2007 2:07 PM | Permalink | Reply to this

Re: Classifying toposes

Tom wrote:

While I’m certainly not a topos hotshot, and it’s clear that the right person to explain Topos Theory is someone with initials TT, I’ll have a go at explaining classifying toposes.

Thanks! Excellent post! That’s really nice. I’ll keep rereading it every time I want to think more about this stuff.

Actually, on second thought, a topos theory hotshot is precisely what I don’t need to understand this stuff. I have a bunch of books — and you probably have them too — by topos theory hotshots we both know and love, but somehow they’re too heavy to make it fun and easy to learn the subject. It’s as if you said “I’d like a snack” and a genie said “Okay!” and — poof — parachuted down an enormous locked truck containing a complete inventory of mouth-watering snacks, hermetically sealed in shipping containers labelled in Greek.

Your post is more ‘bite-sized’.

Posted by: John Baez on October 19, 2007 7:20 PM | Permalink | Reply to this

Re: Classifying toposes

This is fascinating, Tom. Thanks for posting.

Part of this story can be told in an only slightly different way for plain ordinary Lawvere theories. (It also works, I think, in the slightly more general setting of models for finite limit sketches, though I won’t say any more about that.)

Take some algebraic theory – to continue Tom’s example, let’s say the theory of groups. Let \mathbb{C} be some category with finite products. Then the category of groups in \mathbb{C} is equivalent to the category of adjunctions opGrp\mathbb{C}^\mathrm{op} \to Grp, where GrpGrp is the category of ordinary groups. (There I’m writing the adjunction in the direction of the right adjoint again.)

I’m embarrassingly ignorant about this kind of thing, and I came across the above only recently in the introduction to the remarkable 1980 paper Algebraic categories with few monoidal biclosed structures or none by Foltz, Lair and Kelly. I confess I boggled, but when I recovered from my initial shock I found it was reasonably easy to prove.

It does have some slightly strange consequences. For example, a group object in the category of rings (to pick two algebraic theories out of a hat) is “the same thing” as a ring object in the category of groups. Also, the identity adjunction gives you a group object in Grp opGrp^\mathrm{op}.

I looked up what a “flat functor” is, and as I suspected it’s a functor whose left Kan extension along the Yoneda embedding preserves finite limits. Out of interest, does any of you have an easy, direct, proof that a functor with a left adjoint is flat, using the above definition of flatness? (I can extract a confusing, roundabout proof from what I’ve read, but surely there’s a more direct way?)

Posted by: Robin on October 19, 2007 7:59 PM | Permalink | Reply to this

Re: Classifying toposes

Robin wrote:

I confess I boggled, but when I recovered from my initial shock I found it was reasonably easy to prove.

It does have some slightly strange consequences. For example, a group object in the category of rings (to pick two algebraic theories out of a hat) is “the same thing” as a ring object in the category of groups.

I’m still boggling at the main thing you said — but this consequence is familiar to me, since it’s easy to prove another way.

Given two kinds of algebraic gadgets, we can construct a ‘hybrid’ where all the operations of the first gadget are required to commute with all the operations in the second gadget. It takes a while to figure out what it means for an operation with a bunch of inputs and a bunch of outputs to commute with some other operation with a bunch of inputs and a bunch of outputs. But, if you draw these operations as black boxes with wires going in and coming out, you can do it. When both operations have just one input and one output, you should get back the obvious thing: fg=gff g = g f.

For normal mathematicians, the most famous example of such a hybrid is the concept of bialgebra.

A bialgebra is an algebra, and a coalgebra, such that all the algebra operations commute with all the coalgebra operations. Admittedly, in this case ‘commute with’ is usually said a different way! People instead say the algebra operations are coalgebra homomorphisms, or — equivalently — the coalgebra operations are algebra homomorphisms. But this means the same thing.

The ‘equivalently’ mentioned above — the fact that you can think about commutativity two ways — becomes clear if we more slickly define a bialgebra to be a monoid in the category of comonoids in Vect\Vect. Then we see it’s also a comonoid in the category of monoids in Vect\Vect!

This is a special case of a very general idea. I fell in love with this idea when I first learned about it. I called it ‘commutativity of abstraction’.

There’s a version of this idea for operads, and a version for PROPs, and a version for algebraic theories, and surely lots of other versions.

For algebraic theories it goes like this. We use algebraic theories to describe algebraic gadgets, and there’s a ‘tensor product’ of algebraic theories that lets us hybridize these gadgets as described above. So, given algebraic theories AA and BB, there’s an algebraic theory ABA \otimes B such that a model of ABA \otimes B in XX is the same as a model of AA in [models of BB in XX].

But this tensor product is symmetric! So, a model of AA in [models of BB in XX] is the same as a model of BB in [models of AA in XX].

Posted by: John Baez on October 19, 2007 9:04 PM | Permalink | Reply to this

Re: Classifying toposes

John wrote:

It takes a while to figure out what it means for an operation with a bunch of inputs and a bunch of outputs to commute with some other operation with a bunch of inputs and a bunch of outputs. But, if you draw these operations as black boxes with wires going in and coming out, you can do it.

Hey! I just bumped into a picture of this, over at the Secret Blogging Seminar:

It’s in an article by Noah Snyder on the field with one element. It’s no coincidence: Durov’s ‘generalized rings’ are algebraic theories where every operation commutes with every other in the above sense.

Posted by: John Baez on October 20, 2007 7:29 AM | Permalink | Reply to this

Re: Classifying toposes

Todd Trimble pointed out to me by email that I was sloppy in my statement above. You certainly need some more hypotheses on the category \mathbb{C} (more than just that it has finite products, I mean) for what I said to be true.

I think it’s enough to ask for it to be complete and locally small. I’ll think it out properly tomorrow, and correct myself again if this correction turns out to be inadequate. :-)

Posted by: Robin on October 19, 2007 10:57 PM | Permalink | Reply to this

Re: Classifying toposes

I want to sleep on it too, but that sounds right to me, and it’s actually a very nice observation. Perhaps more on this later…

Posted by: Todd Trimble on October 19, 2007 11:27 PM | Permalink | Reply to this

Re: Classifying toposes

I wouldn’t mind taking a stab at this. We have here at least three ways of considering groups as models of a theory:

  • Models of a Lawvere or finite products theory. Here the theory may be reconstructed as the category opposite to the category of finitely generated free groups F[n]F[n]. This theory is a category with finite products. A group in a category with finite products EE is identified with a product-preserving functor FreeGrp fg opE.FreeGrp_{fg}^{op} \to E.
  • Models of a “left exact” theory. Here the theory may be reconstructed as the category opposite to the category of finitely presentable groups; this theory is a finitely complete category. A group in a finitely complete category EE is identified with a left exact or finite-limit preserving functor Grp fp opE.Grp_{fp}^{op} \to E.
  • Models of a “small-complete” theory. Here the theory may be reconstructed as the category opposite to the category of all groups; this theory is a small-complete category. A group in a small-complete EE is identified with a continuous (small-limit preserving) functor Grp opE.Grp^{op} \to E.

Let’s see how this is supposed to work. My point is that there is a uniform argument which specializes to each case, where the free group on one generator F[1]F[1] plays the role of a “generic group” which generates the theory at hand. I’ll run through the argument in the case Robin touched on, the case of models of small-limit theories in small-complete categories EE.

We begin by noticing the underlying-set functor

U:GrpSetU: Grp \to Set

carries a tautological group structure. This means we have group operations m:U×UUm: U \times U \to U, inv:UUinv: U \to U, etc.: this boils down to the obvious fact that for any group GG, the underlying set U(G)U(G) carries a group structure (well, I did say it was tautological!).

This functor is represented by the free group on one generator F[1]F[1], i.e., we have a natural isomorphism UGrp(F[1],)U \cong Grp(F[1], -). The group structure on UU translates to a cogroup structure on the representing object F[1]F[1] as an object of GrpGrp, or to a group structure as an object of Grp opGrp^{op}. In conceptual terms, what is going on is that via the (small-limit preserving) Yoneda embedding

Grp op[Grp,Set]Grp^{op} \to [Grp, Set]

Xhom(X,),X \mapsto \hom(X, -),

the object F[1]F[1] inherits a group structure from the tautological group structure on hom(F[1],)U\hom(F[1], -) \cong U.

Consequently, a small-limit preserving functor

Grp opEGrp^{op} \to E

will carry the group object F[1]F[1] to a group object in EE (because small-limit preserving, indeed product-preserving functors carry groups to groups).

Conversely, given a group object GG in EE, there is (up to isomorphism) a unique small-limit preserving functor

Grp opEGrp^{op} \to E

which takes the group F[1]F[1] to the group GG. In the case E=SetE = Set, this should be obvious: the functor is just the representable hom(,G)\hom(-, G). And actually, the general case can be reduced to the case of Set: a group GG in EE gives, for each object XX of EE, a hom-group E(X,G)E(X, G) in Set. Hence for each object XX we get a limit-preserving functor

Grp(,E(X,G)):Grp opSetGrp(-, E(X, G)): Grp^{op} \to Set

or a limit-preserving functor

Grp(,E(?,G)):Grp opSet E opGrp(-, E(?, G)): Grp^{op} \to Set^{E^{op}}

which factors through a limit-preserving functor (which I will call)

Grp(,G):Grp opEGrp(-, G): Grp^{op} \to E

via the Yoneda embedding! (The uniqueness can be deduced from the fact that every group is a colimit of a diagram involving just copies of F[1]F[1], whence every object in Grp opGrp^{op} is a corresponding limit, which must then be preserved by a continuous functor.)

The argument we just gave carries over essentially verbatim to the other types of theories, where we restrict the class of limits considered. Actually, it also carries over essentially verbatim to any algebraic theory TT instead of the theory of groups.

Remark: each of the full inclusions

FreeGrp fg opGrp fp opGrp opFreeGrp_{fg}^{op} \subseteq Grp_{fp}^{op} \subseteq Grp^{op}

can be thought of as a “completion” of some kind to a larger class of limits, e.g., the first inclusion is the universal extension of a category with finite products to a finitely complete category.

Finally, to connect up with the amazing, mind-boggling fact Robin mentioned: for many small-complete categories EE which arise in practice, it is true that continuous functors Grp opEGrp^{op} \to E coincide with right adjoints. (That would be true of the case where EE is a Grothendieck topos, for instance, or where EE is a category of algebras.) By the yoga of adjoint functors, these would correspond in turn to left adjoints

EGrp opE \to Grp^{op}

and thence to right adjoints

E opGrpE^{op} \to Grp

as Robin was saying. I’d like to hold off on identifying this class of categories, or maybe someone like Robin would like to fill us in further, or offer up a different point of view.

Posted by: Todd Trimble on October 20, 2007 6:06 PM | Permalink | Reply to this

Re: Classifying toposes

Todd, can’t any algebraic theory T be encoded as a topos? So how would what you say work with topoi?

Here is an example of my confusion. The category of abelian groups Ab is not cartesian closed because it lacks exponential objects. Hence Ab is not a topos. What is the difference between Ab and Ab(G) which is the category of abelian group objects in the topos Sh(G)? Thanks.

Posted by: Charlie Stromeyer Jr on October 20, 2007 7:58 PM | Permalink | Reply to this

Re: Classifying toposes

(With apologies to Tom, because here and elsewhere I’m repeating things he’s already said, very nicely I might add.) I think it’s what we’ve been saying: you encode it as a classifying topos, which can be considered a ‘theory’ which amalgamates finite limits and arbitrary colimits. Thus, for the theory of groups, we have two essentially equivalent descriptions of an abelian group in a (Grothendieck) topos EE:

  • A finite-limit preserving functor Ab fg opEAb_{fg}^{op} \to E as discussed in my comment above, and also by Tom and others.
  • A finite-limit and small-colimit preserving functor Set Ab fgESet^{Ab_{fg}} \to E (i.e., a left exact left adjoint).

Right, so the classifying topos for abelian groups, Set Ab fgSet^{Ab_{fg}}, can be regarded as the ‘theory’ of groups for that fragment of logic which deals with finite limits and general colimits (‘geometric logic’), as opposed to say ‘finite product logic (equational logic)’, or ‘finite limit logic’ (essentially algebraic logic, or the logic of Horn clauses), or whatnot.

As in the examples discussed in my prior comment, there is a ‘generic abelian group’ sitting inside Set Ab fgSet^{Ab_{fg}}, namely the underlying-set functor U:Ab fgSetU: Ab_{fg} \to Set, considered as an object equipped with a ‘tautological’ abelian group structure.

In fact, the two descriptions given above of an abelian group in a topos are related by a basic result of topos theory, called Diaconescu’s theorem. It’s exactly what Tom was saying: there is an equivalence of categories between

flatfunctors:C opEflat functors: C^{op} \to E

(or left exact = finite-limit preserving functors C opEC^{op} \to E, in the nice case where C opC^{op} is finitely complete), and

lexleftadjoints:Set CE.lex left adjoints: Set^C \to E.

This applies in particular to the case C=Ab fpC = Ab_{fp} we’re considering above.

If you’d like to read more on this, the book by Mac Lane and Moerdijk would be a great place to start.

Btw, Tom brought up an interesting issue back here:

It turns out that the best notion of a map of toposes is that of geometric morphism: an adjunction with a certain property (that the left adjoint preserves finite limits). I can’t give a good conceptual explanation for this. A practical explanation is that a continuous map XYX \to Y of topological spaces induces a geometric morphism Sh(X)Sh(Y)Sh(X) \to Sh(Y) between toposes of sheaves, but doesn’t in general induce a map of toposes in the ‘obvious’ sense.

I have a kind of response (which I would like to understand better myself), which I may comment on a little later.

Posted by: Todd Trimble on October 20, 2007 9:08 PM | Permalink | Reply to this

Re: Classifying toposes

Todd wrote:

We have here at least three ways of considering groups as models of a theory…

Very nice!

I like it best when topos theory is presented not as an isolated subject but as part of a spectrum of ‘kinds of categories with extra structure’, ranging in expressive power, with topoi near the upper end. If a topos is a Rolls Royce, a cartesian closed category is a Honda Civic and a monoidal category is a stripped-down dune buggy.

In fact, I’m always tempted to formalize this idea! A ‘kind of categories with extra structure’ should be, at very least, a 2-category over the 2-category Cat. We could try to follow Lawvere and work with doctrines — meaning I guess ‘categories monadic over the category Cat’ — but I’m never sure how many examples his formalism actually handles! For example: is there a doctrine, in this technical sense, with topoi as objects and geometric morphisms as morphisms?

Maybe ‘2-categories pseudomonadic over Cat’ would come closer to capturing the intuition… but anyway, let me abuse language call the thing I’m after a doctrine — fill in the definition yourself.

What you’re showing us above is that the concept of group ‘lives’ in 3 different doctrines, and behaves similarly in all three. But this is just an example of some very general idea! And this idea deserves to be made precise.

There should be some definition of a concept. Any concept will live in certain doctrines — but not others. For example, the concept of group lives in the doctrine of topoi, or finite limits theories, or algebraic theories — but not in the doctrine of symmetric monoidal categories.

And, it’s tempting to say a doctrine XX is stronger than a doctrine YY if any concept that lives in YY also lives in XX.

I should explain the crude mental image I have here: I’m imagining a poset of doctrines, some stronger than others, arranged in some sort of tower — and a bunch of concepts running like red threads between these doctrines, with each concept that lives in a given doctrine also living in every stronger doctrine. Each red thread starts somewhere — ‘the weakest doctrine in which that concept can live’ — and runs on up forever.

But I’m pretty sure this mental picture is naive. For one thing, I don’t really believe doctrines are a mere poset. I think the notion of ‘stronger’ only makes sense relative to a choice of a specific ‘forgetful 2-functor’ from the doctrine XX to the doctrine YY.

Sometimes there doesn’t seem to be much choice. For example, I think most experts would agree that the doctrine of topoi is stronger than the doctrine of algebraic theories. After all, Todd and Tom (the Topos Theorists) have just shown us a systematic way to build a classifying topos given an algebraic theory. But, presumably this implicitly relies on the usual standard method for associating to any topos its underlying algebraic theory. Of course there doesn’t seem to be much choice involved in picking this ‘strandard method’! However, I can imagine doctrines XX and YY where there’s more choice as to how any category of type XX is assigned an underlying category of type YY.

Indeed, if a doctrine is a ‘2-category pseudomonadic over Cat’, I guess we can expect there to be a full-fledged 3-category of doctrines! — not just a mere poset. This makes it tougher to make sense of ‘the same concept expressed in a different doctrine’ — the idea that makes me visualize concepts as ‘red threads running between different doctrines’. What if we follow a concept around a loop of different doctrines and come back to a different concept in the same doctrine?

Anyway, I’d be interested to know how much of this fantasy has already been made precise in the decades subsequent to Lawvere’s 1969 paper on doctrines.

Posted by: John Baez on October 20, 2007 11:59 PM | Permalink | Reply to this

Re: Classifying toposes

Hmmm, very interesting.

I just want to pick up on one bit:

For example, the concept of group lives in the doctrine of topoi, or finite limits theories, or algebraic theories — but not in the doctrine of symmetric monoidal categories.

Is it really so clear that the concept of group doesn’t live in the doctrine of symmetric monoidal categories? You can define ‘Hopf algebra’ in any symmetric monoidal category, and a Hopf algebra in a finite product category \mathcal{E} is just a group in \mathcal{E}. So, a group is a Hopf algebra by another name, one might say.

I can think of two possible objections to this:

1. The theory of Hopf algebras is a mixed algebraic/coalgebraic theory. The coalgebraic aspect isn’t welcome here! (There have been some related secret blog-comments.)

2. You weren’t thinking about Hopf algebras when you said ‘group’. You just want the group concept, dammit. I’m putting this comically but I mean it seriously; perhaps I should be using the words ‘intention’ and ‘extension’.

And there’s a further point. A cocommutative Hopf algebra in a finite product category \mathcal{E} is also the same thing as a group object in \mathcal{E}. Should we be using Hopf algebras or cocommutative Hopf algebras, or something else? Are any of these theories truly part of the group ‘concept’, in John’s sense of the word?

Posted by: Tom Leinster on October 21, 2007 12:35 AM | Permalink | Reply to this

Re: Classifying toposes

Tom wrote:

Is it really so clear that the concept of group doesn’t live in the doctrine of symmetric monoidal categories? You can define ‘Hopf algebra’ in any symmetric monoidal category, and a Hopf algebra in a finite product category EE is just a group in EE. So, a group is a Hopf algebra by another name, one might say.

Whoops! For some reason forgot that. I knew it once. Right now, I was for some reason imagining that a Hopf algebra was ‘fundamentally different’ from a group. I should probably explain to the rest of the world some stuff you know:

In defining a group, we make crucial use of the diagonal map Δ:GG×G\Delta: G \to G \times G that we have in a category with finite products, in order to write down the axiom

gg 1=g 1g=1g g^{-1} = g^{-1} g = 1

We’re using the diagonal map to duplicate the variable gg on the left hand side. We’re also using the map to the terminal object, e:G1e: G \to 1, to delete this variable on the right hand side.

In general, a symmetric monoidal category (like VectVect with its usual tensor product) doesn’t have these maps. So, to mimic the definition of a group in an arbitrary symmetric monoidal category, we need to equip our would-be group with its own ‘personal diagonal’ Δ:GGG\Delta : G \to G \otimes G, and its own ‘personal map to the unit object’ e:GIe: G \to I. We make these maps satisfy whatever equations we need to make things work — namely, that they make GG into a comonoid — and march on with our definition.

But, it was a bit silly of me to think of this idea as being ‘fundamentally different’ than a group, since it does in fact reduce to a group when our symmetric monoidal category comes from a category with finite products — since every object in a cartesian category is a comonoid in a unique way!

And there’s a further point. A cocommutative Hopf algebra in a finite product category EE is also the same thing as a group object in EE.

Right… and that’s because in a cartesian category, the unique way to make any object into a comonoid actually gives a cocommutative comonoid!

Should we be using Hopf algebras or cocommutative Hopf algebras, or something else? Are any of these theories truly part of the group ‘concept’, in John’s sense of the word?

Good puzzle — this illustrates the subtleties of tracking ‘the same concept’ across different doctrines!

I actually analyzed this example in great detail in some lecture on universal algebra, starting on page 51. There’s a 2-functor

R:[categorieswithfiniteproducts][symmetricmonoidalcategories]R: [categories with finite products] \to [symmetric monoidal categories]

which is part of a pseudadjunction. We can apply this to any algebraic theory and get a PROP.

If we apply this to the algebraic theory for groups, we get a specific PROP, which I believe is the PROP for cocommutative Hopf algebras. So, one might argue that this is the ‘correct’ answer to the puzzle “What is a group in a symmetric monoidal category?” At least it’s a systematic answer — we can do this to any algebraic theory.

(I remember worrying that the correct answer was not “cocommutative Hopf algebra” but “involutory cocommutative Hopf algebra” — meaning one where the antipode S:GGS: G \to G has square equal to 1. But then maybe I checked and found that all cocommutative Hopf algebras are involutory. I can’t remember — does anyone know? Anyway, my main point right now is that there’s some systematic way to take the concept of group and push it into the world of symmetric monoidal categories. Knowing what you actually get is just icing on the cake.)

Posted by: John Baez on October 21, 2007 5:35 PM | Permalink | Reply to this

Re: Classifying toposes

Most bialgebras (which includes Hopf algebras) are modelled by what is called a “properad”, but some Hopf algebras are modelled by props.

For more please see our comments in this secret blogging post, especially the comment by Bruno Vallette since he is the one who invented properads.

Posted by: Charlie Stromeyer Jr on October 21, 2007 5:56 PM | Permalink | Reply to this

Re: Classifying toposes

I don’t know what a ‘properad’ is, and I don’t really want to: there’s a PROP whose algebras in VectVect are precisely Hopf algebras, and that’s good enough for me.

Posted by: John Baez on October 21, 2007 11:49 PM | Permalink | Reply to this

Re: Classifying toposes

Okay, this is good I guess but where can I learn more about this particular PROP? Also, there are two things that you and Urs may want to know:

1) In theoretical physics you usually won’t find Maurer-Cartan equations but instead master equations which involve a divergence operator. In this case ordinary PROPs and operads won’t work because they can’t encode the concept of trace. This means that if your Hopf algebra (or whatever algebra) has traces then you need what is called a wheeled PROP.

2) There are close connections between the theory of properads and the theory of L_oo- algebras. You can see a simple graphical comparison of operads/properads/PROPs on page 34 of this paper.

Posted by: Charlie Stromeyer Jr on October 22, 2007 1:59 PM | Permalink | Reply to this

Re: Classifying toposes

Charlie wrote:

Okay, this is good I guess but where can I learn more about this particular PROP?

I don’t know. The fact that there’s a PROP for Hopf algebras is equivalent to the fact that you define a “Hopf object” in any symmetric monoidal category (given that a Hopf algebra is a “single-typed” algebraic structure). If you nose around online you’ll see various people working with “Hopf objects”, including Greg Kuperberg. But, it could be easier to learn a bunch about PROPs and then figure out whatever you need for yourself.

Posted by: John Baez on October 22, 2007 8:13 PM | Permalink | Reply to this

Re: Classifying toposes

John wrote:

If we apply this to the algebraic theory for groups, we get a specific PROP, which I believe is the PROP for cocommutative Hopf algebras.

Oh, that’s cool. That’s really cool. I knew about that adjunction, but I hadn’t thought of applying it to a Lawvere theory.

It’s still cool even if the answer isn’t exactly ‘cocommutative Hopf algebra’. Just as long as it’s a theory that gives you back the theory of groups when you interpret it in a finite product category. I haven’t said that quite right but you know what I mean. Presumably there’s some nice abstract way of phrasing it, but I’ve been up all night typing out propaganda on set theory for my students and it’s quite beyond me.

Posted by: Tom Leinster on October 22, 2007 5:31 AM | Permalink | Reply to this

Re: Classifying toposes

Hmm, despite the aforementioned all-nighter, I can’t tear myself away. I’m going to go ahead and post my thoughts, even though I might not respect myself in the morning.

John mentioned the (weak) adjunction L:(finiteproductcategories)(symmetricmonoidalcategories):R. L: (finite product categories) \stackrel{\rightarrow}{\leftarrow} (symmetric monoidal categories): R. Here LL is inclusion (it’s a left adjoint, mind!) and RR takes the category of cocommutative comonoids, which has finite products.

John’s suggested procedure for turning a finitary algebraic theory (a.k.a. a finite product category) into a PROP (a.k.a. a symmetric monoidal category) was to apply LL. Well, actually he said to apply RR, but I assume he meant LL.

I’m not going to try to work out what PROP M\mathbf{M} arises when you feed in the theory of groups. Instead, I just want to observe that M\mathbf{M}-models in a finite product category E\mathbf{E} are exactly groups in E\mathbf{E}, for very general reasons.

Write T\mathbf{T} for the theory of groups; then M=L(T)\mathbf{M} = L(\mathbf{T}). An M\mathbf{M}-model in E\mathbf{E} is a map L(T)L(E)L(\mathbf{T}) \to L(\mathbf{E}). If we can show that LL is full and faithful, this is the same as a map TE\mathbf{T} \to \mathbf{E}, which is a group in E\mathbf{E}.

A standard lemma says that a left adjoint is full and faithful iff the unit of the adjunction is an isomorphism. So, it’s enough to prove that the canonical map 1RL1 \to R L is an isomorphism. This basically says that if T\mathbf{T} is a finite product category then the category of cocommutative comonoids in T\mathbf{T} is isomorphic to T\mathbf{T}: and it is. QED.

John, sorry if I’m repeating stuff that’s in those lecture notes that you cited; I’ve succumbed to the heady pleasures of working stuff out for myself.

Posted by: Tom Leinster on October 22, 2007 6:24 AM | Permalink | Reply to this

Re: Classifying toposes

Tom Leinster wrote:

John mentioned the (weak) adjunction

L:(finiteproductcategories)(symmetricmonoidalcategories):R. L: (finite product categories) \stackrel{\rightarrow}{\leftarrow} (symmetric monoidal categories): R.

Here LL is inclusion (it’s a left adjoint, mind!) and RR takes the category of cocommutative comonoids, which has finite products.

That last sentence isn’t up to your usual high standards of elegance… sounds like that all-nighter took its toll.

More importantly, my lecture really mentioned a weak adjunction

L:[symmetricmonoidalcategories][finiteproductscategories]:RL: [symmetric monoidal categories] \stackrel{\rightarrow}{\leftarrow} [finite products categories]: R

I often mix up left and right… but I’m hoping this time I didn’t.

hom(LC,D)hom(C,RD)hom(L C, D) \simeq hom(C, R D)

For example: if CC is the PROP for monoids, LCL C is the algebraic theory for monoids. If DD is the finite products category of sets, RDR D is the symmetric monoidal category of sets. A finite-product-preserving functor LCDL C \to D is a monoid, and so is a symmetric monoidal functor CRDC \to R D.

Posted by: John Baez on October 22, 2007 8:29 PM | Permalink | Reply to this

Re: Classifying toposes

I have no idea what (pseudo-)adjunction you’re talking about here, John. I’d be interested in hearing more about it. (I looked at your lecture notes, but I can’t seem to find a description of this pseudo-adjunction, though I found on p. 51 the assertion that it exists.)

On the other hand, I think I do know the adjunction Tom was talking about (which was first described by Thomas Fox in a short paper published the year I was born).

From a symmetric monoidal category \mathbb{C}, you can form the category CCom()CCom(\mathbb{C}) of commutative comonoids in \mathbb{C}. It is mildly surprising but easily verified that the obvious tensor product of commutative comonoids actually has the universal property of a cartesian product, so that the CCom operation gives a functor CCom:SymmMonCatFinProdCatCCom: SymmMonCat \to FinProdCat. There’s an obvious forgetful functor U:FinProdCatSymmMonCatU: FinProdCat \to SymmMonCat, which is left (yes, left) adjoint to CCom.

(If you set things up carefully, e.g. by insisting that the objects of FinProdCat should be categories with a selected product cone for each pair of objects, I think you get a real actual honest adjunction here. I know it’s immoral to mind about such things, but life is usually easier if pseudo-adjunctions can be avoided.)

Posted by: Robin on October 23, 2007 12:09 AM | Permalink | Reply to this

Re: Classifying toposes

I have no idea what (pseudo-)adjunction you’re talking about here, John. I’d be interested in hearing more about it. (I looked at your lecture notes, but I can’t seem to find a description of this pseudo-adjunction, though I found on p. 51 the assertion that it exists.)

I sketched the idea in the previous pages. For example: if someone hands you a PROP, presented syntactically in terms of ‘operations and relations’, you can also think of this as a presentation of an algebraic theory. Indeed, from this viewpoint a PROP is just an algebraic theory with a special property: the relations aren’t allowed to duplicate or delete variables.

This gives a 2-functor

L:[PROPs][algebraictheories]L: [PROPs] \to [algebraic theories]

But, we can think of an algebraic theory as the ‘untyped’ special case of a category with finite products, and similarly for PROPS and symmetric monoidal categories. So, the idea generalizes to give us a 2-functor

L:[symmetricmonoidalcategories][finiteproductscategories]L: [symmetric monoidal categories] \to [finite products categories]

And, I think this is left adjoint (in a suitably pseudo sense) to the obvious 2-functor that takes a category with finite product and thinks of it as a specially nice symmetric monoidal category,

R:[finiteproductscategories][symmetricmonoidalcategories]R: [finite products categories] \to [symmetric monoidal categories]

This was supposed to be illustrated by my example:

hom(LC,D)hom(C,RD)hom(L C, D) \simeq hom(C, R D)

For example: if CC is the PROP for monoids, LCL C is the algebraic theory for monoids. If DD is the finite products category of sets, RDR D is the symmetric monoidal category of sets. A finite-product-preserving functor LCDL C \to D is a monoid, and so is a symmetric monoidal functor CRDC \to R D.

Your operation of forming a category with finite products from a symmetric monoidal category by taking the cocommutative comonoids,

CCom:[symmetricmonoidalcategories][finiteproductscategories]CCom: [symmetric monoidal categories] \to [finite products categories]

is a further right adjoint to what I’m calling RR. And, I think the surprise you conveyed when noting that the forgetful functor RR is a left adjoint to CComCCom:

There’s an obvious forgetful functor… which is left (yes, left) adjoint to CComCCom.

is typical of the surprise we always feel upon seeing the far-right member of an string of two adjunctions… the guy so far-right that it makes ‘forgetful’ seem like ‘free’.

Lawvere called these far-right functors ‘fascist’ functors, for the obvious reason. It’s like: “He’s so far-right he makes Reagan look like a liberal.”

Indeed I think the situation here is very much like how the forgetful functor

R:[groups][monoids] R: [groups] \to [monoids]

has both a left and right adjoint. Wanna turn a monoid into a group? Wanna make sure everyone in your monoid has an inverse? There’s the left-wing way and the far-right way. The left-wing way: give everybody an inverse, at government expense. The far-right way: take everybody who doesn’t have an inverse, line them up against the wall and shoot them!

Your ‘CComCCom’ method of turning a symmetric monoidal category into a finite products category has a similar ruthless far-right feel to it: simply kill off anybody who isn’t a cocommutative comonoid. This example is a bit different from the one I just mentioned: instead of eliminating the guys who lack a certain property, you’re eliminating everyone who can’t afford a certain structure. But that’s to be expected, since this example is one level higher on the ladder of nn-categories.

Posted by: John Baez on October 23, 2007 1:18 AM | Permalink | Reply to this

PROPs and algebraic theories

Before we go on, let me suggest an agreed notation.

(It’s mostly me that muddied the waters. Also, unless I’m much mistaken, John made a typo in his first post on the matter: the domain and codomain of RR should be interchanged. Otherwise, (a) it disagrees with his lecture notes, (b) it disagrees with his later post, and (c) the sentence that follows — ‘We can apply this to any algebraic theory and get a PROP’ — doesn’t make sense.)

Let’s agree that R:FinProdCatSymMonCat R: FinProdCat \to SymMonCat denotes the inclusion of (finite product categories) into (symmetric monoidal categories).

Robin and I have observed that RR has a right adjoint CCom:SymMonCatFinProdCat, CCom: SymMonCat \to FinProdCat, where if AA is a symmetric monoidal category then CCom(A)CCom(A) is the category of cocommutative comonoids in AA. (A less sensible person than Robin would denote this Cocommcom(A)Cocommcom(A).)

John has been saying that RR also has a left adjoint L:SymMonCatFinProdCat. L: SymMonCat \to FinProdCat. This is obtained by thinking of symmetric monoidal categories as PROPs, and finite product categories as finitary algebraic theories, then observing that any PROP gives rise to a finitary algebraic theory.

When I say ‘adjunction’ I really mean ‘weak 2-adjunction’. (One or both of the adjunctions may actually be strict.)

I’m still not convinced that LL exists. I need to think about this.

Posted by: Tom Leinster on October 23, 2007 11:33 AM | Permalink | Reply to this

Re: PROPs and algebraic theories

I’m still not convinced that LL exists.

Neither am I, but I’m coming round to the idea. Here’s a guess at what it might look like. Perhaps the mistake is to think of the ‘left-wing’ adjoint as being the product of some kind of generous-minded Scandinavian-style egalitarian socialism. Actually it’s more akin to the Soviet Union under Stalin. We want every object to have a comonoid, but we also don’t want any of them to have more than one. So we give everyone a cheap generic comonoid, then we ruthlessly destroy all the beautiful comonoids they previously had.

Slightly more formally ;-) for every object AA we add a diagonal map Δ A:AAA\Delta_A: A\to A\otimes A and a unit map ! A:AI!_A: A \to I, then we quotient out by the equations that define commutative comonoid, and we also quotient out by the naturality equations: for example, every f:AIf: A\to I is identified with ! A!_A.

I could believe that this process gives a left (mumble-)adjoint to RR.

Posted by: Robin on October 23, 2007 1:36 PM | Permalink | Reply to this

Re: PROPs and algebraic theories

Tom wrote:

Also, unless I’m much mistaken, John made a typo in his first post on the matter: the domain and codomain of RR should be interchanged.

You’re right! I’m going to exercise my super-powers and fix that, but leave your comment and this one as a monument to my fallibility. I hope this doesn’t cause even more confusion… I think it won’t. I’m trying to give far-future readers of this thread an easy time.

I’m also fixing some typos and the like that you and Robin made and later publicly regretted.

Posted by: John Baez on October 23, 2007 8:00 PM | Permalink | Reply to this

Re: PROPs and algebraic theories

OK, now I’m convinced (that RR has a left adjoint). It follows from general stuff about 2-theories.

To explain this, I’ll pick up John’s example of groups and monoids. You get from the (1-)theory of monoids to the theory of groups by adding a new operation (inverse) and some new equations. It follows that there’s an ‘inclusion’ map from the theory of monoids to the theory of groups. This induces a forgetful functor from the category of groups to the category of monoids, and a general result guarantees that this has a left adjoint.

Now let’s consider the 2-theories of finite product categories and symmetric monoidal categories. You get from the 2-theory of symmetric monoidal categories to the 2-theory of finite product categories by adding some operations —

an operation assigning to every pair (X,Y)(X, Y) of objects a map XYXX \otimes Y \to X, and another similar one for YY

an operation assigning to every map WXYW \to X \otimes Y a map WXW \to X, and another similar one for YY

analogous stuff for nullary tensor (the unit/terminal object)

— and some equations (saying that this sets up a bijection between maps WXYW \to X \otimes Y and pairs (WX,WY)(W \to X, W \to Y), and analogous equations for the unit object). So, just as for 1-theories, we get an inclusion of theories and a free-forgetful 2-adjunction on 2-categories of algebras.

It so happens that this forgetful functor RR has a further right adjoint, CComCCom. This has its uses. For instance, suppose we follow John’s suggestion and use RR to turn the finite product theory TT of groups into a symmetric monoidal theory R(T)R(T). What’s R(T)R(T) the theory of?

Well, an R(T)R(T)-algebra in a symmetric monoidal category EE is a map R(T)E. R(T) \to E. Equivalently, it’s a map TCCom(E). T \to CCom(E). Equivalently, it’s

a group in the category of cocommutative comonoids in EE.

A monoid in the category of cocommutative comonoids in EE is a cocommutative bialgebra in EE, so I suspect that a group in this category is an involutory cocommutative Hopf algebra.

Posted by: Tom Leinster on October 23, 2007 8:04 PM | Permalink | Reply to this

Re: Classifying toposes

Todd has given a characteristically elegant treatment of a general version of the theorem I mentioned.

Perhaps I can take up Todd’s invitation and offer a more simple-minded view of the case I mentioned originally. Incidentally, I believe it is due to Peter Freyd, in the 1966 paper Algebra valued functors in general and tensor products in particular, which I haven’t read. Since I haven’t read Freyd’s paper, the thoughts that follow are mine. In particular, any mistakes are mine and not Freyd’s!

I’ll continue to talk about groups, for which you may substitute the algebras of your own favourite algebraic theory. Let \mathbb{C} be a locally-small complete category. As Todd said, if GG is a group in \mathbb{C} then for every object XX\in\mathbb{C} the set (X,G)\mathbb{C}(X, G) has the structure of a group pointwise, and the hom functor (,G)\mathbb{C}(-,G) factors through the category of groups. (This is where the local smallness comes in: we need (X,G)\mathbb{C}(X, G) to be a mere set for this to work.) So each group in \mathbb{C} gives a functor opGrp\mathbb{C}^{op}\to Grp.

I claim that this functor has a left adjoint. Todd seems to be hinting that the adjoint functor theorem could be used here, if I understood him aright. But I don’t think that’s strictly necessary, and in any case I don’t think any additional assumptions are needed of \mathbb{C}.

To justify that, let me back off a bit and talk about adjunctions generally. Suppose we have categories A\mathbf{A} and B\mathbf{B} with a functor U:BAU:\mathbf{B}\to\mathbf{A}. To give a left adjoint for UU is to give a functor F:ABF: \mathbf{A}\to\mathbf{B} and an isomorphism B(FA,B)A(A,UB)\mathbf{B}(F A,B)\cong\mathbf{A}(A,U B) natural in the objects AA and BB. But in a way that’s over-specified, and you could equivalently say: to give a left adjoint for UU is to give, for every object AAA\in\mathbf{A}, an object FABF A\in\mathbf{B} and an isomorphism B(FA,B)A(A,UB)\mathbf{B}(F A,B)\cong\mathbf{A}(A,U B) natural in BBB\in\mathbf{B}. The interesting thing about this is that it takes each object of A\mathbf{A} on its own merits, instead of treating them all at once. People call FAF A a reflection of AA along UU, I think. If you have some morphism f:AAf: A\to A' in A\mathbf{A}, and the objects AA and AA' have reflections FAF A and FAF A', then you can define FfF f to be the unique (by Yoneda) map such that B(Ff,B)\mathbf{B}(F f, B) is equal to the composite

(1)B(FA,B)A(A,UB)A(A,UB)B(FA,B)\mathbf{B}(F A', B) \cong \mathbf{A}(A', U B) \cong \mathbf{A}(A, U B) \cong \mathbf{B}(F A, B)

where the middle isomorphism is A(f,UB)\mathbf{A}(f, U B), and the other two come from the reflections. In particular, if all objects have reflections, then you can turn FF into a functor in such a way that the natural isomorphism is natural in AA as well as BB, which justifies the claim that this is equivalent to the first definition I gave. But for present purposes, the important thing is that FF has a natural definition on any morphism that connects two objects that have reflections! The reason I’m repeating all this standard stuff about adjunctions is that I don’t know a name or a reference for the following fact, which is easy to prove from what I’ve just said.

Fact. Suppose we have some diagram DD in A\mathbf{A} such that every object of DD has a reflection along UU. If DD has a colimit in A\mathbf{A}, and F[D]F[D] has a colimit in B\mathbf{B}, then the colimit of F[D]F[D] is a reflection along UU of the colimit of DD.

(The image F[D]F[D] is defined using the reflections of the objects of DD, as described above.)

Returning now to the algebra situation: to give a left adjoint to our functor (,G): opGrp\mathbb{C}(-,G): \mathbb{C}^{op}\to Grp is to give a reflection along it of every group. Now, the free group on nn generators is the coproduct of nn copies of the free group on one generator; furthermore, every group is a quotient (i.e. coequaliser) of some free group. (This is true for any single-sorted algebraic theory of course, it’s not special to groups.) The category op\mathbb{C}^{op} is cocomplete by assumption. So it actually suffices to give a reflection of the free group on one generator.

But that’s easy! If G freeG_{free} is the free group on one generator, then we have

(2)Grp(G free,(X,G))(X,G) op(G,X) Grp(G_{free}, \mathbb{C}(X,G)) \cong \mathbb{C}(X,G) \cong \mathbb{C}^{op}(G,X)

naturally in XX\in\mathbb{C}, so GG itself is a reflection of G freeG_{free}. Thus our functor has a left adjoint, as we wanted.

The other direction is easy, as Todd said. If we have an adjunction opGrp\mathbb{C}^{op} \to Grp then in particular we have a cocontinuous functor Grp opGrp\to\mathbb{C}^{op}, which is determined (up to isomorphism) by what it does to the free group on one generator, giving a group in \mathbb{C}.

Sorry that was so long-winded!

Posted by: Robin on October 22, 2007 6:54 PM | Permalink | Reply to this

Re: Classifying toposes

Certainly that was shorter-winded than my account, and a very nice bit of categorical reasoning to boot. And it shows that no assumptions other than locally small and complete need be assumed, contrary to an impression I might have given. Thanks!

Posted by: Todd Trimble on October 22, 2007 8:10 PM | Permalink | Reply to this

Re: Classifying toposes

Robin wrote:

I looked up what a “flat functor” is, and as I suspected it’s a functor whose left Kan extension along the Yoneda embedding preserves finite limits. Out of interest, does any of you have an easy, direct, proof that a functor with a left adjoint is flat, using the above definition of flatness?

You have to be careful here. There’s some confusing terminology. A Set-valued functor X:CSetX: \mathbf{C} \to \Set is called flat if its left Kan extension along the Yoneda embedding — namely X:[C op,Set]Set - \otimes X : [\mathbf{C}^op, Set] \to Set — preserves finite limits. For example, any representable X=C(c,)X = \mathbf{C}(c, -) is flat, since then X- \otimes X is evaluation at cc. You can also replace SetSet by another topos, adapting the definition in a predictable kind of way.

However, there’s also a notion of what it means for an arbitrary functor G:BAG: \mathbf{B} \to \mathbf{A} to be flat, and that’s a different definition. (I said it was confusing.) For clarity, I’ll say level to mean flat in this second sense: but that’s just a spur-of-the-moment invention. By definition, GG is level if for all aAa \in \mathbf{A}, the functor A(a,G):BSet \mathbf{A}(a, G-): \mathbf{B} \to \Set is flat.

I learned the latter definition from Borceux’s book, where as far as I can see there’s no acknowledgement of the potential confusion between the two usages of ‘flat’.

So, let’s compare the notions of flatness and levelness for a functor G:CSetG: \mathbf{C} \to Set. Levelness says that Set(S,G)Set(S, G-) is flat for all sets SS. In particular, Set(1,G)=GSet(1, G-) = G is flat. So level implies flat. However, it’s possible to write down a flat GG that isn’t level. So level is stronger than flat.

The reason why I say all this is that I wonder if Robin’s question is based on a confusion between the two definitions.

It’s a theorem (which I’ll prove below) that any functor with a left adjoint is level.

In fact, it’s a lot more than that. I said that flatness was the right notion of “finite-limit-preserving” in cases where the domain category needn’t have all finite limits. There’s a variant notion of flatness for every decent class of limits, and in particular there’s a notion of ‘absolute flatness’, which is to small limits as flatness is to finite limits. And there’s an accompanying notion of ‘absolute levelness’.

Now, a famous theorem says that right adjoints preserve limits, but we now know that limit-preservation is a rather fishy condition when the domain category doesn’t necessarily have all limits. So we might suspect that something stronger and better is true: that any right adjoint is absolutely level. And that’s a theorem, too.

Since level implies flat, any Set-valued functor with a left adjoint is certainly flat (and add the word ‘absolutely’ if you like).

OK, now I’ll prove that every functor G:BAG: \mathbf{B} \to \mathbf{A} with a left adjoint (FF, say) is level. It’s easy! We have to show that for all aAa \in \mathbf{A}, A(a,G)\mathbf{A}(a, G-) is flat. But A(a,G)B(Fa,) \mathbf{A}(a, G-) \cong \mathbf{B}(Fa, -) and representables are flat, so we’re done.

Incidentally, I’ve been sweeping under the carpet smallness conditions on the categories, but I don’t think it makes a serious difference.

Posted by: Tom Leinster on October 19, 2007 11:43 PM | Permalink | Reply to this

Re: Classifying toposes

Can someone explain how Tom’s first definition is equivalent to saying that (the dual of) the category of elements of the functor is filtered ? Thanks.

Posted by: Charlie Stromeyer Jr on October 20, 2007 2:28 AM | Permalink | Reply to this

Re: Classifying toposes

Well, the proof is in several textbooks (e.g. Mac Lane and Moerdijk, and Borceux) and though I could reproduce it here, I don’t think I can add much by way of explanation. I mean, any property of a set-valued functor corresponds to some property of the category of elements (or of the fibration), and when you work it out, flatness of the functor corresponds to cofilteredness of the category of elements. I know that’s not very helpful.

You can get some idea of why it’s true by thinking about the case when the domain category C\mathbf{C} has finite limits. Let’s suppose we have a flat, i.e. finite-limit-preserving, functor X:CSetX: \mathbf{C} \to \Set, and let’s try to prove that the category of elements C/X\mathbf{C}/X is cofiltered.

Well, for a start, we have to prove that C/X\mathbf{C}/X is nonempty, i.e. that there exists an object cCc \in \mathbf{C} with X(c)X(c) nonempty. This is true because C\mathbf{C} has a terminal object 11 and X(1)1X(1) \cong 1 is nonempty.

You can make similar arguments for the other two parts of the usual definition of cofilteredness.

It’s fair to ask ‘but why?’. Perhaps some kind of satisfaction can be got by considering the situation for quite general classes of limits. This here paper contains much of what’s known.

Posted by: Tom Leinster on October 20, 2007 4:07 AM | Permalink | Reply to this

Re: Classifying toposes

You’re right, Tom. I was confusing the two different kinds of “flat”, which goes a long way to explaining why I was feeling so confused about the whole business.

Thank you very much for clearing it up my confusion. It makes perfect sense now.

(I thought I’d posted this hours and hours ago, but it looks as though I forgot to push the magic button.)

Posted by: Robin on October 20, 2007 8:51 PM | Permalink | Reply to this

Re: Classifying toposes

Good, I’m glad I was barking up the right tree.

I should have added one thing. If a set-valued functor has a left adjoint then it’s representable. (If the left adjoint is called LL then, as I’m sure you know, the representing object is L(1)L(1).) And representables are flat, easily.

Posted by: Tom Leinster on October 21, 2007 12:19 AM | Permalink | Reply to this
Read the post Geometric Representation Theory (Lecture 3)
Weblog: The n-Category Café
Excerpt: When you have any structure on a set, it has a group of symmetries. Here James Dolan shows how to work backwards: given the symmetries, how read off an axiom system describing the structure those symmetries preserve!
Tracked: October 19, 2007 3:37 AM

Re: Geometric Representation Theory (Lecture 2)

Off-topic I know: but are all you people in the LA area doing OK? I’ve just read that more than half a million people have “fled their homes”. I hope none of you have had to.

Posted by: Tom Leinster on October 24, 2007 1:09 PM | Permalink | Reply to this

Re: Geometric Representation Theory (Lecture 2)

Many students at U. C. Riverside have had problems with the fires, which have been truly horrendous, even worse than the fires of 2003. But, there have been no fires in Riverside County, so people who actually live near UCR — like Jim Dolan and I — are fine.

Southern California is having the worst drought in recorded history. Pine trees dead from bark beetle infestations cover the mountains north of Los Angeles, and dried brush everywhere is like tinder.

At the beginning of this week, Santa Ana winds started blowing in from the desert at speeds of 75 kilometers per hour, with gusts up to 145 kilometers per hour in places. Temperatures went up to 35° Celsius in places, and the humidity went down to 5%. Perfect conditions for fire — and over a dozen fires sprung up and spread rapidly. They shot flames up to 20 meters high, and sent windblown burning embers flying as much as 3 kilometers.

You can see a map of the currently active fires here. So far the worst damage has been down south in San Diego, a major city south of Los Angeles. That’s where most of the big evacuations have taken place — around a million people by now.

Overall, around 1,100 houses have burned down so far. Luckily, very few people have died: maybe about 5, counting three people over 90 who died while being evacuated from nursing homes.

The winds have died down and it’s supposed to get cooler as the week progresses. So, the hopelessly overstretched fire departments may eventually get the upper hand over these fires, which are already not spreading so fast anymore.

You can read a bit more on the October 21, 2007 entry of my diary. (You’ll need to “reload” a couple of times to get that particular entry to show up — sorry.)

Posted by: John Baez on October 24, 2007 6:39 PM | Permalink | Reply to this
Read the post Beyond the Blog
Weblog: The n-Category Café
Excerpt: How to make best use of blog material.
Tracked: November 25, 2008 2:09 PM
Read the post F and the Shibboleth
Weblog: The n-Category Café
Excerpt: Thompson's group F and free structured categories.
Tracked: January 14, 2010 12:32 AM
Read the post F and the Shibboleth
Weblog: The n-Category Café
Excerpt: Thompson's group F and free structured categories.
Tracked: January 14, 2010 1:34 AM

Post a New Comment