## January 14, 2010

### F and the Shibboleth

#### Posted by Tom Leinster

Marcelo Fiore and I have just sent in what I hope is the final version of our paper An abstract characterization of Thompson’s group $F$, to be published in Semigroup Forum.

When we wrote the paper I thought it was all about $F$, and in a sense it is. But through a long and difficult refereeing process, involving a couple of other journals, I came to realize that in social terms it was more about a shibboleth. I’ll explain each of these things, $F$ and the shibboleth, in turn.

To explain $F$, I’ll begin by quoting our paper.

In the 1960s Richard Thompson discovered three groups, now called $F$, $T$ and $V$, with remarkable properties. The group $F$, in particular, is one of those mathematical objects that appears in many diverse contexts and has been rediscovered repeatedly.

Informally, $F$ is the group of all automorphisms of the interval $[0, 1]$if all you knew about $[0, 1]$ was that it was isomorphic to $[0, 2]$.

Here $[0, 2]$ should be viewed as two copies of $[0, 1]$ stuck end-to-end (sometimes written $[0, 1] \vee [0, 1]$). So, we know that there’s an isomorphism $\alpha: [0, 2] \to [0, 1],$ and that’s all we know about $[0, 1]$. From $\alpha$, we can build some nontrivial automorphisms of $[0, 1]$, that is, some nontrivial elements of $F$. Here’s one:

It does no harm to assume that $\alpha$ is division by $2$, in which case we can redraw this element as a graph:

Another way to redraw the first picture is by thinning it out, so that each wedge-shaped $\alpha$ or $\alpha^{-1}$ becomes a skinny Y-shape:

This is a rather simple, combinatorial way of representing an element of the group — but if you work with these pictures, it’s not so obvious what the group operation is. Points if you can figure it out, and bonus points if you can see what it’s got to do with the bicategory of spans.

Aside  What about Thompson’s other groups, $T$ and $V$? Well, I more or less said that $F$ is the automorphism group of $[0, 1]$ considered as a self-similar space — by which I mean, equipped with the obvious isomorphism $[0, 1] \vee [0, 1] \to [0, 1]$. (As a mere set, the interval has a massive automorphism group; as a topological space or ordered set, its automorphism group is smaller; as a self-similar space, it’s smaller still.) In the same sense, $V$ is the automorphism group of the Cantor set, and $T$ the automorphism group of the circle, both considered as self-similar spaces in a natural way. I’d love to make these statements precise, so that $F$, $T$ and $V$ were literally automorphism groups of these three objects in a category of self-similar spaces; but at present, I can’t.

Here’s our theorem. Given a monoidal category $\mathbf{M}$, an idempotent object in $\mathbf{M}$ is an object $M$ together with an isomorphism $\mu: M \otimes M \to M$. For example, if $\mathbf{M}$ is the monoidal category of sets with cartesian product, an idempotent object is a set $M$ equipped with a bijection $M \times M \to M$: a Jónsson–Tarski algebra.

Theorem  Let $\mathbf{A}$ be the monoidal category freely generated by an idempotent object $(A, \alpha)$. Then $Aut_{\mathbf{A}} (A) \cong F$.

For example, the composite map $A \stackrel{\alpha^{-1}}{\to} A \otimes A \stackrel{\alpha^{-1} \otimes id}{\to} A \otimes A \otimes A \stackrel{id \otimes \alpha}{\to} A \otimes A \stackrel{\alpha^{-1}}{\to} A$ is an automorphism of $A$ in $\mathbf{A}$, and represents the same element of $F$ as shown in the pictures above.

All the objects of $\mathbf{A}$ are isomorphic except for the unit object $I$, which doesn’t really do much. We might as well have used the free ‘semigroupal category’ (monoidal category without unit) instead. It makes no difference, but since monoidal categories are what people usually think about, that’s what we used. Perhaps we should have submitted our paper to Semigroup Forum’s great rival, Monoid Forum.

Aside  If you’re an expert on Thompson’s groups, you may at this point be snorting and muttering to yourself:

But this has been known since Thompson and Higman!

Or, you may be snorting and muttering to yourself:

But this has been known since Freyd and Heller!

And indeed, there are old results of Thompson, Higman, and Freyd and Heller that bear a tantalizing resemblance to the theorem above. But they are not the same! And, more importantly, no one has yet managed to find a simple or direct deduction of our result from one of these older ones, or vice versa. In other words, no one has succeeded in taking advantage of the tantalizing resemblances. Take that as a challenge!

I hope that the theorem comes as no surprise, given the earlier (informal) description of $F$. At least, I hope it wasn’t surprising if you’re comfortable with phrases such as ‘the monoidal category freely generated by an idempotent object’. And this brings us to the shibboleth.

Someone — John Baez, I think — taught me how to spot a fake knot theorist. (You can never be too careful.) Simply ask them to draw a trefoil. If they hesitate in the slightest, they’re faking it. Actually, this will only catch really bad fakes, but in some weak sense it’s a shibboleth, a mark of identity, or at the very least, something that any professional can do.

The point I want to make is that for category theory, the ability to throw around phrases of the form

the free such-and-such category containing a such-and-such

is something like the ability to draw a trefoil without hesitation. Of course, this comparison isn’t entirely serious: one of these skills is much more meaningful than the other. But there is something serious here. While there are plenty of people who are fluent in quite sophisticated category- and topos-speak, it seems to me that outside the smallish group for whom category theory is a central research interest, not many people are comfortable with phrases of this form. And that’s a shame. Maybe there was a time when only hard-core algebraists understood phrases of the form

the group freely generated by such-and-such subject to such-and-such.

If so, we’re now in the same social situation, but categorified.

Let me explain what phrases of this kind mean. I’ll use an example:

the free monoidal category containing a monoid.

Another way to say it would be:

the monoidal category freely generated by a monoid.

When you first hear a phrase like this, you might respond ‘the monoidal category freely generated by which monoid?’ But that’s a kind of grammatical misunderstanding.

To understand this phrase, first you have to know (of course) what a monoidal category is. I’ll assume this. For my purposes, monoidal categories will be strict. Then, crucially, you have to know that it makes sense to talk about monoids in a monoidal category. I’ll assume this too.

Now, there’s an informal description of the monoidal category $\mathbf{A} = (\mathbf{A}, \otimes, I)$ freely generated by a monoid. It contains a monoid, whose underlying object I’ll call $A$ and whose multiplication and unit I’ll call $\mu: A \otimes A \to A,             \eta: I \to A.$ Since $\mathbf{A}$ is a monoidal category, it has objects $A^{\otimes n}$ for all $n \geq 0$ (with $A^{\otimes 0} = I$). There’s nothing forcing $\mathbf{A}$ to have any other objects, and since it’s supposed to be ‘free’, it doesn’t have any other objects. Similarly, there’s nothing forcing any two of these objects $I, A, A^{\otimes 2}, A^{\otimes 3}, \ldots$ to be equal, and it’s ‘free’, so they’re not equal. The maps in $\mathbf{A}$ are built up from $\mu$, $\eta$ and identities using composition and $\otimes$; they only satisfy whatever equations they have to satisfy in order for $\mathbf{A}$ to be a monoidal category and $(A, \mu, \eta)$ to be a monoid in it.

(In fact, there’s a simple, explicit description of $\mathbf{A}$: the maps $A^{\otimes m} \to A^{\otimes n}$ correspond to order-preserving maps $\{ 1, \ldots, m\} \to \{1, \ldots, n\}$. Hence $\mathbf{A}$ is equivalent to the category of finite totally ordered sets.)

Formally, the monoidal category freely generated by a monoid can be characterized as follows. The characterization relies on one more piece of knowledge: that given any monoidal functor $F: \mathbf{M} \to \mathbf{N}$ and any monoid $(M, \mu, \eta)$ in $\mathbf{M}$, you get a monoid $(FM, F\mu, F\eta)$ in $\mathbf{N}$. (Monoidal functors, like monoidal categories, are taken to be strict here.)

Definition  A monoidal category freely generated by a monoid is a monoidal category $\mathbf{A}$ together with a monoid $(A, \mu, \eta)$ in $\mathbf{A}$, satisfying the following universal property:

for any monoidal category $\mathbf{M}$ and monoid $(M, \mu', \eta')$ in $\mathbf{M}$, there is a unique monoidal functor $F: \mathbf{A} \to \mathbf{M}$ such that $(FA, F\mu, F\eta) = (M, \mu', \eta')$.

The universal property determines $\mathbf{A}$ and $(A, \mu, \eta)$ uniquely, up to isomorphism.

Both the informal and formal descriptions are supposed to remind you of presentations of groups, modules etc. Informally, the group presented by a bunch of generators and relations is obtained by starting with the generators, forming all the terms that you have to form in order for it to be a group, then imposing the relations. Formally, this group is characterized by a universal property rather similar to the one above. What we’ve done is categorification:

• sets-with-structure have become categories-with-structure
• structure-preserving functions have become structure-preserving functors
• generating elements have become generating objects and arrows

etc.

Once you’ve digested this idea, a whole lot of powerful mathematical statements become easily accessible. For example:

• The braided monoidal category freely generated by an object is the sequence $(B_n)_{n \geq 0}$ of Artin braid groups. (More precisely: this category has objects $I, A, A^{\otimes 2}, \ldots$, the automorphism group of $A^{\otimes n}$ is $B_n$, and there are no other morphisms.)
• The free category with finite products containing a group, ring, etc., is the Lawvere theory of groups, rings, etc.
• The free topos containing a group, ring, etc., is the classifying topos for groups, rings, etc. (‘Free topos’ has to be understood with respect to the inverse image part of geometric morphisms, as explained here.)
• The free symmetric monoidal category on a commutative Frobenius algebra is the category of 1-dimensional smooth oriented manifolds and diffeomorphism classes of 2-dimensional cobordisms. This is a strong form of the classification theorem for 2-dimensional TQFTs, as explained nicely in Joachim Kock’s book.
• The free monoidal category containing an object $A$ and an isomorphism $A \otimes A \to A$ is equivalent to the groupoid $1 + F$, where $1$ is the terminal groupoid, $+$ is disjoint union of groupoids, and $F$ is Thompson’s group.

The joy of it is that you can use these descriptions as definitions. Need to tell someone what ‘the Lawvere theory of groups’ is? Just tell them it’s the free finite-product category containing a group. Need to tell them what Thompson’s group $F$ is? Just tell them to form the free monoidal category on an object $A$ and an isomorphism $A \otimes A \to A$; then $F$ is the automorphism group of $A$.

Posted at January 14, 2010 1:29 AM UTC

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

### Re: F and the Shibboleth

A very nice post! Let me add a few to your list of examples. (I’m sure you know these, but this is such an important concept that it’s worth going on about.)

• The free symmetric monoidal $(\infty,n)$-category containing a dualizable object is the (∞,n)-category of cobordisms. This is, of course, Lurie’s formulation of the cobordism hypothesis, which seems to have attracted a fair amount of interest outside pure category theory recently.

• We can talk about free topoi relative to logical functors, as well as relative to inverse image functors. Only geometric theories generate free topoi in the inverse-image sense, but arbitrary theories in “higher-order type theory” generate free topoi in the logical sense. (This is the more common use of the phrase “free topos,” unqualified; the other sort are usually called “classifying toposes”.)

• Probably the first of these that many people encounter is that the augmented simplex category is the free monoidal category containing a monoid. This one is in CWM.

This idea is also quite closely connected to the “doctrines of algebraic geometry” stuff that Jim Dolan has been talking about. When you talk about the free X containing a Y, you’re working in the “doctrine” of X’s, in which you can formulate the “theory” of Y’s. The general dogma of doctrines then says that such a “theory” that can be interpreted in X’s can also be viewed as an X, namely the free X generated by a Y.

Finally, in the language I was using back here, you can often construct the free X containing a Y by starting with a suitable kind of operad (perhaps a “colored” one, i.e. a multicategory) and applying the left adjoint to the forgetful functor from “X-structured categories” to “X-multicategories.” This is sometimes convenient because the operad is often easier to describe explicitly than the free category it generates.

Posted by: Mike Shulman on January 14, 2010 3:54 AM | Permalink | PGP Sig | Reply to this

### Re: F and the Shibboleth

Thanks!

I’m sure you know these

Your faith is misplaced (or you’re very polite). In particular, I didn’t know what you wrote about higher-order type theories. Nor had it occurred to me that one might compare and contrast “free toposes” when taken with respect to logical functors on the one hand, and geometric morphisms (backwards) on the other. That’s a nice fact about theories.

Posted by: Tom Leinster on January 15, 2010 12:47 AM | Permalink | Reply to this

### Re: F and the Shibboleth

One of my (more obviously futile) obsessions has been the proper way to use words — when I say futile here, I mean that “shall” and “will” fit together with “should” and “would”, respectively, and none of these quite means “ought”, whatever rhyming usage to the contrary you may find in such delightful films as Jurasic Park. So, clearly, when I say “proper”, I’m not primarily interested in whether any living anglophone will understand me, but in whether my usage is consistent and optimally employs available distinctions. (And again, I don’t claim to really be good at that, either, but never mind…)

So when you mention that the uninitiated are apt to mis-read “free monoidal category generated by a monoid”, I really do think that it might have been clearer to say “free monoidful monoidal category”, even if “monoidful” hasn’t been issued by the mint, just yet.

Posted by: Jesse McKeown on January 14, 2010 5:25 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Jim Dolan would call it the ‘walking monoid’, where we take it for granted that a monoid wants to live in a monoidal category.

I guess I should tell the joke that explains this terminology … Aaron Lauda retold it here:

In the previous section we defined the notion of an adjunction in a 2-category. In this section we will study a very special adjunction — the ‘walking adjunction’. Before defining the walking adjunction we feel obliged to motivate this seemingly strange terminology. Imagine you are sitting in a small table in the back of a crowded pub enjoying a beer with a close friend, when in walks a fellow with enormous bushy eyebrows. His eyebrows are in fact so large that it seems his entire body serves no other purpose than to provide a frame for these enormous eyebrows to perch on. In that case, you might be tempted to comment to your friend: “Look, there goes the walking pair of eyebrows”. In the same way, the walking adjunction is the minimal amount of structure needed in order to have an adjunction; it is the 2-category freely generated by an adjunction. The 2-category is merely the frame upon which the adjunction ‘perches’.

Posted by: John Baez on January 14, 2010 4:58 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Lovely post, Tom, once again.

While most mathematicians today are happy to talk about, say, the free abelian group generated by two elements x and y, it sometimes seems a bit fast and loose with students who are seeing such things for the first time. What exactly are x and y, they sometimes ask. Just elements. Uh, which elements? Or we say they’re formal symbols. What exactly is a formal symbol?

A slightly more satisfying approach, to me, is to talk about the free abelian group on a set $S$, rather than on formal symbols. You can do this constructively by defining it to be the set of functions $S\to \mathbf{Z}$ which are almost everywhere $0$, or you can just talk about the universal property. Then you can say, “When I say ‘Let F be the free abelian group on x and y’, I mean ‘Let F be the free abelian group on a set S of two elements, which we will denote x and y.’” This change seems parallel to expressing universal properties of objects as adjoint functors in that we make the free construction a functor, with a specified domain category, but I find it slightly interesting that it offers some improvement even at the most basic level of comprehending the language.

Anyway, my point should be clear. As you explained, phrases like “free abelian group on two elements x and y” are shibboleths. But the reason they’re shibboleths is that, one, they could be made clearer and, two, the insiders already learned how to do that. So, could you give similarly improved expressions of some of the 2-free constructions you give? (It would probably be a not too hard exercise, not to mention a good one for building up my 2-muscles, but maybe it would also good to have its answer written down here.)

Posted by: James on January 14, 2010 8:04 AM | Permalink | Reply to this

### Re: F and the Shibboleth

This is a nice exercise; the key is to take the word ‘set’ in your example of the free group on a set, and replace it by ‘category’.

Posted by: John Baez on January 14, 2010 5:01 PM | Permalink | Reply to this

### Re: F and the Shibboleth

It’s an interesting question, James (and thanks). I sometimes feel a sense of discomfort when I find myself uttering the words “formal symbol”.

I’m not sure I think the question is quite fairly posed. If it was a matter of rephrasing descriptions such as

the free monoidal category on objects $x, y$ and an arrow $x \to y$

then yes, it would be analogous to your abelian group example. But your challenge, I take it, would include rephrasing descriptions such as

the free monoidal category on an object $x$ and an isomorphism $x \otimes x \to x$.

Here the generating data uses the monoidal structure, so it’s analogous to something like

the free abelian group on an element $x$ subject to $5x = 0$

Now, how would you rephrase that last one to avoid mentioning an ‘element’ or ‘generator’ or ‘formal symbol’ $x$?

(I can think of one answer, involving exact sequences or equalizers. But maybe you have a good pedagogical solution that doesn’t use such advanced technology.)

Posted by: Tom Leinster on January 15, 2010 3:00 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Tom said, “Here the generating data uses the monoidal structure, so it’s analogous to something like the free abelian group on an element $x$ subject to $5x=0$.”

Oh, I see. A “formal monoid” secretly has relations built into it, unlike a formal variable! Let me try again, then. Suppose we define a presentation (of an abelian group, say) to be a set $S$ together with a set $R$ and two maps $R\rightrightarrows F(S)$, where $F(S)$ is the free object generated by $S$. Then we can define the object freely generated by $S$ subject to the relations $R$ to be the coequalizer of the two induced maps $F(R)\rightrightarrows F(S)$. Could we do something similar in your examples?

How is this? Let $F$ be the left 2-adjoint of the forgetful 2-functor from monoidal categories to categories. (Presumably this makes sense and exists.) Then take $S$ to be a (or “the”) category with two objects and one non-identity map, denoted $x\to y$, take $R$ to be a (or “the”) category with one object, denoted $z$, and one morphism $1_z$, and take the two functors $R\to F(S)$ given by $z\mapsto x$ and $z\mapsto y\otimes y$. Then the monoidal category freely generated by “one formal monoid” would be the 2-coequalizer in the 2-category of monoidal categories of the induced functors $F(R)\rightrightarrows F(S)$. (Again, presumably this makes sense and exists).

Assuming this is correct, it answers my question (however confused it may have been) to my satisfaction, in that the mysterious “formal monoid” doesn’t appear. Or rather, it appears as a member of a class of actual mathematical objects: two functors $R\rightrightarrows F(S)$, where $R$ and $S$ are categories, 2-uniquely defined, having the properties above. Can I say the formal monoid now appears semantically rather than syntactically? Whatever the case, I’m now happy to talk about it!

Posted by: James on January 15, 2010 7:22 AM | Permalink | Reply to this

### Re: F and the Shibboleth

I realized soon after I posted this that it’s unlikely to be right because I forgot to use the associativity and unit axioms of monoids! I think this is kind of independent of the concerns in my original question, but it would still be nice to see a proper solution.

Posted by: James on January 16, 2010 12:58 AM | Permalink | Reply to this

### Re: F and the Shibboleth

If you take the description in your paragraph starting ‘How is this?’ and add the condition that the map $x \to y$ is an isomorphism, then I think you get the category that I called A — the one ‘freely generated by an object $A$ and an isomorphism $A \otimes A \to A$’.

As for describing the free monoidal category on a monoid: as you point out, it seems trickier. One has to frame the associativity and unit axioms. At present I can’t see how to do this. Can someone else?

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

### Re: F and the Shibboleth

Oh! Good point! Thanks!

Posted by: James on January 20, 2010 3:54 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Very nice. Some assorted questions:

1. Can $F$ be described as having something to do with the real interval qua the terminal coalgebra we know and love?
2. For $T$, how do you characterise the circle as self-similar? Is it a terminal object?
3. When you form the free set with structure on one element, you get extra structure for free, e.g., $\mathbb{Z}$ is a ring. What happens with free structured categories on one object? Hmm, I guess there’s a multiplication in braids where you replace each strand of one braid by a copy of another given braid. Does $F$ have something ring-like going on?
Posted by: David Corfield on January 14, 2010 10:36 AM | Permalink | Reply to this

### Re: F and the Shibboleth

F is naturally more than a group; there is a morphism FxF → F coming from the monoidal structure.

Posted by: James Griffin on January 14, 2010 2:45 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Hi James! Yes indeed, $F$ is a whooole lot more than just a group. For starters, there’s that homomorphism $F \times F \to F$ that you mention. Actually, I don’t know whether the one I’m about to describe is the one you had in mind — it wouldn’t amaze me if there were several interesting homomorphisms of this form.

Anyway, here’s what I guess you’re thinking of. I’ll continue with the notation of the post, so that $F$ is the automorphism group of the generating object $A$ of that free monoidal category A. Given any two automorphisms $f, g: A \to A$ you can define a new automorphism $f \star g: A \to A$ as the composite $A \stackrel{\alpha}{\to} A \otimes A \stackrel{f \otimes g}{\to} A \otimes A \stackrel{\alpha^{-1}}{\to} A.$ This defines a homomorphism $\star: F \times F \to F$. (But don’t get too excited, reader: as a binary operation, it’s not associative.)

If we view elements of $F$ as functions from $[0, 1]$ to $[0, 1]$ (satisfying certain axioms listed in the paper), and draw their graphs as above, then the $\star$ operation takes two graphs and sticks them together. For example, if $f$ is

and $g$ is

then $f \star g$ is

I’ll restrain myself, for the moment, from describing some of the other structure that $F$ carries. But this group has so much special about it that entire conferences are held on it.

Posted by: Tom Leinster on January 14, 2010 11:56 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Yes, that was the structure that I was drawing on. Although if I had thought a little longer I wouldn’t have written that there was a map FxF → F at all. I would have said that there was a map Aut(A)x Aut(A)→ Aut(AxA) and then remarked that there’s a given isomorphism Aut(AxA) → Aut(A).

You say that the composite multiplication is not associative, but ofcourse that’s only because we’ve changed the basepoint from XxX to X. I think what we should be saying is that F is a monoid in groupoids (at least up to homotopy). Using our given isomorphism just obscures this (although that’s not to say that the multiplication given isn’t worth study).

Viewing it in this way seems to give a very neat way of computing the homology of the group, no wait… the homology of the nerve of the category.

Posted by: James Griffin on January 15, 2010 11:13 AM | Permalink | Reply to this

### Re: F and the Shibboleth

I think what we should be saying is that $F$ is a monoid in groupoids (at least up to homotopy)

I’m having trouble seeing this… what do you mean?

Posted by: Tom Leinster on January 19, 2010 2:55 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Well if you work in the category of algebras in topological spaces you can start with the free algebra on a point x. Now freely adjoin an interval I connecting x and x^2. So this is now an algebra with points x^n, lines x^n.I.x^m, squares x^n.I.x^m.I.x^l, etc. all glued together in the obvious way.

Now I think that I’m right in saying that this is the classifying space of the free monoidal category containing an idempotent element as you described above. The connected component containing x has fundamental group F, but I’m not sure whether it’s aspherical or not.

It’s the fundamental groupoid of this component which is the “monoid in [the category of] groupoids” that I meant in the previous comment. Of course that single component doesn’t possess a unit, so does that make it in fact a semigroup? Has anyone thought about which groups occur as fundamental groups of connected semigroups? The answer should involve the group F.

Posted by: James Griffin on January 19, 2010 2:47 PM | Permalink | Reply to this

### Re: F and the Shibboleth

points x^n, lines x^n.I.x^m, squares x^n.I.x^m.I.x^l, etc. all glued together in the obvious way.

squares? why product rather than concantenation?

Posted by: jim stasheff on January 20, 2010 3:55 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Hmm, I thought I’d replied to you a day or two ago, James G, but it looks like I never hit “post”. Anyway:

Thanks for explaining. Did you see the comments on classifying spaces and ‘Squier complexes’ on page 3 of the paper?

As to whether anyone has thought about which groups occur as fundamental groups of connected semigroups, I’m pretty sure the answer is yes, and once upon a time I might have been able to give you a reference or two, but that knowledge no longer resides in my consciousness. I guess the paper of Guba and Sapir mentioned on p.3 would be a place to start.

Posted by: Tom Leinster on January 21, 2010 6:30 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Oh and I should have thanked you for the interpretation in terms of functions [0,1] → [0,1] and the pretty pictures!

Posted by: James Griffin on January 15, 2010 11:22 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Does this representation of $F$ as monotonically increasing functions whose graphs are piecewise linear with slope a power of 2, and coordinates of points of discontinuous gradient at dyadic rationals, suggest that the initial algebra for Freyd’s construction, i.e., dyadic rationals in $[0, 1]$, is around?

I guess elements of $F$ can approximate the set of monotonic continuous functions. How could you ‘complete’ the set of piecewise linear ones in this set up?

Posted by: David Corfield on January 15, 2010 12:49 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Jim Stasheff just pointed out to me by email that this homomorphism $\star: F \times F \to F$ had better not have a unit… because if it did then $F$ would be abelian, which it certainly isn’t.

This is because of the Eckmann–Hilton argument, which, in some form, states the following. Suppose you have two unital binary operations on a set, say $\cdot$ and $\star$, satisfying the equation $(x_1 \cdot y_1) \star (x_2 \cdot y_2) = (x_1 \star x_2) \cdot (y_1 \star y_2).$ Then $\cdot$ and $\star$ are equal and commutative (and associative, and their units are the same). In our case, where the set is $F$ and $\cdot$ is the group multiplication, the displayed equation says that $\star$ is a homomorphism.

However, from the pictures of graphs it should be clear that $\star$ doesn’t have a unit. So we’re safe. Better still, we come out of this with a nice counterexample demonstrating that that hypothesis in the Eckmann–Hilton argument can’t be dropped.

Posted by: Tom Leinster on January 15, 2010 6:35 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Better still, we come out of this with a nice counterexample demonstrating that that hypothesis in the Eckmann–Hilton argument can’t be dropped.

But there is no shortage of simple counterexamples, is there? I would think that taking any noncommutative monoid and freely adding a second non-unital product yields a counterexample.

Posted by: Urs Schreiber on January 16, 2010 9:46 PM | Permalink | Reply to this

### Re: F and the Shibboleth

I would think that taking any noncommutative monoid and freely adding a second non-unital product yields a counterexample [to the validity of the Eckmann–Hilton argument when applied to non-unital products].

Sure, but how do you prove that? You might think that freely adding a second unital product would yield a counterexample too … but it doesn't, since lots of things collapse and we end up with a simple commutative monoid, by the Eckmann–Hilton argument. (Note: You actually want to freely add a second product that respects the first product.)

There's no general method to actually decide these things, so it's much easier to have an example that you understand completely.

Posted by: Toby Bartels on January 17, 2010 1:04 AM | Permalink | Reply to this

### Re: F and the Shibboleth

so it’s much easier to have an example that you understand completely.

All right: take any unital noncommutative monoid $A$ and equip it with a second operation $\cdot_2 : A\times A \to A$ defined simply by $a_1 \cdot_2 a_2 = 1$ for all $a_1, a_2 \in A$.

Posted by: Urs Schreiber on January 17, 2010 5:13 PM | Permalink | Reply to this

### Re: F and the Shibboleth

OK, now I agree with you.

In fact, let's start with an arbitrary unital magma structure as $\cdot_1$ and then add $\cdot_2$ as you gave ($a \cdot_2 b \coloneqq 1_1$). Then we have the strongest insufficient hypotheses on $\cdot_2$ (which is associative and even commutative), yet we can draw no conclusions (neither associativity nor commutativity, much less equality with $\cdot_2$) about $\cdot_1$. Then at our option, add additional hypotheses to $\cdot_1$ (associativity and/or commutativity) and observe (rather thrivially) that there are still no further conclusions to draw about $\cdot_1$.

So it is a very strong counterexample, and very easy to understand too.

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

### Re: F and the Shibboleth

Ah yes, Urs (and Toby), that’s a much easier counterexample than the Thompson group one.

Posted by: Tom Leinster on January 17, 2010 9:34 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Thanks, David.

1. Can $F$ be described as having something to do with the real interval qua the terminal coalgebra we know and love?

That’s what I was trying to hint at in my first “Aside”. I have a picture in my head something like this: there’s some good category of self-similar objects; one such object is the real interval with the Freyd self-similarity structure that you mention; and in this category, the automorphism group of this object is $F$.

I’ve been looking at this in the context of my work on self-similarity. In it, self-similar objects are characterized as terminal coalgebras.

But so far, I haven’t managed to turn this mental picture of a good category of self-similar objects into reality.

2. For $T$, how do you characterise the circle as self-similar? Is it a terminal object?

The long answer is “see Example 2.2 of this”.

Here’s the short answer. The circle is two copies of $[0, 1]$ with the $0$ of each copy identified with the $1$ of the other copy; and $[0, 1]$ is described in the way that you know. This idea can be formalized to give a characterization of the circle.

Indeed, consider the category C in which an object consists of

• a bipointed set $X_1$, that is, a set with two distinct basepoints, $x_-$ and $x_+$
• a set $X_2$
• a map $\rho: X_1 \to X_2$, injective except that $\rho(x_-) = \rho(x_+)$.

Example: take $X_1 = [0, 1]$ with basepoints $0$ and $1$, take $X_2 = S^1$, and take $\rho$ to be the usual quotient map. Next, there’s an endofunctor $G$ of C. Given $X \in$C as above, $Y = G(X)$ is given by:

• the bipointed set $Y_1$ is two copies of $X_1$ stuck end to end
• the set $Y_2$ is obtained from the disjoint union of two copies of $X_1$ by identifying the $x_-$ of each copy with the $x_+$ of the other
• the map $Y_1 \to Y_2$ is the evident quotient map.

If we take our example $X$ above, then $G(X) = Y$ is isomorphic to $X$. This isomorphism makes $X$ the terminal $G$-coalgebra. Thus, we’ve characterized the circle via terminal coalgebras.

(We’ve only characterized it as a set, but there’s a topological version too.)

As for question 3: interesting…

Posted by: Tom Leinster on January 15, 2010 12:34 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Thanks. Is it hard then to use your characterisation of $X$ as terminal $G$-coalgebra as a means to characterise group $T$?

Posted by: David Corfield on January 15, 2010 9:27 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Well, I explained at the beginning of the comment that you were replying to that I haven’t managed to use the characterization of $[0, 1]$ as a terminal coalgebra as a means to characterize the group $F$ (despite trying). The case of $S^1$ and $T$ seems at least as hard, and I haven’t done that either.

But maybe you were thinking more along the lines of changing ‘monoidal category’ to something else?

E.g. if you take the free symmetric monoidal category containing an object $A$ and an isomorphism $A \otimes A \to A$, then the automorphism group of $A$ is Thompson’s group $V$. The same is true if you replace ‘symmetric monoidal’ by ‘finite product’. If you replace it by ‘braided monoidal’, you get a group called ‘braided $V$’, which I think was first studied by Matt Brin.

Marcelo and I tried to find a monoidal-like structure that would give us $T$. Our discussion touched on things like the cyclic category and traces. But we didn’t succeed.

Posted by: Tom Leinster on January 17, 2010 9:44 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Notice how a Shibboleth is used to identify the _enemy_!
cf. Which way went the winged whiporwill to identify ?
or Lollapalooza to identify ?

Posted by: jim stasheff on January 14, 2010 2:26 PM | Permalink | Reply to this

### Re: F and the Shibboleth

I wonder if with your characterisation of $F$ any of the questions listed in Thompson’s Group at 40 Years become more approachable.

Posted by: David Corfield on January 14, 2010 2:43 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Is this a list of (yet) open problems? E.g. is it an open question if F is amenable?

Posted by: Tim vB on January 14, 2010 3:26 PM | Permalink | Reply to this

### Re: F and the Shibboleth

To answer my own question: Wikipedia has a reference to a paper that claims that F is amenable. So, not all questions posed at “Thompson’s Group at 40 Years” are still open

Posted by: Tim vB on January 14, 2010 4:06 PM | Permalink | Reply to this

### Re: F and the Shibboleth

It seems that the claim may (or may not) be dubious: there is also an apparently plausible paper on the ArXiv claiming to have proven the opposite. See this for a discussion of the two papers.

### Re: F and the Shibboleth

Thanks for the link! So, without knowing, I stumbled across a question that was posed over 40 years ago, and where two papers were published last year with opposite claims, and the jury is still out?

That looks like a good start to see if the new point of view is of help.

Posted by: Tim vB on January 14, 2010 6:19 PM | Permalink | Reply to this

### Re: F and the Shibboleth

The link that Wadsley, S gave is a good one: it’s a blog post by Danny Calegari on the is it/isn’t it debate over the amenability of F. If you skip down to the bottom, you’ll find him saying that Shavgulidze conceded a gap in his proof of amenability, and hasn’t been able to fix it.

Meanwhile, there’s Akhmedov’s proof of non-amenability, about which Calegari says “I do not think it has received nearly so much scrutiny, so I wouldn’t say there is any kind of consensus about it”. He doesn’t say why it hasn’t received so much scrutiny.

Posted by: Tom Leinster on January 15, 2010 1:21 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Well, without wishing to pre-empt DC’s own thoughts on who has looked at Akhmedov’s “proof” and how closely they’ve looked at it: one of the few links I could find when Googling for information back in mid-to-late 2009 was this comment (on a post/article by Etienne Ghys).

My own impression was that since Akhmedov’s argument was using at its base the same language that geometric group theorists are used to, their community felt more comfortable with letting the validity of the argument get worked out by some of the experts - in other words, “no need to rush, someone is bound to check the details”.

By contrast, the Shavgulidze argument came from out of left field. His background and expertise appears to be in stochastic analysis, with one strand of his work devoted to results for certain diffeomorphism groups. Now it’s known, I think, that said groups are amenable, but they are “very non-locally-compact” – and there are examples of non-locally-compact amenable groups that contain discrete free nonabelian subgroups, so that merely embedding F as a discrete subgroup of Diff(I) does not on its own show amenability.

Anyway, to get back to the “meta-question” which I think you and David find more interesting: perhaps it could be that since Shavgulidze’s paper was claiming to use techniques from left field to solve a difficult problem of interest in GGT, the GGTists were more motivated to examine his claims carefully, to learn new techniques. Hence, it is his paper rather than Akhmedov’s which has received more scrutiny.

(Apologies for the lack of hyperlinking, but I am typing this the night before flying and so should really be packing, or sleeping, or even both simultaneously if only that were possible…)

Posted by: Yemon Choi on January 15, 2010 2:44 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Posted by: Tim vB on January 14, 2010 4:12 PM | Permalink | Reply to this

### Re: F and the Shibboleth

There’s a nice discussion paper here: http://arxiv.org/abs/0908.1353 I admit to not following this at all; I don’t know if the consensus is that Shavgulidze’s proof holds, or not…

Posted by: Doormat on January 14, 2010 5:51 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Posted by: Toby Bartels on January 14, 2010 6:34 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Questions have arisen during our readings that have been answered via email by several people from outside the seminar. At least one of our outside consultants is in touch with Shavgulidze, and so we have gotten, indirectly, some of Shavgulidze’s elaborations on some of the points in his paper.

Doesn’t Mr. Shavgulidze have a telephone? Or an email account? Or a scype account? Or a fax? Or…is the communication via posting papers on the arXiv the most effective way to settle these questions?

Posted by: Tim vB on January 14, 2010 6:49 PM | Permalink | Reply to this

### Re: F and the Shibboleth

You seem to be making presumptions about Shavgulidze’s resources, inclination, background, and *interest* in explaining/disseminating his proof.

Posted by: Yemon Choi on January 14, 2010 11:03 PM | Permalink | Reply to this

### Re: F and the Shibboleth

The way I phrased the question, it could easily be understood as a kind of criticism, sorry! That was not my intention, it’s a matter of (communication) culture.

Let me try again: From where I come from (software development), the first thing - when in doubt - would be to try to contact the author. In fact, if you don’t try to, you’ll get massive trouble, and I would like to think that this is the same over the world in all engineering sciences: If you build something that fails because you did not understand how to use one of the components, because you did not ask the producer how to use it, that’s hard to explain to your boss. On the other way ‘round I would expect that anyone who produces anything would be interested in explaining it’s use in a way that is comprehensible to it’s potential users - no sense in producing something that no one can use, right?

Obviously I transferred all this to the situation we are talking about here and was surprised that it did not work out. Why not? E.g. are there usually too many people interested in this kind of paper so that the author cannot afford the time to answer all of them?

Posted by: Tim vB on January 15, 2010 8:21 AM | Permalink | Reply to this

### Re: F and the Shibboleth

I had been planning to go through both Shavgulidze’s paper and Team Brin’s notes, but ran out of stamina rather early on … The source paper leans casually but crucially, with little elaboration, on “facts” about infinite-dimensional analysis, to wit various ways that Wiener measure transforms under certain changes of coordinate. It seems that Shavgulidze, rather than being interested originally in F, came to the problem via some quite old prior work from the late ’70s on quasi-invariant measures on diffeomorphism groups.

So I have no real feel for whether the argument holds up or not. The use of notation and multiple sub/super-scripts in Shavgulidze’s paper is ghastly, in any case.

Posted by: Yemon Choi on January 14, 2010 11:01 PM | Permalink | Reply to this

### Re: F and the Shibboleth

This is a wonderful posting.

On a minor note, regarding “Someone — John Baez, I think — taught me how to spot a fake knot theorist. (You can never be too careful.) Simply ask them to draw a trefoil. If they hesitate in the slightest, they’re faking it. Actually, this will only
catch really bad fakes, but in some weak sense it’s a
shibboleth, a mark of identity, or at the very least, something that any professional can do.” – the last time that I spoke to executives of the hit CBS-TV series NUMB3RS, they told me that they’d love to do a Knot Theory episode, but haven’t seen any good enough teleplays, or even treatments.

I’m working on that, and you just helped.

“We all use math every day; to predict weather, to tell time, to handle money. Math is more than formulas or equations; it’s logic, it’s rationality, it’s using your mind to solve the biggest mysteries we know.”

Posted by: Jonathan Vos Post on January 14, 2010 9:16 PM | Permalink | Reply to this

### Re: F and the Shibboleth

When I was about six there was a Mathnet (Square One) episode whose solution involved a knot you could tie around your own hands, beind your back…

Posted by: some guy on the street on January 17, 2010 1:55 AM | Permalink | Reply to this
Read the post What is a Theory?
Weblog: The n-Category Café
Excerpt: Is a syntactically presented theory as important as its walking model?
Tracked: July 14, 2010 5:46 AM

### Re: F and the Shibboleth

Mark Sapir, cited earlier in this thread, has just started a conversation about this post at meta.mathoverflow.net (MathOverflow’s discussion board). As it’s clearly off topic there, I’m moving the discussion here.

Mark wrote:

On a completely different matter. I just looked at your Web site and found this note: http://golem.ph.utexas.edu/category/2010/01/f_and_the_shibboleth.html. Isn’t this the same characterization of F as in http://front.math.ucdavis.edu/0301.5225? Sorry for the offtopic.

I replied:

Regarding the off-topic matter, if you have an easy deduction of the result described in that $n$-Category Café post from the result in your paper with Guba, I’d like to see it. I tried to find one years ago, when Fiore and I first did that work, but with no success: I couldn’t see a direct way of deducing either characterization from the other. I also discussed this with Guba when he was visiting Glasgow in about 2005. But let’s continue this discussion at the Café.

(Note that this isn’t the same paper of Guba and Sapir as the one cited in the paper by Fiore and me that this post is about.)

Mark replied:

About our paper with Guba: look at the dunce hat example. It is exactly the definition of F that you give.

To that I reply: while they’re related, the dunce hat is not ‘exactly the definition [or rather characterization] of $F$’ that we give: it can’t be, since the word ‘monoidal’ doesn’t appear in your paper.

We wrote what we knew about this on page 3 of our paper. There we do establish a connection between our result and an earlier result of yours and Guba’s.

Posted by: Tom Leinster on December 24, 2011 3:25 PM | Permalink | Reply to this

### Re: F and the Shibboleth

A diagram group in general is defined as follows. Take a directed 2-complex C which is a 2-category enriched over a groupoid. Take a 1-morphism u, then DG(C,u) is the automorphism group of u. You get F if C is the Dunce hat H, i.e. has one vertex, one 1-morphism x, and one 2-morphism y: xx – > x.
F=DG(H,x). It is in the paper I quoted and in fact in the first diagram group paper as wwell but there we used a different terminology. It is exactly the definition you use. I hope this info is enpigh for you to fill in the details (there are not many mmissing).

Posted by: markvs on December 25, 2011 9:00 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Mark, you may be right, but I’m afraid I’m going to treat your claim with scepticism until you provide a detailed proof. It’s nothing personal, but there’s some history to this. Since Marcelo and I came up with this result in about 2005, several people have claimed that it’s easily deducible from one of the older results. They’ve looked at our result, presumably thought to themselves “that’s so similar to the old results that it’s got to be essentially the same”, and claimed that it is. But no one, when challenged, has been able to back up their claim with proof.

On at least one occasion, the problem appears to have been that the person involved hasn’t really understood the meaning of the phrase

the monoidal category freely generated by an object $A$ and an isomorphism $A \otimes A \to A$.

Since this phrase is at the heart of the statement of our theorem, understanding it is a prerequisite to showing how our theorem is related to any other result.

On the other hand, that hasn’t been the problem every time. For example, Peter Freyd, who knows perfectly well what that phrase means, publicly claimed on the categories mailing list that our result was essentially the same as the old characterization of $F$ by him and Alex Heller. When challenged to deduce our result from his, he produced an argument that was clearly wrong, and when the obvious mistake was pointed out, he acknowledged the fault but didn’t come up with a fix. (I wouldn’t normally tell this kind of story, but the claim was public.)

Most of the time when people have thought that our characterization of $F$ was essentially the same as one of the older ones, it’s been either Higman’s or Freyd and Heller’s. (Actually, Higman characterized $V$ rather more readily than $F$. And, incidentally, there’s a slight variant of our result that characterizes $V$ rather than $F$: just change “monoidal” to “symmetric monoidal”.)

But the situation is a bit different in the case of the characterization of $F$ found by Mark and Victor Guba — the “dunce hat” characterization. There, a direct relationship between the two characterizations is known. On page 3 (or 327) of our paper, we sketch how to deduce the dunce hat characterization from our monoidal characterization, and vice versa. Mark, your comments are too brief for me to be able to tell: is that the same argument you have in mind, or do you have something new?

So: Mark, repeatedly claiming that our two characterizations are “exactly” the same isn’t going to get us anywhere. A detailed argument is the only way forward. In particular, I’d like to know:

1. whether what you have in mind is different from what’s on page 3 of our paper, and if so,
2. how the free monoidal category on an idempotent object enters into your argument. (You haven’t uttered the word “monoidal” yet.)

For anyone tuning in but not following the details, here’s a summary.

Victor Guba and Mark Sapir found a way of taking any presentation of a monoid and producing from it a topological space (in fact, a 2-dimensional complex). They call this space the “Squier complex” of the presentation. Its connected-components are in canonical one-to-one correspondence with the elements of the monoid being presented. So, for each element of the monoid, you get a group — the fundamental group of that component of the Squier complex. Applied to the presentation $\langle x | x^2 = x \rangle$ and the element $x$, this gives Thompson’s group $F$. The “dunce hat” that Mark’s referred to is a just a way of drawing the equation $x^2 = x$: it’s a commutative triangle labelled with an $x$ on each edge.

In our paper, we sketch a way of deducing their dunce hat characterization from our monoidal characterization and vice versa, using the classifying space construction (a.k.a. geometric realization). So, including category theory in “algebra”, things are organized as follows:

Posted by: Tom Leinster on January 2, 2012 12:18 PM | Permalink | Reply to this

### Re: F and the Shibboleth

You can be suspicious if you want. The discussion is pointless until you read the article on diagram groups and directed 2-complexes (which are NOT Squier complexes but 2-categories and whose 1-morphisms and 2-morphisms form monoidal category). For your information, all (9 or 10) different characterizations of F are almost obviuously equivalent, each proof of equivalence takes at most 1/2 page. Some characterizations are more useful than others, though. For example, diagram groups were used to establish numerous algebraic properties of F and also results about dimension growth and Hilbert space compression.

Posted by: Mark Sapir on January 3, 2012 3:13 PM | Permalink | Reply to this

### Re: F and the Shibboleth

I’ll stick my neck in the fray without knowing what I am talking about. In their memoir Guba and Sapir groupoidify a semigroup given a presentation. Namely, if S is a semigroup with generators A and relations R, they construct a groupoid whose objects are words in the free semigroup on A and whose arrows are isotopy classes of semigroup van Kampen diagrams. The product is concatenate and remove dipoles and the inverse is taking mirror image. There is a semigroupal category structure (if I understand correctly) which on objects is multiplication in the free semigroup and on arrows is what Guba and Sapir call horizontal composition and denote by +. Basically you paste diagrams side by side. The isomorphism classes in this groupoid are the congruence classes for the homomorphism from the free semigroup to S. So this thing does degroupoidify to S. Now if you present the trivial semigroup by one generator x and relation x=x^2 then the objects look like the powers of x (freely generated) and they are all isomorphic. So we have a semigroupal category generated by an idempotent up to iso object that smells like it should be free. The van Kampen diagrams have duals (see the Guba-Sapir paper) that look like the stringy things monoidal category guys use that I don’t understand. So this I think is the direct link between Guba and Sapir and your paper but I don’t know enough category theory to prove their guy is the free one. Oh, I forgot to mention they prove the automorphism group at x is F. By the way, did you or your coauthor talk about this at a CMS meeting in Calgary? It seems familiar.
Posted by: Benjamin Steinberg on January 11, 2012 4:54 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Thanks, Ben. I think the nub of this is going to be taking the semigroupal category that smells like it should be free and proving that it really is free.

(As you correctly discern, and as I mentioned briefly in my post, the whole thing is a little bit cleaner when done with semigroupal rather than monoidal categories. For example, the free semigroupal category on an idempotent object is $F$. But it doesn’t make a whole lot of difference: using monoidal categories instead just means you also have a unit object sitting there not doing much.)

And yes, I spoke about this at the CMS meeting in Calgary in 2006 (with a streaming cold). We met briefly then, or possibly at the semigroup day (or semi-day) you’d organized with Robin Cockett just before. I hope I didn’t give you my cold.

Posted by: Tom Leinster on January 11, 2012 9:35 AM | Permalink | Reply to this

### Re: F and the Shibboleth

And by the way: impressive memory, Ben!

Posted by: Tom Leinster on January 11, 2012 9:39 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Tom, I remember now your cold. I don’t believe I got it. I only remember 2 talks from the category sessions, yours and Peter Freyd’s. I remember yours because I understood it to some extent and because John Conway appeared. I remember Peter’s because he was writing on the transparencies sideways and I thought for 10 minutes he had been writing in Chinese because a sideways gothic A looks like a Chinese character. I do not think I know enough monoidal category theory to prove the Guba/Sapir example is free, but maybe your paper does it already. Guba and Sapir prove the groupoid I described in my previous comment via van Kampen diagrams is the fundamental groupoid of the Squier complex you mention above. Now the Squier complex has vertices the free semigroup, 1-cells the rewrite rules and their inverses and 2-cells coming from non-overlapping 2-cells. Now one can define the semigroupal structure on the 2-complex. Namely you multiply vertices as in the free semigroup. Multiplying a vertex by a 1-cell changes the “context” of the rewrite rule on one side or the other and the horizontal composition of two 1-cells is exactly one of the 2-cells. That is the tensor product of two one cells should be a path of length two obtained by concatenating the words and doing disjointly the non-overlapping rewrite rules. The 2-cells say these two paths are homotopy equivalent and in fact the 2-cells are exactly the tensors of 1-cells. So the fundamental groupoid is a semigroupal category. In the case of the presentation $\langle x\mid x=x^2\rangle$ one needs to then just show that the above semigroupal 2-complex presents a free idempotent semigroupal category. This should follow with some detail checking. The 2-cells say exactly the tensor of 1-cells is well defined and satisfies some usual identity in monoidal categories. There are no other relations in the category part other than the groupoid relations, which are needed for all objects to be isomorphic, and the objects form a free semigroup. The map sending the arrow $x\to x^2$ corresponding to the unique rewriting rule generates this groupoid as a semigroupal category since every other 1-cell is a translate of this one by the action of the free semigroup on each side. I don’t know enough about monoidal categories to make this a proof but I am sure you do and maybe the paper does it already. Question: do Guba-Sapir groupoidifications of semigroups give other interesting monoidal categories? Ben
Posted by: Benjamin Steinberg on January 11, 2012 4:11 PM | Permalink | Reply to this

### Re: F and the Shibboleth

I think Guba and Sapir have done something much more general but lots of details must be checked. Suppose I have a semigroup presentation $\langle X\mid R\rangle$. Let us categorify this data. Instead of viewing this as saying take the semigroup generated freely by $X$ subject to the relations $R$, let us instead take the semigroupal category freely generated by objects indexed by $X$ subject to the tensor products corresponding to the relations $R$ being isomorphic. So if our semigroup presentation is $\langle x\mid x^2=x\rangle$, we categorify this to the free semigroupal category on one generating object subject to the generator being isomorphic to its tensor square.

Conjecture: The Guba-Sapir groupoid associated to the semigroup presentation $\langle X\mid R\rangle$ with the horizontal composition as tensor is the free semigroupal category on objects indexed by $X$ subject to the tensors specified by the relations $R$ being isomorphic.

Recall here the objects of this groupoid are non-empty words over $X$ and the arrows are isotopy classes of reduced van Kampen diagrams. Composition is concatenation followed by dipole reduction and inversion is mirror image. Tensor product is attaching the diagrams side by side.

Equivalently, the fundamental groupoid of the corresponding Squier complex is our desired guy with the induced tensor product which as I point out above is well defined because the tensor product of two 1-cells is well defined in the fundamental groupoid due to the 2-cells. The Squier complex is defined in comments above.

Ok, any ideas by people who can say semigroupal category without stuttering to prove it? It seems like it should be clear. The vertices are all possible products of objects (we have no relations on products of objects, so we should get the free semigroup). The 1-cells give the isomorphism between both sides of a relation and the product of these isomorphisms with 0-cells so we must have them in the free thing. The 2-cells in the Squier complex are the minimal thing we need in order for the product of two 1-cells to be well defined. So it seems we have put in the Squier complex the minimum we need.

Just as a test, if we have no relations, then all we have is the discrete category whose objects are the elements of the free semigroup and all arrows are identities. That is the free semigroupal category generated by a bunch of objects.

The automorphism groups of these guys are what Guba and Sapir call diagram groups and they are very rich. Their directed two complex paper gives the analogous thing for presentations of categories and I suppose is therefore some higher categorical thing.

BTW, as an editor of Semigroup Forum I feel like I can make the following bad joke: what is a semigroup? A monoid with an identity crisis!

Posted by: Benjamin Steinberg on January 12, 2012 5:19 AM | Permalink | Reply to this

### Re: F and the Shibboleth

Here is a proof of my conjecture and so in particular a proof that the free semigroupal category on an idempotent object is the Guba-Sapir groupoid for the trivial presentation of the trivial semigroup.

Let $\langle X\mid R\rangle$ be a semigroup presentation. The original description of the Guba-Sapir groupoid in terms of van Kampen diagrams lets one easily verify it is a (strict) semigroupal category with tensor product the horizontal decomposition. We want to show that it is freely generated by the objects which are elements of X and the arrows which are basic van Kampen diagrams corresponding to a relation r=r’ (with the empty context).

To show generation, the objects are all words in X and so clearly belong to the semigroupal subcategory generated by X. The description of the Guba-Sapir groupoid as the fundamental group of the Squier complex shows that the morphisms are generated by the left and right translates of the basic van Kampen diagrams. Thus it remains to show freeness. The tensor product on objects has no relations. But the relations of the Guba-Sapir groupoid are generated by the 2-cells in the Squier complex. These each have the form $(a\otimes 1)(1\otimes b)=(1\otimes b)(a\otimes 1)$ and hence are satisfied by any semigroupal category. So the Guba-Sapir groupoid is free on the objects X subject to the tensors in R being isomorphic.

There is an analogue in the diagram groups paper for monoid presentations using the dual notion of a van Kampen diagram called a picture (your colleague Steve Pride is the expert on this). There is a corresponding groupoid in this context which should now be an honest monoidal category with unit the empty word object. I believe it is still the fundamental groupoid of the Squier complex and the above proof works to show it is the free monoidal category generated by the objects subject to isomorphisms from the relations. I won’t swear on this though if some of the relations involve the empty word since I vaguely recall things are more suble in this case and I haven’t looked at the diagram groups book in over 10 years!
Posted by: Benjamin Steinberg on January 12, 2012 12:23 PM | Permalink | Reply to this

### Re: F and the Shibboleth

Great!

Sorry not to have been following this in more detail, too. But I’m glad you’ve got this result.

Posted by: Tom Leinster on January 12, 2012 12:29 PM | Permalink | Reply to this

### Re: F and the Shibboleth

For obvious reasons, I was struck by the lack of reference to the associahedron in the discussion of Thomposon’s group. For a recent contribution in that direction see:

Patrick Dehornoy: Tamari Lattices and the symmetric Thompson monoid