Under consideration for publication in Math. Struct. in Comp. Science
Imaginary groups: lazy monoids and reversible computation
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 ) f (m) f (). Every monoid can be endowed with the discrete partial ordering (m if and only if 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].
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 . This is given to us and it was not designed from the start to be reversible. How can we ‘add an undo function’ to , 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 , does there exist a group and an injective monoid map ? 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, needs to faithfully represent the original states and operations. Otherwise, we could just map all of 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 , calculate , 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:
Consider the two-element monoid 0, 1 with
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 0, 1 then 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 a partially ordered group , and we will exhibit a lazy monoid homomorphism from to . 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 as a set of operations, and monoid composition as their composition, and both of these may be irreversible. Then the ‘lazy’ group 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:
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 to its free group with added ‘imaginary’ inverse . Constructing the underlying set of 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
Consider the following axioms:
— A group is a tuple (, , id, -1) of a carrier set , a composition mapping to , an element id , and an inverse map -1 mapping to , satisfying (assoc), (id), and (inv).
— A monoid is a tuple (, , id) as above, satisfying (assoc) and (id).
A (compatible) order on a monoid is a partial order such that x y implies x z y z and z x z y.
— A partially ordered monoid is a pair (, ) of a monoid and a compatible order on .
— A partially ordered group is a pair (, ) of a group and a compatible order on , considered as a monoid.
If is a group, the first equation can be deduced from the second, as can the identity f (x f (x)-1; but in general both axioms are required.
Suppose now that and are partially ordered monoids. Call a function f a lazy homomorphism when
Call f monotone when x y implies f (x) f (y).
We discuss this definition in Subsection 2.2.
— 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.
For the reader’s convenience we explicitly unpack what it is to be an arrow in PoMonZ. An arrow f : (, ) (, ) is a function f from to such that: 1 f () (laziness). 2 f (x y) f (x) f (y) (laziness). 3 x y implies f (x) 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:
To see in elementary terms why lax homomorphisms are natural, note that if we consider the inequality f ( ) f () f () and imagine what its 0-ary version should be, we obtain f () .
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:
— f () means if we apply f to the identity and execute, we get the identity.
— f (x y) f (x) 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 first, and then applying f .
We call this lazy by analogy with lazy evaluation in the -calculus.
Second, a mathematical intuition: We want to inject into the ‘imaginary’ group which augments 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 be the one-element monoid with monoid composition . Then 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 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 to . 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:
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: 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 for () (Definition 3.29).
3. The imaginary group
Our construction is the simplest possible; given a monoid we take strings of elements-with-a-polarity or and quotient such that mm becomes equal to the empty string. We immediately obtain an imaginary group . It is the free group over 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 in Figure 1, in submonoid style. The order is sound by construction; the rule (leq) makes sure that if n m in then n m in .
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 we consider and build the free group generated by this set.
Given a set X write Xstring for the set inductively defined by:
Call () the empty string. Write string concatenation as st. We may elide the initial (), so for instance we may write m as shorthand for ()m.
So if X 1, 2, 3, . . . then intuitively Xstring is the set of lists of nonzero integers.
Define to be the least equivalence relation on string such that:
2 If s and t then st .
Given a monoid define the free group over as follows:
— The carrier set is string quotiented by .
— Group composition is given by concatenation of representatives.
We may write m for both m and for the -equivalence class of m.
is indeed a group, with the natural composition, identity, and inverse.
2 Suppose is the one-element monoid with underlying set and monoid composition (we also saw this in Subsection 2.2). Then 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 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 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.
— Suppose , , -1) is a group. Call X normal when x X and y implies y x y X.
— Suppose is a monoid. Call X a submonoid when id X and when x X and y X implies x y X.
Suppose P is a normal submonoid of a group . Then write x y when y x P.
We consider each property in turn:
— By assumption id P; it follows that m m and so is reflexive.
— Suppose x y and y z. This means that y x P and z y P. Since P is a monoid also z x P. It follows that is transitive.
— Suppose x y. This means that y x P. To check that is compatible we need to verify that for any z , z x z y and x z y z. Since P is a normal subgroup also z y x z P, and this means that z x z y.
3.3. The partial order
Now the non-standard part begins. Fix a partially ordered monoid (, ). In Definition 3.3 we saw how to construct the free group generated by .
We show how to extend to a preorder on . By Proposition 3.7 it suffices to exhibit a normal submonoid of . 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.
A few words on the rules in Figure 1.
— (leq) expresses that n m implies n m.
— (lazy) expresses that ( ) .
— (norm) expresses that if p q then p r q r (left-compatibility is automatic by construction; see Proposition 3.7).
— (mon) expresses transitivity of .
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.
1 If n m then n m. 2 If n then n .
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 ( ) f () f () from Definition 2.3. What corresponds to the condition f () from Definition 2.3? In fact, this is derivable:
3.4. Technical lemmas
This is where the maths begins to become non-trivial. In Definition 3.8 we defined a relation on . It is easy to see that this is reflexive and transitive; but is it antisymmetric? In other words, is a partial order as the caption to Figure 1 suggests, and not just a preorder? Also, is a conservative extension of 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.
In words, we can say that (s) sums exponents.
The index functions are well-defined as functions on p . That is, if p then for every s, p and every m it is the case that (s)()m and (therefore) (s().
If () p and (p 0 then every proof that p P, does not mention (lazy).
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.
If () p and (p) 0 for all m, then p .
We first use Lemma 3.14 to see that the derivation of () p cannot use rule (lazy). The rules (norm) and (mon) do not affect index at all.
Let n be -minimal in p. This n must have been introduced by (leq) for some n m. Since n is -minimal in p there is no other instance of (leq) for n. By assumption (p) 0, so it must be that n m. The result follows.
1 If p P then (p) 0. 2 If p q then (p) (q).
The first part is by a routine induction on the rules in Figure 1. For the second part, suppose p q. Then () p q. By part 1 of this result, (p q) 0. It is a fact that (p q(p(q). The result follows.
If . . . . and . . . . then k l.
Recall part 1 of Example 3.5 and take to be the monoid of natural numbers 0, 1, 2, 3, . . . under addition (so 0 is the identity). Then by Corollary 3.17 34 7, since (34 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) 0. In order for everything to balance out, there must be some n such that (p) 0—that is, such that there is a deficit of ns—and since p is a finite structure we can find an -minimal such n in p. This is what Proposition 3.19 asserts, and this property turns out to be key.
Suppose p P and (p 0. Suppose (p) 0. Then there exists some -minimal n m such that (p) 0.
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, but we still need to show that (p) 0 and (p) 0. By assumption (mn) 0. This means that m n. It follows by arithmetic that (mn) 0.
— The case of (lazy). If (( 0 then either m id or m id and id or m id and id. All cases are impossible because we assumed (p) 0 (for some m).
— The case of (norm). From the fact that (p)(g p g)m.
— The case of (mon). Suppose (p ) 0. There are now two cases:
– The case (p) 0. By inductive hypothesis there exists a -minimal n m such that (p) 0. There are now two sub-cases:
The case ()(p)n. In this case (p ) 0 and we are done.
The case ()(p)n. In this case, in particular, () 0. So there exists some -minimal n such that () 0. By assumption n was minimal, so (p) 0. It follows that (p ) 0. By transitivity m and we are done.
– The case (p) 0. . . is symmetric with the case ()(p)n.
Proposition 3.19 has a natural dual:
Suppose p P and (p 0. Suppose (p) 0. Then there exists a -maximal n m such that (p) 0.
Suppose p P and (p 1. Then there exist n, , such that n and (p)1 and (p)m 1 and (p)m 1.
By induction on the derivation that p P. We consider each rule in turn:
— The case of (leq) is not relevant since (mn 0.
— The case of (lazy). By construction, since .
— The case of (norm). From the fact that (p)(g p g)m.
— The case of (mon). Suppose (p 1. Then by part 1 of Lemma 3.16 precisely one of (p 1 and ( 0 or ( 1 and (p 0 must hold. Suppose (p 1 and ( 0; the other case is symmetric and we will not consider it. By inductive hypothesis we obtain n, , and as required, in p. Now if ()(p)n then we use Proposition 3.19 to obtain an n such that and then use transitivity of . Similarly if ()m(p)m1 then we use Proposition 3.20 and compatibility of the partial order with . Similarly for . The result follows.
3.5. The preorder is a partial order and the natural map is injective
Suppose p q and q p. Write P q p-1 and Q p q-1. Thus () P and () Q. Also by part 2 of Lemma 3.16 (p(q) and so (P 0.
Now if (P) 0 for all m then using Corollary 3.15 it follows that p q and we are done.
So suppose (P) 0 for some . We will deduce a contradiction. If (P) 0 for some then (P) 0 for some m. By Proposition 3.19 (P) 0 for some n m and n is -minimal such amongst monoid elements mentioned in P. But then (Q) 0 and by Proposition 3.19 again (Q) 0 for some n. This contradicts minimality of n.
We immediately apply Theorem 3.22 to strengthen Corollary 3.17:
If . . . . and . . . . then k l and for every 1ik.
Theorem 3.24 is a conservative extension result expressing that injects into considered as a partially ordered monoid:
also does not introduce any new ‘lazy’ relations:
3.6. The functor from PoMonZ to PoGrp
Since imag( f ) acts elementwise, imag( f )(s imag( f )(s)imag( f )() and imag( f by construction. Thus, imag( f ) is a group homomorphism.
We need to check that imag( f ) : imag() imag() is well-defined on -equivalence classes. We sketch the two least trivial cases:
— imag f ( imag(). (This is slightly interesting because it depends on our assumption that f ( .)
— imag(smm imag(s) f (m) f (m) imag(s), and similarly for smm.
Finally, we must check that imag( f ) is monotone. To do this it suffices to show that if p then imag(p) . It suffices to check the following (note that the second case is not what one might immediately expect):
— If n m then f (n) f (m). This follows since f is monotone by assumption.
— If m then f (m) f () f (). This follows since f is lazy.
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 . Consider the function f : defined by
Then
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 to itself.
Then imag( is the free group on 0, 1, 2, . . . and imag( f ) acts pointwise on strings so that for example
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
Define a functor forg : PoGrp PoMonZ as follows:
— PoGrp maps to considered as a monoid; write this .
— An arrow g : PoGrp maps to itself considered as a (lazy) monoid homomorphism.
We exhibit the unit and counit of the adjunction. The unit () is given by the function mapping m to 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 () is given by the function inductively defined on representatives as follows:
By construction this is a group homomorphism. We prove inductively on the definition of in Figure 1 that the map is monotone, that is, if s then (s) ():
— Rule (leq). Suppose n m because n m. Then n m and we are done.
— Rule (lazy). Suppose m because m, , and m . Then by construction
and we are done.
— Rules (norm) and (mon) follow by inductive hypothesis and by compatibility and transitivity of . It is not hard to see that the adjunction maps
— g : PoGrp to : which takes m to g(m), and
— f : PoMon to : which acts on generators by taking m to f (m) and m to f (m)-1.
Verifying naturality is routine.
In Definition 3.12 we defined the measure function (-) from to integers considered as a group under addition, for each partially ordered monoid . 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 to (i.e. to considered as a monoid under addition).
It is not hard to see that this monotone lazy homomorphism is the trivial function mapping every m to 1 . 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 ; 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 and are taken to be abelian.
That is, even if x y y x for all x, y , by our construction in Definition 3.2 it is not the case that xy yx—what is true is that xy (x y (y 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 is commutative we could make 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 , 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 and 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:
Call a category 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.
A lazy functor on locally posetal categories F : is a map from objects of to objects of and from hom-posets (X, Y) to (F(X), F(Y)) such that:
— If f in (X, Y) then F( ) F( f ) in (F(X), F(Y)).
— F() for every X Obj().
— F( f g) F( f ) F(g) for every f (X, Y) and g (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.
Given a locally posetal category define a locally posetal groupoid as follows:
— Objects of are objects of .
— An arrow is the quotiented well-typed formal sum of arrows from just as in Definition 3.3, where if f (X, Y) then f is given type (X, Y) and f is given type (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:
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:
— f in (X, Y) if and only if f, for , f (X, Y).
— f gh in (X, Z) if and only if f g h in (X, Z), for f (X, Z) and g (X, Y) and h (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 monoid action to a partially ordered set with an group action.
Examples of sets with a monoid action are common in computer science, including:
— Syntax acted on by a monoid of substitutions.
— Integers acted on by the monoid of functions from to .
— A domain model of the -calculus D acted on by D 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 -action and lazy functions between them, and of partially ordered sets with an -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
Suppose (, ) PoMonZ. A poset with an -action is a tuple (, , ) of a carrier set , a partial order , and an action xm such that:
— If x and m then xm (the order on is compatible with that on ).
— x x and (xm) x(m ) (the action is a monoid action).
We define a poset with a action similarly, for (, ) a partially ordered group.
Suppose a poset with a compatible -action , ). We show how to extend this to a set with an -action.
The ordering is compatible, in the sense that (x, g) (y, h) implies (x, g ) (y, h ).
If (x, g) (y, h) then there exist , . . . , such that . . h g-1.
If (x, g) (y, h) then (g) (h).
If (x, g) (y, h) and (y, h) (z, g) then g h.
If (x, g) (y, g) then x y.
By induction on the rules in Definition 5.2.
— (absorb) cannot be used since g m g is impossible since (g) (m g 1 (g) and this contradicts part 2 of Lemma 3.16.
— The case of (compat) is immediate.
— For (trans), suppose (x, g) (, ) and (, ) (y, g). By Lemma 5.7 g. We use the inductive hypothesis and transitivity of .
5.2. The natural adjunction
Suppose is a partially ordered monoid. Write PoSetZ for the category such that:
— An object is a poset with a compatible -action.
— An arrow f : is a function f such that
– x implies f (x) f ().
–
Suppose is a partially ordered group. Write PoSet for the category such that:
— An object is a poset with a compatible -action.
— An arrow f : is a function f such that:
– y implies f (y) f ().
–
Let imag : PoSetZ PoSet have the following action:
— An object maps to (Definition 5.10).
— An arrow f : maps to imag( f ) : () which is defined by (x, g) maps to ( f (x), g).
Let forg : PoSet PoSetZ have the following action:
— An object (which is a set with an group action) maps to considered as a set with an action; write this .
— An arrow f : PoSet maps to itself considered as a monoid homomorphism.
We consider an example of Definition 5.12 in Section 6.
Suppose f : PoSetZ. 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 then ( f (x), g) ( f (y), h) in . We do this by induction on the derivation of (x, g) (y, h). The case of (absorb) follows from the assumption that f (xm) f (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)h f (x), g h). But this holds direct from Definition 5.10.
The unit maps x to (x, ()) (). We check that (xm) (x)m:
The counit : () maps (x, g) to x(g). We check that (x, g)h (x, g h):
5.3. More detailed analysis for the partial order
In this subsection we go deeper into the structure of objects in PoSet, asking the following question: if xg yh and m g, can yh 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].
Suppose is a set with an -action. Suppose (x, g) (y, h). Then: 1 If m g then there exists n such that n h and xm yn. 2 If () g then either
— () h and x y, or
— there exists n such that n h and x yn.
For the first part we work by induction on the derivation of .
— The case of (absorb). By (absorb) (xm, g) (x, m g). Suppose n g. Then (m n) mn m g, and it is a fact that (xm)n x(m n). It follows that (xm)n x(m n).
— The case of (compat). Suppose (x, g) (, ) because x and g . Suppose m g. Then also m and xm m.
— The case of (trans). Suppose (x, g) (y, h) because (x, g) (, ) and (, ) (y, h). Suppose m g. By inductive hypothesis there exists such that xm . Also by inductive hypothesis there exists n h such that yn. The result follows by transitivity of . The second part is also by induction.
— The case of (absorb). By (absorb) (xm, g) (x, m g). Suppose () g. Then it follows that m m g and it is a fact that xm xm. If m g then we proceed as in the first part of this lemma.
— The case of (compat). Suppose (x, g) (, ) because x and g . Suppose () g. Then also () and x . If m g then we proceed as in the first part of this lemma.
— The case of (trans) is similar.
6. An example: substitutions
Consider some first-order syntax (e.g. r :: a f(r, . . . , r) for some term-formers f and variables a) and consider substitution on it r[as] [Baader and Nipkow, 1998]. Write for the set of substitutions on with functional composition.
Let range over elements of . Substitutions form a submonoid of the function space on , that is, we can view as a subset 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 as trivially partially ordered.
Then we can form the imaginary group of substitutions, and 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 is just the set of variables a, b, c, . . . . For brevity write for . Then:
—
—
— a [ab] a. We deduce this by taking a [ab] b and applying [ab]-1 to both sides.
— a [ab] b is deduced similarly.
In view of the inequalities above, we can think of a [ab]-1 as being ‘like the un-ordered pair a, b’. However, this is only an analogy; a [ab]-1 displays behaviour that is not like the behaviour of a, b. In particular, a [ab] b [ba]-1, yet (by symmetry) both are ‘like a, b’.
6.2. Substitutions on terms
Now suppose that there are term-formers. Then r [as] r[s/a] (where r[s/a] is the term obtained by really replacing a by s in r). Also, r [as] for any such that [s/a r.
Now consider a rewrite rule R ) in the sense of first-order rewriting [Baader and Nipkow, 1998]. Then if r rewrites to with rule R then (r [a]-1) [a] .
For instance, given 0-ary term-formers 1 and 2 (i.e. constant symbols) it is easy to verify that (1 [a1]-1) [a2] 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 . As an easy corollary, 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 may be undecidable even if 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 compare with a corresponding ‘(lazy) algebra’ of ? 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 is a partial order with further structure, such as being a lattice, what further structure 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 are two arrows in (X, Y) and g are two arrows in (Y, Z) then f g in (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 (X, Y) and g (Y, Z). It is easy to see that e.g. f f is well-typed and in (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. ↩