Theory and Applications of Categories, Vol. 32, No. 44, 2017, pp. 1522–1562.

APPROXIMATE CATEGORICAL STRUCTURES

ABDELKRIM ALIOUCHE AND CARLOS SIMPSON

Abstract. We consider notions of metrized categories, and then approximate categorical structures defined by a function of three variables generalizing the notion of 2-metric space. We prove an embedding theorem giving sufficient conditions for an approximate categorical structure to come from an inclusion into a metrized category.

1. Introduction

Gähler [Gähler, 1963] introduced the notion of 2-metric space which is a set X together with a function called the 2-metric d(x, y, z) ∈ ℝ satisfying some properties generalizing the axioms for a metric space. Notably, the triangle inequality generalizes to the tetrahedral inequality for a 2-metric

d(x, y, w) ≤ d(x, y, z) + d(y, z, w) + d(x, z, w).

One of the main examples of a 2-metric is obtained by setting d(x, y, z) equal to the area of the triangle spanned by x, y, z. Here, we consider triangles with straight edges. One might imagine considering more generally triangles with various paths as edges. In this case, in addition to x, y and z, we should specify a path f from x to y, a path g from y to z and a path h from x to z. We could then set d(f, g, h) to be the area of the figure spanned by these paths, more precisely the minimal area of a disk whose boundary consists of the circle formed by these three paths.

This generalization takes us in the direction of category theory: we may think of d(f, g, h) as being some kind of distance between h and a “composition” of f and g. We will formalize this notion here and call it an approximate categorical structure.

Generalizing the notion of 2-metric space in this direction may be viewed as directly analogue to the recent paper of Weiss [Weiss, 2012] in which he proposed the notion of “metric 1-space” which was a category together with a “distance function” d(f) for arrows f : x → y, which would then be required to satisfy the analogues of the usual axioms of a metric space. In his setup, the pair (x, y) is replaced by a pair of objects plus an arrow f from x to y.

We would like to thank the referees for many interesting comments and suggestions.

Received by the editors 2016-03-10 and, in final form, 2017-12-14.

Transmitted by Tom Leinster. Published on 2017-12-18.

2010 Mathematics Subject Classification: Primary 18A05; Secondary 54E35, 08A72.

Key words and phrases: metric, 2-metric space, category, functor, Yoneda embedding, bimodule, path, triangle.

\begin{matrix}c \\ ◯ \end{matrix} Abdelkrim Aliouche and Carlos Simpson, 2017. Permission to copy for private use granted.

In our situation, we would like to generalize the notion of 2-metric in a similar way replacing a triple of points (x, y, z) by a triple of objects together with arrows f : x → y, g : y → z and h : x → z. In this setup, we don’t need to start with a category but only with a graph and the 2-metric itself represents some kind of approximation of the notion of composition.

In an approximate categorical structure, then, the underlying set-theoretical object is a graph, consisting of a set of objects X and sets of arrows A(x, y) for any x, y ∈ X. The distance function d(f, g, h) is required to be defined whenever f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z). The main axioms, generalizing the tetrahedral axiom of a 2-metric space, are the left and right associativity properties. These concern the situation of a sequence of objects x, y, z, w and arrows going in the increasing direction:

\xymatrix{ &  & z \ar[dr]^{h} \\ x \ar[r]^{f} \ar[urr]^{a} \ar[rrr]_{c} & y \ar[ur]^{g} \ar[rr]^{b} &  & w}

The left associativity condition says

d(a, h, c) ≤ d(f, g, a) + d(g, h, b) + d(f, b, c).

It means that if a is close to a composition of f and g, if b is close to a composition of g and h and if c is close to a composition of f and b, then c is also close to a composition of a and h.

Looking at the same picture but viewed with the arrow c passing along the top:

\xymatrix{x \ar[rr]^{a} \ar[dr]_{f} \ar[rrr]^{c} &  & z \ar[r]^{h} & w \\  & y \ar[ur]_{g} \ar[urr]_{b}}

the right associativity condition says

d(f, b, c) ≤ d(f, g, a) + d(g, h, b) + d(a, h, c).

It is natural to add the data of identity elements 1_{x} ∈ A(x, x) such that

d(1_{x}, f, f) = 0 and d(f, 1_{y}, f) = 0.

The theory now works out pretty nicely. For example, we obtain a distance function on the arrow sets

dist_{A(x,y)}(f, g) := d(1_{x}, f, g).

This is a pseudometric, that is to say it satisfies the triangle inequality but there might be distinct pairs f, g at distance zero apart. We may however identify them together. This is discussed in Section 4.

Perhaps a more direct way to introduce a categorical notion such that the arrow sets are metric spaces, would be just to consider a category enriched in metric spaces. Here, it will be useful for our development to consider the enrichment as being with respect to the product structure where the metric on the product of two metric spaces is the sum of the metrics on the pieces:

d((x, x′), (y, y′)) := d(x, y) + d(x′, y′).

We describe this theory first, in Section 2.

A metrized category then yields an approximate categorical structure, with the tetrahedral inequalities stated in Proposition 2.2.

Approximate categorical structures are weaker objects, in that any subgraph of an approximate categorical structure will have an induced approximate categorical structure. In particular, if we start with a metrized category and take any subgraph then we get an approximate categorical structure. It is natural to ask whether an arbitrary approximate categorical structure arises in this way. There is a good notion of contracting functor (X, A, d) → (Y, B, d) between two approximate categorical structures, see Definition 5.3, so we can look at contracting functors from an approximate categorical structure to metrized categories. Any such functor induces a distance on the free category Free(X, A) generated by the graph (X, A) and we obtain a distance denoted d^{max} on Free(X, A) as the supremum of these distances. This is discussed in Section 10. The upper bound

d^{max}(f, g, h) ≤ d(f, g, h)

is tautological. In general it is not sharp, meaning that an approximate categorical structure doesn’t always come from a metrized category. An example is given in Subsection 6.6.

Let us look at some of the motivation for introducing this kind of structure. There are many directions of study looking into the notion of “higher dimensional category theory”, most notably of course the various theories of n-categories, ∞-categories and the like. In this context, when one learns of the notion of 2-metric space, it seems compelling to think that there might be other, possibly related ways of approaching higher-dimensionality. The basic idea of a 2-metric is to replace distance by area, in that sense it is higherdimensional. We were therefore interested in looking for a notion related to 2-metric spaces but with a stronger categorical flavor. At the same time, one of the applications of metric spaces and various related notions, is to the theory of optimization. It is therefore natural to think of the notion of “path” joining one state to another. One way of going to a higher-dimensional structure was to generalize the notion of 2-metric to encompass the idea of looking at the area cut out by a collection of paths. As we shall see in the example treated in Subsection 6.4 and then in Section 11, this intuition does indeed work out.

If these were some of our basic motivations, the main thrust of the present work is to introduce the theory in its formal aspects. Numerous relationships with notions from enriched category theory suggest that further thought in those directions could uncover more links with the idea of higher-dimensional categories.

Getting back to the contents of the paper, we are going to look at how far an approximate categorical structure is from being a substructure of a metrized category. This is measured by the distance d^{max}, and we give a strong lower bound for d^{max} under a certain hypothesis. Recall that in [Aliouche and Simpson, 2012] and [Aliouche and Simpson, 2014], it was useful to introduce a new axiom, called transitivity, for 2-metric spaces. This was a metric version of the idea that given four points, if two triples are colinear then all four are colinear, especially if the two middle points aren’t too close together.

In Section 7, we introduce the analogue of the transitivity axiom for approximate categorical structures in Definition 7.3. This axiom turns out to be what is required in order to be able to define the Yoneda functors Y_{u}, for u ∈ X. We would like to set Y_{u}(x) := A(u, x) together with its distance. This is a metric space and the distance d(a, f, b) allows us to define a bimodule [Lawvere, 1973] from Y_{u}(x) to Y_{u}(y), see Section 9. There is a metrized category of (bounded) metric spaces with morphisms the bimodules. If (X, A, d) is transitive, then Y_{u} is a contracting functor from (X, A, d) to this metrized category.

Existence of these functors yields lower bounds on d^{max}(f, g, h) and somewhat surprisingly the lower bounds are sharp: we have that

d^{max}(f, g, h) = d(f, g, h)

whenever (X, A, d) is absolutely transitive (also needed are boundedness and a very weak graph transitivity hypothesis 7.1). We obtain the following embedding theorem saying that an approximate categorical structure with these properties is obtained as a subgraph of a metrized category.

1.1. Theorem. Suppose (X, A, d) is an approximate categorical structure that is bounded, satisfies the separation property (Definition 4.7), is absolutely transitive (Definition 7.3) and satisfies Hypothesis 7.1. Then there exists a metrized category 𝒞 with Ob(𝒞) = X and inclusions A(x, y) ⊂ 𝒞 (x, y) such that for any f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z),

d(f, g, h) = d_{𝒞} (g ∘_{𝒞} f, h).

Then example of Subsection 6.6 shows that an hypothesis like absolute transitivity is needed for such an embedding statement.

In Section 11 we discuss how the d^{max} construction, applied to the standard 2-metric space with triangle area, gives rise to the category of piecewise-linear paths. Then, in Section 12, we discuss further questions and directions.

2. Metrized categories

A category is a triple (X, A, ∘) where X is the set of objects, A(x, y) is the set of arrows from x to y for each pair of objects and g ∘ f ∈ A(x, z) whenever f ∈ A(x, y) and g ∈ A(y, z). These are subject to the existence of an identity arrow 1_{x} ∈ A(x, x) satisfying f ∘ 1_{x} = f and 1_{y} ∘ f = f for all f ∈ A(x, y) and the associativity axiom for f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(z, w) requiring

h ∘ (f ∘ g) = (h ∘ f) ∘ g.

We can introduce the notion of pseudometric structure on a category as above. A pseudometric collection is the data of a pseudometric on each morphism set, that is to say ϕ(f, g) ∈ ℝ defined for every f, g ∈ A(x, y), satisfying the properties of a pseudometric:

ϕ(f, f) = 0, ϕ(f, g) = ϕ(g, f) and ϕ(f, g) ≤ ϕ(f, h) + ϕ(h, g).

If in addition

ϕ(f, g) = 0 ⇒ f = g,

then it is a metric collection. This separation condition will be imposed as appropriate, see also Definition 4.7 below.

We require the following compatibility with the structure of category: for any triple of objects x, y, z ∈ X, the composition function

A(x, y) × A(y, z) → A(x, z), (f, g) ↦ g ∘ f

should be nonincreasing, where we provide the product on the left with the metric

(ϕ + ϕ)((f, g), (f′, g′)) := ϕ(f, f′) + ϕ(g, g′).

In concrete terms this is equivalent to requiring that

ϕ(g ∘ f, g′ ∘ f′) ≤ ϕ(f, f′) + ϕ(g, g′).  (1)

If there is no confusion, we denote ϕ(f, f′) by just dist_{A(x,y)}(f, f′) or d_{A(x,y)}(f, f′).

2.1. Definition. A pseudo-metric structure on a category, is a pseudometric collection that satisfies the axiom (1). We call a category with such a structure a pseudo-metrized category. If the separation property holds we call it a metrized category.

In more abstract terms, if we view metric spaces as (ℝ_{≥0}, +)-enriched categories [Lawvere, 1973], the metric that we are using on the product of two metric spaces corresponds to the Eilenberg-Kelly tensor product of enriched categories [Kelly, 1982]. A metrized category is, in turn, a category enriched over this tensor product. In that sense, it is some kind of 2-categorical structure.

As motivation for the next section, if (X, A, ∘, ϕ) is a pseudo-metrized category, we can define a function of three variables d(f, g, h) defined whenever f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z) by putting

d(f, g, h) := ϕ(g ∘ f, h).

2.2. Proposition. This function satisfies the following properties: —for all f, g ∈ A(x, y) we have

d(f, 1_{y}, g) = d(1_{x}, f, g) = ϕ(f, g);

—for all (f, g, h; a, b; c) with

x →^{f} y →^{g} z →^{h} w

and

x →^{a} z, y →^{b} w, x →^{c} w

we have:

d(f, b, c) ≤ d(f, g, a) + d(g, h, b) + d(a, h, c)

and

d(a, h, c) ≤ d(f, g, a) + d(g, h, b) + d(f, b, c).

Proof. For the first statements note that

d(f, 1_{y}, g) := ϕ(1_{y} ∘ f, g) = ϕ(f, g)

and

d(1_{x}, f, g) := ϕ(f ∘ 1_{x}, g) = ϕ(f, g).

In the second part, applying the definitions, the first inequality that we would like to show is equivalent to

ϕ(b ∘ f, c) ≤ ϕ(g ∘ f, a) + ϕ(h ∘ g, b) + ϕ(h ∘ a, c).

By the triangle inequality in A(x, w) applied to the sequence b ∘ f, h ∘ g ∘ f, h ∘ a, c we have

ϕ(b ∘ f, c) ≤ ϕ(b ∘ f, h ∘ g ∘ f) + ϕ(h ∘ g ∘ f, h ∘ a) + ϕ(h ∘ a, c).

The composition axiom (1) implies that

ϕ(h ∘ g ∘ f, h ∘ a) ≤ ϕ(h, h) + ϕ(g ∘ f, a) = ϕ(g ∘ f, a).

Similarly

ϕ(b ∘ f, h ∘ g ∘ f) ≤ ϕ(b, h ∘ g) = ϕ(h ∘ g, b).

Therefore we get

ϕ(b ∘ f, c) ≤ ϕ(h ∘ g, b) + ϕ(g ∘ f, a) + ϕ(h ∘ a, c).

Putting in the definition d(f, g, h) := ϕ(g ∘ f, h) this gives

d(f, b, c) ≤ d(g, h, b) + d(f, g, a) + d(a, h, c),

which is the first inequality. The proof of the second inequality is similar.

Suppose (X, A, ∘, ϕ) is a category with a pseudometric ϕ. Define a new set Ã(x, y) to be the quotient of A(x, y) by the relation that x ∼ x′ if ϕ(x, x′) = 0. This is an equivalence relation. It is compatible with the composition operation by the axiom (1). Therefore ∘ induces a composition which we again denote ∘ on (X, Ã). Also the distance ϕ induces a metric ϕ̃ on Ã(x, y), and (X, Ã, ∘, ϕ̃) is a metrized category satisfying the separation property.

2.3. Example. Let Met be the category of bounded metric spaces, with morphisms the non-expansive maps. If we give the morphism sets the sup-norm metric

ϕ_{Met(X,Y)}(f, g) := sup_{x∈X} d_{Y} (f(x), g(x))

we get a metrized category.

3. Approximate categories

Abstracting the properties given by Proposition 2.2, we can forget about the composition operation and just look at the function of three variables d(f, g, h).

Consider a set of objects X and for each x, y ∈ X a set of arrows A(x, y). Suppose we have isolated an identity arrow 1_{x} ∈ A(x, x) for each x ∈ X. Consider a triangular distance function d(f, g, h) ∈ ℝ defined whenever

\xymatrix{ & y \ar[dr]^{g} \\ x \ar[ur]^{f} \ar[rr]^{h} &  & z}

that is to say f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z).

Assume the following axioms: Identity axioms— Left identity : for all f ∈ A(x, y) we have

d(f, 1_{y}, f) = 0;

Right identity : for all f ∈ A(x, y) we get

d(1_{x}, f, f) = 0;

Associativity axioms—given a “tetrahedron” denoted (f, g, h; a, b; c) that consists of arrows

x →^{f} y →^{g} z →^{h} w and x →^{a} z, y →^{b} w, x →^{c} w,  (2)

Left associativity :

d(a, h, c) ≤ d(f, g, a) + d(g, h, b) + d(f, b, c);

Right associativity:

d(f, b, c) ≤ d(f, g, a) + d(g, h, b) + d(a, h, c).

3.1. Definition. An approximate categorical structure is a triple (X, A, d), together with the specified identities 1_{x}, satisfying the above axioms.

An approximate semi-categorical structure is a triple (X, A, d), without specified identities, satisfying just the associativity axioms.

3.2. Lemma. Suppose (X, A, d) is an approximate categorical structure. Then for any x, y, z ∈ X with f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z), we have d(f, g, h) ≥ 0.

Proof. For notational simplicity we denote the third map by a. Then, use left associativity for (f, g, 1_{z}; a, g; a). It says

d(a, 1_{z}, a) ≤ d(f, g, a) + d(g, 1_{z}, g) + d(f, g, a).

Since d(a, 1_{z}, a) = 0 and d(g, 1_{z}, g) = 0 we get 2d(f, g, a) ≥ 0, therefore d(f, g, a) ≥ 0 as claimed.

3.3. Lemma. Suppose (X, A, d) is an approximate semi-categorical structure (resp. categorical structure) and suppose we are given subsets B(x, y) ⊂ A(x, y) (resp. subsets containing 1_{x} if x = y). Then (X, B, d|_{B}) is an approximate semi-categorical (resp. categorical) structure.

Proof. The conditions for d|_{B} follow from the same conditions for d on A.

3.4. Corollary. Let (X, C, ∘, ϕ) be a pseudo-metrized category and suppose A(x, y) ⊂ C(x, y) are subsets. Then (X, A, d|_{A}) is an approximate semi categorical structure and if 1_{x} ∈ A(x, x) then we get an approximate categorical structure. Again assuming 1_{x} ∈ A(x, x), if (X, C, ∘, ϕ) was a metrized category then (X, A, d|_{A}) is a separated approximate categorical structure, cf Definition 4.7 below.

An approximate categorical structure is clearly also an approximate semi-categorical structure.

3.5. Question. Suppose (X, A, d) is an approximate semi-categorical structure. Let A^{+}(x, y) := A(x, y) for x ≠ y and A^{+}(x, y) := A(x, x) ⊔ {1_{x}}. Is there a natural way to extend d to A^{+} to obtain an approximate categorical structure?

4. Metrics on the arrow sets

Suppose (X, A, d) is an almost categorical structure. We would like to use d to put a (pseudo)-metric on the arrow sets of the graph A(x, y). The idea is to use the identity morphisms to go from a pair of arrows to a triangle. The first lemma shows that this process will be independent of direction.

4.1. Lemma. If x, y ∈ X and f, g ∈ A(x, y) then

d(f, 1_{y}, g) = d(1_{x}, f, g).

Proof. For the tetrahedron denoted as in (2) by (1_{x}, f, 1_{y}; f, f; g), the left associativity axiom says

d(f, 1_{y}, g) ≤ d(1_{x}, f, f) + d(f, 1_{y}, f) + d(1_{x}, f, g) = d(1_{x}, f, g).

On the other hand, the right associativity axiom for the same tetrahedron (1_{x}, f, 1_{y}; f, f; g) gives

d(1_{x}, f, g) ≤ d(1_{x}, f, f) + d(f, 1_{y}, f) + d(f, 1_{y}, g) = d(f, 1_{y}, g).

By the preceding lemma, we can define a distance on A(x, y) as follows, for f, g ∈ A(x, y) put

ϕ(f, g) := d(1_{x}, f, g).

From the previous lemma, we also have

ϕ(f, g) := d(f, 1_{y}, g).

Note that for any x we have

d(1_{x}, 1_{x}, 1_{x}) = 0.

4.2. Lemma. This distance is a pseudo-metric, in other words it is reflexive:

ϕ(f, f) = 0,

symmetric:

ϕ(f, g) = ϕ(g, f),

and satisfies the triangle inequality:

ϕ(f, g) ≤ ϕ(f, h) + ϕ(h, g).

Proof. By definition

ϕ(f, f) = d(f, 1_{y}, f) = 0

by the left identity axiom. Using left associativity we have

ϕ(f, g) = d(f, 1_{y}, g)
≤ d(g, 1_{y}, f) + d(1_{y}, 1_{y}, 1_{y}) + d(g, 1_{y}, g),

so

ϕ(f, g) ≤ d(g, 1_{y}, f) = ϕ(g, f),

which by symmetry gives ϕ(f, g) = ϕ(g, f). For the triangle inequality suppose f, g, h ∈ A(x, y), then applying left associativity we get

ϕ(f, g) = d(f, 1_{y}, g)
≤ d(h, 1_{y}, f) + d(1_{y}, 1_{y}, 1_{y}) + d(h, 1_{y}, g),

therefore

ϕ(f, g) ≤ ϕ(h, f) + ϕ(h, g).

APPROXIMATE CATEGORICAL STRUCTURES  1531

4.3. Lemma. Given f, f′ ∈ A(x, y), h ∈ A(y, z) and c ∈ A(x, z) we have

d(f, h, c) ≤ d(f′, h, c) + ϕ(f, f′).

Proof. Applying right associativity with (f, 1_{y}, h; f′, h; c), that is g := 1_{y}, a := f′ and b := h we get

d(f, b, c) ≤ d(f, g, a) + d(g, h, b) + d(a, h, c),

which in our case says

d(f, h, c) ≤ d(f, 1_{y}, f′) + d(1_{y}, h, h) + d(f′, h, c).

Since ϕ(f, f′) = d(f, 1_{y}, f′) and d(1_{y}, h, h) = 0 we obtain the desired statement.

Similarly: 4.4. Lemma. Given f ∈ A(x, y), h, h′ ∈ A(y, z) and c ∈ A(x, z) we have

d(f, h, c) ≤ d(f, h′, c) + ϕ(h, h′).

Proof. Same as for the previous lemma but using left associativity.

For the third edge: 4.5. Lemma. Given f ∈ A(x, y), g ∈ A(y, z) and c ∈ A(x, z) we have

d(f, g, c) ≤ d(f, g, c′) + ϕ(c, c′).

Proof. Applying right associativity with (f, g, 1_{z}; c′, g; c), that is h := 1_{z}, a := c′ and b := g we have

d(f, b, c) ≤ d(f, g, a) + d(g, h, b) + d(a, h, c),

which in our case says

d(f, g, c) ≤ d(f, g, c′) + d(g, 1_{z}, g) + d(c′, 1_{z}, c).

Since

ϕ(c, c′) = d(c′, 1_{z}, c) and d(g, 1_{z}, g) = 0,

we obtain the desired statement.

Putting these together we get: 4.6. Corollary. Given f, f′ ∈ A(x, y), g, g′ ∈ A(y, z) and h, h′ ∈ A(x, z) we have

d(f, g, h) ≤ d(f′, g′, h′) + ϕ(f, f′) + ϕ(g, g′) + ϕ(h, h′).

Proof. Combine the above.

4.7. Definition. We say that an approximate categorical structure is separated if

ϕ(f, f′) = 0 ⇒ f = f′.

Equivalently, each (A(x, y), ϕ) is a metric space rather than a pseudometric space.

The separation property may be ensured by a quotient construction. Given an approximate categorical structure in general, define the relation that

f ∼ f′ if ϕ(f, f′) = 0.

4.8. Lemma. This is an equivalence relation on A(x, y). Let Ã(x, y) := A(x, y)/ ∼. The distance function d(f, g, h) passes to the quotient to be a function of f ∈ Ã(x, y), g ∈ Ã(y, z) and h ∈ A(x, z). Then (X, Ã, d) is a separated approximate categorical structure.

Proof. It is an equivalence relation by the triangle inequality of ϕ. The above corollary says that d passes to the quotient. The axioms hold to get an approximate categorical structure.

The lemma shows that an approximate categorical structure can always be replaced by one which satisfies the separation property. We will generally assume that this has been done.

4.9. Lemma. Suppose (X, A, d) is a separated approximate categorical structure. The function d is continuous on the topologies associated to the metric spaces A(·, ·). More precisely, for any x, y, z ∈ X,

d : A(x, y) × A(y, z) × A(x, y) → ℝ

is a continuous function of its three variables.

Proof. This also follows from Corollary 4.6.

Here is a bound going in the opposite direction of the previous ones.

4.10. Lemma. In an approximate categorical structure (X, A, d), for any x, y, z ∈ X and any f ∈ A(x, y), g ∈ A(y, z) and a, a′ ∈ A(x, z) we have

ϕ(a, a′) ≤ d(f, g, a) + d(f, g, a′).

Proof. Applying left associativity for the tetrahedron (f, g, 1_{z}; a, g; a′), that is for h := 1_{z}, b := g and c := a′ we get

d(a, h, c) ≤ d(f, g, a) + d(g, h, b) + d(f, b, c),

which in our case says

d(a, 1_{z}, a′) ≤ d(f, g, a) + d(g, 1_{z}, g) + d(f, g, a′).

As d(g, 1_{z}, g) = 0 and d(a, 1_{z}, a′) = ϕ(a, a′) we obtain the desired statement.

4.11. Corollary. If

d(f, g, h) = d(f, g, h′) = 0,

then ϕ(h, h′) = 0. In particular, if the separation property (Definition 4.7) is satisfied then it implies that h = h′.

Below we shall also need the following notion of boundedness.

4.12. Lemma. For an approximate categorical structure (X, A, d) the following conditions are equivalent:

1. For each triple x, y, z the set of values of d(f, g, h) for f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z) is bounded.

2. For each x, y the pseudo-metric space (A(x, y), ϕ) is bounded.

If these are satisfied we say that (X, A, d) is bounded.

Proof. Clearly the first condition implies the second. Assume that the (A(x, y), ϕ) are bounded. Then, for any triple x, y, z using this boundedness for (x, y), (y, z) and (x, z), Corollary 4.6 implies the first condition for x, y, z.

5. Functors

Given two graphs (X, A) and (Y, B), a prefunctorial map F : (X, A) → (Y, B) consists of a map F : X → Y and, for all x, y ∈ X, a map F : A(x, y) → A(F x, F y). If the graphs are provided with chosen identity arrows, then we generally assume that a F is unital, that is F (1_{x}) = 1_{F x}.

Given approximate categorical structures on these graphs (X, A, d) and (Y, B, d), and a real number k ≥ 0, we say that a prefunctorial map F is k-contractive if it is unital and whenever x, y, z ∈ X and f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z) we have

d(F (f), F (g), F (h)) ≤ kd(f, g, h).

Recall that ϕ denotes the metrics on the morphism spaces defined in the previous section.

5.1. Lemma. Suppose F : (X, A, d) → (Y, B, d) is a k-contractive prefunctorial map. Then for any x, y ∈ X and f, f′ ∈ A(x, y) we have

ϕ(F (f), F (f′)) ≤ kϕ(f, f′).

Proof. It follows from the definition of ϕ and the condition that F is unital.

5.2. Proposition. Suppose (X, A, ∘, ϕ_{A}) and (Y, B, ∘, ϕ_{B}) are metrized categories, and let (X, A, d_{A}) and (Y, B, d_{B}) be the associated approximate categorical structures. Then a k-contractive prefunctorial map F from (X, A, d_{A}) to (Y, B, d_{B}) is the same thing as a functor from (X, A, ∘) to (Y, B, ∘) which is k-contractive on the metric spaces of morphisms.

Proof. Suppose given a k-contractive prefunctorial map. Since ϕ_{B} is a metric, it separates points. We have

ϕ_{B}(F (g) ∘ F (f), F (g ∘ f)) ≤ kϕ_{A}(g ∘ f, g ∘ f) = 0

so F (g) ∘ F (f) = F (g ∘ f). Compatibility with identities is part of the definition, so F is a functor. The previous lemma shows that F is k-contractive on the morphism spaces. In the other direction, given a functor that is k-contractive on the morphism spaces, it is a prefunctorial map and

d_{B}(F (f), F (g), F (h)) = ϕ_{B}(F (g) ∘ F (f), F (h)) = ϕ_{B}(F (g ∘ f), F (h))
≤ kϕ_{A}(g ∘ f, h) = kϕ_{A}(f, g, h),

so F is k-contracting as a map between approximate categorical structures.

5.3. Definition. A contracting functor between approximate categorical structures F : (X, A, d) → (Y, B, d) is a 1-contractive prefunctorial map, in other words a unital prefunctorial map such that d(F (f), F (g), F (h)) ≤ d(f, g, h). It is said to be an embedding if equality holds for all f, g, h.

A contracting functor (resp. embedding) from an approximate categorical structure to a metrized category (𝒞 , ∘, ϕ_{𝒞} ), is defined to be a contracting functor F (resp. embedding) to the associated approximate categorical structure. This means that it should send the unit arrows to the identities of 𝒞, and should satisfy the inequality

ϕ_{𝒞} (F (g) ∘ F (f), F (h)) ≤ d(f, g, h)  (3)

(resp. should satisfy equality here).

5.4. Remark. In the situation of Lemma 3.3, where (X, A, d) is an approximate categorical structure and for each x, y ∈ X there is B(x, y) ⊂ A(x, y) containing the identities if x = y, the inclusion (X, B, d) ↪ (X, A, d) is an embedding. In the other direction, any embedding in the sense of Definition 5.3 that induces an isomorphism on the set of objects, is of this form.

6. Examples

Let us now consider some examples. Various aspects illustrate definitions to be given in later sections, so there will be forward referencing towards those.

6.1. Example from a 2-metric space. Suppose (X, d_{X}) is a set with a function x, y, z ∈ X ↦ d_{X}(x, y, z) ∈ ℝ. Consider A^{coarse}(x, y) := {∗_{x,y}} the coarse graph structure on X, in other words A^{coarse}(x, y) is the set with a single element which is denoted by ∗_{x,y}. We would like to relate the property of (X, d) being a 2-metric space [Gähler, 1963], and a few of the additional axioms proposed in [Aliouche and Simpson, 2012], to the notion of approximate categorical structure for (X, A).

We assume that x, y, z ↦ d_{X}(x, y, z) is symmetric under permutations of x, y, z.

Set 1_{x} := ∗_{x,x}, and define

d(∗_{x,y}, ∗_{y,z}, ∗_{x,z}) := d_{X}(x, y, z).

6.2. Theorem. Keep the above notations and symmetry hypothesis. Then (X, A^{coarse}, d) is an approximate categorical structure if and only if (X, d_{X}) is a 2-metric space.

Suppose d_{X} is a bounded 2-metric, and define the function α by α(∗_{x,y}) := φ(x, y) where φ(x, y) := sup_{c∈X} d(x, y, c) is the distance function [Aliouche and Simpson, 2012]. This provides an amplitude for (X, A^{coarse}, d) in the sense of Definition 12.2 below.

With the notations of the preceding paragraph, if now (X, d_{X}) satisfies the transitivity axiom (Trans) of [Aliouche and Simpson, 2012], the approximate categorical structure (X, A^{coarse}, d) is α/2-transitive in the sense of Definition 7.3 below. In the other direction, if (X, A^{coarse}, d) is α-transitive then (X, d_{X}) satisfies the transitivity axiom (Trans) of [Aliouche and Simpson, 2012].

Proof. Suppose (X, d_{X}) is a 2-metric space, then we obtain an approximate categorical structure. The identities are 1_{x} := ∗_{x,x}. We have d_{X}(x, x, y) = 0 and d_{X}(x, y, y) = 0 by the reflexivity axioms for a 2-metric space, which show the left and right identity axioms for an approximate categorical structure. The left associativity property for an approximate categorical structure requires that for any x, y, z, w ∈ X we have

d(∗_{x,z}, ∗_{z,w}, ∗_{x,w}) ≤ d(∗_{x,y}, ∗_{y,x}, ∗_{x,z}) + d(∗_{y,z}, ∗_{z,w}, ∗_{y,w})
+d(∗_{x,y}, ∗_{y,w}, ∗_{x,w}).

This translates as

d_{X}(x, z, w) ≤ d_{X}(x, y, z) + d_{X}(y, z, w) + d_{X}(x, y, w)

which is the tetrahedral axiom (Tetr) for a 2-metric space with y as the point in the middle. Similarly, right associativity for the approximate categorical structure translates to the same tetrahedral axiom but with z as the point in the middle. Thus if (X, d_{X}) is a 2-metric space then (X, A, d) is an approximate categorical structure.

In the other direction, if (X, A, d) is an approximate categorical structure then we have seen that d(∗_{x,y}, ∗_{y,z}, ∗_{x,z}) ≥ 0, so d_{X}(x, y, z) ≥ 0. The axioms for a 2-metric space now translate from the axioms for an approximate categorical structure as above, noting that the symmetry axiom for a 2-metric space has been supposed here as a hypothesis.

Next consider the definition of an amplitude, see Definition 12.2 below. Suppose (X, d_{X}) is a bounded 2-metric space and put

α(∗_{x,y}) := φ(x, y) = sup_{c∈X} d_{X}(x, y, c).

This satisfies the reflexivity property for Definition 12.2 since α(1_{x}) = α(∗_{x,x}) = φ(x, x) =

0. It also satisfies the various triangle inequalities, indeed for any x, y, z we have [Aliouche and Simpson, 2012, Lemma 3.2]

φ(x, z) ≤ φ(x, y) + φ(y, z) + d(x, y, z)

so α is an amplitude.

We now relate the transitivity conditions, see Definition 7.3 below. This is not a perfect correspondence, because we have modified our definition of transitivity slightly in order that it work better with the discussion to come later in the paper.

The transitivity axiom (Trans) of [Aliouche and Simpson, 2012] says that given 4 points x, y, z, w we should have

d_{X}(x, y, w)φ(y, z) ≤ d_{X}(x, y, z) + d_{X}(y, z, w).

It implies by permutation that

d_{X}(x, z, w)φ(y, z) ≤ d_{X}(x, y, z) + d_{X}(y, z, w).

On the other hand, for an amplitude α our left and right transitivity axioms in Definition 7.3 both translate in terms of d_{X} to

α(∗_{y,z})(d_{X}(x, y, w) + d_{X}(x, z, w)) ≤ d_{X}(x, y, z) + d_{X}(y, z, w).

In the case of left transitivity we should apply Definition 7.3 to the points in order y, x, z, w which is the same as right transitivity of Definition 7.3 for the points in order x, y, w, z.

If we assume the transitivity of [Aliouche and Simpson, 2012] then by adding the two previous equations and dividing by 2 we get Definition 7.3 for the function α/2. On the other hand, by positivity of the distances, if we know the condition of Definition 7.3 for α then we get the transitivity property of [Aliouche and Simpson, 2012].

If L ⊂ X is a line, then it corresponds to a 0-categoric sub-structure of (X, A, d).

The approximate categorical structure (X, A, d) defined from a 2-metric space as above, is generally not absolutely transitive, because we need to use the amplitude α given by φ, that has in particular α(1_{x}) = 0.

6.3. A finite example. Consider a very first case. Let X = {x} have a single object and A(x, x) = {1, e} with 1 = 1_{x}. Put

ϕ := ϕ(1, e) = d(1, e, 1) = d(e, 1, 1) = d(1, 1, e).

The remaining quantities to consider are d(e, e, e) and d(e, e, 1). Recall that there are two categorical structures, with e^{2} = e or e^{2} = 1 and these two numbers represent the distances to these two cases.

From the various associativity laws we get the following inequalities:

d(e, e, e) ≤ ϕ,
d(e, e, 1) ≤ 2ϕ,
|d(e, e, e) − ϕ| ≤ d(e, e, 1),

and

|d(e, e, 1) − ϕ| ≤ d(e, e, e).

Since everything is invariant under scaling (and trivial if ϕ = 0) we may assume ϕ = 1 and set

u := d(e, e, e), v := d(e, e, 1).

Note that u, v ≥ 0. The inequalities become

u ≤ 1, v ≤ 2, |u − 1| ≤ v and |v − 1| ≤ u

which reduce to

u ≤ 1, u + v ≥ 1 and v ≤ u + 1.

Hence, the graph of the allowed region in the (u, v)-plane looks like:

[figure: v; u; e^{2}=1; e^{2}=e]

The categorical structures are (u, v) = (1, 0) for e^{2} = 1 and (u, v) = (0, 1) for e^{2} = e. The third vertex (1, 2) is an extremal case where no categorical relations hold.

A case-by-case analysis shows that these almost categorical structures are absolutely transitive for any (u, v) in the given region. By our main Theorem 10.7, they embed into metrized categories. Such an embedding can be given explicitly, using Example 2.3. If (Z, d_{Z}) ∈ Met is a bounded metric space with a non-expansive self-mapping e : Z → Z, the structure of metrized category on Met induces an approximate categorical structure on the graph ({Z}, {1, e}). Let Z have three points 1, 2, 3 ∈ Z with e(1) = 2, e(2) = 3, e(3) = 2 and put d_{Z}(1, 2) = 1, d_{Z}(2, 3) = u, d_{Z}(1, 3) = v. For (u, v) in the pictured region this satisfies the triangle inequality, e is a contractive mapping and we have ϕ_{Met(Z,Z)}(e ∘ e, e) = u, ϕ_{Met(Z,Z)}(e ∘ e, 1) = v.

6.4. Paths. Consider X := ℝ^{2}, and let A(x, y) be the set of continuous paths f : [0, 1] → X with f(0) = x and f(1) = y. Let d(f, g, h) denote the infimum of the areas, i.e. the measures in X = ℝ^{2} of the images, of disks mapping to X such that the boundary maps to the circle defined by joining the paths f, g and h. Let 1_{x} denote the constant path at the point x.

6.5. Lemma. The resulting triple (X, A, d) is an approximate categorical structure.

Proof. Suppose f : [0, 1] → X is a path from x to y. To show the identity axiom, define the mapping p : [0, 1]^{2} → X by p(s, t) := f(s), and restrict p to the triangle whose vertices are (0, 0), (1, 0) and (1, 1). The triangle is homeomorphic to a disk and we obtain a disk mapping to X whose boundary consists of the paths f, 1_{y} and f such that the disk has total area zero. This shows d(f, 1_{y}, f) = 0. The other identity axiom holds similarly. For the tetrahedral axioms, given three disks corresponding to triangles in the interior of the tetrahedron we can paste them together to get a disk whose boundary consists of the three outer edges and whose area is the sum of the three areas. This shows the required tetrahedral property for either left or right associativity.

This example will be considered further in Section 11.

6.6. A non-embeddable example. In this subsection we give an example of an approximate categorical structure that cannot be embedded in a metrized category. The reader may want to consult Section 10 below for the motivation—this example shows that some hypothesis such as absolute transitivity is necessary in Theorem 10.7.

Let X := {x, y, z, w, u, v} and let A be the graph with arrows denoted ∗_{a,b} ∈ A(a, b) for the following pairs (a, b):

(x, y), (y, z), (z, w), (x, z), (y, w), (x, w),
(x, u), (y, u), (u, z), (u, w) and (x, v), (y, v), (v, z), (v, w)

as well as the identities ∗_{a,a}. The picture is:

\xymatrix{ &  & u \ar[dr] \ar[drr] \\ x \ar[urr] \ar[drr] \ar[r] \ar[rrrr] \ar[rrr] & y \ar[rr] \ar[rrr] \ar[dr] \ar[ur] &  & z \ar[r] & w \\  &  & v \ar[ur] \ar[urr]}

Since there is at most one arrow between any pairs of objects, we will define an approximate categorical structure denoting the distances by a 2-metric style notation d(a, b, c) := d(∗_{a,b}, ∗_{b,c}, ∗_{a,c}).

First assign the following null values: d(x, y, u) = d(y, u, z) = d(u, z, w) = d(x, y, v) = d(y, v, z) = d(v, z, w) = 0. This assigns 0 to the 6 triangles that are pictured with straight edges. Then assign the following values for triangles going from x to z or y to w:

d(x, u, z) = d(x, y, z) = d(x, v, z) = α > 0,
d(y, u, w) = d(y, z, w) = d(y, v, w) = β > 0.

The remaining distances that need to be defined are those going from x to w, namely d(x, y, w), d(x, z, w), d(x, u, w), and d(x, v, w). The reader may check that some of the tetrahedral axioms are guaranteed by the choices made above, and the remaining ones correspond to the conditions in the following lemma.

6.7. Lemma. We get an approximate categorical structure if and only if these distances satisfy the following inequalities:

|d(x, u, w) − d(x, z, w)| ≤ α, |d(x, v, w) − d(x, z, w)| ≤ α,
|d(x, y, w) − d(x, u, w)| ≤ β, |d(x, y, w) − d(x, v, w)| ≤ β.

In particular it is possible to choose values such that d(x, u, w) ≠ d(x, v, w). In that case the approximate categorical structure cannot be embedded into a metrized category, meaning in the terminology of Section 10 below, that d ≠ d^{max}.

Proof. We leave the verification of the tetrahedral axioms to the reader. As α, β > 0 one may choose values with d(x, u, w) ≠ d(x, v, w). If F : (X, A, d) → (𝒞 , ∘, ϕ) is a contracting functor to the approximate categorical structure associated to a metrized category (see Definition 5.3 and particularly inequalities (3)), then the choices of null values imply

F (∗_{u,w}) ∘ F (∗_{x,u}) = F (∗_{z,w}) ∘ F (∗_{y,z}) ∘ F (∗_{x,y}) = F (∗_{v,w}) ∘ F (∗_{x,v}).

Assuming d(x, u, w) ≠ d(x, v, w), it would therefore not be possible to have both

d(x, u, w) = ϕ(F (∗_{u,w}) ∘ F (∗_{x,u}), F (∗_{x,w}))

and

d(x, v, w) = ϕ(F (∗_{v,w}) ∘ F (∗_{x,v}), F (∗_{x,w})).

So this structure cannot be embedded in a metrized category.

We note that this example is not absolutely transitive in the sense of Definition 7.3 below. This motivates the idea that such a transitivity condition could be sufficient to get embeddability, as shall be seen in Theorem 10.7.

7. Category-like conditions

In this section we’ll consider some conditions on an approximate categorical structure, that go in the direction of being a category. The first is a simple existence statement for compositions in the graph.

7.1. Hypothesis. Whenever A(x, y) and A(y, z) are nonempty, then A(x, z) is nonempty too.

7.2. Transitivity. Next we define the absolute transitivity condition that will become the principal hypothesis of our main Theorem 10.7.

In view of the analogy with metric spaces (see Theorem 6.2 above), it is convenient to envision a definition relative to an accessory function. In what follows, let α denote a function on the arrow sets, in other words for any x, y ∈ X we are given

α_{x,y} : A(x, y) → ℝ_{≥0},

usually dropping the subscripts if there is no confusion. See Section 12.1 for a further discussion of natural axioms that α might be required to satisfy.

The following definition gives several related notions of transitivity, first relative to α and then absolute transitivity obtained by using α(k) = 1. Here by convention an inf over the empty set is +∞ and its product with 0 is said to be 0.

7.3. Definition. We say that (X, A, d) satisfies left transitivity with respect to α if for all x, y, z, w ∈ X and f ∈ A(x, y), g ∈ A(y, z), h ∈ A(z, w), k ∈ A(y, w) and l ∈ A(x, w) we have

α(k) inf_{a∈A(x,z)}(d(f, g, a) + d(a, h, l)) ≤ d(g, h, k) + d(f, k, l).

We say that (X, A, d) satisfies right transitivity with respect to α if for all x, y, z, w ∈ X and f ∈ A(x, y), g ∈ A(y, z), h ∈ A(z, w), k ∈ A(x, z) and l ∈ A(x, w) we have

α(k) inf_{a∈A(y,w)}(d(g, h, a) + d(f, a, l)) ≤ d(f, g, k) + d(k, h, l).

We say that (X, A, d) is α-transitive if it satisfies both conditions.

We say that (X, A, d) is absolutely (left or right) transitive if it satisfies one or both of the above conditions for the unit function α = μ defined by μ(k) = 1 for all k.

These notions were originally motivated by the transitivity condition for 2-metric spaces introduced in [Aliouche and Simpson, 2012] as shown in the example of Theorem 6.2 above.

Interestingly for us, the absolute transitivity condition turned out to provide exactly the information needed Section 9 below in order to show that the Yoneda constructions give contracting functors.

7.4. Remark. Absolute transitivity doesn’t imply Condition 7.1, for example a graph with three objects x, y, z and non-identity arrows only from x to y and y to z, satisfies absolute transitivity because of lack of enough input arrows. One therefore usually includes Hypothesis 7.1 at the same time.

7.5. Lemma. Suppose (𝒞 , ϕ) is a metrized category. Then its associated approximate categorical structure is absolutely transitive.

Proof. We show left transitivity. Suppose given x, y, z, w ∈ X and f ∈ A(x, y), g ∈ A(y, z), h ∈ A(z, w), k ∈ A(y, w) and l ∈ A(x, w). Set a := g∘f. Then d(f, g, a) = 0 so the infimum on the left of the required inequality, is ≤ d(a, h, l) = d(g ∘f, h, l) = ϕ(h∘g ∘f, l). We have by the triangle inequality for ϕ,

ϕ(h ∘ g ∘ f, l) ≤ ϕ(h ∘ g ∘ f, k ∘ f) + ϕ(k ∘ f, l)

but ϕ(h ∘ g ∘ f, k ∘ f) ≤ ϕ(h ∘ g, k) by Condition 1) using ϕ(f, f) = 0. Therefore,

d(a, h, l) ≤ d(h, g, k) + d(k, f, l)

giving left absolute transitivity. The proof for right absolute transitivity is similar.

Of course, Hypothesis 7.1 is automatically satisfied by a metrized category.

7.6. The ϵ-categoric condition. We finish the section on category-like conditions with a simple condition stating how close an approximate categorical structure is to coming from a category.

7.7. Definition. We say that (X, A, d) is ϵ-categoric if for any f ∈ A(x, y) and g ∈ A(y, z) there exists h ∈ A(x, z) such that

d(f, g, h) ≤ ϵ.

If (X, A, d) is 0-categoric, then we shall see that it corresponds to an actual category, and the composition is a non expansive function A(x, y) × A(y, z) → A(x, z) with respect to the sum distance on the product.

7.8. Theorem. Suppose (X, A, d) is a 0-categoric approximate category, and suppose that it is separated (Definition 4.7). Then for any f ∈ A(x, y) and g ∈ A(y, z) there is a unique element denoted g ∘ f ∈ A(x, z) such that d(f, g, g ∘ f) = 0. This defines a composition operation making (X, A, ∘, ϕ) into a metrized category. If we let d_{ϕ}(f, g, h) := ϕ(g ∘ f, h) then we have d_{ϕ}(f, g, h) ≤ d(f, g, h) whenever these are defined. The composition maps

A(x, y) × A(y, z) → A(x, z)

are continuous, and indeed they are distance nonincreasing if the left hand side is provided with the sum metric.

Proof. By Corollary 4.11, if h and h′ are any elements such that

d(f, g, h) = d(f, g, h′) = 0,

then ϕ(h, h′) = 0. Since (X, A, d) is separated, this implies that h = h′. Therefore, the composition h = g ∘ f is unique. The associativity (resp. unit) properties imply that the composition is associative (resp. has units).

We would now like to bound the norm of the composition operation. Suppose f, f′ ∈ A(x, y), g, g′ ∈ A(y, z) and let h := g∘f and h′ := g′∘f′. Apply Corollary 4.6 to f′, f, g′, g, and two times h′. As d(f′, g′, h′) = 0 and ϕ(h′, h′) = 0 we get

d(f, g, h′) ≤ ϕ(f, f′) + ϕ(g, g′).

On the other hand,

ϕ(h, h′) = d(h, 1_{z}, h′).

Applying the associativity tetrahedral property to f, g, 1_{z}; h, g; h′ we get

d(h, 1_{z}, h′) ≤ d(f, g, h) + d(g, 1_{z}, g) + d(f, g, h′).

This gives

ϕ(h, h′) ≤ ϕ(f, f′) + ϕ(g, g′).

It says that the composition map is non increasing from the sum distance on A(x, y) × A(y, z) to A(x, z).

7.9. Proposition. Suppose that (X, A, d) is ϵ-categoric for all ϵ > 0 and each metric space (A(x, y), ϕ) is complete. Then it is 0-categoric.

Proof. Given f ∈ A(x, y) and g ∈ A(y, z), for every positive integer m, choose an h_{m} such that

d(f, g, h_{m}) ≤ 1/m.

By left associativity for f, g, 1_{z}; h_{m}, g; h_{n} we have

ϕ(h_{m}, h_{n}) = d(h_{m}, 1_{z}, h_{n})
≤ d(f, g, h_{m}) + d(g, 1_{z}, g) + d(f, g, h_{n})
≤ \frac{1}{m} + \frac{1}{n}.

It follows that (h_{m}) is a Cauchy sequence. By the completeness hypothesis, it has a limit which we denote g ∘ f. By left associativity for 1_{x}, f, g; f, h_{m}; g ∘ f we get

d(f, g, g ∘ f) ≤ d(1_{x}, f, f) + d(f, g, h_{m}) + d(1_{x}, h_{m}, g ∘ f)
≤ \frac{1}{m} + ϕ(h_{m}, g ∘ f).

The right side → 0 as m → ∞ so we obtain d(f, g, g ∘ f) = 0. This is the 0-categoric property.

7.10. Lemma. If (X, A, d, α) is ϵ-categoric for all ϵ > 0, then it is absolutely transitive.

Proof. We show absolute left transitivity. Suppose given f, g, h, k, l as in the definition. For any ϵ > 0 there exists a ∈ A(x, z) such that d(f, g, a) < ϵ. By the tetrahedral axiom,

d(a, h, l) ≤ d(f, g, a) + d(g, h, k) + d(f, k, l)
= ϵ + d(g, h, k) + d(f, k, l).

Therefore

d(f, g, a) + d(a, h, l) ≤ 2ϵ + d(g, h, k) + d(f, k, l).

Such an a exists for any ϵ > 0, thus

inf_{a∈A(x,z)}(d(f, g, a) + d(a, h, l)) ≤ d(g, h, k) + d(f, k, l).

This is the absolute left transitivity condition. The proof for absolute right transitivity is similar.

8. Bimodules

Through the analogy between metric spaces and enriched categories (see the very interesting commentary [Lawvere, 2002]), Lawvere defines the notion of bimodule between two metric spaces [Lawvere, 1973, §3]. These objects serve as weak versions of morphisms, well suited to our present purposes. One may view a bimodule as a kind of “metric correspondence” between metric spaces.

Suppose (X, d_{X}) and (Y, d_{Y}) are bounded metric spaces. Consider the set of bimodules denoted B(X, Y) as follows.

An element of B(X, Y) is a function f : X × Y → ℝ satisfying the following axioms: (B0)—if X is nonempty then Y is nonempty;^{1} (B1)—for any x, x′ ∈ X and y ∈ Y we have

f(x, y) ≤ d_{X}(x, x′) + f(x′, y);

(B2)—for any x ∈ X and y, y′ ∈ Y we get

f(x, y) ≤ f(x, y′) + d_{Y} (y, y′).

Notice that since we assumed d_{X} and d_{Y} to be bounded, the function f will also be bounded.

A functional bimodule is a bimodule which also satisfies the axiom (F)—for any x ∈ X and y, y′ ∈ Y we obtain

d_{Y} (y, y′) ≤ f(x, y) + f(x, y′).

Let F (X, Y) ⊂ B(X, Y) be the subset of functional bimodules.

1Axiom (B0) could be avoided by allowing functions to take the value +∞.

8.1. Definition. If X, Y, Z are metric spaces, and f ∈ B(X, Y) and g ∈ B(Y, Z) we define following [Lawvere, 1973, p 159] the composition denoted g ∘ f by

(g ∘ f)(x, z) := inf_{y∈Y} (f(x, y) + g(y, z)).

If X ≠ ∅ then by (B0) also Y ≠ ∅ so we can form the inf. If X = ∅ then nothing needs to be given to define (g ∘ f).

Define the identity i_{X} ∈ B(X, X) by

i_{X}(x, x′) := d_{X}(x, x′).

Define a distance on B(X, Y) by

d_{B(X,Y)}(f, f′) := sup_{x∈X,y∈Y} |f(x, y) − f′(x, y)|.

The supremum exists since we have assumed that our correspondence function f in the bimodule is bounded.

8.2. Proposition. The composition operation

∘ : B(Y, Z) × B(X, Y) → B(X, Z)

defined in the previous definition, with the identities i_{X}, provides a structure of metrized category denoted Bim whose objects are bounded metric spaces and whose morphism spaces are the metric spaces (B(X, Y), d_{B(X,Y)}).

Proof. First, suppose f ∈ B(X, Y), and consider the composition g := f ∘ i_{X}. We have

g(x, y) = inf_{u∈X}(i_{X}(x, u) + f(u, y)).

Taking u := x we get g(x, y) ≤ f(x, y), but on the other hand, by hypothesis

f(x, y) ≤ d_{X}(x, u) + f(u, y) = i_{X}(x, u) + f(u, y)

for any u, so f(x, y) ≤ g(x, y). This shows the right identity axiom f ∘ i_{X} = f and the proof for left identity is the same.

Suppose f ∈ B(X, Y), g ∈ B(Y, Z) and h ∈ B(Z, W). Put a := g ∘ f. Then

a(x, z) = inf_{y∈Y} (f(x, y) + g(y, z))

and

(h ∘ a)(x, w) = inf_{z∈Z}(a(x, z) + h(z, w))
= inf_{y∈Y,z∈Z}(f(x, y) + g(y, z) + h(z, w)).

If we put b := h ∘ g then the expression for (b ∘ f)(x, w) is the same, showing associativity. The composition operation therefore defines a category.

To show that the metric gives a metrized structure, we need to show that

d_{B(X,Z)}(g ∘ f, g ∘ f′) ≤ d_{B(X,Y)}(f, f′) + d_{B(Y,Z)}(g, g′).

Suppose

d_{B(X,Y)}(f, f′) ≤ ϵ and d_{B(Y,Z)}(g, g′) ≤ ε.

It means that

f(x, y) ≤ f′(x, y) + ϵ, f′(x, y) ≤ f(x, y) + ϵ

and

g(y, z) ≤ g′(y, z) + ε, g′(y, z) ≤ g(y, z) + ε.

Then

(g′ ∘ f′)(x, z) = inf_{y∈Y} (f′(x, y) + g′(y, z))
≤ inf_{y∈Y} (f(x, y) + ϵ + g(y, z) + ε)
= (g ∘ f)(x, z) + ϵ + ε.

Similarly

(g ∘ f)(x, z) ≤ (g′ ∘ f′)(x, z) + ϵ + ε.

It follows from this statement that

d_{B(X,Z)}(g ∘ f, g ∘ f′) ≤ d_{B(X,Y)}(f, f′) + d_{B(Y,Z)}(g, g′)

as required.

The metrized category structure means that we can provide the collection of sets B(X, Y) with an approximate categorical structure. If X, Y, Z are three metric spaces, this gives for f ∈ B(X, Y), g ∈ B(Y, Z) and h ∈ B(X, Z) the distance

d(f, g, h) := d_{B(X,Z)}(g ∘ f, h) = sup_{x∈X,z∈Z} |h(x, z) − inf_{y∈Y} (f(x, y) + g(y, z))| .

Write X −−→^{f} Y if f ∈ B(X, Y).

8.3. Lemma. The condition d(f, g, h) ≤ ϵ is equivalent to the conjunction of the following two conditions: (d1)—for any x, y, z we have

h(x, z) ≤ f(x, y) + g(y, z) + ϵ

and (d2)—for any x, z and any ϵ′ > ϵ there exists y ∈ Y with

f(x, y) + g(y, z) ≤ h(x, z) + ϵ′.

Proof. This is similar to the technique used in the previous proof.

8.4. Corollary. The above distance satisfies the axioms for an approximate categorical structure. Furthermore, it is absolutely transitive. It is the approximate categorical structure associated to the metrized category Bim.

Proof. This follows from Propositions 8.2 and 2.2. Absolute transitivity follows from Lemma 7.10.

We can more generally define, for any k > 0, the set of k-contractive bimodules B(X, Y; k). For this, we keep the second condition the same but modify the first condition so it says (B1’)—for any x, x′ ∈ X and y ∈ Y we have

f(x, y) ≤ kd_{X}(x, x′) + f(x′, y);

(B2)—for any x ∈ X and y, y′ ∈ Y we have

f(x, y) ≤ f(x, y′) + d_{Y} (y, y′).

Again, the functionality condition (F) is the same as before. Notice that the identity i_{X} will be in here only if k ≥ 1 and furthermore if f is k-contractive then we would need k ≤ 1 in order to get d(i_{X}, f, f) = 0.

It will undoubtedly be interesting to try to iterate the composition of k-contractive bimodules and to study convergence of the iterates.

9. The Yoneda functors

Suppose (X, A, d) is a separated bounded approximate categorical structure, meaning that each A(x, y) is a bounded metric space (Lemma 4.12). Choose u ∈ X. Then we would like to define a “Yoneda functor” x ↦ A(u, x) from (X, A, d) to the approximate categorical structure associated to the metrized category of bimodules Bim defined in the previous section. Put

Y_{u}(x) := (A(u, x), dist_{A(u,x)})

where the distance dist_{A(u,x)} is the distance ϕ coming from d as in Section 4. We assume the separation axiom of Definition 4.7, so Y_{u}(x) is a metric space and it is bounded by assumption.

We will also generally use Hypothesis 7.1, necessary to define certain functions, and then absolute transitivity of Definition 7.3 to get good properties.

For any f ∈ A(x, y) define Y_{u}(f) ∈ B(Y_{u}(x), Y_{u}(y)) by

Y_{u}(f)(a, b) := d(a, f, b).

9.1. Lemma. Assuming Hypothesis 7.1, if f ∈ A(x, y) then

Y_{u}(f) ∈ B(Y_{u}(x), Y_{u}(y)).

Proof. We need to show (B0), (B1) and (B2). Suppose Y_{u}(x) = A(u, x) is nonempty. By Hypothesis 7.1, Y_{u}(y) = A(u, y) is also nonempty, giving (B0).

Suppose a, a′ ∈ Y_{u}(x) = A(u, x) and b ∈ Y_{u}(y) = A(u, y). We have

Y_{u}(f)(a, b) = d(a, f, b) ≤ d_{A(u,x)}(a, a′) + d(a′, f, b)
= d_{A(u,x)}(a, a′) + Y_{u}(f)(a′, b)

by Lemma 4.3, giving (B1).

Suppose a ∈ Y_{u}(x) = A(u, x) and b, b′ ∈ Y_{u}(y) = A(u, y), then

Y_{u}(f)(a, b) = d(a, f, b) ≤ d_{A(u,y)}(b, b′) + d(a, f, b′)
= d_{A(u,y)}(b, b′) + Y_{u}(f)(a, b′)

by Lemma 4.5, giving (B2).

9.2. Proposition. Suppose (X, A, d) is bounded, separated, satisfies Hypothesis 7.1, and furthermore satisfies absolute left transitivity (Definition 7.3). Then the Yoneda map Y_{u} defined above is a contracting functor (Definition 5.3) to the metrized category Bim of bounded metric spaces with morphisms the bimodules.

Proof. Suppose x, y, z ∈ X and f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z). We would like to show the inequality (3). The metric spaces of morphisms in Bim are B(−, −), so what we need to show for (3) is the statement that

d_{B(Y_{u}(x),Y_{u}(z))}(Y_{u}(g) ∘ Y_{u}(f), Y_{u}(h)) ≤ d(f, g, h).

We have for a ∈ Y_{u}(x) = A(u, x) and c ∈ Y_{u}(z) = A(u, z),

Y_{u}(g) ∘ Y_{u}(f)(a, c) = inf_{b∈A(u,y)}(Y_{u}(g)(b, c) + Y_{u}(f)(a, b)).

Note that by Hypothesis 7.1, given a and f it follows that A(u, y) is nonempty so the inf exists. Now

d_{B(Y_{u}(x),Y_{u}(z))}(Y_{u}(g) ∘ Y_{u}(f), Y_{u}(h)) =
sup_{a∈A(u,x),c∈A(u,z)} |Y_{u}(h)(a, c) − Y_{u}(g) ∘ Y_{u}(f)(a, c)|

= sup_{a∈A(u,x),c∈A(u,z)} |Y_{u}(h)(a, c) − inf_{b∈A(u,y)}(Y_{u}(g)(b, c) + Y_{u}(f)(a, b))|

= sup_{a∈A(u,x),c∈A(u,z)} |d(a, h, c) − inf_{b∈A(u,y)}(d(b, g, c) + d(a, f, b))| .

We would like to show that this is ≤ d(f, g, h). This is equivalent to asking that for all a ∈ A(u, x) and c ∈ A(u, z) we should have

d(a, h, c) − inf_{b∈A(u,y)}(d(b, g, c) + d(a, f, b)) ≤ d(f, g, h)  (4)

and

inf_{b∈A(u,y)}(d(b, g, c) + d(a, f, b)) − d(a, h, c) ≤ d(f, g, h).  (5)

In turn, the first one (4) is equivalent to

d(a, h, c) ≤ d(f, g, h) + inf_{b∈A(u,y)}(d(b, g, c) + d(a, f, b))

and this is true by the tetrahedral inequality

d(a, h, c) ≤ d(f, g, h) + d(b, g, c) + d(a, f, b)

for any b. The second one (5) is equivalent to

inf_{b∈A(u,y)}(d(b, g, c) + d(a, f, b)) ≤ d(f, g, h) + d(a, h, c),

but that is exactly the statement of the absolute left transitivity condition of Definition 7.3. Thus under our hypothesis, (5) is true. We obtain the required inequality (3).

For the identities, we need to know that Y_{u}(1_{x}) = i_{Y_{u}(x)}. Recall that the identity i_{Y_{u}(x)} in B(Y_{u}(x), Y_{u}(x)) is just the distance function d_{Y_{u}(x)}, and Y_{u}(x) = A(u, x). Its distance function is

d_{Y_{u}(x)}(f, f′) = d(f, 1_{x}, f′)

by the discussion of Section 4, and in turn this is exactly Y_{u}(1_{x}). This shows that Y_{u} preserves identities, and completes the proof that Y_{u} is a contracting functor.

We can similarly define Yoneda functors in the other direction

Y^{u}(x) := A(x, u)

with the same properties. The opposed statement of the previous proposition says

9.3. Proposition. Suppose (X, A, d) satisfies absolute right transitivity (Definition 7.3). Then the Yoneda map Y^{u} is a contracting functor.

The proof is similar.

9.4. Enrichment over Bim. The referee has pointed out a conceptual interpretation. The category Bim has a monoidal structure

⊠ : Bim × Bim → Bim

defined as follows: (X, d_{X}) ⊠ (Y, d_{Y}) := (X × Y, d_{X⊠Y}) where d_{X⊠Y} ((x, y), (x′, y′)) = d_{X}(x, x′) + d_{Y} (y, y′) is the product metric we have been using. The monoidal structure acts on the morphisms with

⊠ : B(X, Z) × B(Y, W) → B(X × Y, Z × W)

defined by sending a pair (η, ξ) to the bimodule (η ⊠ ξ)((x, y), (z, w)) := η(x, z) + ξ(y, w).

Now, if (X, A, d) is an approximate categorical structure we can try to view it as a (Bim, ⊠)-enriched category. Indeed, the metric spaces (A(x, y), ϕ) provide the required objects of Bim, and for each x, y, z ∈ Ob(X), d_{x,y,z} may be viewed as an element

d_{x,y,z} ∈ B(A(x, y) × A(y, z), A(x, z))

by Corollary 4.6 (note that to get axiom (B0) one should assume Hypothesis 7.1).

9.5. Proposition. Given a bounded approximate categorical structure (X, A, d), then the above collection of data defines a (Bim, ⊠)-enriched category if and only if (X, A, d) satisfies Hypothesis 7.1 and is absolutely transitive.

Proof. In view of axiom (B0) we may assume satisfied Hypothesis 7.1. Then, in our usual situation and notations, associativity of the enrichment says

inf_{a′,h′} (d(f, g, a′) + d(a′, h′, c) + ϕ(h, h′)) = inf_{b′,f′} (ϕ(f, f′) + d(f′, b′, c) + d(g, h, b′)) .

This may be seen to give left and right absolute transitivity, and vice-versa.

Now, the Yoneda functors Y_{u} and Y^{u} are just the classical Yoneda functors for an enriched category.

9.6. Remark. A (Bim, ⊠)-enriched category does not necessarily define an approximate categorical structure, because the tetrahedral associativity axioms need not hold. For these, note that given an approximate categorical structure then actually by Lemma 4.10

d_{x,y,z} ∈ F (A(x, y) × A(y, z), A(x, z))

is in the subspace of functional bimodules—see axiom (F) of Section 8. Conversely, if we already know the Bim-enrichment condition then axiom (F) implies the tetrahedral associativity axioms. Let FBim ⊂ Bim denote the monoidal subcategory whose morphism spaces are F (Y, Z) ⊂ B(Y, Z). Then, a bounded absolutely transitive approximate categorical structure satisfying Hypothesis 7.1, is the same thing as an FBim-enriched category (see however the next remark concerning units).

9.7. Remark. In the above discussion we are assuming given the unital structure of the graph, and only consider enrichments whose units are given that way. But, in a similar vein the referee points out that one could replace this by a weaker collection of “identity bimodules”, yielding notably the property that subgraphs, not necessarily unital, conserve the resulting structure. The details are left to the reader.

10. Functors to metrized categories

Suppose (X, A, d) is an approximate categorical structure. We would like to look at contracting functors F : (X, A, d) → (𝒞 , ϕ_{𝒞} ) to metrized categories. Recall that these are prefunctorial maps preserving unit elements and satisfying the inequalities (3).

First, we consider the free category on (X, A). Let Free(X, A) denote the free category on the graph (X, A). Thus, the set of objects of Free(X, A) is equal to X and

Free(X, A)(x, y) :=
{(x_{0}, …, x_{k}; a_{1}, …, a_{k}) : x_{i} ∈ X, x_{0} = x, x_{k} = y, a_{i} ∈ A(x_{i−1}, x_{i})}.

An arrow (x_{0}, …, x_{k}; a_{1}, …, a_{k}) ∈ Free(X, A)(x_{0}, x_{k}) will be denoted just by ⟨a_{1}, …, a_{k}⟩ if there is no confusion. In particular, ⟨a_{1}⟩ denotes the sequence of length 1. Composition is by concatenation and the identity of x in Free(X, A) is the sequence ⟨⟩_{x} of length k = 0 based at x_{0} = x.

Suppose given a prefunctorial map F : (X, A) → (𝒞 , ϕ_{𝒞} ) from a graph to a metrized category. In particular, F : X → Ob(𝒞) and for any x, y ∈ X we have F : A(x, y) → 𝒞 (F x, F y). Such an F induces a functor of usual categories

Free(F) : Free(X, A) → 𝒞

defined by sending a sequence ⟨a_{1}, …, a_{k}⟩ to the composition F (a_{k})∘⋯∘F (a_{1}) and sending ⟨⟩_{x} to 1_{F x}. Pulling back the distance on 𝒞 we obtain a pseudometric ϕ_{F} on Free(X, A), which is to say for each x, y we have a pullback distance ϕ_{F} on Free(X, A)(x, y) defined by

ϕ_{F} (u, v) := ϕ_{𝒞} (Free(F)(u), Free(F)(v))

The pullback distance gives a structure of pseudometrized category on Free(X, A), not necessarily metric because the separation axiom might not hold.

Now, suppose the graph comes from an almost categorical structure (X, A, d). Then, as was stated in the paragraph after Definition 5.3, F is a contracting functor of approximate categorical structures, if and only if

ϕ_{𝒞} (F (g) ∘ F (f), F (h)) ≤ d(f, g, h)

for any f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z); and also ϕ_{𝒞} (F (1_{x}), 1_{F x}) = 0, that corresponds to the unitality condition for a contracting functor.

These conditions may be formalized. Let dfunct(X, A, d) denote the set of pseudometric structures ϕ on Free(X, A) (Definition 2.1), satisfying the following conditions:

ϕ(⟨f, g⟩, ⟨h⟩) ≤ d(f, g, h) and ϕ(⟨1_{x}⟩, ⟨⟩_{x}) = 0.  (6)

We call the elements of dfunct(X, A, d) functorial distances.

In the second part of Condition (6), note that the sequence ⟨1_{x}⟩ of length one, with the unit arrow that comes from the approximate categorical structure, is not the identity morphism ⟨⟩_{x} of x in Free(X, A).

The previous discussion may be summed up by saying:

10.1. Lemma. A prefunctorial map F : (X, A, d) → (𝒞 , ϕ_{𝒞} ) from an almost categorical structure to a metrized category, is a contracting functor if and only if the pullback distance ϕ_{F} is a functorial distance.

Proof. If F is a contracting functor, then it is unital, giving the second part of (6). The contracting condition means that it satisfies the inequality (3), ϕ_{𝒞} (F (g) ∘ F (f), F (h)) ≤ d(f, g, h), giving the first part of Condition (6). Conversely if (6) is satisfied then F is unital, and it satisfies the contracting condition of Definition 5.3 using the fact that the approximate categorical structure associated to 𝒞 is given by d_{𝒞} (u, v, w) = ϕ_{𝒞} (v ∘ u, w).

10.2. Proposition. Assume Hypothesis 7.1. Given two arrows a, b ∈ Free(X, A)(x, y), the set of values of ϕ(a, b) over all ϕ ∈ dfunct(X, A, d) is bounded. Therefore we may set

ϕ^{max}(a, b) := sup_{ϕ∈dfunct(X,A,d)} ϕ(a, b),

and ϕ^{max} ∈ dfunct(X, A, d) is the unique maximal functorial distance.

Proof. Given that Free(X, A)(x, y) is non empty, Hypothesis 7.1 implies that A(x, y) is nonempty, so we may fix some h ∈ A(x, y). For any ϕ ∈ dfunct(X, A, d) we have

ϕ(a, b) ≤ ϕ(a, ⟨h⟩) + ϕ(⟨h⟩, b),

so it suffices to show that ϕ(a, ⟨h⟩) is bounded (the case of ϕ(⟨h⟩, b) being the same by symmetry). Suppose a = ⟨a_{1}, …, a_{n}⟩ is the composition of a sequence of arrows a_{i} ∈ A(x_{i−1}, x_{i}) with x_{0} = x and x_{n} = y. Again by our hypothesis, we may choose h_{i} ∈ A(x_{0}, x_{i}) with h_{n} = h. We show by induction on i that ϕ(⟨a_{1}, ⋯, a_{i}⟩, ⟨h_{i}⟩) is bounded as ϕ ranges over all functorial distances. This is true for i = 1 since

ϕ(⟨a_{1}⟩, ⟨h_{1}⟩) ≤ ϕ(⟨a_{1}⟩, ⟨1_{x}, h_{1}⟩) + ϕ(⟨1_{x}, h_{1}⟩, ⟨h_{1}⟩)
≤ d(1_{x}, h_{1}, a_{1}) + d(1_{x}, h_{1}, h_{1})
= d(1_{x}, h_{1}, a_{1}).

Suppose it is known for i − 1. Then

ϕ(⟨a_{1}, ⋯, a_{i}⟩, ⟨h_{i}⟩) = ϕ(⟨a_{i}⟩ ∘ ⟨a_{1}, ⋯, a_{i−1}⟩, ⟨h_{i}⟩)
≤ ϕ(⟨a_{i}⟩ ∘ ⟨a_{1}, ⋯, a_{i−1}⟩, ⟨a_{i}⟩ ∘ ⟨h_{i−1}⟩)
+ϕ(⟨h_{i−1}, a_{i}⟩, ⟨h_{i}⟩) (triangle inequality)
≤ ϕ(⟨a_{i}⟩, ⟨a_{i}⟩) + ϕ(⟨a_{1}, ⋯, a_{i−1}⟩, ⟨h_{i−1}⟩)
+ϕ(⟨h_{i−1}, a_{i}⟩, ⟨h_{i}⟩) (by (1))

but ϕ(⟨a_{i}⟩, ⟨a_{i}⟩) = 0 and

ϕ(⟨h_{i−1}, a_{i}⟩, ⟨h_{i}⟩) ≤ d(h_{i−1}, a_{i}, h_{i})

by (6), whereas ϕ(⟨a_{1}, ⋯, a_{i−1}⟩, ⟨h_{i−1}⟩) is bounded by hypothesis. This completes the induction step and we conclude for i = n that ϕ(a, ⟨h⟩) is bounded.

In view of the form of the axioms for a pseudometric structure on the category Free(X, A)(x, y), given a family of pseudometric structures that are individually bounded on any pair of arrows, their supremum is again a pesudometric structure. Also the supremum will satisfy the conditions for a functorial distance. Therefore ϕ^{max} ∈ dfunct(X, A, d).

Denote by d^{max}(f, g, h) the value ϕ^{max}(⟨f, g⟩, ⟨h⟩).

10.3. Remark. We have the tautological upper bound

d^{max}(f, g, h) ≤ d(f, g, h).

We would like to get a lower bound. The following proposition shows that we may think of d^{max} as the maximal function pulled back from a metrized category, that is smaller than d.

10.4. Proposition. Suppose F : (X, A, d) → (𝒞 , ϕ_{𝒞} ) is a contracting functor from (X, A, d) to a metrized category (𝒞 , ϕ_{𝒞} ). Assume Hypothesis 7.1. Then we have

ϕ_{𝒞} (F (g) ∘ F (f), F (h)) ≤ d^{max}(f, g, h).

There exists such a contracting functor on which this inequality is an equality for all f, g, h.

Proof. Let ϕ_{F} be the pullback distance induced by F. Then ϕ_{F} ∈ dfunct(X, A, d) by Lemma 10.1. By the construction of ϕ^{max} we have ϕ_{F} ≤ ϕ^{max}, so

ϕ_{𝒞} (F (g) ∘ F (f), F (h)) = ϕ_{F} (⟨f, g⟩, ⟨h⟩)
≤ ϕ^{max}(⟨f, g⟩, ⟨h⟩) = d^{max}(f, g, h).

This shows the inequality.

Let 𝒞^{max} be the metrized category obtained from Free(X, A)(x, y) by identifying arrows a and b whenever ϕ^{max}(a, b) = 0, as described in the paragraph at the end of Section 2. This is a metrized category with distance induced by ϕ^{max}, the distance is a metric and the map f ↦ ⟨f⟩ defines a contracting functor F^{max} from (X, A, d) to 𝒞^{max}. Tautologically, the inequality is an equality for this functor.

We now apply Proposition 10.4 to the Yoneda functors. Assume that (X, A, d) is a separated bounded approximate categorical structure, and assume that it satisfies absolute transitivity, Definition 7.3, as well as Hypothesis 7.1. Then we have seen in Proposition 9.2 that the Yoneda constructions define contracting functors Y_{u} from (X, A, d) to the metrized category Bim of bounded metric spaces with morphisms the bimodules. More precisely, recall that

Y_{u}(x) = (A(u, x), φ_{u,x})

and for a ∈ A(x, y),

Y_{u}(a) ∈ B(Y_{u}(x), Y_{u}(y)) with Y_{u}(f)(a, b) := d(a, f, b).

Using the assumption that (X, A, d) is absolutely transitive, Proposition 9.2 tells us that Y_{u} is a contracting functor.

10.5. Corollary. Suppose (X, A, d) is separated, bounded, absolutely transitive and satisfies Hypothesis 7.1. Then for any u, x, y, z and a ∈ A(u, x), b ∈ A(u, y), c ∈ A(u, z) and f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z) we have

d(a, h, c) ≤ d^{max}(f, g, h) + d(a, f, b) + d(b, g, c).

For any a, c, f, g, h as above,

inf_{b∈A(u,y)}(d(a, f, b) + d(b, g, c)) ≤ d^{max}(f, g, h) + d(a, h, c).

Proof. Suppose u ∈ X. Then Proposition 9.2 applies because of the hypotheses, to give that Y_{u} is a contracting functor from (X, A, d) to the metrized category Bim. Now, apply Proposition 10.4 to this contracting functor. Suppose x, y, z ∈ X and f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z). In the metrized category Bim, the morphism space from Y_{u}(x) to Y_{u}(z) is (B(Y_{u}(x), Y_{u}(z)), d_{B(Y_{u}(x),Y_{u}(z))}). Therefore, we may write the inequality given by Proposition 10.4 for f, g, h as

d_{B(Y_{u}(x),Y_{u}(z))}(Y_{u}(g) ∘ Y_{u}(f), Y_{u}(h)) ≤ d^{max}(f, g, h).  (7)

Recall that d_{B(Y_{u}(x),Y_{u}(z))} is the sup-norm, in other words

d_{B(Y_{u}(x),Y_{u}(z))}(Y_{u}(g) ∘ Y_{u}(f), Y_{u}(h)) =

sup_{a∈A(u,x),c∈A(u,z)} |Y_{u}(h)(a, c) − Y_{u}(g) ∘ Y_{u}(f)(a, c)| .

Recall furthermore from Definition 8.1 that

(Y_{u}(g) ∘ Y_{u}(f)) (a, c) = inf_{b∈A(u,y)}(d(a, f, b) + d(b, g, c))

whereas Y_{u}(h)(a, c) = d(a, h, c). Therefore, the inequality (7) may be rewritten as

sup_{a∈A(u,x),c∈A(u,z)} |d(a, h, c) − inf_{b∈A(u,y)}(d(a, f, b) + d(b, g, c))| ≤ d^{max}(f, g, h).

This gives, for any a and c, the two inequalities

d(a, h, c) − inf_{b∈A(u,y)}(d(a, f, b) + d(b, g, c)) ≤ d^{max}(f, g, h)

and

inf_{b∈A(u,y)}(d(a, f, b) + d(b, g, c)) − d(a, h, c) ≤ d^{max}(f, g, h).

The first one implies the same inequality for any b, giving the first statement of the corollary. The second one gives the second statement of the corollary.

10.6. Corollary. Suppose (X, A, d) is separated, bounded, absolutely transitive and satisfies Hypothesis 7.1. Then for any f, g, h we have

inf_{b∈A(x,y)}(dist_{A(x,y)}(f, b) + d(b, g, h)) ≤ d^{max}(f, g, h).

Proof. Apply the previous corollary to u = x, a = 1_{x} and c = h. Then

d(a, c, h) = d(1_{x}, h, h) = 0

and

d(a, f, b) = d(1_{x}, f, b) = dist_{A(x,y)}(f, b).

We obtain the following embedding theorem.

10.7. Theorem. Suppose (X, A, d) is bounded, absolutely transitive and satisfies Hypothesis 7.1. Then for any f, g, h we have d^{max}(f, g, h) = d(f, g, h). Hence, there exists a contracting functor F : (X, A, d) → (𝒞 , ϕ_{𝒞} ) to a metrized category, such that for any f, g, h we have

d(f, g, h) = ϕ_{𝒞} (F (g) ∘ F (f), F (h)).  (8)

Proof. By first projecting to the separated quotient, we may assume that (X, A, d) is separated too. We have d^{max}(f, g, h) ≤ d(f, g, h) by Remark 10.3. On the other hand, for any b ∈ A(x, y) we have

d(f, g, h) ≤ d(b, g, h) + dist_{A(x,y)}(f, b),

by Lemma 4.3. Applying the result of the previous corollary, this gives

d(f, g, h) ≤ d^{max}(f, g, h).

Now the last statement of Proposition 10.4 gives existence of a contracting functor F satisfying (8).

We note that the example of Subsection 6.6 shows that some hypothesis such as absolute transitivity is necessary for the statement of this theorem. Proof of Theorem 1.1: Notice that the contracting functor constructed in Theorem 10.7 is the identity on the set of objects. The target metrized category 𝒞^{max} is the quotient of Free(X, A) by the equivalence relation induced by the pseudo-metric ϕ^{max}. By assumption (X, A, d) satisfies the separation property (Definition 4.7). The maps on arrow sets F : A(x, y) → 𝒞 (x, y) preserve distances, as may be seen by taking y = x and f := 1_{x} in the property. It follows that they are injective, so we may consider that A(x, y) ⊂ 𝒞 (x, y). This gives the inclusion required to finish the proof of Theorem 1.1. □

The following corollary may be viewed as an improvement of Theorem 7.8.

10.8. Corollary. Suppose (X, A, d) is bounded and ϵ-categoric for all ϵ > 0. Then there exists a contracting functor F : (X, A, d) → (𝒞 , ϕ_{𝒞} ) to a metrized category, such that for any f, g, h we have

d(f, g, h) = ϕ_{𝒞} (F (g) ∘ F (f), F (h)).

Proof. By Lemma 7.10, (X, A, d) is absolutely transitive. Furthermore, the ϵ-categoric condition for any one ϵ implies Hypothesis 7.1. Apply Theorem 10.7.

11. Paths in ℝ^{n}

As we have noted above, the absolute transitivity condition doesn’t apply to the approximate categorical structure coming from a 2-metric space. We look at how to calculate d^{max}, but for simplicity we restrict to the standard example of euclidean space as a 2-metric space. This will provide a new viewpoint to the example of Subsection 6.4.

In what follows, let X := ℝ^{n} with the standard 2-metric: d_{X}(x, y, z) is the area of the triangle spanned by x, y, z. Let (X, A, d_{A}) be the associated approximate categorical structure. Recall that A(x, y) = {∗_{x,y}}. Let ϕ^{max} be the maximal functorial distance on Free(X, A) given by Proposition 10.2.

Arrows in Free(X, A) have the following geometric interpretation. An arrow from x to y corresponds to a composable sequence in (X, A) going from x to y, which in this case just means a sequence of points (x_{0}, …, x_{k}) with x_{0} = x and x_{k} = y. We may picture this sequence as being a piecewise linear path composed of the line segments \overline{x_{i}x_{i+1}}. Thus, we may consider elements a ∈ Free(X, A)(x, y) as being piecewise linear paths from x to y.

Suppose D ⊂ ℝ^{2} is a compact convex polygonal region. Its boundary ∂D is a closed piecewise linear path. If s : D → ℝ^{n} is a piecewise linear map, its boundary ∂s is a closed piecewise linear path in ℝ^{n}. We can divide D up into triangles on which s is linear, and define Area(D, s) to be the sum of the areas of the images of these triangles in ℝ^{n}. This could also be written as

Area(D, s) = ∫_{D} |ds|.

Suppose a is a closed piecewise linear path in X = ℝ^{n}. Put

MinArea(a) := inf_{∂s=a} Area(D, s)

be the minimum of the area of piecewise linear maps from compact convex polyhedral regions to X with boundary a. Remark: MinArea(a) is also the minimum of areas of piecewise C^{1} maps from the disk, with boundary a.

If f, g are piecewise linear paths from x to y, let g^{−1}f denote the closed path based at x obtained by following f by the inverse of g (the path g run backwards). Define a metrized structure on the category Free(X, A) of piecewise linear paths, by

ϕ_{Area}(f, g) := MinArea(g^{−1}f).

The associated approximate categorical structure also denoted by d_{Area} is given by

d_{Area}(f, g, h) = ϕ_{Area}(g ∘ f, h) = MinArea(h^{−1}gf).

11.1. Lemma. Suppose two paths f, g differ by an elementary move, in the sense that one is f = (x_{0}, …, x_{i}, z, x_{i+1}, …, x_{k}) and the other is g = (x_{0}, …, x_{i}, x_{i+1}, …, x_{k}). Then

ϕ^{max}(f, g) ≤ ϕ_{Area}(f, g) = d_{X}(x_{i}, z, x_{i+1}).

Proof. By the axiom (1) for a metrized category applied to the compositions on either side with the paths (x_{0}, …, x_{i}) and (x_{i+1}, …, x_{k}), we get

ϕ^{max}(f, g) ≤ ϕ^{max}((x_{i}, z, x_{i+1}), (x_{i}, x_{i+1})).

By the definition of ϕ^{max},

ϕ^{max}((x_{i}, z, x_{i+1}),(x_{i}, x_{i+1})) ≤ d_{A}(∗_{x_{i},z},∗_{z,x_{i+1}},∗_{x_{i},x_{i+1}}) = d_{X}(x_{i}, z, x_{i+1}).

Note that the minimal area of a disk whose boundary is a triangle, is the area of the triangle. Given a disk with boundary g^{−1}f, the pieces of the boundary corresponding to the paths before x_{i} and after x_{i+1} may be glued together and we get a disk with boundary the triangle (x_{i}, z, x_{i+1}), therefore d_{X}(x_{i}, z, x_{i+1}) is also equal to ϕ_{Area}(f, g).

11.2. Theorem. For (X, A, d_{A}) the approximate categorical structure associated to the 2-metric space X = ℝ^{n} with its standard area metric, on the category of piecewise linear paths Free(X, A) we have ϕ^{max} = ϕ_{Area}. In particular, for f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z) we have

d_{A}(f, g, h) = d_{X}(x, y, z) = ϕ^{max}(g ∘ f, h) = d^{max}(f, g, h).

Sketch of proof: The pseudo-metric ϕ_{Area} gives a structure of pseudo-metrized category on Free(X, A), which agrees with d_{A} on (X, A). It follows from the definition of ϕ^{max} that ϕ^{max} ≥ ϕ_{Area}.

In the other direction, suppose f, g ∈ Free(X, A)(x, y) and suppose we are given a piecewise linear map s from a polyhedron D to ℝ^{n} with boundary ∂s = g^{−1}f. Dividing the polyhedron up into triangles, we obtain a sequence of paths f_{0} = f, f_{1}, …, f_{m} = g such that f_{i} and f_{i+1} differ by an elementary move as in the previous lemma, and the triangles occurring in these elementary moves together make up the polyhedron D. Applying the previous lemma, and in view of the fact that Area(D, s) is the sum of the areas of the triangles in ℝ^{n} in the image of D, we have

∑_{i=1^{k}} ϕ^{max}(f_{i−1}, f_{i}) ≤ Area(D, s).

By the triangle inequality for ϕ^{max} we get

ϕ^{max}(f, g) ≤ Area(D, s),

and since ϕ_{Area}(f, g) is the minimum of Area(D, s) over all choices of D, s, this shows that ϕ^{max} ≤ ϕ_{Area}. Therefore ϕ^{max} = ϕ_{Area}. □

12. Further questions

12.1. Amplitudes. It was natural to include a function on the arrow sets in the transitivity condition. In this subsection, we formulate some conditions that a function α : ∐_{x,y∈X} A(x, y) → ℝ might be required to satisfy. The definitions given here are intended to set out the contours of our motivations for thinking about the transitivity condition.

We would like to consider α as analogous to the metric function considered in [Weiss, 2012], that is α(f) is supposed to represent the “length” of f. In terms of optimization questions, α(f) could be seen as the “cost” of traveling along the path f.

We ask first that α satisfy the reflexivity axiom α(1_{x}) = 0.

Recall that if (X, d) is a bounded 2-metric space then the distance function φ(x, y), defined by φ(x, y) := sup_{z∈X} d(x, y, z) in [Aliouche and Simpson, 2012], satisfied

φ(x, z) ≤ φ(x, y) + φ(y, z) + d(x, y, z).

With this motivation, we ask that α satisfy the triangle inequality: for any x, y, z ∈ X and f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z), we should have

α(h) ≤ α(f) + α(g) + d(f, g, h).

Recall furthermore that Weiss imposed an additional axiom for his metric function, namely (in his notations [Weiss, 2012]) that

|φ(u) − φ(v)| ≤ φ(v ∘ u).

Transposed into our approximately categorical situation, we therefore add the permuted triangle inequalities: for any x, y, z ∈ X and f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z), we should have

α(f) ≤ α(g) + α(h) + d(f, g, h)

and

α(g) ≤ α(f) + α(h) + d(f, g, h).

12.2. Definition. Suppose (X, A, d) is an approximate categorical structure. A function α : ∐_{x,y∈X} A(x, y) → ℝ is called an amplitude if it satisfies the reflexivity axiom and triangle and permuted triangle inequalities discussed above. It is called a semi-amplitude if it satisfies the triangle and permuted triangle inequalities but not necessarily the reflexivity axiom.

Notice that the function α = μ used for the definition of absolutely transitive, is only a semi-amplitude but not an amplitude since it doesn’t satisfy the property α(1_{x}) = 0.

On the other hand, the notion adapted to 2-metric spaces (Theorem 6.2) is that of transitivity with respect to an amplitude. It will be interesting to see if Theorems 1.1 and 10.7, which use the absolute transitivity condition in an essential way, can be extended to relative transitivity with respect to an amplitude function α.

12.3. Lemma. If α is an amplitude then we have α(f) ≥ 0 for all f ∈ A(x, y).

Proof. Let g := 1_{y} and h := f, then

d(f, g, h) = d(f, 1_{y}, f) = 0

by the left identity property of d, so

0 = α(g) ≤ α(f) + α(h) + d(f, g, h) = 2α(f).

12.4. Lemma. Suppose given an approximate categorical structure with an amplitude (X, A, d, α). Suppose f, f′ ∈ A(x, y). Then

α(f′) ≤ α(f) + ϕ(f, f′),

implying that

|α(f) − α(f′)| ≤ ϕ(f, f′).

In particular, α is continuous.

Proof. Apply the main property of α with g := 1_{y} and h := f′. It says

α(f′) ≤ α(f) + α(1_{y}) + d(f, 1_{y}, f′).

Since α(1_{y}) = 0 by hypothesis and

d(f, 1_{y}, f′) = ϕ(f, f′),

we get the first statement. The rest follows.

We might want to assume the anti-reflexivity property that

α(f) = 0 ⇒ x = y, f = 1_{x}.

In a different vein, we can define the unit semi-amplitude μ defined by μ(f) := 1 for all f.

12.5. Lower bound for α-transitive approximate categorical structures. In Theorem 10.7 we used the absolute transitivity condition. However, in examples such as the approximate categorical structure coming from a transitive 2-metric space, only transitivity relative to an amplitude α holds. Therefore, it is an interesting question to see what kind of lower bound for d^{max} could be obtained using α-transitivity.

12.6. More transitivity conditions. Various other transitivity conditions may be considered. For example, a weaker ≤ ϵ transitivity axiom would require existence of m only when the right hand side is ≤ ϵ.

The small transitivity condition is that if f ∈ A(x, y) and g ∈ A(y, z) then there exists m ∈ A(x, z) such that

d(f, g, m) ≤ min{α(f), α(g)}.

Remark: In the situation of Theorem 6.2, the approximate categorical structure associated to a 2-metric space always satisfies this small transitivity condition, even if the 2-metric space wasn’t transitive. Indeed,

d_{X}(x, y, z) ≤ min{α(∗_{x,y}), α(∗_{y,z})}

in view of the definition of α(∗_{x,y}) = φ(x, y) = sup_{c∈X} d_{X}(x, y, c) coming from the 2-metric in the notations of Theorem 6.2.

We could also weaken the basic transitivity conditions of Definition 7.3, for example by allowing an error of some ϵ. It would be interesting to see what kinds of lower bounds for d^{max} could be obtained with these conditions.

12.7. Paths in a 2-metric space. In the example of a 2-metric space (X, d_{X}), we put

A(x, y) := {∗_{x,y}} and d(∗_{x,y}, ∗_{y,z}, ∗_{x,z}) := d_{X}(x, y, z).

We can then construct the induced pseudometric d^{max} on Free(X, A). Morphisms in Free(X, A) may be viewed as paths in X. If X = ℝ^{n} then we view such a path as a piecewise linear path in ℝ^{n}, replacing ∗_{x,y} by the straight line segment joining x to y, and we have seen in Section 11 that d^{max}(f, g, h) is the minimal area of a disk whose boundary consists of the paths f, g and h, as in the example of Subsection 6.4. It will be interesting to generalize this to arbitrary 2-metric spaces.

12.8. Natural transformations. Classically the next step after functors is to consider natural transformations. It is an interesting question to understand the appropriate generalization of this notion to the approximate categorical context.

Suppose F, G : (X, A) → (Y, B) are two prefunctorial maps. A pre-natural transformation η : F → G is a function which for any x, y ∈ X and f ∈ A(x, y) associates η(f) ∈ B(F x, Gy). We say that η is a k-natural transformation if, for any x, y, z ∈ X and f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z) we have

d(F (f), η(g), η(h)) ≤ kd(f, g, h) and d(η(f), G(g), η(h)) ≤ kd(f, g, h).

If F is k-functorial then defining η(f) := F (f) gives an “identity prenatural transformation” from F to itself, and it is also k-natural.

Suppose F, G, H : (X, A) → (Y, B) are three prefunctorial maps. Suppose η : F → G, ζ : G → H and ω : F → H are prenatural transformations.

For any x, y, z ∈ X and f ∈ A(x, y), g ∈ A(y, z) and h ∈ A(x, z), consider

F x →^{η(f)} Gy →^{ζ(g)} F z

and ask that

d(η(f), ζ(g), ω(h)) ≤ kd(f, g, h) + δ_{0}(η, ζ, ω).

Let δ(η, ζ, ω) be the inf of the δ_{0}(η, ζ, ω) which work here. We hope that this will allow to define an approximate categorical structure on the functors and natural transformations. This is left open as a question for the future.

12.9. Correspondence functors. It was useful to introduce a notion of bimodule, viewed as a metric correspondence between metric spaces. One may ask whether this notion can be extended naturally to metrized categories and approximate categorical structures.

Let (X, A, d_{A}) and (Y, B, d_{B}) be approximate categorical structures. We would like to define a notion of functor from A to B using the idea of bimodules on the morphism sets. Let us try as follows. Consider a function F : X → Y and functions f(x, x′, a, b) ∈ ℝ for any x, x′ ∈ X and a ∈ A(x, x′) and b ∈ B(F x, F x′). Roughly speaking we would like to have

inf_{a′′} (f(x, x′′, a′′, b′′) + d_{A}(a, a′, a′′))

≤ inf_{b,b′} (f(x, x′, a, b) + f(x′, x′′, a′, b′) + d_{B}(b, b′, b′′)) .

This translates also into: for any x, x′, x′′ ∈ X, any a ∈ A(x, x′), any a′ ∈ A(x′, x′′) and any a′′ ∈ A(x, x′′), and any b′′ ∈ B(F x, F x′′) we have

inf_{\begin{matrix}b∈B(F x,F x′) \\ b′∈B(F x′,F x′′) \end{matrix}} ( \begin{matrix}f(x, x′, a, b) + f(x′, x′′, a′, b′) − f(x, x′′, a′′, b′′) \\ +d_{B}(b, b′, b′′) \end{matrix} )

≤ d_{A}(a, a′, a′′).

12.10. Reconstruction questions. Given a category (X, C, ∘) with a metric structure ψ, we get an approximate categorical structure by Proposition 2.2.

We could then consider a collection of subsets A(x, y) ⊂ C(x, y) such that A(x, x) contains 1_{x}. This will again give an approximate categorical structure.

One question will be, to what extent can we recover the structure of C just by knowing (X, A, d)? Our main theorem provides an existence result in the absolutely transitive case. One may then ask, to what extent is the enveloping metrized category unique?

Another somewhat similar question: suppose A(x, y) = C(x, y). However, suppose d′ is a different approximate categorical structure obtained by perturbing the original one. For example, note that d′ = d + ϵd_{1} is again an approximate categorical structure for any approximate categorical structure d_{1}. Question: can we recover the categorical structure, i.e. the composition ∘, from the perturbed d′?

The approximate categorical structures on (X, A) form a cone, because if d_{1} and d_{2} are approximate categorical structures and c_{1}, c_{2} are positive constants then c_{1}d_{1} + c_{2}d_{2} is again an approximate categorical structure. So, another question is, what properties does this cone have? What do the boundary points or extremal rays look like?

The picture in Subsection 6.3 suggests that we should look for the position of the categorical structures within this cone. To recast the questions of two paragraphs ago, given a finite graph, are there small values of ϵ such that any ϵ-categorical structure is near to a 0-categorical structure?

12.11. Category theory. To what extent can we generalize the classical structures and constructions of category theory to the situation of metrized categories and approximate categorical structures?

In a different direction, can we following [Lawvere, 1973, Lawvere, 2002] define a notion of approximate categorical structure with values in a complete closed symmetric monoidal category instead of ℝ?

12.12. Fixed points and optimization. One of our main original motivations for looking at 2-metric spaces in [Aliouche and Simpson, 2012, Aliouche and Simpson, 2014] was to consider the theory of fixed points and other fixed subsets such as lines. In the more general setting of approximate categorical structures, we can envision several different kinds of fixed point and iteration problems, for example fixed points of a functor, fixed points of a bimodule between metric spaces, as well as fixed arrows within a metrized category or approximate categorical structure. It will be interesting to see what applications these might have to optimization problems.

References

A. Aliouche and C. Simpson (2012), Fixed points and lines in 2-metric spaces. Adv. Math. 229, 668-690.

A. Aliouche and C. Simpson (2014), Common fixtures of several maps on 2-metric spaces. Indian J. Math. 56, 229-262.

S. Gähler (1963), 2-metrische Räume und ihre topologische Struktur. Math. Nachr. 26, 115-148.

G.M. Kelly (1982), Basic concepts of enriched category theory. London Math. Soc. Lecture Note Series 64, Cambridge University Press. Reprints in Theory and Applications of Categories 10.

F. W. Lawvere (1973), Metric spaces, generalized logic, and closed categories. Rend. Sem. Mat. Fis. Milano 43, 135-166. Reprints in Theory and Applications of Categories 1, 6-37.

F. W. Lawvere (2002), Author’s commentary on “Metric spaces, generalized logic, and closed categories”, Reprints in Theory and Applications of Categories 1, 1-5.

I. Weiss (2012), Metric 1-spaces. Preprint arXiv:1201.3980.

Laboratoire des Systèmes Dynamiques et Contrôle, Université Larbi Ben M’Hidi, Oum-El-Bouaghi, 04000, Algérie

CNRS, Laboratoire J.A. Dieudonné, Université Côte d’Azur, France

Email: alioumath@gmail.com
      carlos@unice.fr
This article may be accessed at http://www.tac.mta.ca/tac/

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. Full text of the journal is freely available from the journal’s server at http://www.tac.mta.ca/tac/. It is archived electronically and in printed paper format.

Subscription information Individual subscribers receive abstracts of articles by e-mail as they are published. 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}TEX2e is required. Articles in PDF format may be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis: cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown(at)btinternet.com Valeria de Paiva: Nuance Communications Inc: valeria.depaiva@gmail.com Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Kathryn Hess, Ecole Polytechnique Fédérale de Lausanne: kathryn.hess@epfl.ch Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Edinburgh: Tom.Leinster@ed.ac.uk Ieke Moerdijk, Utrecht University: i.moerdijk@uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Giuseppe Rosolini, Università di Genova: rosolini@disi.unige.it Alex Simpson, University of Ljubljana: Alex.Simpson@fmf.uni-lj.si James Stasheff, University of North Carolina: jds@math.upenn.edu Ross Street, Macquarie University: ross.street@mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca