That Logic Blog

February 26, 2008

Invariants (preprint)

I seem to have been on a bit of a blogging hiatus for a bit, while trying to get some research done. In this slightly self-indulgent post, I want to talk about some work I've done linking up a few things from universal algebra, category theory and combinatorial group theory.

I've been thinking a bit about invariants for logics and related things. That is, given two logics L and L', we wish to construct gadgets I(L) and I(L') that are isomorphic whenever L and L' are equivalent.

The above paragraph is rather fuzzy, mainly because I have not specified what I mean by a "logic". In the present context, I'm going to take this to be an equationally defined algebraic theory. Examples are things like boolean algebras, distributive lattices and monoids. This is in keeping with classical algebraic logic, which reinterprets logical operators such as conjunction by algebraic operations such as meet.

Within the above context, Patrick Dehornoy has managed to construct algebraic invariants. To every equational theory (satisfying some mild conditions), Dehornoy attaches an inverse monoid, which he has variously called the structure/structural/geometry monoid of the theory. The original construction is detailed in:

P. Dehornoy, Structural monoids associated to equational varieties; Proc. Amer. Math. Soc. 117-2 (1993) 293-304.

In some cases, the structure monoid of an equational theory turns out to be a group. This is, in particular, the case for the theories for semigroups and for commutative semigroups. Dehornoy later went on to show that the structure groups for these theories are Thompson's groups F and V, respectively - rather famous algebraic objects! For instance, they were the first known examples of finitely presentable infinite simple groups. The details are in:

P. Dehornoy, Geometric presentations for Thompson's groups.

In the above paper, Dehornoy constructs presentations for F and V by making essential use of Mac Lane's pentagon and hexagon coherence axioms (arising originally in monoidal and symmetric monoidal categories). This appearence of coherence axioms piqued my interest and I started trying to formalise the connection between structure monoids and coherence theorems. As a warm up to the general case, I toyed around with notions of associativity and commutativity for higher-order functions. This turned out to be a fruitful exercise, as the structure groups in these cases are the higher Thompson groups and the Higman-Thompson groups, respectively. These are infinite families of groups into which F and V slot, which share many of the properties of F and V. After this promising start, I thought about what the coherence axioms for higher-order associativity and commutativity might look like and ended up with a generalisation of the pentagon and hexagon axioms to the higher-order case. Interestingly enough though, several more axioms are required in the higher order case - these do not appear in the usual binary case since everything is a bit too "squished".

Then it was a matter of using the coherence theorems to build presentations of the groups. Being a lazy slob, I did not want to construct both presentations, so I cooked up a procedure that takes a coherent categorification of an equational theory and constructs a presentation for the associated structure monoid, thus saving me the effort.

Anyway, all of this is detailed in the following preprint:

Jonathan A. Cohen, Coherent presentations of structure monoids and the Higman-Thompson groups

Now its back to the thesis-writing salt mines for me (if you look at the conclusions section of the preprint, you'll get a vague idea of what my thesis is on. Stay tuned for more...)