## January 14, 2009

### Hopf Algebras from Posets

#### Posted by John Baez As usual, visiting my friend Bill Schmitt in DC made me think about combinatorics. A long time ago, based on ideas of his advisor Gian-Carlo Rota, he developed some nice ways to get Hopf algebras from collections of partially ordered sets, or ‘posets’:

The last example in this paper later became known as the ‘Connes–Kreimer’ Hopf algebra. Why? Because those guys rediscovered it and applied it to renormalization in quantum field theory!

I would like to understand Bill’s constructions in a more category-theoretic way. But this raises some questions about posets of subobjects… and I’m hoping some of you can help me out!

Bill can construct a Hopf algebra from any collection of posets satisfying certain conditions. In examples, these collections of posets are often formed by taking a category and looking at all its ‘posets of subobjects’.

Any object $c$ in any category $C$ has a poset of subobjects, which I’ll call $Sub(c)$. For example, the subobjects of a set are just its subsets. The subobjects of a vector space are just its linear subspaces. And so on.

The two examples I just mentioned give interesting Hopf algebras… at least if we work with finite sets and finite-dimensional vector spaces. But I want to know why. In other words: I want to know which categories give collections of posets — namely, posets of subobjects — that make Bill’s construction work.

Here’s the condition that’s puzzling me most. I think some of you category theory experts can help me out.

Question: What conditions on a category make the following condition true? Given any object $c$ and any subobject $x$ of $c$, there’s an object $c/x$ such that $Sub(c/x)$ is isomorphic to the poset of all subobjects of $c$ that are greater than or equal to $x$.

For example, the category of sets has this property, where $c/x$ is just the set $c$ minus the subset $x$. Why? Because subsets $a$ with $x \subseteq a \subseteq c$ are in natural one-to-one correspondence with subsets of $c/x$… and this correspondence is order-preserving.

Also, the category of vector spaces has this property, where $c/x$ is just the vector space $c$ modulo the subspace $x$. Why? Because subspaces $a$ with $x \subseteq a \subseteq c$ are in natural one-to-one correspondence with subspace of $c/x$… and this correspondence is order-preserving.

Now, in both these cases I know what’s going on. The category in question has coproducts, and for any subobject $x$ of $c$, there’s an object $y$ such that $x + y \cong c$. We can then take $c/x = y$.

In other words, every subobject $x$ has a ‘complement’ $y$, such that $c$ is the sum of $x$ and $y$.

But this is a very drastic condition. It’s not true in the category of modules of a typical ring. Nonetheless, in any such category we can still get things to work: just $c/x$ to be the usual quotient. In fact, we can do this in any abelian category.

So: what condition most naturally handles both abelian categories and categories like $Set$, which are not abelian?

I’ll restate my question more formally, just for people who like lots of precision.

Given two elements $x,y$ of a poset $P$, the interval $[x,y]$ is the set of all $a \in P$ lying between $x$ and $y$:

$x \le a \le y$

This interval becomes a poset in its own right.

Question: What conditions on a category $C$ make the following true? Given any object $c$ and any subobject $x \in Sub(c)$, there is an object I’ll call $c/x \in C$ such that

$[x,c] \cong Sub(c/x)$

as posets. (Here note that $c$ is a subobject of itself — the biggest one.)

Posted at January 14, 2009 4:36 PM UTC

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

### Re: Hopf Algebras from Posets

Incomplete as it is, maybe the $n$Lab entry on subobject ($\to$ $n$Lab) is already better than the Wikipedia entry.

Posted by: Urs Schreiber on January 14, 2009 6:58 PM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

I’ll change my reference! I looked for an $n$Lab reference to ‘Hopf algebra’ and didn’t find one. Since I was in a big rush I didn’t take the time to create one — now I have.

I then felt too rushed to look for $n$Lab references to ‘poset’ or ‘subobject’, which was a mistake.

I do want to point people to the $n$Lab entries whenever it makes sense. And, I want people to improve those entries!

Posted by: John Baez on January 15, 2009 5:49 PM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

There are nice concepts that generalise both abelian categories and toposes. But that will probably not work, since constructively $\Sub(c \setminus x)$ is only a retract of $[x,c]$.

Is there a nice concept that generalises both abelian categories and boolean toposes? (Incidentally, even constructivists believe that $\Fin\Set$, if appropriately defined, is boolean.)

Posted by: Toby Bartels on January 14, 2009 8:17 PM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

On a tangent, what was so ‘startling’ about what Vaughan Pratt explains here?:

Just how close vector spaces come to sets can be measured by the startling new fact found two months ago by Peter Freyd that the only difference between an abelian category and a topos is in the behavior of 0 (the initial object). Among AT categories, those satisfying the universal Horn sentences of category theory common to the theories of abelian categories and toposes, the abelian categories are those for which 0 is isomorphic to 1 (the final object – 0 and 1 are both the trivial group in the category of abelian groups, the canonical abelian category), whereas the toposes are those for which 0 is an annihilator for product ($A \times 0 ~ 0$ for all objects $A$, the familiar behavior of the empty set under Cartesian product in the category of sets, the canonical topos).

Posted by: David Corfield on January 14, 2009 8:57 PM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

David wrote:

On a tangent, what was so ‘startling’ about what Vaughan Pratt explains here?

It may not be much of a tangent, since I’m trying to understand why both the topos $Set$ and any abelian category have ‘quotient objects’ $c/x$ with the properties I described. You’re hinting that Michael Barr will know the answer.

As for why it’s startling… well, if someone told you the only difference between set theory and linear algebra was the difference between the empty set and the zero-dimensional vector space, wouldn’t you be startled? That’s basically what Barr showed.

Topoi are the nice category-theoretic generalization of the category of sets. Abelian categories are the nice category-theoretic generalization of the category of vector spaces — or modules of any ring. They’re very different, but they also have lots in common. So, list everything that they have in common — or more precisely, everything you can say in very simple sentences (‘universal Horn sentences’). This is the definition of an ‘AT category’.

Then, if you add one axiom saying $0 = 1$ — that is, the initial object is terminal — you’ve got the axioms for an abelian category! But if you add an axiom saying $A \times 0 = 0$ — the product of the initial object and any other is initial — you’ve got the axioms for a topos!

Surely you’re not so jaded as to find this unsurprising?

Posted by: John Baez on January 16, 2009 7:27 AM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

Surely you’re not so jaded as to find this unsurprising?

It’s not jadedness. More a question of putting too little thought into the definition of an AT category. What is in common to both? Better read this.

You might imagine they wouldn’t be so far apart, given that sets are vector spaces over the field with no elements. So then where do pointed sets feature?

By the way wasn’t it Freyd rather than Barr? Vaughan Pratt says here:

In an AT category, false implies true, i.e. there is a (necessarily unique) arrow from 0 to 1. Freyd shows that every AT category is the product of an abelian category and a topos. An AT category is an abelian category when its topos component is degenerate (the singleton category), and a topos when its abelian component is degenerate. A quick test for each is to look at 0: if $A \times 0 ~ 0$ (0 is an annihilator with respect to product) then it is a topos, while if there exists a map from 1 to 0 (also necessarily unique, and necessarily making 0 and 1 isomorphic) then it is an abelian category.

He seems very fond of this result, and talks about it elsewhere.

Posted by: David Corfield on January 16, 2009 8:36 AM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

David wrote:

That was just a joke.

More a question of putting too little thought into the definition of an AT category.

I have no idea what the definition is — except in the ultra-abstract form you just quoted, which is more like an recipe for generating a definition. What I have is some intuition for topoi and abelian categories, and I don’t normally think of them as differing merely in properties of the initial object!

In particular — getting back to the theme of this blog entry — given a subobject

$x \hookrightarrow c$

in an abelian category, we can form a ‘quotient object’ $c/x$ which is equipped with a quotient map

$c \to c/x$

This is not true in any useful way in $Set$: I described a concept of $c/x$ that works in $Set$, namely the set $c$ minus the subset $x$, but this has a map

$c/x \to c$

So, they seem very different in this way (and others)… but if I stare harder at what’s going on, I see that a certain property of the initial object is important here. Namely, in $Vect$ it’s also terminal, but not in $Set$.

You might imagine they wouldn’t be so far apart, given that sets are vector spaces over the field with no elements.

Ah, see, now you’re sounding like a jaded sophisticate.

So then where do pointed sets feature?

Now you’re seeing deeper into my secret reasons for posting my question (which nobody has really answered yet). In many ways pointed sets are closer to vector spaces, since they both have a ‘zero object’ — an object that’s both initial and terminal. But, they don’t form an abelian category, since the homsets aren’t abelian groups. So, by Freyd’s result, they must not form an AT category. So precisely what are they lacking?

By the way wasn’t it Freyd rather than Barr?

Whoops! Sorry, I somehow misread it the first time.

Posted by: John Baez on January 16, 2009 8:49 PM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

Where are we now? Pointed sets satisfy the condition of your original ‘question’, as do ordinary sets and vector spaces. Are you after (at least) a generalization of all three? Do general pointed categories satisfy the condition?

Posted by: David Corfield on January 17, 2009 7:48 PM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

I have just finished my PhD thesis and I am getting very interested in the categorification of various familiar mathematical structures. I am following n-cat cafe often and I wanted to say that I have found it very enjoyable.

Also, could someone tell me what the categorification of the symmetric group of n letters S_n is?

Posted by: ss on January 15, 2009 1:21 AM | Permalink | Reply to this

### categorified symmetric group

could someone tell me what the categorification of the symmetric group of $n$ letters $S_n$ is?

The symmetric group $S_n$ is, by definition, the automorphism group in the category of Sets of the object which is the set with $n$ elements.

So one good notion of what its categorification could be is: the automorphism 2-group of an object in a 2-category which has a decategorification functor down to sets.

For instance take the 2-category Cat of small categories (categories internal to Sets) and let the functor

$\pi_0 : Cat \to Set$

be such such that it sends any category to its set of connected components. To simplify we could restrict this to groupoids so that

$\pi_0 : Grpd \to Set$

sends each groupoid to its collection of connected component. Two objects in a groupoid are in the same connected component if and only if there is a morphism between them. So this functor is “take isomorphism classes of objects in a groupoid”. It is the decategorification functor from groupoids to sets.

Now, to find a categorification of tthe symmetric group $S_n$, which is the automorphism group of the $n$-element set $[n]$, we

a) first choose a categorification of $[n]$, i.e. a lift $\widehat{[n]}$ of the set $[n]$ through the above functor $\pi_0$ to a groupoid with $n$ conencted components;

b) then we form the automorphism 2-group $AUT_{Grpd}(\widehat{[n]})$ of this groupoid: this 2-group is the groupoid whose objects are the invertible (strictly, say) functors $g : \widehat{[n]} \to \widehat{[n]}$ and whose morphisms are the natural transformations between these.

Notice that step a) involves a choice. In fact there are infinitely many different and inequivalent choices possible. This is characteristic of categorification: since decategorification is many-to-one, categorification is one-to-many.

But whatever groupoid with $n$ connected components you choose, its automorphism 2-group (a monoidal groupoid) will be such that that its isomorphism classes form the symmetric group $S_n$. So any 2-group $AUT_{Grpd}(\widehat{[n]})$ is a categorification of $S_N = Aut([n])$.

But these infinitely many choices need not be all choices there are. You could come up with other 2-categories $D$ with a suitable functor $D \to Set$. All 2-groups of the form $AUT_D(\widehat{[n]})$ forlifts of the $n$-element set through such functors would qualify as categorifications of the symmetric group on $n$ elements.

Posted by: Urs Schreiber on January 15, 2009 10:09 AM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

One categorification of (the group algebra of) S_n is given by projective functors on an integral block of category O for sl_n.
I think this categorification is due to Bernstein and Gelfand- it has a slightly different flavor than the ones described by Urs.

A nice introduction to some representation-theoretic examples of categorification (which includes a discussion of the above example and pointers to other references) is the paper of Khovanov–Mazorchuk–Stroppel.

Posted by: Tony Licata on January 16, 2009 1:29 AM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

Thanks Urs and Tony. Just building up on this … how does the forming fractions process work ? If FinSets are the categorification of natural numbers, what is the categorification of rationals? How do we represent the object corresponding to 3/4? Could we mimic this construction to the categorification of S_n ( AUT_Grpd([n]) ) so that we can talk about things like (1 2 3)/(2 1 3) ?

Posted by: ss on January 16, 2009 5:22 AM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

Maybe the following could help? http://archive.numdam.org/ARCHIVE/SG/SG_1957__1_/SG_1957__1__A1_0/SG_1957__1__A1_0.pdf

It is the first talk of the first “Séminaire A.Grothendieck”. Take a look at “3- Sous-trucs,trucs quotients” pp 1-03,1-04.

Posted by: yael on January 20, 2009 8:41 AM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

Both David and Toby made some suggestive comments in reply to John’s question; I’d like to put down some things they suggested to me, which I think give a solution to John’s problem.

I’ll interpret the problem as finding some exactness conditions on a category $C$ that ensure the existence of the interval “quotient” John is after. Here’s one set of possibilities: suppose $C$ is a category such that

1. $C$ is finitely complete and finitely cocomplete;
2. The pushout of any mono along any morphism is a mono, and such pushout squares are also pullbacks;
3. The pullback of any epi along any morphism is an epi, and such pullback squares are also pushouts.
4. For any object $x$, the arrow $0 \to x$ is monic; if $x$ is not initial, then the arrow $x \to 1$ is epic.

Notice that conditions 1, 2, 3 taken together are self-dual. Condition 4 is not, but it’s somewhat in that vein; it reads that way partly on account of the fundamental schism between toposes and abelian categories discussed by Freyd in the notion of AT category.

(It’s true that in a topos, every arrow $0 \to x$ is monic. Of course it’s not generally true that in a topos, every arrow $x \to 1$ is epic, even if $x$ is not initial. But then again, not every topos has the sorts of objects John is looking for either, so some sort of restriction is called for. More on this below.)

If $C$ satisfies conditions 1-4, then we can prove a result (proposition 1) which is sort of a halfway house on the road to the objects John wants. Let $c$ be an object, $x \leq c$ a subobject. Define $c/x$ to be the pushout of

$1 \leftarrow x \hookrightarrow c$

(NB: not the same in general as what John was calling $c/x$ – we’ll get to that later.)

In particular, $x/x$ is terminal, and since pushouts of monos are monos, every chain of subobjects

$x \leq y \leq c$

gives rise to a chain of subobjects

$x/x \leq y/x \leq c/x$

(notice $y/x$ and $c/x$ are pointed objects, where the point in each is $x/x$).

If $x \cong 0$, then $c/x$ just adds a point to $c$: $c/0 \cong c + 1$. However, we can ignore this case: since $0 \to x$ is assumed monic for any $x$, we have that $[0, c] = Sub(c)$ anyway, making John’s problem trivial. So assume $x$ is not initial.

Proposition 1: The interval $[x, c]$ is isomorphic to the interval $[x/x, c/x]$, via the assignment $y \mapsto y/x$ for $y \in [x, c]$.

Proof: We claim the inverse map is the one which takes $z \in [x/x, c/x]$ to the pullback of the monic $z \hookrightarrow c/x$ along the pushout projection $c \to c/x$. This is a monic (denoted $z^\sim \hookrightarrow c$) that contains the subobject $x \leq c$, so $z^\sim \in [x, c]$.

Start with $y \in [x, c]$. Then the pushout

$\array{ y & \hookrightarrow & c \\ \downarrow & & \downarrow \\ y/x & \hookrightarrow & c/x, }$

being the pushout of a monic, is also a pullback by condition 2, and hence $y = (y/x)^\sim$ (as elements of $[x, c]$).

Now take $z \in [x/x, c/x]$. Since we assume $x \cong 0$ is false, the arrow $x \to 1$ is epic (condition 4), and so $c \to c/x$ is epic as well (pushouts of epis are epi). Therefore the pullback of $c \to c/x$ along $z \hookrightarrow x$, which is the map $z^\sim \to z$, is epi as well (condition 3). We have now a pullback

$\array{ x & \hookrightarrow & z^\sim \\ \downarrow & & \downarrow \\ x/x & \hookrightarrow & z }$

which is also a pushout, by condition 3. It follows that $z = z^\sim/x$ (as elements of $[x/x, c/x]$). The proof is now complete. $\Box$

To get the objects John wants, assume one more condition (condition 5):

• Every point $p: 1 \to a$ has a complement $\neg p \leq a$.

Under conditions 1-4, this amounts to existence of a square

$\array{ 0 & \to & \neg p \\ \downarrow & & \downarrow \\ 1 & \stackrel{p}{\to} & a }$

which is simultaneously a pushout and a pullback (a “dolittle square”).

Of course, this condition is trivially satisfied whenever $0 \cong 1$ (e.g., abelian categories).

Proposition 2: The complement of $x/x \to c/x$, denoted $(c/x)^{\bullet}$, has the property that

$Sub((c/x)^{\bullet}) \cong [x, c]$

Proof: Since $0 \to y$ is monic for any $y$, it suffices to prove (by proposition 1) that

$[0, (c/x)^{\bullet}] \cong [x/x, c/x] = [1, c/x]$

Put $a = c/x$. The map $[0, a^\bullet] \to [1, a]$ takes $y \in [0, a^\bullet]$ to $1 + y \in [1, a]$; in the other direction, we take $z \in [1, a]$ to $z \wedge a^\bullet \in [0, a^\bullet]$.

The proof that $(1 + y) \wedge a^\bullet = y$ uses the fact that the pushout of a mono $y \leq a$ is a dolittle square, much as in the proof of proposition 1. In the other direction, to prove $1 + (z \wedge a^\bullet) = z$, we just need to show $z^\bullet = z \wedge a^\bullet$ in order to again get a dolittle square; this equation is easy and is left to the reader. $\Box$

Remarks: conditions 1-3 hold in any AT category, such as an abelian category or a topos. However, the result that John is after cannot be expected to hold in a general topos. For example, in the topos of sheaves over the space $[0, 1]$, for instance, considered as local homeomorphisms $X \to [0, 1]$, the terminal object is $t = [0, 1]$. If we take the subobject $x = (0, 1]$, then the interval $[x, t]$ consists of two elements. But there is no sheaf over $[0, 1]$ with just two subsheaves! So what John is asking for cannot work in cases like this.

Generally speaking, it seems to me that the existence of subobjects strictly between 0 and 1 poses some awkwardness for the kind of thing John wants to consider, so my condition 4 is a kind of “two-valuedness” condition which precludes that. In a topos, two-valuedness implies Boolean [do I hear Toby piping in here? I’m assuming the metalogic is classical, in case there’s any doubt], so condition 5 is not that much of a stretch really.

I’d have to check, but I’m guessing that all these conditions are satisfied in the categories of interest mentioned by others: sets and modules of course, but I’m also guessing pointed sets. I’m not completely sold on the aesthetics of these conditions, but they seem at least to be a reasonable first step toward something more satisfactory.

Posted by: Todd Trimble on January 27, 2009 3:59 AM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

WOW!

I was wondering why you hadn’t said anything. Little did I know what you were cooking up.

It’ll take me a while to recover and post a more sensible reply. But: thanks!

If you haven’t looked at it yet, you might really enjoy looking at Bill Schmitt’s paper, especially pages 3–4, leading up to Theorem 3.1, which builds a coalgebra from a family of posets satisfying some conditions. Your result should give lots of examples. (Besides the conditions you list, we’ll also need to work with objects that have finitely many subobjects.)

Since you’re assuming your category has finite products, this coalgebra should often be a bialgebra — and in fact a Hopf algebra, thanks to Theorem 4.1.

Posted by: John Baez on January 27, 2009 5:43 AM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

I’d better make a few corrections:

1. The first word of proposition 2 should be ‘A’, not ‘The’.
2. The first line of the second paragraph of the proof of proposition 2 should have $y \leq a^\bullet$, not $y \leq a$.
3. In the last line of the same proof, there are the infamous words, “it is easy to see”. In particular, the equation now looks suspect to me due to the possible nonuniqueness of complements.

A propos of 3., my back of the envelope calculations had that we need only show $z^\bullet \leq a^\bullet = \neg p$. (More pedantically, that $i z^\bullet \leq \neg p$, where $i: z \to a$ is the given monic.) And I jumped the gun here by assuming that was equivalent to the (true) statement $i z^\bullet \wedge p = 0$ as subobjects of $a$. That is, in imagining that equivalence, I had unconsciously slipped into thinking we had $\neg p = p \Rightarrow 0$, a la Heyting algebras, whereas we’re not making any such assumption about our subobject posets.

Well, here I am just rattling on. Suffice it to say that what I was cooking up needs to cook a bit longer. Hopefully I or someone else will see a fix.

Posted by: Todd Trimble on January 27, 2009 8:46 AM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

Hi (again) John. I’ve had in the past 30 minutes or so a serious “oh duh!” moment related to my previous two comments – but in a good way.

All we need to do is assume, on top of the five conditions already given in the first of those comments, that all the posets $Sub(c)$ are modular lattices. For then there is this diamond isomorphism theorem that gives us exactly what we need in the proof of proposition 2: an isomorphism between intervals

$[0, a^\bullet] \cong [1, a]$

where $a^\bullet \leq a$ is a complement of $1 \leq a$.

(Hm, I hope this is followable, and sorry for the earlier mess.)

The modularity condition seems to be a very reasonable condition to assume [perhaps the most reasonable condition of all!], because it holds for abelian categories as well as toposes and other nice categories (e.g., AT categories, pointed sets, …). And I’m guessing it fits in well with the framework in Bill Schmitt’s paper – Rota was a big champion of modular lattices, and I get the impression that Schmitt is advancing Rota’s work.

So good. I can relax now, I think.

Posted by: Todd Trimble on January 27, 2009 5:23 PM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

That looks neat. Thanks for posting the references.

Posted by: Eric on January 27, 2009 6:24 PM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

Eric wrote:

That # looks neat. Thanks for posting the references.

Just a message to Eric, to amplify this point: indeed, if the poset in question is that of a globally hyperbolic Lorentzian spacetime (with $x \to y$ iff $x$ is in the past of $y$ ) then these diamonds

$\array{ && x \vee y \\ & \nearrow && \nwarrow \\ x &&&& y \\ & \nwarrow && \nearrow \\ && x \wedge y }$

are indeed the familiar causal double cones.

The “meet$x \wedge y$ is the spacetime point which is universal with the property of being in the past of both $x$ and $y$ (every other point in the past of both is also in the past of $x \wedge y$) and the “join$x \vee y$ is the spacetime point universal with the property of being in the future of both $x$ and $y$: every other point which is in the future of $x$ and $y$ is also in the future of $x \vee y$.

Posted by: Urs Schreiber on January 27, 2009 7:26 PM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

Super neat :)

Thanks Urs. I’ve got some homework to do before I understand everything, but it does seem very… well… neat :)

Posted by: Eric on January 27, 2009 7:37 PM | Permalink | Reply to this

### Re: Hopf Algebras from Posets

I’ve got some homework to do before I understand everything

Just go step-by-step through the definition of product and coproduct and check that the “product” of two spacetime points in the globally hyperbolic Lorentzian manifold’s causal poset is the “universal” point in their past, and the coproduct the “universal” point in their future.

Posted by: Urs Schreiber on January 27, 2009 8:34 PM | Permalink | Reply to this

Post a New Comment