HTML reading edition · 29 source pages · Open the source PDF

Under consideration for publication in Math. Struct. in Comp. Science

Imaginary groups: lazy monoids and reversible computation

Murdoch J. Gabbay1 and Peter H. Kropholler2

1 School of Mathematical and Computer Sciences, Heriot-Watt University, Edinburgh EH14 4AS, United Kingdom http://www.gabbay.org.uk

2 Mathematical Sciences, Southampton University, Highfield, Southampton SO17 1BJ, United Kingdom p.h.kropholler@southampton.ac.uk†

Received 30 September 2011; Revised 21 April 2012

By constructions in monoid and group theory we exhibit an adjunction between the category of partially ordered monoids and lazy monoid homomorphisms, and the category of partially ordered groups and group homomorphisms, such that the unit of the adjunction is injective. We also prove a similar result for sets acted on by monoids and groups. We introduce the new notion of lazy homomorphism for a function f between partially-ordered monoids such that f (m ◦ m′) ≤ f (m) ◦ f (m′). Every monoid can be endowed with the discrete partial ordering (m ≤ m′ if and only if m = m′) so our constructions provide a way of embedding monoids into groups. A simple counterexample (the two-element monoid with a non-trivial idempotent) and some calculations show that one can never hope for such an embedding to be a monoid homomorphism, so the price paid for injecting a monoid into a group is that we must weaken the notion of homomorphism to this new notion of lazy homomorphism. The computational significance of this is that a monoid is an abstract model of computation—or at least of ‘operations’—and similarly a group models reversible computations/operations. By this reading, the adjunction with its injective unit gives a systematic high-level way of faithfully translating an irreversible system to a ‘lazy’ reversible one. Informally, but perhaps informatively, we can describe this work as follows: we give an abstract analysis of how to sensibly add ‘undo’ (in the sense of ‘control-Z’).

1. Introduction

1.1. Monoids, groups, computation, and inverses

Suppose we have a computer. We run programs, and this changes the state of the computer.

This can be thought of as a set X (representing states) and some functions f : X → X (representing operations) closed under function composition. The functions in X → X form a monoid, which is like a group but does not have inverses. Monoids provide an abstract model of state and computation.

Now suppose we want to undo the effects of an operation. But since f : X → X need not be injective, given some x ∈ X there may be several y such that f (y) = x. Monoids do not have inverses.

Yet ‘undo’ or ‘rollback’ operations are very common. This may be familiar to the reader from e.g. word processing or version control (subversion was used in the pro-duction of this paper). A notion of ‘state, with rollback’ called transactional memory is useful, especially in concurrency where updates from one process may need to be un-done in the light of results later arrived at by a concurrent process [Herlihy and Moss, 1993]. In proof-search the difference between proof-rules which are reversible, such as left conjunction introduction (∧L) below, also called asynchronous, and those that are not reversible, such right disjunction introduction (∨R) below, also called synchronous, has mathematical significance [Liang and Miller, 2009].

AsynchronousΓ, A ∧B ⊢C(∧L)Γ, A, B ⊢CSynchronousΓ ⊢A(∨R)Γ ⊢A ∨B

Note that (∧L) just rearranges connectives (by turning a ‘∧’ into a ‘,’ if we read the rule bottom-up), but (∨R) eliminates B so is (from the point of view of proof-search) an irreversible step.

Further, the field of reversible computation, which has physical importance for heat-dissipation and the design of biological and quantum computation, is devoted to the study of hand-tailored reversible computational mechanisms. References and further discussion are in the Conclusions.

Now let us return to our monoid M. This is given to us and it was not designed from the start to be reversible. How can we ‘add an undo function’ to M, in some abstract sense? In view of the discussion above we can mathematically distil this to the following formal and rigorously answerable question:

Given a monoid M, does there exist a group M± and an injective monoid map M →M±? We ask for the map to be injective so that distinct operations in the monoid correspond to distinct reversible operations in the group. That is, M± needs to faithfully represent the original states and operations. Otherwise, we could just map all of M to the trivial group with one element.

Given the injection above, we could have our cake and eat it: given any notion of computation, represent it as a monoid M, calculate M±, compute in that group (with an undo function) and then, if we like the result, we can return our result and if we do not, we can always undo.

1.2. Monoids, lazy monoids, and our solution

Unfortunately what we have asked for is impossible.

This can easily be proved with a small counterexample:

Example 1.1

Consider the two-element monoid {0, 1} with

1 ◦x = x for x ∈{0, 1} and 0 ◦x = 0 for x ∈{0, 1}.

If we try to adjoin an element 0-1 then 0 = 0 ◦ 0 and so (applying 0-1 to both sides) 0 = 1. We lose injectivity; if M = {0, 1} then M± is the trivial group in which computation is reversible because everything is equal to the identity operation which does nothing at all.

In this paper we will indeed exhibit a construction which assigns to a monoid M a partially ordered group M±, and we will exhibit a lazy monoid homomorphism from M to M±. By moving to partially ordered structures and lazy homomorphisms, the contradiction noted in the previous paragraph is avoided.

Thus it is possible to add ‘undo’ to a monoid after all—we just have to do it in the right way. How this should work, is not immediately obvious.

Our solution supports an attractive computational interpretation: think of the monoid M as a set of operations, and monoid composition as their composition, and both of these may be irreversible. Then the ‘lazy’ group M± which we build, is operations which have been assembled but not yet carried out; they are ‘suspended’. Each element in the group is a plan of action; we can compose plans, modify them, erase elements from them—and this is reversible because nothing has been carried out. The partial order represents the operation of actually carrying out the plan; moving down along the partial order represents refining results as the plan is executed, which may lose information and is irreversible.

Our main result can be stated as follows: There is an adjunction between the categories of partially-ordered monoids and lazy homomorphisms, and of partially-ordered groups and group homomorphisms, and the unit of the adjunction is injective. This is Theorems 3.22, 3.24, 3.25, and 3.30.

1.3. Map of the paper

Here is an eagle’s eye view of how our construction works for monoids:

Monoidinj.PoMoninj.PoMonZfree⊥PoGrpforget

Monoid is the category of monoids and monoid homomorphisms. PoMon is the category of partially-ordered monoids and monotone monoid homomorphisms. The injection from Monoid to PoMon is just obtained by giving a monoid the trivial partial order relating x to itself.

PoMonZ is the category of partially-ordered monoids and lazy monotone monoid homomorphisms, where ‘lazy’ is defined in Definition 2.3. Every monotone monoid homomorphism is a lazy monotone monoid homomorphism so we obtain a trivial injection from PoMon to PoMonZ.

PoGrp is the category of partially-ordered groups and monotone group homomorphisms. There is an easy forgetful functor from PoGrp to PoMonZ and a free functor that is left adjoint to the forgetful functor mapping a monoid M to its free group with added ‘imaginary’ inverse M±. Constructing the underlying set of M± easy, as is defining its group structure and giving it a natural preorder (Definitions 3.3 and 3.6). What is not easy is proving that the preorder is a partial order, and showing that the unit of the adjunction is a monomorphism. This is Theorems 3.22 and 3.24, see also Theorem 3.25.

Later on in Section 4 we discuss how this can be generalised in various ways, and in Section 5 we extend the construction to sets with a lazy monoid or group action. The generalisations are essentially routine, and extending to sets with an action is not entirely trivial, but no harder.

2. Basic definitions

2.1. Partially ordered groups and monoids, and lazy homomorphisms

Definition 2.1

Consider the following axioms:

(assoc) x ◦(x′ ◦x′′) = (x ◦x′) ◦x′′(id) id ◦x = x ◦id = x(inv) x ◦x-1 = x-1 ◦x = id

— A group G is a tuple (|G|, ◦, id, -1) of a carrier set |G|, a composition ◦ mapping |G| × |G| to |G|, an element id ∈|G|, and an inverse map -1 mapping |G| to |G|, satisfying (assoc), (id), and (inv).

— A monoid M is a tuple (|M|, ◦, id) as above, satisfying (assoc) and (id).

Definition 2.2

A (compatible) order on a monoid M is a partial order ≤⊆|M| × |M| such that x ≤ y implies x ◦ z ≤ y ◦ z and z ◦ x ≤ z ◦ y.

— A partially ordered monoid is a pair (M, ≤) of a monoid M and a compatible order on M.

— A partially ordered group is a pair (G, ≤) of a group G and a compatible order on G, considered as a monoid.

Definition 2.3

Call a function f ∈|M| →|M′| between monoids M and M′ a homomorphism when it satisfies the two axioms

idM′ = f (idM) and f (x1 ◦M x2) = f (x1) ◦M′ f (x2).

If M′ is a group, the first equation can be deduced from the second, as can the identity f (x-1) = f (x)-1; but in general both axioms are required.

Suppose now that M and M′ are partially ordered monoids. Call a function f ∈ |M| →|M′| a lazy homomorphism when

idM′ ≤M′ f (idM) and f (x1 ◦M x2) ≤M′ f (x1) ◦M′ f (x2).

Call f ∈|M| →|M′| monotone when x ≤M y implies f (x) ≤M′ f (y).

We discuss this definition in Subsection 2.2.

Definition 2.4

— Write PoMonZ for the category of partially ordered monoids and monotone lazy homomorphisms between them (Partially Ordered MONoids with laZy homomorphisms).

— Write PoGrp for the category of partially ordered groups and monotone lazy group homomorphisms between them (Partially Ordered GRouPs and homomorphisms).

Note in Definition 2.4 that we take lazy homomorphisms in PoMonZ but ‘real’ homomorphisms in PoGrp. We could certainly define PoGrpZ, but it turns out that we will never use it; see Example 3.28 for an example illustrating why this is the case.

Remark 2.5

For the reader’s convenience we explicitly unpack what it is to be an arrow in PoMonZ. An arrow f : (M, ≤M) → (M′, ≤M′) is a function f from |M| to |M′| such that: 1 idM′ ≤M′ f (idM) (laziness). 2 f (x ◦M y) ≤M′ f (x) ◦M′ f (y) (laziness). 3 x ≤M y implies f (x) ≤M′ f (y) (monotonicity).

2.2. Why lazy?

There is a notion of lax functor between 2-categories (see for instance [Leinster, 2004, Definition 1.5.8]). Specifically for us here,† this suggests the following definition:

Definition 2.6

Suppose now that M and M′ are partially ordered monoids. Call a function f ∈|M| →|M′| a lax homomorphism when

f (idM) ≤M′ idM′and f (x1 ◦M x2) ≤M′ f (x1) ◦M′ f (x2).

Call a function f ∈|M| →|M′| an oplax or colax homomorphism when

idM′ ≤M′ f (idM) and f (x1) ◦M′ f (x2) ≤M′ f (x1 ◦M x2).

To see in elementary terms why lax homomorphisms are natural, note that if we consider the inequality f (x1 ◦M x2) ≤M′ f (x1) ◦M′ f (x2) and imagine what its 0-ary version should be, we obtain f (idM) ≤ idM′.

A lazy homomorphism sits in-between lax and oplax, combining the first axiom of oplax with the second axiom of lax. This is new.

We would like to give some intuition, in elementary terms, about why lazy homomorphisms are interesting.

First, an informal computational intuition: Read a partially ordered monoid or group as a set of operations, which can be composed. Think of the partial order as describing ‘execution’ of these operations—so z ≤ x ◦ y means “if we combine x with y and execute then we obtain z”. Then we can give the lazy inequalities the following informal reading:

— idM′ ≤M′ f (idM) means if we apply f to the identity and execute, we get the identity.

— f (x ◦M y) ≤M′ f (x) ◦M′ f (y) means if we apply f to x and apply f to y and combine, then if we execute we can obtain the result of combining x and y in M first, and then applying f .

We call this lazy by analogy with lazy evaluation in the λ-calculus.

Second, a mathematical intuition: We want M to inject into the ‘imaginary’ group M± which augments M with ‘imaginary’ inverses (formal definition in Subsection 3.1). So let us consider a specific example and see what is required to make this work.

Let M be the one-element monoid {∗} with monoid composition ∗◦∗= ∗. Then M± is isomorphic to the integers under addition: the unit is (); the number 1 corresponds to +∗; the number 2 corresponds to +∗+∗; the number −1 corresponds to −∗, and so on. The function taking ∗ to 1 is lazy because 0 ≤ 1 and 1 ≤ 2. This function is not lax, because 1 ≰ 0, and not oplax because 2 ≰ 1, but it is lazy.

So, with lazy homomorphisms the integers Z considered as a group with their natural arithmetic ordering are exhibited as the free object over a single generator.

Interestingly, our proof of injectivity hinges on studying index functions ι(-)m from M± to Z. See Definition 3.12. So the meat of our proof—the technical action happens between Definition 3.12 and Lemma 3.16—hinges on a study of the structure of the functions and objects making up the following commuting square:

Mη! terminal mapM± ι(-){∗}∗↦→1{∗}± = Z

The reader should be careful: though the total index function ι(-) (a ‘sum of exponents’ function) is an arrow in PoMonZ, the proof uses measure functions ι(-)m that are not arrows in this category. So the abstract nonsense above is useful for organising the ma-terial, but the proofs themselves cannot be conveniently phrased purely in categorical terms; we use combinatorial arguments on concrete constructions.

For reference: M± is defined in Definition 3.3; η is defined in Theorem 3.30; the proof that η is mono is Theorem 3.22; and commutativity is an easy calculation. With respect to later notation, we have abused notation in the diagram above and written M± for (M±)̸-1 (Definition 3.29).

3. The imaginary group

Our construction is the simplest possible; given a monoid M we take strings of elements-with-a-polarity + or − and quotient such that +m−m becomes equal to the empty string. We immediately obtain an imaginary group M±. It is the free group over M in the category of lazy monoids, to be precise. This is Definition 3.3 (the hard part is not constructing it, but proving it is not trivial; see the conservative extension results below).

For the following step we need a little general theory about partial orders on groups. It is a fact that a partial order can be generated by a normal submonoid. This turns out to be useful: see Proposition 3.7.

We then define a preorder on M± in Figure 1, in submonoid style. The order is sound by construction; the rule (leq) makes sure that if n ≤ m in M then +n ≤+m in M±.

The hard work is injectivity and conservative extension results, that the preorder is a partial order and is not ‘too big’—we do not want +n ≤+m to hold because +n = +m always, in the spirit of Example 1.1. The main technical lemma is Proposition 3.19, and the main results are Theorems 3.22, 3.24 and 3.25.

Once we have this, it is a matter of fairly routine calculations to convert this into the adjunction promised in the Introduction, culminating with Theorem 3.30.

3.1. The free group

This subsection describes an easy construction. Given M we consider |M| and build the free group generated by this set.

Definition 3.1

Given a set X write X±string for the set inductively defined by:

s ::= () | s+x | s−x (x ∈X)

Call () the empty string. Write string concatenation as s·t. We may elide the initial (), so for instance we may write +m as shorthand for ()+m.

So if X = {1, 2, 3, . . . } then intuitively X±string is the set of lists of nonzero integers.

Definition 3.2

Define ∼ to be the least equivalence relation on |M|±string such that:

1 ()+m−m ∼() ∼()−m+m.

2 If s ∼ s′ and t ∼ t′ then s·t ∼ s′·t′.

Definition 3.3

Given a monoid M define the free group M± over |M| as follows:

— The carrier set is |M|±string quotiented by ∼.

— Group composition is given by concatenation of representatives.

We may write m for both m ∈|M| and for the ∼-equivalence class of () + m.

Lemma 3.4

M± is indeed a group, with the natural composition, identity, and inverse.

Example 3.5

1 Suppose M is the monoid of natural numbers N = {0, 1, 2, 3, . . . } under addition (so 0 is the identity). Then M± is not isomorphic to the integers. For instance, +3+4 ∈ |M±| is not equal to +7. We return to this in a mathematically richer context, later on in Remark 3.18.

2 Suppose M is the one-element monoid with underlying set {∗} and monoid composition ∗◦∗= ∗ (we also saw this in Subsection 2.2). Then M± is isomorphic to the integers under addition: the unit is (); the number 1 corresponds to +∗; the number 2 corresponds to +∗+∗; the number −1 corresponds to −∗, and so on. So M± is resource sensitive. Note, however, that resources can be destroyed if we interpret ≥ as ‘entailment’; +∗+∗≥+∗.‡

3.2. Positive cones

This subsection develops some more standard theory. There is a bijection between normal submonoids of G and compatible partial orders. We only need one direction of this for the proofs to follow; see [Glass, 1999, Subsection 1.1] for more details.

Definition 3.6

— Suppose G = (|G|, ◦, -1) is a group. Call X ⊆|G| normal when x ∈ X and y ∈|G| implies y ◦ x ◦ y-1 ∈ X.

— Suppose M is a monoid. Call X ⊆|M| a submonoid when id ∈ X and when x ∈ X and y ∈ X implies x ◦ y ∈ X.

Suppose P ⊆|G| is a normal submonoid of a group G. Then write x ≤P y when y ◦ x-1 ∈ P.

Proposition 3.7

Suppose G = (|G|, ◦, -1) is a group and P ⊆|G| is a normal submonoid of G. Then ≤P from Definition 3.6 is a compatible preorder on |G|.§

Proof

We consider each property in turn:

— By assumption id ∈ P; it follows that m ≤P m and so ≤P is reflexive.

— Suppose x ≤P y and y ≤P z. This means that y ◦ x-1 ∈ P and z ◦ y-1 ∈ P. Since P is a monoid also z ◦ x-1 ∈ P. It follows that ≤P is transitive.

— Suppose x ≤P y. This means that y ◦ x-1 ∈ P. To check that ≤P is compatible we need to verify that for any z ∈|G|, z ◦ x ≤P z ◦ y and x ◦ z ≤P y ◦ z. Since P is a normal subgroup also z ◦ y ◦ x-1 ◦ z-1 ∈ P, and this means that z ◦ x ≤P z ◦ y.

Also, y ◦x-1 = y ◦z ◦z-1 ◦x-1, so that x ◦z ≤P y ◦z.End of proof
(n ≤M m)(leq)+m−n ∈P+(m1, m2 ∈|M|)(lazy)+m1+m2−(m1 ◦M m2) ∈P+p ∈P+ (g ∈M±)(norm)g-1 ◦M± p ◦M± g ∈P+p ∈P+p′ ∈P+(mon)p ◦M± p′ ∈P+
Fig. 1: Rules determining the partial order on M±

3.3. The partial order

Now the non-standard part begins. Fix a partially ordered monoid (M, ≤M). In Definition 3.3 we saw how to construct the free group M± generated by |M|.

We show how to extend ≤M to a preorder ≤M± on M±. By Proposition 3.7 it suffices to exhibit a normal submonoid of M±. In fact the preorder is also a partial order, but proving this takes more work: the main technical result is Proposition 3.19 and this quickly yields Theorem 3.22.

Definition 3.8

Define P+ to be the least subset of |M±| closed under rules (leq), (lazy), (norm), and (mon) from Figure 1. By rules (norm) and (mon) this is a normal submonoid of M± and so by Proposition 3.7 P+ determines a compatible preorder on |M±|. We write this ≤M±.

Remark 3.9

A few words on the rules in Figure 1.

— (leq) expresses that n ≤M m implies n ≤M± m.

— (lazy) expresses that +(m1 ◦M m2) ≤M± +m1+m2.

— (norm) expresses that if p ≤M± q then p ◦M± r ≤M± q ◦M± r (left-compatibility is automatic by construction; see Proposition 3.7).

— (mon) expresses transitivity of ≤M±.

The two base cases are (leq) and (lazy). Of these, rule (leq) introduces a string which has index 0; and rule (lazy) introduces a string which has index 1.

Lemma 3.10

1 If n ≤M m then +n ≤M± +m. 2 If n ≤M m1 ◦M m2 then +n ≤M± +m1+m2.

Proof

The first part is direct from (leq) and Definition 3.6. The second part follows using (lazy).End of proof

Converse implications also hold but the proofs are harder: see Theorems 3.24 and 3.25.

Now (lazy) in Figure 1 corresponds to the condition f (x1 ◦M′ x2) ≤M′ f (x1) ◦M′ f (x2) from Definition 2.3. What corresponds to the condition idM′ ≤M′ f (idM) from Definition 2.3? In fact, this is derivable:

Corollary 3.11

() ≤M± +idM. (Recall from Subsection 3.1 that () is the identity element of M±.)

Proof

By part 2 of Lemma 3.10 +idM ≤M± +idM+idM. We apply −idM to both sides.End of proof

3.4. Technical lemmas

This is where the maths begins to become non-trivial. In Definition 3.8 we defined a relation ≤M± on |M±|. It is easy to see that this is reflexive and transitive; but is it antisymmetric? In other words, is ≤M± a partial order as the caption to Figure 1 suggests, and not just a preorder? Also, is ≤M± a conservative extension of ≤M or does it introduce spurious relations that should not be there?

This subsection develops the technical machinery we need to answer these questions. These lemmas are then used to give the questions concise answers, in Subsection 3.5.

Definition 3.12

Suppose m ∈|M|. Define index functions ι(s)m and ι(s) on |M|±string as follows:

ι(())m = 0 ι(s+m′)m = ι(s)m (m′≠m) ι(s−m′)m = ι(s)m (m′≠m)ι(s−m)m = ι(s)m−1 ι(s+m)m = ι(s)m+1 ι(s) = Σm∈|M|ι(s)m

In words, we can say that ι(s) sums exponents.

Lemma 3.13

The index functions are well-defined as functions on p ∈|M±|. That is, if p ∈|M±| then for every s, s′ ∈ p and every m it is the case that ι(s)m = ι(s′)m and (therefore) ι(s) = ι(s′).

Proof

We consider each of the rules in Definition 3.2 and see that they conserve index.End of proof

Lemma 3.14

If () ≤M± p and ι(p) = 0 then every proof that p ∈ P+, does not mention (lazy).

Proof

We note by arithmetic that (leq) generates an element with index 0, (lazy) increases the index by 1, and (norm) and (mon) leave the index unchanged. The result follows.End of proof

Corollary 3.15

If () ≤M± p and ι(p)m = 0 for all m, then p = ().

Proof

We first use Lemma 3.14 to see that the derivation of () ≤M± p cannot use rule (lazy). The rules (norm) and (mon) do not affect index at all.

Let n be ≤M-minimal in p. This n must have been introduced by (leq) for some n ≤M m. Since n is ≤M-minimal in p there is no other instance of (leq) for n′ ⪇M n. By assumption ι(p)n = 0, so it must be that n = m. The result follows.End of proof

Lemma 3.16

1 If p ∈ P+ then ι(p) ≥ 0. 2 If p ≤M± q then ι(p) ≤ι(q).

Proof

The first part is by a routine induction on the rules in Figure 1. For the second part, suppose p ≤M± q. Then () ≤M± p-1 ◦M± q. By part 1 of this result, ι(p-1 ◦M± q) ≥ 0. It is a fact that ι(p-1 ◦M± q) = −ι(p) + ι(q). The result follows.End of proof

Corollary 3.17

If +m1. . . +mk ≤M± +n1. . . +nl and +n1. . . +nl ≤M± +m1. . . +mk then k = l.

Proof

ι(+m1. . . +mk) = k and ι(+n1. . . +nl) = l. We use part 2 of Lemma 3.16.End of proof

Remark 3.18

Recall part 1 of Example 3.5 and take M to be the monoid of natural numbers N = {0, 1, 2, 3, . . . } under addition (so 0 is the identity). Then by Corollary 3.17 +3+4 ≰M± +7, since ι(+3+4) = 2 and ι(+7) = 1 and 2 ≰ 1.

In fact, a much stronger result than Corollary 3.17 can be obtained, but the proof is harder. See Corollary 3.23.

Proposition 3.19 might seem a little formidable, but in fact it only expresses some common sense: Suppose the index of p is 0, so that for every +m in p there is a corresponding −n. Suppose there are more +ms in p than −ms, so that there is a surfeit of ms in p and ι(p)m > 0. In order for everything to balance out, there must be some n such that ι(p)n < 0—that is, such that there is a deficit of ns—and since p is a finite structure we can find an ≤M-minimal such n in p. This is what Proposition 3.19 asserts, and this property turns out to be key.

Proposition 3.19

Suppose p ∈ P+ and ι(p) = 0. Suppose ι(p)m > 0. Then there exists some ≤M-minimal n ⪇M m such that ι(p)n < 0.

Proof

By induction on the derivation that p ∈ P+. We consider each rule in turn, in a long but essentially routine analysis of cases ((mon) is arguably the more interesting, and certainly the most complex, case).

— The case of (leq). Then n ≤M m, but we still need to show that ι(p)m > 0 and ι(p)n < 0. By assumption ι(+m−n)m > 0. This means that m ≠ n. It follows by arithmetic that ι(+m−n)n < 0.

— The case of (lazy). If ι(+m1+m2−(m1 ◦M m2)) = 0 then either m1 = m2 = m = id or m1 = m ≠ id and m2 = id or m2 = m ≠ id and m1 = id. All cases are impossible because we assumed ι(p)m > 0 (for some m).

— The case of (norm). From the fact that ι(p)m = ι(g-1 ◦M± p ◦M± g)m.

— The case of (mon). Suppose ι(p ◦M± p′)m > 0. There are now two cases:

– The case ι(p)m > 0. By inductive hypothesis there exists a ≤M-minimal n ≤M m such that ι(p)n < 0. There are now two sub-cases:

• The case ι(p′)n < −ι(p)n. In this case ι(p ◦M± p′)n < 0 and we are done.

• The case ι(p′)n ≥−ι(p)n. In this case, in particular, ι(p′)n > 0. So there exists some ≤M-minimal n′ ≤M n such that ι(p′)n′ < 0. By assumption n was minimal, so ι(p)n = 0. It follows that ι(p ◦M± p′)n′ < 0. By transitivity n′ ≤M m and we are done.

– The case ι(p)m ≤ 0. . . is symmetric with the case ι(p′)n < −ι(p)n.

End of proof

Proposition 3.19 has a natural dual:

Proposition 3.20

Suppose p ∈ P+ and ι(p) = 0. Suppose ι(p)m < 0. Then there exists a ≤M-maximal n ⪈M m such that ι(p)n > 0.

Proof

We take M and p and consider M′ which is M but we invert ≤M (we omit a formal definition), and p-1. Thus, ι(p)m < 0 becomes ι(p-1)m > 0 and n ⪈M m becomes n ⪇M′ m, and ‘≤M-maximal’ becomes ‘≤M′-minimal’. The result is then just Proposition 3.19.End of proof

Corollary 3.21

Suppose p ∈ P+ and ι(p) = 1. Then there exist n, m1, m2 ∈|M| such that n ≤M m1 ◦M m2 and ι(p)n ≤−1 and ι(p)m1 ≥ 1 and ι(p)m2 ≥ 1.

Proof

By induction on the derivation that p ∈ P+. We consider each rule in turn:

— The case of (leq) is not relevant since ι(+m−n) = 0.

— The case of (lazy). By construction, since m1 ◦M m2 ≤M m1 ◦M m2.

— The case of (norm). From the fact that ι(p)m = ι(g-1 ◦M± p ◦M± g)m.

— The case of (mon). Suppose ι(p ◦M± p′) = 1. Then by part 1 of Lemma 3.16 precisely one of ι(p) = 1 and ι(p′) = 0 or ι(p′) = 1 and ι(p) = 0 must hold. Suppose ι(p) = 1 and ι(p′) = 0; the other case is symmetric and we will not consider it. By inductive hypothesis we obtain n, m1, and m2 as required, in p. Now if ι(p′)n ≥−ι(p)n then we use Proposition 3.19 to obtain an n′ ≤M n such that n′ ≤M m1 ◦M m2 and then use transitivity of ≤M. Similarly if ι(p′)m1 ≤−ι(p)m1 then we use Proposition 3.20 and compatibility of the partial order with ◦M. Similarly for m2. The result follows.End of proof

3.5. The preorder is a partial order and the natural map is injective

Theorem 3.22. If p ≤M± q and q ≤M± p then p = q.
Proof

Suppose p ≤M± q and q ≤M± p. Write P = q ◦M± p-1 and Q = p ◦M± q-1. Thus () ≤M± P and () ≤M± Q. Also by part 2 of Lemma 3.16 ι(p) = ι(q) and so ι(P) = 0.

Now if ι(P)m = 0 for all m then using Corollary 3.15 it follows that p = q and we are done.

So suppose ι(P)m′ ≠ 0 for some m′. We will deduce a contradiction. If ι(P)m′ ≠ 0 for some m′ then ι(P)m > 0 for some m. By Proposition 3.19 ι(P)n < 0 for some n ⪇M m and n is ≤M-minimal such amongst monoid elements mentioned in P. But then ι(Q)n > 0 and by Proposition 3.19 again ι(Q)m′′ < 0 for some m′′ ⪇M n. This contradicts minimality of n.End of proof

We immediately apply Theorem 3.22 to strengthen Corollary 3.17:

Corollary 3.23

If +m1. . . +mk ≤M± +n1. . . +nl and +n1. . . +nl ≤M± +m1. . . +mk then k = l and mi = ni for every 1≤i≤k.

Proof

By Theorem 3.22 +m1. . . +mk = +n1. . . +nl. The result follows from Definition 3.3.End of proof

Theorem 3.24 is a conservative extension result expressing that M injects into M± considered as a partially ordered monoid:

Theorem 3.24.+n ≤M± +m if and only if n ≤M m.
Proof

The right-to-left implication is part 1 of Lemma 3.10. For the left-to-right implication we reason as follows: If m = n then n ≤M m by reflexivity. So suppose m ≠ n and suppose +n ≤M± +m.

By Definition 3.6 this means that +m−n ∈ P+. We note that ι(+m−n) = 0 and ι(+m−n)m > 0. Using Proposition 3.19 it follows that n ≤M m.End of proof

M± also does not introduce any new ‘lazy’ relations:

Theorem 3.25.+n ≤M± +m1+m2 if and only if n ≤M m1 ◦M m2.
Proof

The right-to-left implication is part 2 of Lemma 3.10. The left-to-right implication follows using Corollary 3.21.End of proof

3.6. The functor from PoMonZ to PoGrp

Definition 3.26

Define a functor imag : PoMonZ → PoGrp as follows:

— M ∈ PoMonZ maps to (M±, ≤M±) (Definitions 3.3 and 3.8).

— An arrow f : M →M′ ∈ PoMonZ acts elementwise on representatives of ∼-equivalence classes. In full:

imag(f )() = () imag(f )(s+m) = imag(f )(s)+f (m) imag(f )(s−m) = imag(f )(s)−f (m)
Lemma 3.27

imag from Definition 3.26 is well-defined and is a functor from PoMonZ to PoGrp.

Proof

Since imag( f ) acts elementwise, imag( f )(s·s′) = imag( f )(s)·imag( f )(s′) and imag( f )() = () by construction. Thus, imag( f ) is a group homomorphism.

We need to check that imag( f ) : imag(M) → imag(M′) is well-defined on ∼-equivalence classes. We sketch the two least trivial cases:

— imag() = idM′ = f (idM) = imag(idM). (This is slightly interesting because it depends on our assumption that f (idM) = idM′.)

— imag(s+m−m) = imag(s)+ f (m)− f (m) ∼ imag(s), and similarly for s−m+m.

Finally, we must check that imag( f ) is monotone. To do this it suffices to show that if p ∈ PM then imag(p) ∈ PM′. It suffices to check the following (note that the second case is not what one might immediately expect):

— If n ≤M m then f (n) ≤M f (m). This follows since f is monotone by assumption.

— If m = m1 ◦M m2 then f (m) ≤M′ f (m1) ◦M′ f (m2). This follows since f is lazy.End of proof

Example 3.28

Consider the natural numbers {0, 1, 2, . . . } with their usual ordering. This can be regarded as an object in PoMonZ, with 0 being the additive identity. Write this object just as N. Consider the function f : N →N defined by

f (n) = n + 1 if n ≠ 0 f (0) = 0.

Then

f (n + m) = n + m + 1 ≤n + 1 + m + 1 = f (n) + f (m),

unless one or both of n and m are zero in which case f (n + m) = f (n) + f (m). So f is an example of a monotone lazy homomorphism and is an arrow in PoMonZ from N to itself.

Then imag(N) = N± is the free group on {0, 1, 2, . . . } and imag( f ) acts pointwise on strings so that for example

imag(f )(+0+1+2) = +0+2+3.

This illustrates why in Definition 2.4 we took homomorphisms, not lazy homomorphisms, between the partially ordered groups; imag( f ) is always a homomorphism, by construction.

3.7. The forgetful functor from PoGrp to PoMonZ

Definition 3.29

Define a functor forg : PoGrp → PoMonZ as follows:

— G ∈ PoGrp maps to G considered as a monoid; write this G̸-1.

— An arrow g : G →G′ ∈ PoGrp maps to itself considered as a (lazy) monoid homomorphism.

Theorem 3.30

imag : PoMonZ → PoGrp is left adjoint to forg : PoGrp → PoMonZ. In symbols:

imag ⊣forg : PoGrp →PoMonZ
Proof

We exhibit the unit and counit of the adjunction. The unit ηM: M → (M±)̸-1 is given by the function mapping m ∈|M| to +m ∈|M±|. By part 1 of Lemma 3.10 this is monotone. By part 2 of Lemma 3.10 and Corollary 3.11 it is a lazy homomorphism (Definition 2.3).

The counit ϵG: (G±)̸-1 →G is given by the function inductively defined on representatives as follows:

ϵG() = idGϵG(s+m) = ϵG(s) ◦G m ϵG(s−m) = ϵG(s) ◦G m-1

By construction this is a group homomorphism. We prove inductively on the definition of ≤(G̸-1)± in Figure 1 that the map is monotone, that is, if s ≤(G̸-1)± s′ then ϵG(s) ≤G ϵG(s′):

— Rule (leq). Suppose +n ≤(G̸-1)± +m because n ≤G̸-1 m. Then n ≤G m and we are done.

— Rule (lazy). Suppose +m ≤(G̸-1)±+m1+m2 because m, m1, m2 ∈|G±| and m = m1 ◦G̸-1 m2. Then by construction

ϵG(+m) = ϵG(+m1+m2),

and we are done.

— Rules (norm) and (mon) follow by inductive hypothesis and by compatibility and transitivity of ≤G. It is not hard to see that the adjunction maps

— g : M± →G ∈ PoGrp to ¯g : M →G̸-1 which takes m to g(+m), and

— f : M →G̸-1 ∈ PoMon to ¯f : M± →G which acts on generators by taking +m to f (m) and −m to f (m)-1.

Verifying naturality is routine.End of proof

Remark 3.31

In Definition 3.12 we defined the measure function ι(-) from |M±| to integers Z considered as a group under addition, for each partially ordered monoid M. It is easy to check that ι(-) is a monotone homomorphism of groups so by Theorem 3.30 it must correspond to a unique monotone lazy homomorphism from M to Z̸-1 (i.e. to Z considered as a monoid under addition).

It is not hard to see that this monotone lazy homomorphism is the trivial function mapping every m ∈|M| to 1 ∈Z. The laziness conditions from Definition 2.3 then correspond to the arithmetic inequalities 0 ≤ 1 and 1 ≤ 2.

One could consider other measure functions coming from different functions out of M; discovering whether any of them are useful, is future research.

From the point of view of these general categorical observations, the injectivity and conservative extension results Theorems 3.22, 3.24 and 3.25 are proved by a detailed analysis of the fine structure of this measure function; we decompose it into ι(-)m for each m—which is not monotone and so is not an arrow in PoGrp—and then reason by a succession of counting arguments which culminate with Proposition 3.19.

4. Commutative and nonassociative generalisation

In this brief section we make a few observations about generalising the proofs.

4.1. Commutative and other generalisations

The key technical lemmas in Subsection 3.4 are by counting arguments, where the counting is performed by the index function of Definition 3.12. Because of this, it is not hard to verify that we can re-play all the proofs for the special cases where M and M± are taken to be abelian.

That is, even if x ◦M y = y ◦M x for all x, y ∈|M|, by our construction in Definition 3.2 it is not the case that +x+y ∼+y+x—what is true is that +x+y ≥M± +(x ◦M y) = +(y ◦M x). However, none of the proofs depend on this; the proofs we have seen only count elements, and we can rearrange elements however we like. So if M is commutative we could make M± be commutative too, just by extending ∼ in Definition 3.2. Then we would obtain an adjunction between abelian monoids and abelian groups ((mon) in Figure 1 would become irrelevant).

Similarly, there is nothing in our proofs that depends on associativity of M, or even on the existence of a unit (we would drop the first laziness condition Definition 2.3).

So it is not hard to generalise or specialise the results of this paper to e.g.

— abelian monoids (monoids in which x ◦ y = y ◦ x) and abelian groups—the theorems in Subsection 3.5 should survive unchanged except that Corollary 3.23 would have to take mi and ni up to some permutative rearrangement,

— semigroups (like monoids, but without a unit) and groups, so that we add both inverses and a unit,

— applicative structures (like monoids, but without a unit and without associativity) and applicative structures with inverses and a unit (but without associativity), and so on. For instance elements of a Boolean algebra form a commutative monoid under ∧; we can turn this into a commutative group. In that sense, the proofs of this paper are robust: so long as none of the congru-ences we choose to put in or take out of Definition 3.2 affect the index function of Definition 3.12, then the proofs should survive.

4.2. Generalisation to categories and groupoids

It is not hard to add types to our results, i.e. to generalise from monoids to categories. We sketch the relevant definitions:

Definition 4.1

Call a category C locally posetal when its hom-sets are enriched to be partial orders, and this is consistent with arrow composition.

A groupoid is a category in which every arrow has an inverse.

A locally posetal category can be viewed as an instance of a 2-category [Leinster, 2004, Cheng and Lauda, 2004] in which the hom-sets are posets.

Definition 4.2

A lazy functor on locally posetal categories F : C →D is a map from objects of C to objects of D and from hom-posets C(X, Y) to D(F(X), F(Y)) such that:

— If f′ ≤ f in C(X, Y) then F( f′) ≤ F( f ) in D(F(X), F(Y)).

— idF(X) ≤ F(idX) for every X ∈ Obj(C).

— F( f ◦ g) ≤ F( f ) ◦ F(g) for every f ∈C(X, Y) and g ∈C(Y, Z).

Write PoCatZ and PoGrpoid for the categories of small locally posetal categories and lazy functors, and small locally posetal groupoids and functors between them, respec-tively.

Definition 4.3

Given a locally posetal category C define a locally posetal groupoid C± as follows:

— Objects of C± are objects of C.

— An arrow is the quotiented well-typed∥ formal sum of arrows from C just as in Definition 3.3, where if f ∈C(X, Y) then + f is given type C±(X, Y) and − f is given type C±(Y, X).

— The partial order is defined on arrows just as in Figure 1 (thus: only on well-typed representatives).

With Definition 4.3 the adjunction of Subsection 3.7 extends to an adjunction between PoCatZ and PoGrpoid. The proof of injectivity is no different from the case of monoids; we just have to keep track of types. So for instance:

Definition 4.4

Define index functions ι(s)m and ι(s) just as in Definition 3.12.

The well-typedness conditions are orthogonal to the counting arguments that follow, and it is easy to replay the proofs to obtain, for instance, the following:

Theorem 4.5

— + f′ ≤+ f in C±(X, Y) if and only if f′ ≤ f, for f′, f ∈C(X, Y).

— + f ≤+g+h in C±(X, Z) if and only if f ≤ g ◦ h in C(X, Z), for f ∈C(X, Z) and g ∈C(X, Y) and h ∈C(Y, Z).

We leave it as an exercise to the interested reader to fill in the details of the relevant generalisations. Since our proofs are by counting arguments, the generalisation to the typed case introduces extra richness but no essential difficulties.

5. Sets with an action

We now extend the results of Section 3 to sets with a monoid action, showing how to extend a partially ordered set with an M monoid action to a partially ordered set with an M± group action.

Examples of sets with a monoid action are common in computer science, including:

— Syntax acted on by a monoid of substitutions.

— Integers Z acted on by the monoid of functions from Z to Z.

— A domain model of the λ-calculus D acted on by DD ∼= D considered as a monoid under functional composition.

So, it is an interesting question to see how our results can be extended.

Subsection 5.1 contains the basic definitions, several key technical lemmas, and one important result (Theorem 5.9). Subsection 5.2 defines the relevant adjunctions between the categories of partially ordered sets with a compatible M-action and lazy functions between them, and of partially ordered sets with an M±-action and functions between them.

The proofs are easier than in Section 3, but they are not trivial and do not follow by abstract nonsense. Certainly, if we can extend monoids to groups then we can extend sets acted on by monoids to sets acted on by groups in a standard way.

Just as in Section 3, what does not follow from abstract nonsense is injectivity results like Theorem 5.9 or Proposition 5.15, which are proved, just as in Section 3, by careful counting.

5.1. Construction of the sets with an action

Definition 5.1

Suppose (M, ≤M) ∈ PoMonZ. A poset with an M-action X is a tuple (|X|, ·X, ≤X) of a carrier set |X|, a partial order ≤X, and an action x·Xm such that:

— If x ≤X x′ and m ≤M m′ then x·Xm ≤ x′·Xm′ (the order on X is compatible with that on M).

— x·XidM = x and (x·Xm)·Mm′ = x·X(m ◦M m′) (the action is a monoid action).

We define a poset with a G action similarly, for (G, ≤G) a partially ordered group.

Suppose a poset with a compatible M-action X = (|X|, ·M). We show how to extend this to a set with an M±-action.

Definition 5.2

Define ≤ to be the least transitive relation on |X| × |M±| such that:

(absorb)(x·Xm, g) ≤(x, +m ◦M± g)x ≤X x′g ≤M± g′(compat)(x, g) ≤X± (x′, g′)(x, g) ≤(x′, g′) (x′, g′) ≤(y, h)(trans)(x, g) ≤(y, h)
Lemma 5.3

The ordering ≤ is compatible, in the sense that (x, g) ≤ (y, h) implies (x, g ◦M± g′) ≤ (y, h ◦M± g′).

Proof

By an easy induction on the rules in Definition 5.2.End of proof

Remark 5.4

By assumption ≤X is reflexive and by construction so is ≤X±, thus by (compat) ≤ is too. We still need to prove that ≤X± is antisymmetric, that is, we need to show that X± is a partially ordered set and not only a preordered set. This we do next, culminating with Theorem 5.9.

Lemma 5.5

If (x, g) ≤ (y, h) then there exist m1, . . . , mk ∈|M| such that +m1. . . +mk ≤M± h ◦M± g-1.

Proof

By an easy induction on the rules in Definition 5.2.End of proof

Lemma 5.6

If (x, g) ≤ (y, h) then ι(g) ≤ι(h).

Proof

By induction on Definition 5.2:

— The case of (absorb). It is a fact that ι(g) + 1 = ι(m ◦M± g).

— The case of (compat). If g ≤M± h then by part 2 of Lemma 3.16 ι(g) ≤ι(h).

— The case of (trans). A fact of numbers.End of proof

Lemma 5.7

If (x, g) ≤ (y, h) and (y, h) ≤ (z, g) then g = h.

Proof

Suppose (x, g) ≤ (y, h) and (y, h) ≤ (z, g). By Lemma 5.6 ι(g) = ι(h). Using this fact and Lemma 5.5 it follows that g ≤M± h and h ≤M± g. Therefore by Theorem 3.22 g = h.End of proof

Lemma 5.8

If (x, g) ≤ (y, g) then x ≤X y.

Proof

By induction on the rules in Definition 5.2.

— (absorb) cannot be used since g = +m ◦M± g is impossible since ι(g) ≠ ι(+m ◦M± g) = 1 + ι(g) and this contradicts part 2 of Lemma 3.16.

— The case of (compat) is immediate.

— For (trans), suppose (x, g) ≤ (x′, g′) and (x′, g′) ≤ (y, g). By Lemma 5.7 g′ = g. We use the inductive hypothesis and transitivity of ≤X.End of proof

Theorem 5.9. If (x, g) ≤(y, h) and (y, h) ≤(x, g) then x = y and g = h.
Proof

By Lemmas 5.7 and 5.8 and the fact that X and (by Theorem 3.22) M± are partially ordered sets.End of proof

5.2. The natural adjunction

Definition 5.10. Let X± have underlying set |X| × |M±| and action ·X± given by (x, g)·X±h = (x, g ◦M± h).
Definition 5.11

Suppose M is a partially ordered monoid. Write MPoSetZ for the category such that:

— An object X is a poset with a compatible M-action.

— An arrow f : X →X′ is a function f ∈|X| →|X′| such that

– x ≤X x′ implies f (x) ≤X′ f (x′).

– f (x·Xm) ≤X′ f (x)·X′m.

Suppose G is a partially ordered group. Write GPoSet for the category such that:

— An object Y is a poset with a compatible G-action.

— An arrow f : Y →Y′ is a function f ∈|Y| →|Y′| such that:

– y ≤Y y′ implies f (y) ≤Y′ f (y′).

– f (y·Yg) = f (y)·Y′g.

Definition 5.12

Let imag : MPoSetZ →M±PoSet have the following action:

— An object X maps to X± (Definition 5.10).

— An arrow f : X →X′ maps to imag( f ) : X± → (X′)± which is defined by (x, g) maps to ( f (x), g).

Let forg : M±PoSet →MPoSetZ have the following action:

— An object Y (which is a set with an M± group action) maps to Y considered as a set with an M action; write this YM.

— An arrow f : Y →Y′ ∈M±PoSet maps to itself considered as a monoid homomorphism.

We consider an example of Definition 5.12 in Section 6.

Lemma 5.13

imag from Definition 5.12 is a functor from MPoSetZ to M±PoSet.

Proof

Suppose f : X →Y ∈MPoSetZ. We have two things to check:

— imag( f ) is monotone. That is, we need to prove that if (x, g) ≤ (y, h) (Definition 5.2) in |X| × |M±| then ( f (x), g) ≤ ( f (y), h) in |X′| × |M±|. We do this by induction on the derivation of (x, g) ≤ (y, h). The case of (absorb) follows from the assumption that f (x·Xm) ≤X′ f (x)·X′m and using (compat); the case of (compat) is a structural fact; transitivity also follows.

— imag( f ) is a homomorphism. That is, we need to prove that ( f (x), g)·X±h = ( f (x), g ◦M± h). But this holds direct from Definition 5.10.

Proposition 5.14. imag ⊣forg : M±PoSet →MPoSetZ.
Proof

The unit ηX maps x ∈|X| to (x, ()) ∈|(X±)M|. We check that ηX(x·Xm) ≤ ηX(x)·(X±)Mm:

ηX(x)·(X±)Mm = (x, ())·X± +m = (x, +m) ≥(x·Xm) = ηX(x·Xm)

The counit ϵY : (YM)± →Y maps (x, g) to x·YϵM±(g). We check that ϵY(x, g)·Yh = ϵY(x, g ◦M± h):

ϵY(x, g)·Yh = (x·Yg)·Yh = x·Y(g ◦M± h) = ϵY(x, g ◦M± h)End of proof

5.3. More detailed analysis for the partial order

In this subsection we go deeper into the structure of objects in M±PoSet, asking the following question: if x·g ≤ y·h and +m ≤ g, can y·h imitate this behaviour in some compatible sense?

This is Proposition 5.15—the reader who knows about process calculi can think of this loosely as a simulation result in the sense of e.g. [Milner, 1999, Definition 3.3].

Proposition 5.15

Suppose X is a set with an M-action. Suppose (x, g) ≤ (y, h). Then: 1 If +m ≤M± g then there exists n ∈|M| such that +n ≤M± h and x·Mm ≤X y·Mn. 2 If () ≤M± g then either

— () ≤M± h and x ≤X y, or

— there exists n ∈|M| such that +n ≤M± h and x ≤X y·Mn.

Proof

For the first part we work by induction on the derivation of ≤.

— The case of (absorb). By (absorb) (x·Xm, g) ≤ (x, +m ◦M± g). Suppose +n ≤M± g. Then +(m ◦M n) ≤M± +m+n ≤M± +m ◦M± g, and it is a fact that (x·Mm)·Mn = x·M(m ◦M n). It follows that (x·Mm)·Xn ≤M x·M(m ◦M n).

— The case of (compat). Suppose (x, g) ≤ (x′, g′) because x ≤X x′ and g ≤M± g′. Suppose +m ≤M± g. Then also +m ≤M± g′ and x·Mm ≤X x′·Mm.

— The case of (trans). Suppose (x, g) ≤ (y, h) because (x, g) ≤ (x′, g′) and (x′, g′) ≤ (y, h). Suppose +m ≤M± g. By inductive hypothesis there exists +m′ ≤M± g′ such that x·Xm ≤X x′·Xm′. Also by inductive hypothesis there exists +n ≤M± h such that x′·Xm′ ≤X y·Xn. The result follows by transitivity of ≤X. The second part is also by induction.

— The case of (absorb). By (absorb) (x·Xm, g) ≤ (x, +m ◦M± g). Suppose () ≤M± g. Then it follows that +m ≤M±+m ◦M± g and it is a fact that x·Mm = x·Mm. If m ≤M± g then we proceed as in the first part of this lemma.

— The case of (compat). Suppose (x, g) ≤ (x′, g′) because x ≤X x′ and g ≤M± g′. Suppose () ≤M± g. Then also () ≤M± g′ and x ≤X x′. If m ≤M± g then we proceed as in the first part of this lemma.

— The case of (trans) is similar.End of proof

6. An example: substitutions

Consider some first-order syntax L (e.g. r ::= a | f(r, . . . , r) for some term-formers f and variables a) and consider substitution on it r[a↦→s] [Baader and Nipkow, 1998]. Write Σ for the set of substitutions on L with functional composition.

Let σ range over elements of Σ. Substitutions form a submonoid of the function space on L, that is, we can view Σ as a subset Σ ⊆LL that is closed under functional composition (so if σ, σ′ ∈Σ then σ ◦σ′ ∈Σ and maps a to (σ(a))σ′) and contains the identity function id.

Consider Σ as trivially partially ordered, so that σ ≤σ′ if and only if σ = σ′. Similarly consider L as trivially partially ordered.

Then we can form Σ± the imaginary group of substitutions, and L± the set of terms lazily acted on by substitutions.

What do these look like?

6.1. Substitutions just on variables

Consider the special case where there are no term-formers so that L is just the set of variables {a, b, c, . . . }. For brevity write • for ·L±. Then:

— a • [a↦→b] ≥b.

— b • [a↦→b] ≥b.

— a • [a↦→b]-1 ≥ a. We deduce this by taking a • [a↦→b] ≥ b and applying [a↦→b]-1 to both sides.

— a • [a↦→b]-1 ≥ b is deduced similarly.

In view of the inequalities above, we can think of a • [a↦→b]-1 as being ‘like the un-ordered pair {a, b}’. However, this is only an analogy; a • [a↦→b]-1 displays behaviour that is not like the behaviour of {a, b}. In particular, a • [a↦→b]-1 ≠ b • [b↦→a]-1, yet (by symmetry) both are ‘like {a, b}’.

6.2. Substitutions on terms

Now suppose that there are term-formers. Then r • [a↦→s] ≥ r[s/a] (where r[s/a] is the term obtained by really replacing a by s in r). Also, r • [a↦→s]-1 ≥ r′ for any r′ such that r′[s/a] = r.

Now consider a rewrite rule R = (s1 → s2) in the sense of first-order rewriting [Baader and Nipkow, 1998]. Then if r rewrites to r′ with rule R then (r • [a↦→s1]-1) • [a↦→s2] ≥ r′.

For instance, given 0-ary term-formers 1 and 2 (i.e. constant symbols) it is easy to verify that (1 • [a↦→1]-1) • [a↦→2] ≥ 2. This encodes, in a certain sense, the rewrite rule 1 → 2.

By combining substitutions and their lazy inverses, it is not hard to encode arbitrary first-order rewriting in L±. As an easy corollary, ≤L± is undecidable—it suffices to write out a rewrite system for combinators S and K [Hindley and Seldin, 2008, Section 2].

So equality in Σ is decidable (we just unfold the substitution) but equality in Σ± is not (given even two term-formers, lazy substitutions can encode undecidable computations).

7. Conclusions

We set off wanting to homomorphically inject every monoid into a group. This is impossible, but we can do something similar which perhaps captures the spirit of this: we can inject every monoid into a partially ordered group.

There is an appealing computational interpretation for this, in which the groups are interpreted as ‘executable plans’ and the monoids as ‘computation steps’.

In order to expand this observation to a categorical adjunction we discover, some-what surprisingly, an adjunction between the category of partially ordered monoids and lazy homomorphisms and the category of partially ordered groups and homomorphisms (we do not need this latter to be lazy).

We also obtain similar results for sets with an action. This is motivated by the spirit of Cayley’s theorem which allows every monoid and group to be represented as the action on a set.†† These also display the lazy homomorphism/homomorphism structure.

The technical highlights of this paper are in the very specific design of the definitions, notably Definitions 3.8, 3.12, and 5.2, and in the proofs of Theorems 3.22, 3.24 and 5.9. The proofs involve some detailed combinatorial arguments, and which rely on technical lemmas the choice of which is non-evident: specifically these are Lemma 3.14 to Proposition 3.19, and Lemma 5.5 to Lemma 5.8.‡‡

In conclusion, let us recall why this is interesting. Monoids are an abstract model of computation, which preserves only the idea that there are some operations (including a ‘do nothing’ identity operation) and operations can be composed. Groups are a similar model, but for reversible operations.

We have given a sense in which any monoid can systematically be injected into a universe of reversible operations. In that sense, the results in this paper give a new map for moving between irreversible and reversible computation.

Related work

To the best of our knowledge the connection we have observed between partially ordered monoids and lazy morphisms, and partially ordered groups and morphisms, is new. It sheds quite an interesting light on these structures and suggests a new way of (and indeed, a new motivation for) looking at them, one coming from the theory of logic and computation.

Conditions for being able to embed (homomorphically inject) a monoid in a group were considered by Mal’cev [Mal’cev, 1937, 1939] and Lambek [Lambek, 1951]; these are infinite sets of Horn clauses that characterise the class of monoids that inject into some group. This was later generalised to categories and groupoids by Johnstone [Johnstone, 2008]. It should be clear that we are solving a distinct problem; we take all monoids, but weaken ‘homomorphism/functor’ to ‘lazy homomorphism/functor’.§§ An inverse semigroup has a natural partial order given by x ≤ y when x = ye for some idempotent e. A prehomomorphism of inverse semigroups is a function θ such that θ(xy) ≤θ(x)θ(y). Finally, an inductive groupoid is a groupoid whose hom-sets form a meet semilattice and an ordered functor on them is monotone on the ordering of the hom-sets. This extends by the Ehresmann-Schein-Nambooripad theorem to an isomorphism between the categories of inverse semigroups and prehomomorphisms, and inductive groupoids. For full definitions and proofs see [Lawson, 1998]. This theorem expresses an equivalence between two ways of capturing the notion of “partial symmetry ordered by the size of the domain”; one notion expressed by semigroups (untyped) and another by inductive groupoids (typed). There is a similarity to our results, but they are not the same. Superficially, we use monoids (but we could drop the identity) and we map to partially-ordered groups (but we could generalise to categories and locally posetal groupoids). A deeper difference is that in our adjunction the unit is not an identity map; we do not build an isomorphism. That is, our main result is not an equivalence, it is an embedding. It remains to be seen if a variation of our result is possible, which might be more aggressive in quotienting the partially ordered group when mapping back to monoids, and so recover something more like the equivalence theorem above as a special case.

A number of computational systems have been studied which bear reversibility in mind, motivated by three facts:

— Physical systems are time-reversible, so reversible computation is, in fact, the computation of the physical world as we know it. Most recently this is relevant in the design of DNA circuits, where the possibility of a computation running ‘backwards’ in some chemical soup in the test-tube must be taken into account.

— A corollary of Landauer’s principle is that reversible computation dissipates less heat (i.e. irreversibility is caused by increasing entropy, which corresponds to erasing information). Thus from the point of view of designing circuits, it is relevant to keep track of where information is lost and heat is generated.

— Quantum computation has aroused much interest and here, the basic model of computation is again reversible (with irreversibility caused by measurement).

Relevant publications are as follows:

— [Toffoli, 1980] introduced the Toffoli gate, which is a universal reversible logic gate

If so, then something easier would be sufficient to begin with, since our constructions are orthogonal to whether the monoid is commutative: a commutative monoid is embeddable in a group if and only if it satisfies cancellation: xy = xz ⇒ y = z.

(see also [Storme et al., 1999], which studies universal reversible logic gates in general).¶¶

— Bennet’s classic paper [Bennett, 1973] studied the notion of a reversible Turing ma-chine.

— For reversible computation in biologically inspired computing see [Danos and Krivine, 2004, Phillips and Ulidowski, 2007]; for quantum computation good places to start reading are [Spiller, 1998] and [Kitaev et al., 2002, Section 7].

— The connection between reversibility, entropy, and computation is discussed in [Keyes and Landauer, 1970, Landauer, 1961].

The papers above are about concrete reversible computational structures; our concern is more abstract. We consider how, given a possibly irreversible system represented abstractly as a monoid, we can generate a corresponding reversible system represented as a group, which corresponds to it in some natural way.

So on the topic of reversible computation, we hope that the constructions in this paper are interesting theoretical tools but the reader should be clear that we do not pretend to have provided evidence that they are directly computationally useful. In particular, we have not studied the representation of this group aside from that given by its construction. We note that determining the partial order in the group may be strictly more complex than determining equality in the monoid, as Subsection 6.2 illustrates, where we note that ≤M± may be undecidable even if ≤M is decidable.

Of course, equality of most non-trivial computational systems is undecidable, so this is to be expected and is not the end of the world. We can reasonably hope that the constructions of this paper might be useful as a framework with which to design invertible programming systems; the methodology would be, in principle, to design a non-invertible one and apply (-)± (of course there is more to a programming language than that, but the underlying idea stands). We now discuss further future work:

Future work

Briefly, we can suggest the following future work and applications:

— Generalisation to weaker monoid-like structures: We noted in Section 4 that the proofs in this paper seem quite robust, and it should be possible generalise the ideas in this paper to the cases of e.g. commutative monoids, semigroups, and applicative structures. Similarly, a monoid is a special case of a category with one element. It is natural to take the results of this paper and extend them to categories. Thus, given an input category we can generate a category (whose hom-sets are partially ordered) in which every arrow is invertible.

— Algorithms enriched with inverses: Substitutions on syntax form a monoid. Therefore, it is possible to consider syntax enriched with invertible substitutions, as hinted at in Section 6.

A little more work is needed to enrich syntax with invertible substitutions, but it can be done: we need to build inductive definitions that include inverses of substitutions, but a corollary of Theorem 3.30 is that the ‘lazy’ functor preserves colimits, thus it preserves least upper bounds of countably ascending chains, thus by general nonsense Theorem 3.30 tells us that we can indeed interleave (-)± with the construction of an inductive datatype. It remains to study the properties of such syntax, e.g. whether unification has most general unifiers. We believe that it does, because substitutions can be inverted.∥∥ An algorithm would be theoretically interesting, though not necessarily practical since equality might not be decidable. Of course, higher-order unification [Dowek, 2001] is also not decidable and that does not stop useful heuristics from being constructed that seem to work well in practice, e.g. [Huet, 1975]. So syntax with invertible substitutions is an interesting topic—it might even be useful.

— Computational models: Taking up the comments in the Related work, it remains to investigate the application of our construction to monoids or similar structures which are specifically designed to model computation: such as a monoid of functions of the untyped λ-calculus under functional composition; or a monoid of processes under parallel composition [Milner, 1999, Danos and Krivine, 2004]; or the applicative structure of a model of the untyped λ-calculus.

— Generalisation to richer structures: Suppose the monoid has extra structure (e.g. the algebraic study of λ-models has met with some success [Manzonetto and Salibra, 2010]). This structure transfers to the lazy case.
It remains to study how algebraic properties of the monoid carry across; how does the ‘algebra’ of M compare with a corresponding ‘(lazy) algebra’ of M±? If the partial order on the monoid is part of a domain [Abramsky and Jung, 1994], what are the properties of the partial order on its free group?

— Lattice properties of the free group: On a related note, we can ask whether if M is a partial order with further structure, such as being a lattice, what further structure M± will have. For instance, elements of a Boolean algebra B form a commutative monoid under conjunction and a lattice under implication (x ≤ y when x ∧ y = x) so it is interesting to ask what kind of logical entity B± would be (possibly the commutative version, as discussed in Section 4). This seems related, at least in spirit, to the anti-formulae (formulae which when added to a database delete an item from it) considered in [Gabbay et al., 2004]. Is there some sense in which the ‘logic’ of B extends to a ‘logic’ of B±?

Last but not least is this: the proofs in this paper are unambiguous, but a higher-level explanation of why they work is currently lacking. That is, the counting arguments in this paper work, but they do so ‘by magic’: some general conceptual framework of which the counting arguments are an instance, is an open question.

References

Samson Abramsky and Achim Jung. Domain theory. In Handbook of Logic in Computer Science: Semantic Structures, volume 3, pages 1–168. Oxford University Press, 1994.

Franz Baader and Tobias Nipkow. Term Rewriting and All That. Cambridge University Press, 1998.

Charles H. Bennett. Logical reversibility of computation. IBM journal of Research and Development, 17(6):525–532, 1973.

Eugenia Cheng and Aaron Lauda. Higher-dimensional categories: an illustrated guide book, August 2004. Notes prepared for IMA workshop.

Vincent Danos and Jean Krivine. Reversible communicating systems. In Proceedings of the 15th International Conference on Concurrency Theory (CONCUR 2004), pages 292– 307. Springer, 2004.

Gilles Dowek. Higher-order unification and matching. In Handbook of automated reason-ing, pages 1009–1062. Elsevier, 2001.

Dov M. Gabbay, Odinaldo Rodrigues, and John Woods. Belief contraction, anti-formulae and resource overdraft: Part II deletion in resource unbounded logics. In Logic, Epistemology, and the Unity of Science, volume 1, pages 291–326. Springer, 2004.

Andrew M. W. Glass. Partially ordered groups, volume 7 of Series in Algebra. World Scientific, 1999.

Maurice Herlihy and J. Eliot B. Moss. Transactional memory: Architectural support for lock-free data structures, volume 21(2). ACM Press, 1993.

J. Roger Hindley and Jonathan P. Seldin. Lambda-Calculus and Combinators, An Introduction. Cambridge University Press, 2nd edition, 2008.

Gérard Huet. A unification algorithm for typed λ-calculus. Theoretical Computer Science, 1:27–57, 1975.

Peter T. Johnstone. On embedding categories in groupoids. Mathematical Proceedings of the Cambridge Philosophical Society, 145:273–294, 2008.

Robert W. Keyes and Rolf Landauer. Minimal energy dissipation in logic. IBM Journal of Research and Development, 14:153–157, 1970.

Alexi Yu Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. Classical and quantum computation, volume 47 of Graduate Studies in Mathematics. American Mathematical Society, 2002. Translated from the Russian by Lester J. Senechal.

J. Lambek. The immersibility of a semigroup into a group. Canadian Journal of Mathematics, 3:3443, 1951.

Rolf Landauer. Irreversibility and heat generation in the computational process. IBM Journal of Research and Development, 5:183–191, 1961.

Mark V. Lawson. Inverse semigroups: the theory of partial symmetries. World Scientific, 1998.

Tom Leinster. Higher Operads, Higher Categories, volume 298 of London Mathematical Society Lecture Note Series. Cambridge University Press, 2004.

Chuck Liang and Dale Miller. Focusing and polarization in linear, intuitionistic, and classical logics. Theoretical Computer Science, 410(46):4747–4768, 2009.

Anatolii I. Mal’cev. On the immersion of an algebraic ring into a field. Mathematische Annalen, 113:686–691, 1937.

Anatolii I. Mal’cev. On the embedding of associative systems in groups i. Matematich-eskii Sbornik, 6(48)(2):331–336, 1939. In German: Über die Einbettung von assoziativen Systemen in Gruppen.

Giulio Manzonetto and Antonino Salibra. Applying universal algebra to lambda calculus. Journal of Logic and computation, 20(4):877–915, August 2010. .

Robin Milner. Communicating and mobile systems: the pi-calculus. Cambridge University Press, 1999.

Eric Nummela. Cayley’s theorem for topological groups. American Mathematical Monthly, 87(3):202–203, 1980.

Iain Phillips and Irek Ulidowski. Reversing algebraic process calculi. Journal of Logic and Algebraic Programming, 73(1-2):70–96, 2007.

Greg Restall. An Introduction to Substructural Logics. Routledge, 1999.

Timothy P. Spiller. Basic elements of quantum information technology. In Introduction to Quantum Computation and Information, pages 1–28. World Scientific, 1998.

Leo Storme, Alexis De Vos, and Gerald Jacobs. Group theoretical aspects of reversible logic gates. Journal of Universal Computer Science (J.UCS), 5(5):307–321, 1999.

Tommasso Toffoli. Reversible computing. In Proceedings of the 7th Colloquium on Au-tomata, Languages and Programming, pages 632–644. Springer, 1980.

Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, September 2004. .

Notes

† Many thanks to Phil Scott and to an anonymous referee, without whom the paper would not have attained its current form. The first author acknowledges the support of the Leverhulme trust and of grant RYC- 2006-002131 at the Polytechnic University of Madrid; the second author acknowledges the support of Cornell University, New York and of the Institut Mittag-Leffler, Sweden. ↩

† That is, specialising laxness to the case of a locally posetal 2-category on one object, a.k.a. partially ordered monoid. ↩

‡ In logical terminology, we are observing that we have contraction on the right but not on the left. Contraction in logic is a rule that allows us to convert from A ∧ A to A. If A represents an assertion and ∧ represents logical conjunction, then this is immediate. If A represents a pound coin and ∧ represents addition, then this may not be so. ‘Contraction on the left’ means we may go from A to A ∧ A (like truth, or taxes) whereas ‘contraction on the right’ means we may go from A ∧ A to A (like truth, or our bank account). More on this is in the field of substructural logics, and the interested reader is referred elsewhere [Restall, 1999]. ↩

§ Recall that a preorder is reflexive and transitive, but not necessarily antisymmetric. A partial order is an antisymmetric preorder. ↩

So if f′ ≤ f are two arrows in C(X, Y) and g′ ≤ g are two arrows in C(Y, Z) then f ◦ g ≤ f′ ◦ g′ in C(X, Z). ↩

∥ We just do the obvious thing here: well-typed means, for instance, that we only allow ourselves to write + f +g when f ∈C(X, Y) and g ∈C(Y, Z). It is easy to see that e.g. + f − f is well-typed and in C(X, X). ↩

†† Some interesting historical comments on the the attribution of Cayley’s name to this family of results is in [Nummela, 1980]—Cayley certainly did not prove it for monoids. Still, ‘Cayley’s theorem’ is the standard word for this kind of result. ↩

‡‡ Framing the question and then finding the proof structure took two years, from start to finish. ↩

§§ One could study our construction in the special case that the Mal’cev or Lambek conditions are satisfied. ↩

¶¶ So: one can build any circuit out of NAND gates, thus a NAND gate is a universal logic gate; similarly, one can build any reversible circuit out of Toffoli gates. ↩

∥∥ One of the original motivations for this work comes from nominal unification [Urban et al., 2004]. This is based on permutations, which are invertible, and because of that nominal unification has most general solutions. The question the first author asked which motivated this line of research was: Suppose substitutions had inverses too; would something like higher-order unification then have most general solutions? Preliminary calculations suggest that the answer is yes. ↩