Theory and Applications of Categories, Vol. 6, No. 3, 1999, pp. 33–46.

THE CATEGORICAL THEORY OF SELF-SIMILARITY

This paper is dedicated to Joachim Lambek, whose work was the inspiration for the following results.

PETER HINES

ABSTRACT. We demonstrate how the identity N ⊗ N ≅ N in a monoidal category allows us to construct a functor from the full subcategory generated by N and ⊗ to the endomorphism monoid of the object N. This provides a categorical foundation for one-object analogues of the symmetric monoidal categories used by J.-Y. Girard in his Geometry of Interaction series of papers, and explicitly described in terms of inverse semigroup theory in [6, 11]. This functor also allows the construction of one-object analogues of other categorical structures. We give the example of one-object analogues of the categorical trace, and compact closedness. Finally, we demonstrate how the categorical theory of self-similarity can be related to the algebraic theory (as presented in [11]), and Girard’s dynamical algebra, by considering one-object analogues of projections and inclusions.

1. Introduction

It is well-known, [12], that any one-object monoidal category is an abelian monoid with respect to two operations that satisfy the interchange law (a · b) ∘ (c · d) = (a ∘ c) · (b ∘ d); that is, all the canonical isomorphisms for the tensor are identities. However, non-trivial one-object analogues of the canonical associativity and commutativity morphisms for symmetric monoidal categories have been implicitly constructed by Girard for his work on linear logic, [4, 5], and have been studied in terms of inverse semigroups in [6] and [11]. The absence of a unit allows for a more interesting theory.

We demonstrate in section 2 how these examples arise naturally from the assumption of self-similarity. This is motivated by the examples of either the intuitive construction of the Cantor set, or bijections between ℕ and ℕ × ℕ. We define a self-similar object of a symmetric monoidal category to be an object N satisfying N ≅ N ⊗N. In the categorical case, this gives rise to examples of structure-preserving maps between categories and monoids. In section 3, we then demonstrate how these maps allow us to construct oneobject analogues of the categorical trace and compact closedness. Finally, in section 4, these categorical constructions are related to the algebraic approach to self-similarity described in [11], and Girard’s dynamical algebra, by considering one-object analogues of projections and inclusions.

Received by the editors 1998 October 6 and, in revised form, 1999 September 13.

Published on 1999 November 30.

1991 Mathematics Subject Classification: 18D10, 20M18.

Key words and phrases: Monoidal Categories, Categorical Trace, Compact Closure, Linear Logic, Inverse Semigroups.

\begin{matrix}c \\ ◯ \end{matrix} Peter Hines 1999. Permission to copy for private use granted.

2. Self-similarity and tensors

2.1. Definition. Let (M, ⊗) be a symmetric monoidal category and denote the associativity, commutativity, and left and right unit isomorphisms by t_{A,B,C}, s_{A,B}, λ_{A}, ρ_{A} respectively. We say that an object N of M is self-similar if N ≅ N ⊗ N; that is, there exist morphisms c : N ⊗ N → N and d : N → N ⊗ N that satisfy dc = 1_{N⊗N} and cd = 1_{N}. We call these morphisms the compression and division morphisms of N.

For the purposes of this paper, we will require the additional condition that the tensor ⊗ is not strict at N, so t_{N,N,N} is not the identity map. We also assume that the commutativity is not strict, to avoid studying degenerate cases. We study the full subcategory of M given by all objects constructed from N and ⊗, which we refer to as N^{⊗}. We assume throughout that N ≠ I.

The subcategory N^{⊗} has all the structure of a monoidal category apart from the unit object; we use the awkward term unitless monoidal categories^{1} for structures of this form. The following is then immediate:

2.2. Lemma. All objects of N^{⊗} are isomorphic to N, by maps d_{X} : N → X and c_{X} : X → N.

Proof. We (inductively) define the isomorphisms by:

• d_{N} = 1_{N} = c_{N} : N → N,

• d_{U⊗V} = (d_{U} ⊗ d_{V})d : N → U ⊗ V

• c_{U⊗V} = c(c_{U} ⊗ c_{V}) : U ⊗ V → N.

First note that c = c_{N⊗N} and d = d_{N⊗N}. The uniqueness of these maps then follows from the requirement that ⊗ is not strict at N, and hence that t_{X,Y,Z} is never the identity map, for any X, Y, Z ∈ Ob(N^{⊗}). This ensures that the set of objects is in direct correspondence to the set of (non-empty) binary bracketings of a single symbol, and the tensor corresponds to bracketing two objects together. This can be compared to the objects and tensor of Mac Lane’s free monoidal category on one generator, as used in the proof of his celebrated coherence theorem. We refer to [12] for this construction and proof.

Let U and V be objects of N^{⊗} satisfying d_{U}c_{U} = 1_{U} and d_{V} c_{V} = 1_{V}. (This holds trivially for U = V = N). Then

d_{U⊗V} c_{U⊗V} = (d_{U} ⊗ d_{V})dc(c_{U} ⊗ c_{V}) = (d_{U} ⊗ d_{V})1_{N⊗N}(c_{U} ⊗ c_{V})
= (d_{U}c_{U} ⊗ d_{V} c_{V}) = (1_{U} ⊗ 1_{V}) = 1_{U⊗V} .

Therefore, by induction, d_{X}c_{X} = 1_{X} for all objects X. Similarly, c_{X}d_{X} = 1_{N}.

1This is admittedly an abuse of notation, inasmuch as a monoid without an identity is a semigroup.

However, the natural alternatives, ‘multiplicative category’, or ‘semigroup category’ have already been used in the work of Hyland and DePaiva, and Lawson respectively.

This allows us to construct a functor from the category N^{⊗} to the endomorphism monoid of N (considered as a one-object category), as follows:

2.3. Proposition. Let N be a self-similar object of a symmetric monoidal category, (M, ⊗). The map ϕ : N^{⊗} → M(N, N), defined by ϕ(f) = c_{Y} fd_{X} for all f : X → Y and ϕ(X) = N for all X ∈ Ob(N^{⊗}) is a functor.

Proof. For all f : X → Y and g : Y → Z in N^{⊗}, by definition,

ϕ(g)ϕ(f) = c_{Z}gd_{Y} c_{Y} fd_{X} = c_{Z}g1_{Y} fc_{X} = ϕ(gf).

Therefore, ϕ preserves composition, and it is immediate from the definition that ϕ(1_{X}) = 1_{N} for all objects X. Hence ϕ is a functor.

These definitions allow us to construct a monoid homomorphism that has a very close connection with the tensor, as follows:

2.4. Lemma. Let N be a self-similar object of a symmetric monoidal category (M, ⊗), and let ⊕ : M(N, N) × M(N, N) → M(N, N) be defined by f ⊕ g = c(f ⊗ g)d, for all f, g : N → N. Then

(i) ⊕ is a monoid homomorphism, (ii) ϕ(f ⊗ g) = ϕ(f) ⊕ ϕ(g) for all f : U → X and g : V → Y, for U, V, X, Y ∈ Ob(N^{⊗}).

Proof.

(i) By definition, (1 ⊕ 1) = cd = 1_{N}, and

(f ⊕ g)(h ⊕ k) = c(f ⊗ g)dc(h ⊗ k)d = c(fh ⊗ gk)d = fh ⊕ gk.

Hence ⊕ is a monoid homomorphism. (ii) By definition ϕ(f) ⊕ ϕ(g) = c(ϕ(f) ⊗ ϕ(g))d. Hence, by definition of ϕ,

ϕ(f) ⊕ ϕ(g) = c(c_{X}fd_{U} ⊗ c_{Y} gd_{V})d = c(c_{X} ⊗ c_{Y})(f ⊗ g)(d_{U} ⊗ d_{V})d

and so, by definition of c_{X⊗Y} and d_{U⊗V},

ϕ(f) ⊕ ϕ(g) = c_{X⊗Y} (f ⊗ g)d_{U⊗V} = ϕ(f ⊗ g).

Our claim is that this monoid homomorphism (which, in [6], is referred to as the internalisation of the tensor) gives the endomorphism monoid of N the structure of a one-object (unitless) symmetric monoidal category, with ⊕ as the tensor.

2.5. Definition. The one-object analogues of the axioms for a tensor are as follows: There exist special elements s and t (the analogues of the commutativity and associativity elements respectively) that satisfy:

1. s(u ⊕ v) = (v ⊕ u)s, 2. t(u ⊕ (v ⊕ w)) = ((u ⊕ v) ⊕ w)t,

3. t^{2} = (t ⊕ 1)t(1 ⊕ t),

4. tst = (s ⊕ 1)t(1 ⊕ s),

5. s^{2} = 1,

6. t has an inverse, t^{−1}, satisfying tt^{−1} = 1 = t^{−1}t.

These are just the axioms for a (unitless) symmetric monoidal category with the object subscripts erased.

The homomorphism ⊕ satisfies the above conditions, as follows:

2.6. Theorem. Let N be a self-similar object of a symmetric monoidal category (M, ⊗), and let ⊕ be as defined in Lemma 2.4 of Section 2. Then there exist distinguished elements s and t of the endomorphism monoid of N satisfying 1. to 6. above.

Proof. Define s = ϕ(s_{NN}), where s_{X,Y} is the family of commutativity morphisms for (M, ⊗). Similarly, define t = ϕ(t_{N,N,N}) and t^{−1} = ϕ(t_{N,N,N}^{−1}). Note that, for the isomorphisms of Lemma 1 to be well-defined, we require that t_{N,N,N} ≠ 1_{N⊗(N⊗N)}

Then ϕ(t_{X,Y,Z}) = ϕ(t_{N,N,N}) = t, by the naturality of t_{X,Y,Z}, and the fact that ϕ(1_{X}) = 1, for all X, Y, Z ∈ Ob(N^{⊗}). Similarly, ϕ(s_{X,Y}) = s, for all X, Y ∈ Ob(N^{⊗}).

The conditions 1. to 4. follow immediately, by applying ϕ to the axioms 1. to 4. respectively.

1. s(b ⊗ a) = (a ⊗ b)s,

2. t(a ⊗ (b ⊗ c)) = ((a ⊗ b) ⊗ c)t,

3. The Mac Lane Pentagon:

t_{(A⊗B),C,D}t_{A,B,(C⊗D)} = (t_{A,B,C} ⊗ 1_{D})t_{A,(B⊗C),D}(1_{A} ⊗ t_{B,C,D}).

4. The Commutativity Hexagon:

t_{C,A,B}s_{(A⊗B),C}t_{A,B,C} = (s_{A,C} ⊗ 1_{B})t_{A,C,B}(1_{A} ⊗ s_{B,C}),

and by the naturality of the canonical isomorphisms for a symmetric monoidal category. For example, applying ϕ to the Mac Lane pentagon gives

ϕ(t_{(A⊗B),C,D}t_{A,B,(C⊗D)}) = ϕ((t_{A,B,C} ⊗ 1_{D})t_{A,(B⊗C),D}(1_{A} ⊗ t_{B,C,D})),

and so

ϕ(t_{(A⊗B),C,D})ϕ(t_{A,B,(C⊗D)}) = (ϕ(t_{A,B,C}) ⊕ ϕ(1_{D}))ϕ(t_{A,(B⊗C),D})(ϕ(1_{A}) ⊕ ϕ(t_{B,C,D})).

Therefore, tt = (t ⊕ 1)t(1 ⊕ t), which is condition 3. above. Conditions 5. and 6. follow by applying ϕ to the equations s_{A,B}s_{B,A} = 1 and t_{X,Y,Z}t_{X,Y,Z}^{−1} = 1, which follow from the definition of a symmetric monoidal category.

Hence, the endomorphism monoid of a self-similar object of a symmetric monoidal category is a unitless one-object symmetric monoidal category.

2.7. Definition. We define a monoidal functor between unitless symmetric monoidal categories (C, ⊗) and (D, ⊕) to be a pair (F, m), where F : C → D is a functor, and m is a natural transformation with components m_{A,B} : F (A) ⊕ F (B) → F (A ⊗ B).

With this terminology, the following is immediate

2.8. Corollary. Let N be a self-similar object of a symmetric monoidal category M. Then ϕ is a monoidal functor from N^{⊗} to M(N, N), considered a one-object unitless symmetric monoidal category.

Monoids M that have monoid homomorphisms from M×M to M, together with analogues of the associativity and commutativity elements satisfying 1. to 6. above have already been constructed, under the name (strong) M–monoids in [6] and Girard Monoids in [11]. We demonstrate how the two examples given are examples of this construction in the category of partial injective maps.

2.9. Examples of self-similarity. Any infinite object in the category Set is selfsimilar with respect to two distinct tensors; Set is a symmetric monoidal category with respect to both the Cartesian product of sets, X × Y = {(x, y) : x ∈ X, y ∈ Y } and the coproduct, A ⊔ B = {(a, 0) : a ∈ A} ∪ {(b, 1) : b ∈ B}. This then gives us the following:

2.10. Proposition. The set of natural numbers, ℕ is a self-similar object of Set, with respect to both × and ⊔.

Proof. The elementary theory of infinite sets gives the existence of bijections ℕ → ℕ × ℕ, and ℕ → ℕ ⊔ ℕ. Therefore, our result follows.

M-monoid structures can then be derived from specific examples of bijections φ : ℕ⊔ℕ → ℕ and ψ : ℕ × ℕ → ℕ. The examples given in [6, 11] are constructed from the function

φ(n, i) = 2n + i n ∈ ℕ , i ∈ {0, 1}

which is a bijection from ℕ ⊔ ℕ to ℕ This is then used to construct a bijection from ℕ × ℕ to ℕ by denoting φ(n, i) by φ_{i}(n), and defining

ψ(x, y) = φ_{1}^{y}(φ_{0}(x)).

Similar results hold for the category of relations, and the category of partial injective maps – interestingly, algebraic representations of these M-monoid structures are given in terms of inverse semigroup theory and polycyclic monoids (see Section 4 for the constructions of these). We refer to [11] for the algebraic theory of inverse semigroups, and to [6, 11] for explicit descriptions of M-monoids in terms of the inverse monoid of partial injections on the natural numbers.

3. Monoid analogues of other categorical structures

A functor from a symmetric monoidal category to the endomorphism monoid of an object (viewed as a unitless one-object symmetric monoidal category), that preserves both the category structure and the symmetric monoidal structure, might be expected to preserve other categorical properties. We demonstrate how the assumption of self-similarity allows us to construct one-object analogues of the categorical trace (as described by Joyal, Street, and Verity in [8]) and, in some cases, one-object analogues of compact closedness.

These specific examples were motivated by Abramsky’s analysis of the Geometry of Interaction, [1], and the paper of Abramsky and Jagadeesan, [2], where it is demonstrated that the system of [1] is equivalent to the construction of [8] — hence demonstrating that the dynamics of the Geometry of Interaction system is given by a categorical trace, and compact closedness. The motivation for constructing one-object analogues of compact closedness and the categorical trace then comes from Girard’s comment in [4] where he states that his system ‘forgets types’ — the usual representation of types being objects in a category.

3.1. The categorical trace.

3.2. Definition. Let (M, ⊗, s, t, λ, ρ, I) be a symmetric monoidal category. A trace on it is defined in [8] to be a family of functions, T r_{A,B}^{U} : M(A ⊗ U, B ⊗ U) → M(A, B), that are natural in A, B and U, and satisfy the following:

1. Given f : X ⊗ I → Y ⊗ I, then T r_{X,Y}^{I} (f) = ρfρ^{−1} : X → Y.

2. Given f : A ⊗ (U ⊗ V) → B ⊗ (U ⊗ V), then

T r_{A,B}^{U⊗V} (f) = T r_{A,B}^{U}(T r_{A⊗U,B⊗U}^{V}(t_{B,U,V} ft_{A,U,V}^{−1} )).

3. Given f : A ⊗ U → B ⊗ U, and g : C → D, then

T r_{A,B}^{U}(f) ⊗ g = T r_{A⊗C,B⊗D}^{U}(t_{BDU}(1_{B} ⊗ s_{D,U})t_{BUD}^{−1}(f ⊗ g)t_{AUC}(1_{A} ⊗ s_{C,U})t_{ACU}^{−1})

4. T r_{U,U}^{U}(s_{U,U}) = 1_{U}.

Let N be a self-similar object of a symmetric monoidal category. Then N^{⊗} is a traced symmetric monoidal category (although axiom 1 is not applicable, due to the absence of the unit object). We can use the functor ϕ to construct one-object analogues of the categorical trace, as follows:

3.3. Lemma. Let N be a self-similar object of a traced symmetric monoidal category (M, ⊗), and denote the compression and division morphisms by c and d respectively. Then the map trace : M(N, N) → M(N, N) defined by trace(f) = T r_{N,N}^{N}(dfc) satisfies trace(ϕ(F)) = ϕ(T r_{X,Y}^{U} (F)) for all F ∈ N^{⊗}(X ⊗ U, Y ⊗ U).

Proof. trace(ϕ(F)) = T r_{N,N}^{N}(dϕ(F)c) = T r_{N,N}^{N}(dc_{Y ⊗U}F d_{X⊗U}c) by definition of trace and ϕ. However, c_{Y ⊗U} = c(c_{Y} ⊗ c_{U}) and d_{X⊗U} = (d_{X} ⊗ d_{U})d, by definition of the division and compression morphisms. Therefore

trace(ϕ(F)) = T r_{N,N}^{N}(dc(c_{Y} ⊗ c_{U})F (d_{X} ⊗ d_{U})dc)
= T r_{N,N}^{N}((c_{Y} ⊗ c_{U})F (d_{X} ⊗ d_{U})) = c_{Y} (T r_{X,Y}^{N} ((1_{Y} ⊗ c_{U})F (1_{X} ⊗ d_{U})))d_{X},

by the naturality of the trace in X and Y, and so

trace(ϕ(F)) = c_{Y} T r_{X,Y}^{U} (F (1_{X} ⊗ d_{U}c_{U}))d_{X}
= c_{Y} T r_{X,Y}^{U} (F (1_{X} ⊗ 1_{U}))d_{X} = c_{Y} T r_{X,Y}^{U} (F)d_{X},

by the naturality of the trace in U. Therefore trace(ϕ(F)) = ϕ(T r_{X,Y}^{U} (F)), by the definition of ϕ.

This then satisfies one-object analogues of the categorical trace, as follows:

3.4. Theorem. Let N be a self-similar object of a traced symmetric monoidal category (M, ⊗), let ⊕, s, t, t^{−1} be as defined in Theorem 2.6 of Section 2, and let the map trace be as defined above. Then

(i) trace(f) = trace(trace(tft^{−1})), (ii) trace(f) ⊕ g = trace(t(1 ⊕ s)t^{−1}(f ⊕ g)t(1 ⊕ s)t^{−1}), (iii) trace(s) = 1, (iv) trace((h ⊕ 1)f(g ⊕ 1)) = h(trace(f))g,

(v) trace(f(1 ⊕ g)) = trace((1 ⊕ g)f).

Proof. These follow immediately from the above Lemma, the axioms for the categorical trace, and the fact that ⊕ is a monoid homomorphism.

Specific examples can be constructed at any countable set, in both the category of relations (which is demonstrated in [8] to be a traced symmetric monoidal category), and in the sub-category of partial injective maps (which is demonstrated in [6] to be closed under the same categorical trace).

3.5. compact closedness.

3.6. Definition. A compact closed category M is a symmetric monoidal category where for every object A, there exists a left dual, A^{∨}. The left dual has the following properties: For every A ∈ Ob(M), there exist two morphisms, the counit map ϵ_{A} : A^{∨} ⊗ A → I, and the unit map η_{A} : I → A ⊗ A^{∨}, that satisfy the following coherence conditions:

1. ρ_{A}(1_{A} ⊗ ϵ_{A})t_{AA^{∨}A}^{−1}(η_{A} ⊗ 1_{A})λ_{A}^{−1} = 1_{A}

2. λ_{A^{∨}}(ϵ_{A} ⊗ 1_{A^{∨}})t_{A^{∨}AA^{∨}}(1_{A^{∨}} ⊗ η_{A})ρ_{A^{∨}}^{−1} = 1_{A}^{∨} We refer to [9] for the details of the coherence theorem for compact closed categories.

The point of the main construction of [8] was to show that every traced symmetric monoidal category is a monoidal full subcategory of a compact closed category, which gives a structure theorem for traced symmetric monoidal categories. In light of this, we would again expect that the assumption of self-similarity at an object (together with possible extra conditions) should allow us to construct one-object analogues of compact closedness. However, this raises the following problem: the distinguished maps that make a symmetric monoidal category into a compact closed category (the units and counits) are defined in terms of the unit object. However the ϕ functor of Proposition 2.3 of Section 2 gives one-object analogues of unitless symmetric monoidal categories. This motivates an alternative characterisation of compact closed categories.

In many applications of compact closed categories (for example, the construction of a canonical trace on a compact closed category, [8]), the ϵ and η maps always appear in conjunction with the unit isomorphisms λ, ρ and λ^{−1}, ρ^{−1} respectively. For example, [8] uses morphisms between X and X ⊗ (A ⊗ A^{∨}) for all X and A defined by (1_{X} ⊗ η_{A})ρ_{X}^{−1}, and similarly for ϵ and ρ. We take maps of this form as primitive; this gives the following alternative set of axioms for a compact closed category:

3.7. Definition. For every object A ∈ Ob(M), there exists a dual object A^{∨}, together with morphisms

• κ_{XA} : X → (A ⊗ A^{∨}) ⊗ X,

• δ_{XA} : X ⊗ (A^{∨} ⊗ A) → X,

that are natural in X and satisfy the following axioms

1. δ_{AA}t_{AA^{∨}A}^{−1}κ_{AA} = 1_{A},

2. δ_{A^{∨}A}s_{A^{∨}⊗A,A^{∨}}t_{A^{∨}AA^{∨}}s_{A⊗A^{∨},A^{∨}}κ_{A^{∨}A} = 1_{A^{∨}},

3. (ρ_{A⊗A^{∨}}κ_{IA} ⊗ 1_{X})λ_{X}^{−1} = κ_{XA},

4. ρ_{X}(1_{X} ⊗ δ_{IA}λ_{A^{∨}⊗A}^{−1}) = δ_{XA}.

The naturality of κ_{XA} and δ_{XA} in X can be written explicitly as, ((1_{A}⊗1_{A^{∨}})⊗f)κ_{XA} = κ_{Y A}f and fδ_{XA} = δ_{Y A}(f ⊗ (1_{A^{∨}} ⊗ 1_{A})) for all f : X → Y.

The proof of the equivalence of this set of axioms with the usual set is postponed until the Appendix. However, note that the unit element is not central to the above characterisation of compact closedness. This allows us to define one-object (unitless) analogues of these axioms for M-monoids, as follows:

3.8. Definition. An M-monoid is said to satisfy the one-object analogues of compact closedness if there exist distinguished elements κ, κ^{−1} and δ, δ^{−1} that satisfy

1. δt^{−1}κ = 1, 2. δstsκ = 1,

3. (1 ⊕ a)κ = κa,

4. aδ = δ(a ⊕ 1).

Axioms 1. and 2. are one-object analogues of axioms 1. and 2. of Definition 3.7, and axioms 3. and 4. are one-object analogues of the naturality conditions.

3.9. Theorem. Let (M, ⊗) be a compact closed category, and let N be a self-dual selfsimilar object of M. Then there exist elements κ and δ that satisfy the one-object analogues of the alternative axioms for a compact closed category.

Proof. Define κ = ϕ(κ_{NN}) and δ = ϕ(δ_{NN}). The naturality of κ_{XN} and δ_{XN} in X allows us to deduce that ϕ(κ_{XN}) = ϕ(κ_{NN}), and similarly, ϕ(Δ_{XN}) = ϕ(Δ_{NN}). Then, as N^{∨} = N, applying ϕ to the alternative axioms for a compact closed category will give 1. and 2. of the above Definition, and applying ϕ to the explicit description of the naturality conditions (and using the fact that (1 ⊕ 1) = 1), will give us 3. and 4. of the above Definition.

4. Relating the categorical and algebraic theories of self-similarity

We relate the categorical approach to self-similarity given above to the inverse semigroup theoretic approach given in [11], where self-similarity is studied algebraically in terms of polycyclic monoids. These were introduced in [13], as follows:

4.1. Definition. P_{X}, the polycyclic monoid on the set X, is defined to be the inverse monoid (with a zero, for n ≥ 2) generated by a set of countable cardinality, X, say {p_{0}, … p_{n−1}}, in case |X| = n, or {p_{0}, p_{1}, …} for countably infinite X, subject to the relations p_{i}p_{j}^{−1} = δ_{ij}, where p^{−1} is the generalised inverse^{2} of p_{i}.

It will be convenient to denote the polycylic monoid on the set {p, q} by P_{2} – this is following the convention of Girard, who uses elements of a C^{∗} algebra satisfying the above axioms (which he refers to as the dynamical algebra) in his work on linear logic, [4, 5]. In [3], this is demonstrated to be a representation of the free contracted semigroup ring over a monoid, which is trivially the polycyclic monoid on two generators

The polycyclic monoids appear to be the algebraic representation of self-similarity. It is demonstrated in [11] that the polycyclic monoid on two generators can also be constructed in terms of the inverse monoid of partial isomorphisms of the Cantor set, and in [7] that an embedding of a polycyclic monoid into a ring R gives the ring isomorphism M_{n}(R) ≅ R, for all n ∈ ℕ. They also have a close connection with the algebraic theory of tilings; we again refer to [11].

2Note that the existence of generalised inverses is a significantly weaker condition than group-theoretic inverses. In the inverse semigroup theoretic case, for every element a, there exists a unique generalised inverse, which satisfies aa^{−1}a = a and a^{−1}aa^{−1} = a^{−1}. However, we cannot, in general, deduce aa^{−1} = 1 = a^{−1}a. We refer to [11] for a comprehensive account of the theory of inverse semigroups.

4.2. Definition. Let N be a self-similar object of a symmetric monoidal category (M, ⊗), and let M(N, N) have a zero, which we denote 0. We say that maps π_{1}, π_{2} ∈ M(N ⊗N, N) are left and right projection maps and i_{1}, i_{2} ∈ M(N, N ⊗ N) are their inclusion maps, if they satisfy

1. π_{1}i_{1} = 1_{N} and π_{2}i_{2} = 1_{N},

2. i_{1}π_{1} = 1_{N} ⊗ 0 and i_{2}π_{2} = 0 ⊗ 1_{N}.

4.3. Theorem. Let N be a self-similar object of a symmetric monoidal category (M, ⊗). If N has projection and inclusion maps, then there exists an embedding of P_{2} into M(N, N).

Proof. As ϕ preserves composition, ϕ(π_{1})ϕ(i_{1}) = 1_{N} = ϕ(π_{2})ϕ(i_{2}). Similarly, ϕ(i_{1})ϕ(π_{1}) = 1⊕0, and ϕ(i_{2})ϕ(π_{2}) = 0⊕1, since ϕ(0) = 0. Hence, as ⊕ is a semigroup homomorphism,

ϕ(i_{1})ϕ(π_{1})ϕ(i_{2})ϕ(π_{2}) = 0 = ϕ(i_{2})ϕ(π_{2})ϕ(i_{1})ϕ(π_{1}).

Therefore, ϕ(π_{1})ϕ(i_{2}) = 0 = ϕ(π_{2})ϕ(i_{1}), and so ϕ(π_{1}), ϕ(π_{2}) satisfy the axioms for the generators of P_{2}, and ϕ(i_{1}), ϕ(i_{2}) satisfy the conditions for their generalised inverses. Also, by [13], the polycyclic monoids are congruence-free, hence the only quotient of P_{2} is the trivial monoid. Therefore, these elements generate an embedding of P_{2} into M(N, N).

From the above, we are in a position to prove the converse to the main result of [7], where it is proved that an embedding of P_{2} into the multiplicative monoid of a ring R defines a family of isomorphisms R ≅ M_{n}(R) for all positive integers n. For a unital ring R, we define the category Mat_{R} that has natural numbers as objects, and b × a matrices as morphisms from a to b. It is immediate that this category is a symmetric monoidal

category, with the tensor ⊔ given by A ⊔ B = ( \begin{matrix}A & 0 \\ 0 & B \end{matrix} ).

4.4. Theorem. Let R be a unital ring, and assume there exists c ∈ Mat_{R}(2, 1), d ∈ Mat_{R}(1, 2) such that the map ϕ : Mat_{R}(2, 2) → R, defined by ϕ(X) = cXd, is an injective ring homomorphism. Then P_{2} is embedded in R.

Proof. First note that the condition on R is equivalent to stating that 1 is a self-similar object of the category Mat_{R}. We demonstrate that Mat_{R} has inclusions and projections. Define

π_{1} = (1 0) , π_{2} = (0 1) , i_{1} = ( \begin{matrix}1 \\ 0 \end{matrix} ) , i_{2} = ( \begin{matrix}0 \\ 1 \end{matrix} ) .

Then it is immediate from the definition of composition in Mat_{R} that π_{1}i_{1} = 1_{R} = π_{2}i_{2}, and

i_{1}π_{1} = ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) , i_{2}π_{2} = ( \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} ) .

Therefore, i_{1}π_{1} = 1 ⊔ 0 and i_{2}π_{2} = 0 ⊔ 1, and so Mat_{R} has projections and inclusions. Therefore, by Theorem 4.3 above, there exists an embedding of P_{2} into the multiplicative monoid of R.

5. Research questions

This paper is by no means a complete account of the theory of self-similarity. The following points are among the many it raises:

• Although we have concentrated on practical applications, presumably there is a reasonable definition of the free self-similar monoidal category, analogously to the Mac Lane definition of the free monoidal category on one generator [12]. This should allow for the formulation and proof of a coherence theorem for self-similar categories. This is related to the second point:

• The requirement that the tensor ⊗ is not strictly associative at the object N is not needed - in [6], self-similarity is used to construct one-object analogues of monoidal categories in the strictly associative case. However, this is done in an ad hoc way. It is also curious that the monoid at N satisfies one-object analogues of the axioms for a non-strict monoidal category. Clearly there is some underlying theory that covers all cases.

• In at least some of [4], Girard uses a weaker condition to our self-similarity that is equivalent to maps c : N ⊗ N → N and d : N → N ⊗ N satisfying dc = 1_{N⊗N} and cd < 1_{N}. Although this does not allow the definition of a functor from a category to a monoid, it allows a function that preserves composition and maps identities at objects to idempotents of a monoid. This clearly defines a functor from the category N^{⊗} to the Karoubi envelope of the monoid at N. However, the computational or logical interpretation of this remains unclear.

• The construction of a compact closed category from a traced symmetric monoidal category, as a ‘dualising’ process is given in [8], and the logical and computational significance of this has been well studied. It would be interesting to be able to use a similar process to go from traced M-monoids to compact closed M-monoids, without passing though a many-object category in an intermediate stage.

• For monoidal categories with additional categorical structure X, we would like to say that the functor ϕ allows us to define one-object analogues of X-categories. The problem is to make this precise, and relate it to the direct limit construction used to construct one-object analogues of Cartesian closed categories, as found in [10].

6. Acknowledgements

Special thanks are due to Ross Street, for reading a preliminary version of this paper and helping me clarify some definitions, and to Samson Abramsky, for an explanation of the computational significance. Similarly, thanks are due to John Fountain for a critical reading of [6], and Mark Lawson, who helped develop the algebraic theory of self-similarity.

Appendix: Equivalence of axioms for compact closedness

We demonstrate that the alternative axioms for compact closed categories given in Definition 3.7 are equivalent to the usual set. We refer to the usual set of axioms, as found in Definition 3.6, as A1 and the alternative set of axioms as A2.

6.1. Theorem. A symmetric monoidal category that satisfies the axioms A1 also satisfies the axioms A2, and vice versa.

Proof. (⇒) Let (M, ⊗, η, ϵ) be a symmetric monoidal category satisfying A1. For all X, A ∈ Ob(M), we define κ_{XA} = (η_{A} ⊗ 1_{X})λ_{X}^{−1} and δ_{XA} = ρ_{X}(1_{X} ⊗ ϵ_{A}). Consider arbitrary f : X → Y. By the definition of κ, and the naturality of λ_{X} in X, we can deduce that (1_{A⊗A^{∨}} ⊗f)κ_{XA} = κ_{Y A}f, and so κ_{XA} is natural in X. Similarly, by definition of δ, and the naturality of ρ_{X} in X, δ_{XA} is natural in X. Also, by definition of κ and δ,

1. δ_{AA}t_{AA^{∨}A}^{−1}κ_{AA} = ρ_{A}(1_{A} ⊗ ϵ_{A})t_{AA^{∨}A}^{−1}(η_{A} ⊗ 1_{A})λ_{A}^{−1} = 1_{A}, by axiom 1 of A1.

2. By definition, δ_{A^{∨}A}s_{A^{∨}⊗A,A^{∨}}t_{A^{∨}AA^{∨}}s_{A⊗A^{∨},A^{∨}}δ_{A^{∨}A} =

ρ_{A^{∨}}(1_{A^{∨}} ⊗ ϵ_{A})s_{A^{∨}⊗A,A^{∨}}t_{A^{∨}AA^{∨}}s_{A⊗A^{∨},A^{∨}}(η_{A} ⊗ 1_{A}^{∨})λ_{A^{∨}}^{−1}.

By the naturality of s_{XY} in X and Y this is equal to

ρ_{A^{∨}}s_{I,A^{∨}}(ϵ_{A} ⊗ 1_{A^{∨}})t_{A^{∨}AA^{∨}}(1_{A^{∨}} ⊗ η_{A})s_{A^{∨},I}λ_{A^{∨}}^{−1}.

Also, as ρ_{X}s_{IX} = λ_{X}, this is equal to λ_{A^{∨}}(ϵ_{A} ⊗ 1_{A^{∨}})t_{A^{∨}AA^{∨}}(1_{A^{∨}} ⊗ η_{A})ρ_{A^{∨}}^{−1}, which is 1_{A^{∨}}, by axiom 2 of A1.

3. By the naturality of ρ_{Z} in Z, and the definition of κ_{XA},

(ρ_{A⊗A^{∨}} ⊗ 1_{X})(κ_{IA} ⊗ 1_{X})λ_{X}^{−1} = (ρ_{A⊗A^{∨}} ⊗ 1_{X})(η_{A} ⊗ 1_{I})(λ_{I}^{−1} ⊗ 1_{X}) =

(η_{A} ⊗ 1_{X})(ρ_{I}λ_{I}^{−1} ⊗ 1_{X})λ_{X}^{−1} = (η_{A} ⊗ 1_{X})(1_{I} ⊗ 1_{X})λ_{X}^{−1} = (η_{A} ⊗ 1_{X})λ_{X}^{−1} = κ_{XA}

4. In a similar way to 3,

ρ_{X}(1_{X} ⊗ δ_{IA})(1_{X} ⊗ λ_{A^{∨}⊗A}^{−1}) = ρ_{X}(1_{X} ⊗ ϵ_{A}) = δ_{XA}

by the definition of κ and the naturality of λ_{Z} in Z.

Therefore, κ_{AX} and δ_{AX} are morphisms that are natural in X, and satisfy the axioms A2. Therefore, every symmetric monoidal category satisfying A1 also satisfies A2. (⇐) Let (M, ⊗, κ, δ) be a symmetric monoidal category satisfying A2. We define morphisms

ϵ_{A} : (A^{∨} ⊗ A) → I , η_{A} : I → (A ⊗ A^{∨})

by η_{A} = ρ_{A⊗A^{∨}}κ_{IA} and ϵ_{A} = δ_{IA}λ_{A^{∨}⊗A}^{−1}. We now check the that these morphisms satisfy the axioms A1:

Theory and Applications of Categories, Vol. 6, No. 3 45

1. ρ_{A}(1_{A} ⊗ ϵ_{A})t_{AA^{∨}A}^{−1}(η_{A} ⊗ 1_{A})λ_{A}^{−1} = κ_{A,A}t_{AA^{∨}A}^{−1}δ_{AA} = 1_{A}, by axiom 1 of A2.

2. By definition of ϵ and η,

λ_{A^{∨}}(ϵ_{A^{∨}} ⊗ 1_{A^{∨}})t_{A^{∨}AA^{∨}}(1_{A^{∨}} ⊗ η_{A})ρ_{A^{∨}}^{−1} =

λ_{A^{∨}}(δ_{IA^{∨}}λ_{A⊗A^{∨}}^{−1} ⊗ 1_{A^{∨}|})t_{A^{∨}AA^{∨}}(1_{A^{∨}} ⊗ ρ_{A⊗A^{∨}}κ_{IA})ρ_{A^{∨}}^{−1}.

However, λ_{A^{∨}} = ρ_{A^{∨}}s_{IA^{∨}} and ρ_{A^{∨}}^{−1} = s_{IA^{∨}}λ_{A^{∨}}^{−1}. Therefore, this is equal to

ρ_{A^{∨}}s_{IA}(δ_{IA^{∨}}λ_{A⊗A^{∨}}^{−1} ⊗ 1_{A^{∨}|})t_{A^{∨}AA^{∨}}(1_{A^{∨}} ⊗ ρ_{A⊗A^{∨}}κ_{IA})s_{IA^{∨}}λ_{A^{∨}}^{−1},

and by the naturality of s_{XY} in X and Y, the above is equal to

ρ_{A^{∨}}(1_{A^{∨}} ⊗ δ_{IA^{∨}}λ_{A⊗A^{∨}}^{−1})s_{A^{∨}⊗A,A^{∨}}t_{A^{∨}AA^{∨}}s_{A⊗A^{∨},A^{∨}}(ρ_{A⊗A^{∨}}κ_{IA} ⊗ 1_{A^{∨}})λ_{A^{∨}}^{−1}. Then by axioms 3 and 4 of A2, this is δ_{A^{∨}A}s_{A^{∨}⊗A,A^{∨}}t_{A^{∨}AA^{∨}}s_{A⊗A^{∨},A^{∨}}κ_{A^{∨}A}, which is 1_{A^{∨}}, by axiom 2 of A2.

Therefore, the axioms A1 are satisfied, and this completes our proof.

References

[1] S. Abramsky, Retracing some paths in Process algebra, CONCUR 96.

[2] S. Abramsky, R. Jagadeesan, New Foundations for the Geometry of Interaction, Proc. Seventh IEEE Symposium on Logic in Computer Science, 211-222 (1992)

[3] V. Danos, L. Regnier, Local and Asynchronous Beta Reduction, (an analysis of Girard’s execution formula), Proc. Eighth Ann. IEEE Symposium on Logic in Computer Science, IEEE Comp. Soc. Press 296-306 (1993)

[4] J-Y. Girard, Geometry of interaction 1, Proceedings Logic Colloquium ’88, (1989) 221-260, North Holland.

[5] J-Y. Girard, Geometry of interaction 2, Proceedings of COLOG 88, Martin-Lof & Mints, 76-93 SLNCS 417

[6] P.M. Hines, The Algebra of Self-similarity and its Applications, PhD thesis, University of Wales (1997)

[7] P. Hines, M.V. Lawson, An application of polycyclic monoids to rings, Semigroup Forum 56 (1998), 146–149.

[8] A. Joyal, R. Street, D. Verity, Traced Monoidal categories, Math. Proc. Camb. Phil. Soc., (1996) 425-446 [9] G. Kelly, M. Laplaza, Coherence for compact closed categories, Journal of Pure and

Applied Algebra 19 (1980) 193-213

[10] J. Lambek, P.J. Scott, Introduction to Higher Order Categorical Logic, Cambridge Studies in Advanced Mathematics, Cambridge University Press (1986)

[11] M.V. Lawson, Inverse Semigroups: the theory of partial symmetries, World Scientific, Singapore (1998)

[12] S. Mac Lane, Categories for the Working Mathematician, Springer-Verlag New York, (1971)

[13] M. Nivat, J.-F. Perrot, Une Generalisation du Monoide bicyclique, C. R. Acad. Sc. Paris, t.271 (1970)

[14] M. Petrich, Inverse Semigroups, Pure and Applied Mathematics, Wiley-Interscience Series, John Wiley and Sons (1984)

School of Informatics, University of Wales, Bangor, Gwynedd, U.K. LL57 1UT

Email: max003@bangor.ac.uk

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/6/n3/n3.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi and Postscript format. Details will be e-mailed to new subscribers and are available by WWW/ftp. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at URL http://www.tac.mta.ca/tac/ or by anonymous ftp from ftp.tac.mta.ca in the directory pub/tac/info. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: carboni@fis.unico.it P. T. Johnstone, University of Cambridge: ptj@pmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.ruu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mscs.dal.ca Andrew Pitts, University of Cambridge: ap@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@charlie.math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Sydney: walters b@maths.usyd.edu.au R. J. Wood, Dalhousie University: rjwood@mscs.dal.ca