Thesis!

I graduated from my PhD in December and have finally gotten around to placing my thesis on the arXiv. Because of the space limitations of arXiv metadata, the abstract on the webpage has been truncated somewhat, so I will put the real abstract below.

Coherence for rewriting 2-theories: General theorems with applications to presentations of Higman-Thompson groups and iterated monoidal categories; Jonathan Asher Cohen

Abstract:

The problems of the identity of proofs, equivalences of reductions in term rewriting systems and coherence in categories all share the common goal of describing the notion of equivalence generated by a two-dimensional congruence. This thesis provides a unifying setting for studying such structures, develops general tools for determining when a congruence identifies all reasonable parallel pairs of reductions and examines specific applications of these results within combinatorial algebra. The problems investigated fall under the umbrella of ``coherence'' problems, which deal with the commutativity of diagrams in free categorical structures --- essentially a two-dimensional word problem. It is categorical structures equipped with a congruence that collapses the free algebra into a preorder that are termed ``coherent''.

The first main result links coherence problems with algebraic invariants of equational theories. It is shown that a coherent categorification of an equational theory yields a presentation of the associated structure monoid. It is subsequently shown that the higher Thompson groups $F_{n,1}$ and the Higman-Thompson groups $G_{n,1}$ arise as structure groups of equational theories, setting up the problem of obtaining coherent categorifications for these theories.

Two general approaches to obtaining coherence theorems are presented. The first applies in the case where the underlying rewriting system is confluent and terminating. A general theorem is developed, which applies to many coherence problems arising in the literature. As a specific application of the result, coherent categorifications for the theories of higher order associativity and of higher order associativity and commutativity are constructed, yielding presentations for $F_{n,1}$ and $G_{n,1}$, respectively.

The second approach does not rely on the confluence of the underlying rewriting system and requires only a weak form of termination. General results are obtained in this setting for the decidability of the two-dimensional word problem and for determining when a structure satisfying the weakened properties is coherent. A specific application of the general theorem is made to obtain a conceptually straightforward proof of the coherence theorem for iterated monoidal categories, which form a categorical model of iterated loop spaces and fail to be confluent.

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...)

Galavanting

I fly off to the land up over on Saturday to attend various things as well as for a bit of a holiday. For the insatiably curious, there is a preprint floating around now covering the things I will be talking about: Coherence without unique normal forms.