Theory and Applications of Categories, Vol. 15, No. 4, 2005, pp. 95–146.

THE SHAPE OF A CATEGORY UP TO DIRECTED HOMOTOPY

MARCO GRANDIS

Abstract.

This work is a contribution to a recent field, Directed Algebraic Topology. Categories which appear as fundamental categories of ‘directed structures’, e.g. ordered topological spaces, have to be studied up to appropriate notions of directed homotopy equivalence, which are more general than ordinary equivalence of categories. Here we introduce past and future equivalences of categories—sort of symmetric versions of an adjunction—and use them and their combinations to get ‘directed models’ of a category; in the simplest case, these are the join of the least full reflective and the least full coreflective subcategory.

Introduction

Directed Algebraic Topology studies structures where paths and homotopies cannot generally be reversed, like ‘directed spaces’ in some sense—ordered topological spaces, ‘inequilogical spaces’, simplicial and cubical sets, etc. References for this domain are given below.

The study of homotopy invariance is far richer and more complex than in the classical case, where homotopy equivalence between ‘spaces’ produces a plain equivalence of their fundamental groupoids, for which one can simply take—as a minimal model—the categorical skeleton. Our directed structures have a fundamental category ↑Π_{1}(X), and this must be studied up to appropriate notions of directed homotopy equivalence, which are more general than categorical equivalence.

We shall use two (dual) directed notions, which take care, respectively, of variation ‘in the future’ or ‘from the past’: future equivalence (a symmetric version of an adjunction, with two units) and its dual, a past equivalence (with two counits); and then study how to combine them. Minimal models of a category, up to these equivalences, are then introduced to better understand the ‘shape’ and properties of the category we are analysing, as well as of the process it represents.

An elementary example will give some idea of this analysis. Let us start from the standard ordered square ↑[0, 1]^{2} (with the euclidean topology and the product order, (x, y) ≤ (x′, y′) if x ≤ x′ and y ≤ y′), and consider the (compact) ordered subspace X obtained by taking out an open square (marked with a cross)

Work supported by MIUR Research Projects.

Received by the editors 2004-07-28 and, in revised form, 2005-06-17.

Published on 2005-06-23 in the volume of articles from CT2004.

2000 Mathematics Subject Classification: 55Pxx, 18A40, 68Q85.

Key words and phrases: homotopy theory, adjunctions, reflective subcategories, directed algebraic topology, fundamental category, concurrent processes.

\begin{matrix}c \\ ◯ \end{matrix} Marco Grandis, 2005. Permission to copy for private use granted.

[figure: X; E; F; P; ×; ×; ×; ×; •; •; •; •; •; •; •; •; 0; a; b; 1; a; 1; 0; b]  (1)

Its directed paths are, by definition, the continuous order-preserving maps ↑[0, 1] → X defined on the standard ordered interval, and move ‘rightward and upward’ (in the weak sense). Directed homotopies of such paths are continuous order-preserving maps ↑[0, 1]^{2} → X. The fundamental category C = ↑Π_{1}(X) has, for arrows, the classes of directed paths up to the equivalence relation generated by directed homotopy (with fixed endpoints, of course).

In our case, the whole category C is easy to visualise and ‘essentially represented’ by the full subcategory E on four vertices 0, a, b, 1 (the central cell does not commute). But E is far from being equivalent to C, as a category, since C is already a skeleton, in the ordinary sense.

To get this result, we determine first the least full reflective subcategory F of C, which is future equivalent to C and minimal as such; its objects are a future branching point a (where one must choose between different ways out of it) and a maximal point 1 (where one cannot further proceed); they form the future spectrum sp^{+}(C). Dually, we have the past spectrum P, i.e. the least full coreflective subcategory, whose objects form the past spectrum sp^{−}(C). E is now the full subcategory of C on sp(C) = sp^{−}(C) ∪ sp^{+}(C), the spectral injective model of X (which is a minimal embedded model, in a sense which will be made precise).

The situation can now be analysed as follows, in E:

- the action begins at 0, from where we move to a,

- a is an (effective) future branching point, where we have to choose between two paths,

- which join at b, an (effective) past branching point,

- from where we can only move to 1, where the process ends.

An alternative description will be obtained with the associated projective model M, the full subcategory of the category C^{2} (of morphisms of C) on the four maps α, β, σ, τ - obtained from a canonical factorisation of the composed adjunction P ⇄ C ⇄ F (cf.

4.6)

[figure: E; M; ×; ×; ×; 0; a; b; 1; 0; a; b; 1; α; β; σ; τ; α; σ; τ; β]  (2)

These two representations are compared in 5.2, 5.4 and Section 9. A pf-spectrum (when it exists) is an effective way of constructing a minimal embedded model; it also produces a projective model (cf. 7.6, 8.4), which need not be minimal: iterating the procedure, we get a smaller projective model of M, its full subcategory on the objects α, β.

Directed homotopies have been studied in various structures: differential graded algebras [8], ordered or locally ordered topological spaces [4, 6, 7], simplicial, precubical and cubical sets [4, 6, 9, 11], directed simplicial complexes [9], directed topological spaces [10], inequilogical spaces [12], small categories [10], etc. Their present applications deal mostly with concurrency (see [4, 6, 7] and references there). The present study has similarities with a recent one [5], using categories of fractions for the same goal of constructing a ‘minimal model’ of the fundamental category; its results are often similar to the present projective models.

On the other hand, within category theory, the study of future (and past) equivalences is a sort of ‘variation on adjunctions’: they compose as the latter (2.3) and— perhaps unexpectedly—two categories are future homotopy equivalent if and only if they can be embedded as full reflective subcategories of a common one (Thm. 2.5); therefore, a property is invariant for future equivalences if and only if it is preserved by full reflective embeddings as well as by their reflectors. Moreover, comma (or cocomma) categories amount to directed homotopy pullbacks (or pushouts) of categories; future and past equivalences are the natural tool to describe their diagrammatic properties, like the pasting property (1.6). Split projective models are known as essential localisations, cf. 3.7. For references on the ordered set of replete reflective subcategories of a category, see 7.1. Outline. After a brief presentation of directed homotopies, Section 2 introduces and studies past and future homotopy equivalences. Then, in the next three sections, we combine future and past equivalences, dealing with injective and projective models. Section 6 deals with future invariant properties, like future regular morphisms and future branching ones. In the next two sections, these are used to define and study pf-spectra, which produce a minimal injective model and an associated projective one. In Section 9, we compute these invariants for the fundamental category of various ordered spaces (or preordered, in 9.5). Hints to possible applications outside of concurrency can be found in 9.9. Notation. A homotopy φ between maps f, g: X → Y is written as φ: f → g: X → Y. A preorder relation is assumed to be reflexive and transitive; it is a (partial) order if it is also anti-symmetric. As usual, a preordered set will be identified with a (small) category having at most one arrow between any two given objects. We shall distinguish between the ordered real line r and the ordered topological space ↑R (the euclidean line with the natural order), whose fundamental category is r. The classical properties of adjunctions and equivalences of categories are used without reference (see [18]). Cat denotes the category of small categories. Acknowledgements. The author is grateful to the referee for many helpful suggestions, meant to make the exposition clearer.

1. Directed homotopies and the fundamental category

In this section we give a brief presentation of directed homotopies for preordered topological spaces. This will lead us to the question of ’homotopy equivalence’ between fundamental categories and the problem of reducing the latter to simpler models. Exploring diagrammatic properties of comma squares (in 1.6) will give some hints for such problems.

1.1. Homotopy for preordered spaces. The simplest topological setting where one can study directed paths and directed homotopies is likely the category pTop of preordered topological spaces and preorder-preserving continuous mappings; the latter will be called simply morphisms or maps (when it is understood we are in this category).

In this setting, a (directed) path in the preordered space X is a map a: ↑[0, 1] → X, defined on the standard directed interval ↑I = ↑[0, 1] (with euclidean topology and natural order). A (directed) homotopy φ: f → g: X → Y, from f to g, is a map φ: X ×↑I → Y coinciding with f on the 0-basis of the cylinder X ×↑I, with g on the 1-basis. Of course, this (directed) cylinder is a product in pTop: it is equipped with the product topology and with the product preorder, where (x, t) ≺ (x′, t′) if x ≺ x′ in X and t ≤ t′ in ↑I.

The fundamental category C = ↑Π_{1}(X) has, for arrows, the classes of directed paths up to the equivalence relation generated by directed homotopy with fixed endpoints; composition is given by the concatenation of consecutive paths.

Note that the fundamental category of a preordered space X is not a preorder, generally (cf. 1.2); but any loop in X lives in a zone of equivalent points and is reversible, so that all endomorphisms of ↑Π_{1}(X) are invertible. Moreover, if X is ordered, all loops are constant: the fundamental category has no endomorphisms and no isomorphisms, except the identities, and is skeletal.

The fundamental category of a preordered space can be computed by a van Kampentype theorem, as proved in [10], Thm. 3.6, in a much more general setting (‘d-spaces’, defined by a family of distinguished paths).

The forgetful functor U: pTop → Top to the category of topological spaces has both a left and a right adjoint, D ⊣ U ⊣ C, where DX (resp. CX) is the space X with the discrete order (resp. the coarse preorder). Therefore, U preserves limits and colimits. The standard embedding of Top in pTop will be the coarse one, so that all (ordinary) paths in X are directed in CX. Note that the category of ordered spaces does not allow for such an embedding, and has different colimits.

1.2. An example. It will be useful to see how directed homotopy works in an elementary case, the ordered space X ⊂ ↑[0, 1]^{2} of the Introduction (the complement of ]1/4, 3/4[^{2} in ↑I^{2}).

Here, the fundamental category C = ↑Π_{1}(X) has some arrow x → x′ provided that x ≤ x′ and both points are in L or in L′ (the closed subspaces represented below)

[figure: X; L; L′; ×; ×; •; •]  (3)

Precisely, there are two arrows when x ≤ (1/4, 1/4) and x′ ≥ (3/4, 3/4) (as in the last figure above), and one otherwise. This visible fact can be easily proved with the ‘van Kampen’ theorem cited above, using the closed subspaces L, L′ (whose fundamental category is the induced order).

In this case, the fundamental category is a subcategory of the fundamental groupoid Π_{1}(|X|) of the underlying topological space (forgetting the order). This is no longer the case in more complex situations, like the three-dimensional ordered spaces considered in Section 9 (complements of a cube in a cube).

We have already seen in the Introduction that, while the fundamental category C is quite simple, we have to find new ways of modelling it: ordinary equivalence is of no help, since there are no non-trivial isomorphisms and C is already a skeleton.

1.3. The directed circle. Preordered topological spaces are not sufficient for the development of Directed Algebraic Topology: one cannot realise a model of the directed circle or the directed torus in pTop. Some remarks about more general ‘directed topological structures’ may be of interest to the reader, even if not technically needed for the sequel.

Let us start with the fundamental groupoid Π_{1}(S^{1}) of the standard circle. We shall study its subcategory c containing all points of the circle and the homotopy classes of the ‘anticlockwise’ paths, showing that c is modelled by its full subcategory at any point x (5.6). Again, we need a new approach to formulate this result: while the fundamental group π_{1}(S^{1}, x) is the skeleton of the fundamental groupoid, c has no non-trivial isomorphism and is its own skeleton.

Now, c cannot be the fundamental category of a preordered topological space, because we have already noted that in such a category all endomorphisms are invertible (1.1).

However, c can be viewed as the fundamental category of a ‘directed circle’, living in a more general setting: e.g. ‘locally ordered spaces’, as often considered in concurrency [4, 6, 7], ‘d-spaces’ [10] or—perhaps more simply—‘inequilogical spaces’.

The category pEql of inequilogical spaces, introduced in [12], is a directed version of D. Scott’s equilogical spaces [20, 19, 1]; an object of this category is a preordered topological space equipped with an equivalence relation, while a morphism is an equivalence class of preorder-preserving continuous mappings which respect the given equivalence relations (equivalent if they induce the same mapping, modulo the latter). There are various models of the directed circle, all ‘locally homotopy equivalent’, but the simplest (or the nicest) is perhaps the inequilogical space ↑\overline{S}_{e}^{1} = (↑R, ≡_{Z}), i.e. the quotient (in this category) of the ordered topological line ↑R modulo the action of the group Z ([12], 1.7). The fundamental category of an inequilogical space is defined in [12], 2.4, and is based again on the directed interval ↑I (with equivalence relation the identity).

The powers of this directed circle ↑\overline{S}_{e}^{1} in pEql give the inequilogical tori (↑\overline{S}_{e}^{1})^{n} = (↑R^{n}, ≡_{Z^{n}}), where directed paths have to turn ‘anticlockwise in each variable’; notice that, for n ≥ 2, this has nothing to do with orientation, as was already the case for preordered spaces.

1.4. Directed homotopy invariance. Let us summarise the problem we want to analyse.

In Algebraic Topology, the fundamental groupoid Π_{1}(X) of a topological space is a homotopy invariant in a clear sense: a homotopy φ: f → g: X → Y produces an isomorphism of the associated functors f_{∗}, g_{∗}: Π_{1}(X) → Π_{1}(Y), so that a homotopy equivalence X ≃ Y produces an equivalence of groupoids Π_{1}(X) ≃ Π_{1}(Y). Thus, a 1-dimensional homotopy model of the space is its fundamental groupoid, up to groupoid-equivalence; if we want a minimal model, we can always take a skeleton of the latter (choosing one point in each path component of the space).

In Directed Algebraic Topology, homotopy invariance requires a deeper analysis which we want to develop here, taking on a study begun in [10].

Now, paths and homotopies are no longer reversible, in general. Thus, a ‘directed topological structure’ (e.g. a preordered topological space) produces a fundamental category ↑Π_{1}(X), and a homotopy φ: f → g: X → Y only produces a natural transformation between the associated functors

φ_{∗}: f_{∗} → g_{∗}: ↑Π_{1}(X) → ↑Π_{1}(Y),  φ_{∗}x = [φ(x, −)]: f(x) → g(x) (x ∈ X), (4)

which, generally, is not invertible, because the paths φ(x, −): ↑I → Y need not be reversible.

Equivalence of categories is not, by far, sufficient to ‘link’ categories having—loosely speaking—the same appearance; and the problem of defining and constructing minimal models is important, both theoretically, for Directed Algebraic Topology, and in applications (see [5], where this problem is studied with the purpose of analysing concurrent processes).

1.5. Directed homotopy for categories. Let us begin with a description of directed homotopy in Cat (the category of small categories), as presented in [10], 4.1. This elementary theory is based on the directed interval 2 = {0 → 1}, an order category on two objects, with the obvious faces ∂^{±}: 1 → 2 defined on the pointlike category 1 = {∗}. (We shall occasionally use the same notions for large categories.)

A point x: 1 → X of a small category X is an object of the latter; we will also write x ∈ X. A (directed) path a: 2 → X from x to x′ is an arrow a: x → x′ of X; concatenation of paths amounts to composition in X (strictly associative, with strict identities). The (directed) cylinder functor IX = X ×2 and its right adjoint, P Y = Y^{2} (the category of morphisms of Y) show that a (directed) homotopy φ: f → g: X → Y is the same as a natural transformation between functors; their operations coincide with the 2-categorical structure of Cat.

The existence of a map x → x′ in X (a path) produces the path preorder x ≺ x′ (x reaches x′) on the points of X; the resulting path equivalence relation, meaning that there are maps x ⇄ x′, will be written as x ≃ x′. For this preorder, a point x is

- maximal if it can only reach the points ≃ x,

- a maximum if it can be reached from every point of X; (the latter is the same as a weak terminal object, and is only determined up to path equivalence). If the category X ‘is’ a preorder, the path preorder coincides with the original relation.

For the fundamental category X = ↑Π_{1}(T) of a preordered space T, note that the path-preorder x ≺ x′ in X means that there is some directed path from x to x′ in T, and implies the original preorder in T, which is generally coarser (cf. 1.2). Therefore, when the latter is an order, so must the path-preorder x ≺ x′ be.

1.6. Comma categories and homotopy pullbacks. The necessity of notions of directed homotopy in Cat already appears in the general theory of categories, for instance in the diagrammatic properties of (co)comma squares.

Consider the pasting of two comma squares X = f|g, Y = q|h

[figure: Y; p′; q′; β; X; p; q; α; A; f; Z; p′′; q′′; γ; A; f; D; h; B; g; C; D; gh; C]  (5)

and the ‘global’ comma Z = f|(gh). The categories Y and Z are generally not equivalent; but Z is—canonically—a full reflective subcategory of Y, with embedding i, reflector r and unit η: 1 → ir (with obvious notation: a ∈ A, etc.; u in C and v in B)

\begin{matrix}i: Z → Y,  r: Y → Z,  η: 1 → ir: Y → Y, \\ i(a, d; u: f(a) → gh(d)) = (a, h(d), d; u: f(a) → gh(d), 1_{h(d)}), \\ r(a, b, d; u: f(a) → g(b); v: b → h(d)) = (a, d; g(v)^{∘}u: f(a) → gh(d)), \\ η(a, b, d; u, v) = (1_{a}, v, 1_{d}): (a, b, d; u, v) → (a, hd, d; gv^{∘}u, 1_{hd}). \end{matrix}  (6)

Reversing the ‘direction’ of comma categories (X = g|f, Y = h|q, Z = (gh)|f), the global comma Z becomes a full coreflective subcategory of Y. Similar results hold for other diagrammatic properties of (co)commas. A general treatment should be based on the universal properties of the latter, to take advantage of duality and avoid the complicated construction of cocomma categories.

Now, a comma category in Cat corresponds to a standard homotopy pullback in Top, and it is well known that pasting homotopy pullbacks of spaces, as in (5), one obtains a space Y which is homotopy equivalent to the ‘global’ standard homotopy pullback Z. We should therefore be prepared to consider a full reflective or coreflective subcategory Z ⊂ Y as ‘equivalent’ to Y, in some sense related with directed homotopy in Cat. And indeed, being full reflective (resp. coreflective) subcategories of a common one will amount to the notion of ‘future equivalence’ (resp. ‘past equivalence’) studied below. Future and past equivalences are thus natural tools to describe the diagrammatic properties of comma and cocomma categories.

2. Future and past homotopy equivalences

Directed homotopy equivalence of categories is introduced in two dual forms, which are meant to identify future invariant and past invariant properties, respectively. Each of them is a symmetric version of the notion of adjunction.

2.1. Future homotopy equivalences. A homotopy equivalence in the future (f, g; φ, ψ) between the categories X, Y (as defined in [10]) consists of a pair of functors and a pair of natural transformations (i.e., directed homotopies), the units

f: X ⇄ Y :g  φ: 1_{X} → gf,  ψ: 1_{Y} → fg,  (7)

which go from the identities of X, Y to the composed functors. This four-tuple will be called a future equivalence, or a forward equivalence, if the following coherence conditions hold

fφ = ψf: f → fgf,  φg = gψ: g → gfg (coherence).  (8)

Here, we shall only use the coherent form. A property (making sense in a category, or for a category) will be said to be future invariant if it is preserved by future equivalences. Some elementary examples will be discussed in 2.7; more interesting ones will follow in Section 6.

A future equivalence is a ‘variation’ of the notion of adjunction, and some aspects of the theory will be similar. But let us note at once that, in a future equivalence, f need not determine g (see (30)). Our data produce two natural transformations between hom-functors (which will often be used implicitly in what follows)

\begin{matrix}Φ: Y (fx, y) → X(x, gy), & b ↦ gb.φx & (φx = Φ(1_{fx}), f(Φ(b)) = ψy.b), \\ Ψ: X(gy, x) → Y (y, fx), & a ↦ fa.ψy & (ψy = Ψ(1_{gy}), g(Ψ(a)) = φx.a). \end{matrix}  (9)

One can also note that an adjunction f ⊣ g with invertible counit ε: fg ≅ 1 amounts to a future equivalence with invertible ψ = ε^{−1}; this case will be treated later and called a split future equivalence (2.4).

A future equivalence (f, g; φ, ψ) will be said to be faithful if the functors f and g are faithful and, moreover, all the components of φ and ψ are epi and mono. (Motivations for the latter condition will appear in 2.4 and Thm. 2.5.) The next lemma (similar to classical properties of adjunctions) will prove that it suffices to know that one of the following equivalent conditions holds:

(i) all the components of φ and ψ are mono, (ii) f and g are faithful and all the components of φ and ψ are epi.

Plainly, all future equivalences between preordered sets (viewed as categories) are faithful. There are non-faithful future equivalences where all unit-components are epi (see 2.8d). A faithful future equivalence between balanced categories (where every map which is mono and epi is an isomorphism) is plainly an equivalence. But a faithful future equivalence can link a balanced category with a non-balanced one (see (55)).

Dually, a past equivalence, or backward equivalence, has natural transformations in the opposite direction, from the composed functors to the identities, called counits

\begin{matrix}f: X ⇄ Y :g & φ: gf → 1, & ψ: fg → 1, \\ fφ = ψf: fgf → f, & φg = gψ: gfg → g & (coherence). \end{matrix}  (10)

An adjoint equivalence is at the same time a future and a past equivalence. Future equivalences, which will be shown to be linked with reflective subcategories and idempotent monads (2.4), will generally be given priority over the dual case (related with coreflective subcategories and comonads).

2.2. Lemma. [Cancellation Lemma] Let (f, g; φ, ψ) be a future equivalence (2.1).

(a) If all the components φx: x → gfx are mono, then all of them are epi and f is faithful.

(b) The transformation φ is invertible if and only if all its components are split mono; in this case f is right adjoint to g, full and faithful.

(c) If g is faithful and all the components of φ are epi, then f preserves all epis.

(d) If gf is faithful and all the components of φ are epi, then they are also mono.

(e) The conditions (i) and (ii) of 2.1 are equivalent; when they hold, f and g preserve all epis.

Proof. (a) Assume that all the components φx are mono, and let a_{i}.φx = a in X (i = 1, 2).

\xymatrix{x \ar[r]^{φx} \ar[dr]_{a} & gfx \ar[r]^{φgfx} \ar[d]_{a_{i}} \ar@{-->}[dr]_{gfa} & gfgfx \ar[d]^{gfa_{i}} \\  & x′ \ar[r]_{φx′} & gfx′}  (11)

Since φgf = gfφ (by coherence) we have φx′.a_{i} = gfa_{i}.φgfx = gf(a_{i}.φx) = gf(a), and—cancelling φx′—we deduce a_{1} = a_{2}. The faithfulness of gf (hence of f) works as in adjunctions: given a_{i}: x → x′ with gfa_{1} = gfa_{2}, we get φx′.a_{1} = gfa_{i}.φx = φx′.a_{2} and we cancel φx′.

(b) The first assertion follows from (a). Then g ⊣ f with an invertible counit φ^{−1}: gf → 1, which implies that f is full and faithful [18].

(c) Assume that g is faithful and that all the components of φ are epi. Given an epimorphism a: x → x′, we have that gfa.φx = φx′.a is also epi, whence gfa is epi and fa as well.

(d) Assume that gf is faithful and that all the components of φ are epi. Let φx.a_{i} = a: x′ → gfx; then gfa_{i}.φx′ = φx.a_{i} = a; cancelling φx′ we have gfa_{1} = gfa_{2}, and a_{1} = a_{2}.

(e) The equivalence of (i) and (ii) follows from (a) and (d); the last point from (c).

2.3. Future homotopy equivalence of categories. Future equivalences can be composed (much in the same way as adjunctions), which shows that being future equivalent categories is an equivalence relation. Given (f, g; φ, ψ) (as in (7, 8)) and a second future equivalence

\begin{matrix}h: Y ⇄ Z:k, & ϑ: 1_{Y} → kh, ζ: 1_{Z} → hk, \\ hϑ = ζh: h → hkh, & ϑk = kζ: k → khk. \end{matrix}  (12)

their composite will be:

hf: X ⇄ Z:gk,  gϑf.φ: 1_{X} → gk.hf,  hψk.ζ: 1_{Z} → hf.gk.  (13)

Its coherence is proved by the following computation, where fgϑ.ψ = ψkh.ϑ

\begin{matrix}hf(gϑf.φ) = h(fgϑf.fφ) = h(fgϑf.ψf) = h(fgϑ.ψ)f, \\ (hψk.ζ)hf = (hψkh.ζh)f = (hψkh.hϑ)f = h(ψkh.ϑ)f. \end{matrix}  (14)

(This composition is easily seen to be associative, with obvious identities.) The same holds in the faithful case. Indeed, using the form 2.1(ii), it suffices to note that the general component g(ϑfx).φx is epi (also because g preserves epis, by 2.2e).

Two categories will be said to be past and future equivalent if they are both past equivalent and future equivalent. Generally, one needs different pairs of functors for these two notions (see 2.6); finer relations, linking the past and future structure, will be introduced later and give more interesting results. Marginally, we also consider coarse equivalence of categories, defined as the equivalence relation generated by past equivalence and future equivalence.

2.4. Full reflective subcategories as future retracts. We deal now with a special case of future equivalence, which is important for its own sake, but will also be shown (in Thm. 2.5) to generate the general case.

A split future equivalence of F into X (or of X onto F) will be a future equivalence (i, p; 1, η) where the unit 1 → pi is an identity

i: F ⇄ X:p  η: 1_{X} → ip  (the main unit)
pi = 1_{F} ,  pη = 1_{p},  ηi = 1_{i}  (p ⊣ i). (15)

We also say that F is a future retract of X. Note that p is now left adjoint to i, which is full and faithful. (Note also that (i, p; 1, η) is a split mono in the category of future equivalences, with retraction (p, i; η, 1).)

As in 2.1, we say that this future equivalence is faithful if all the components of η are mono; but, because of the adjunction, this is equivalent to saying that p is faithful (and implies that all the components of η are epi). In this case, we say that F is a faithful future retract of X.

Forgetting about direction, a future retract corresponds—in Topology—to a strong deformation retract (with an additional coherence condition, pη = 1). Here, this structure means that F is (isomorphic to) a full reflective subcategory of X, i.e. that there is a full embedding i: F → X with a left adjoint p: X → F (then p is essentially determined by i, and—via the universal property of the unit—can always be constructed so that the counit pi → 1_{F} be an identity, as we are assuming).

Equivalently, one can assign a strictly idempotent monad (e, η) on X

e: X → X,  η: 1_{X} → e,  ee = e,  eη = 1_{e} = ηe.  (16)

Indeed, given (i, p; η), we take e = ip; given (e, η), we factor e = ip splitting e through the subcategory F of X formed of the objects and arrows which e leaves fixed.

Dually, a split past equivalence, of P into X (or of X onto P) is a past equivalence (i, p; 1, ε) where the counit pi → 1_{P} is an identity

i: P ⇄ X:p  ε: ip → 1_{X}  (the counit)
pi = 1_{P} ,  pε = 1_{p}, ,  εi = 1_{i}  (i ⊣ p). (17)

This amounts to saying that i(P) is a full coreflective subcategory of X (with a choice of the coreflection making the unit 1 → pi an identity); P will also be called a past retract of X.

2.5. Theorem. [Future equivalence and reflective subcategories]

(a) A future equivalence (f, g; φ, ψ) between X and Y (2.1) has a canonical factorisation into two split future equivalences

\xymatrix{X \ar[r]^{i} & W \ar[l]^{p} \ar[r]^{q} & Y \ar[l]^{j} & (η: 1_{W} → ip, η′: 1_{W} → jq),}  (18)

so that X and Y are full reflective subcategories of W. (It is a mono-epi factorisation in the category of future equivalences, through a sort of ‘graph’ of (f, g; φ, ψ)).

(b) Two categories are future equivalent if and only if they are full reflective subcategories of a third.

(c) Two categories are faithfully future equivalent if and only if they are faithful future retracts of a third.

(d) A property is future invariant if and only if it is preserved by all embeddings of full reflective subcategories, as well as by their reflectors. Similarly in the faithful case.

Proof. (a). First, we construct the category W:

(i) an object is a four-tuple (x, y; u, v) such that:

u: x → gy (in X),  v: y → fx (in Y),  gv.u = φx,  fu.v = ψy,  (19)

\xymatrix{x \ar[r]^{u} \ar[dr]_{φx} & gy \ar[d]^{gv} & y \ar[r]^{v} \ar[dr]_{ψy} & gy \ar[d]^{fu} \\  & gfx &  & fgy}  (20)

(ii) a morphism is a pair (a, b): (x, y; u, v) → (x′, y′; u′, v′) such that:

a: x → x′ (in X),  b: y → y′ (in Y),  gb.u = u′.a,  fa.v = v′.b, (21)

\xymatrix{x \ar[r]^{u} \ar[d]_{a} & gy \ar[d]^{gb} & y \ar[r]^{v} \ar[d]_{b} & gy \ar[d]^{fa} \\ x′ \ar[r]_{u′} & gy′ & y′ \ar[r]_{v′} & fx′}  (22)

Then, we have a split future equivalence of X into W:

\begin{matrix}i: X ⇄ W :p, & η: 1_{W} → ip, \\ i(x) = (x, fx; φx, 1_{fx}), & i(a) = (a, fa), \\ p(x, y; u, v) = x, & p(a, b) = a, \\ η(x, y; u, v) = (1_{x}, v): (x, y; u, v) → (x, fx; φx, 1_{fx}). \end{matrix}  (23)

The correctness of the definitions is easily verified, as well as the coherence conditions: pi = 1_{W}, pη = 1_{p}, ηi = 1_{i} (in particular, i is well defined because the given equivalence is coherent.)

Symmetrically, there is a split future equivalence of Y into W:

\begin{matrix}j: Y ⇄ W :q, & η′: 1_{W} → jq, \\ j(y) = (gy, y; 1_{gy}, ψy), & j(b) = (gb, b), \\ q(x, y; u, v) = y, & q(a, b) = b, \\ η′(x, y; u, v) = (u, 1_{y}): (x, y; u, v) → (gy, y; 1_{gy}, ψy). \end{matrix}  (24)

Finally, composing these two equivalences as in (18) (cf. (13)), gives back the original future equivalence (f, g; φ, ψ)

\begin{matrix}qi(x) = f(x), & qi(a) = f(a), \\ pη′i: 1_{X} → pj.qi, & pη′i(x) = pη′(x, fx; φx, 1_{fx}) = p(φx, 1_{fx}) = φx. \end{matrix}  (25)

Now, (b) follows immediately from (a). For (c), it suffices to modify the previous construction: if (f, g; φ, ψ) is faithful, we use the full subcategory W_{0} ⊂ W on the objects (x, y; u, v) where u and v are mono. Then, the functor i take values in W_{0} (as i(x) = (x, fx; φx, 1_{fx})); we restrict p, η and get a future retract which is faithful, since the general component η(x, y; u, v) = (1_{x}, v) is obviously mono. Symmetrically for j, q, η′. (One can also use a smaller full subcategory W_{1}, requiring that u, v be mono and epi).

Finally, (d) is an obvious consequence.

2.6. Future contractible categories. We say that a category X is future contractible if it is future equivalent to 1 (the singleton category {∗}); this happens if and only if X has a terminal object.

Indeed, if this is the case, we have a (split) future equivalence t: 1 ⇄ X:p where ηx: x → t(∗) is the unique map to the terminal object of X. Conversely, a future equivalence t: 1 ⇄ X:p necessarily splits: pt = 1; thus t: 1 → X is right adjoint to p and preserves the terminal object. (More analytically: every object x has a map ηx: x → t(∗); and indeed a unique one: given a: x → t(∗), the naturality of η implies a = ηx.)

It is interesting to note that faithful contractibility is much more restrictive than the previous condition. In fact, the functor p: X → 1 is faithful if and only if each hom-set of X has at most one element, which means that X ‘is’ a preordered set. Therefore, a category is faithfully future contractible—i.e. faithfully future equivalent to 1—if and only if it is a preordered set with a maximum; and dually for the past.

Finally, a category is past and future contractible (i.e., past and future equivalent to 1) if and only if it has an initial and a terminal object. Then, the future embedding (t: 1 → X) and the past one (i: 1 → X) can only coincide if X has a zero object (this will amount to contractibility for the finer relation of injective equivalence studied later, see 5.4). Marginally, we also use the notion of coarse contractibility, meaning coarse equivalent to 1 (2.3). Examples for all these cases will be considered in 2.8.

The future cone C^{+}X, obtained by freely adding a terminal object to the category X, is future contractible; it is also past contractible if and only if X is past contractible or empty.

2.7. Lemma. [Extremal points] The following properties of an object x ∈ X are future invariant:

(a) x is the terminal object of X,

(b) x is a weak terminal object of X, i.e. a maximum for the path preorder ≺ (1.5),

(c) x is maximal in X, for the path preorder,

(d) x does not reach a maximal point z.

Proof. Let f: X ⇄ Y :g be a future equivalence.

(a) Follows immediately from 2.6 (and 2.3): composing the future equivalence t: 1 ⇄ X:p produced by the terminal object x with the given one, we get a composite ft: 1 ⇄ Y :pg, which shows that ft(∗) = f(x) is terminal in Y.

(b) If x is a maximum in X, for every y ∈ Y: g(y) ≺ x and y ≺ fg(y) ≺ f(x).

(c) Let x be maximal and f(x) < y in Y. Then x ≺ gf(x) ≺ g(y) and all these points are equivalent, whence f(x) ≃ fg(y). But f(x) ≺ y ≺ fg(y) and y ≃ f(x).

(d) Since z is maximal, from z ≺ gf(z) we deduce that z ≃ gf(z). Therefore, if f(x) ≺ f(z) in Y, we have x ≺ gf(x) ≺ gf(z) ≃ z, and x ≺ z in X.

2.8. Elementary examples.

(a) Let us begin with a few examples, produced by finite or countable ordered sets. For preordered sets (viewed as categories), a future equivalence consists of a pair of preorderpreserving mappings f: X ⇄ Y :g such that 1_{X} ≤ gf and 1_{Y} ≤ fg, and is necessarily faithful. We already know that future contractibility means having a maximum

[figure: •; •; •; •; •; •; •; •; (past and future contractible)]  (26)

[figure: •; •; •; •; •; •; … •; •; •; •; (just future contractible); •]  (27)

[figure: •; •; •; •; •; •; •; •; •; •; •; •…; (just past contractible); •]  (28)

[figure: •; •; •; •; •; •; •; •; … •; •; •; •…; (just coarse-contractible); •; •]  (29)

(b) Consider again (as in (28)) the ordered set n of natural numbers, as a category. (Not to be confused with the monoid N, a quite different category on one object.) There are future equivalences

\begin{matrix}f: n ⇄ n :g, & f(x) = x, \\ g(x) = max(x, x_{0}), & φ(x) = ψ(x): x ≤ g(x), \end{matrix}  (30)

where x_{0} ∈ n is arbitrary (and coherence automatically holds, since our categories are preorders). Thus, f does not determine g. Note also (in relation with a previous result, 2.2b) that all components ψ(x) are mono and epi, but g is not full, i.e. does not reflect the preorder (when x_{0} > 0).

(c) Now we consider some finite categories, generated by the directed graphs drawn below; the outer cells, marked with a cross, do not commute and these categories are not preorders. The category represented in (31) is (faithfully) future equivalent to the first in (32), past equivalent to the second, past and future equivalent to the third and coarseequivalent to the last

[figure: •; •; •; •; •; 0; a; ×; b; 1; •; •; •; •; •]  (31)

\xymatrix{0 \ar[r] \ar[rrr] \ar[rrr] & a & × & 1 & 0 \ar[rrr] \ar[rrr] & × & b \ar[r] & 1 & 0 \ar[r] \ar[rrr] \ar[rrr] & a × & b \ar[r] & 1 & 0 \ar[rr] \ar[rr] & × & 1}  (32)

This shows a situation of interest in concurrency. There is a given starting point 0, which is minimal (1.5), but not initial nor the unique minimal point (generally); and a given ending point 1, which is maximal. Moreover:

- 0 is also a future branching point, where one has to choose among different ways of going forward; being such is a future invariant property (as will be proved in Thm. 6.6);

- a is a deadlock, i.e. a maximal unsafe vertex (from where one cannot reach 1); this is again a future invariant property, as already proved in 2.7;

- b is a minimal unreachable vertex (which cannot be reached from 0); being such is a past invariant property (according to the dual of 2.7);

- 1 is a past branching point, preserved by past equivalences (Thm. 6.6).

The ‘past and future model’ above (the third category in (32)) preserves all these properties, while the coarse one only recognises that there are two paths from 0 to 1.

(d) Finally, the following category (described by generators and relations)

\xymatrix{0 \ar[r]^{h} \ar[dr]_{h′} & a \ar[d]_{u} \ar[d]^{v} \ar[dr]^{k′} &  & uh = vh = h′, \\  & b \ar[r]_{k} & 1 & ku = kv = k′,}  (33)

has an initial object (0) and a terminal one (1): it is past and future contractible, but not faithfully so. Note also that, in the future contraction, all the components of the unit (x → 1) are epi.

3. Bilateral directed equivalences

In this section we study past and future equivalences sharing one functor, under the name of pf-equivalences. A particular case has been studied in category theory—essential localisations (3.7); the dual case, an adjoint reflexive cograph (3.6), should also be of interest.

The opposition between past and future is often marked with an index α which takes values 0, 1, written −, + in superscripts (a standard notation in cubical homotopical algebra).

3.1. Pf-equivalences. We have already considered categories which are ’separately’ past and future equivalent (e.g., in 2.6). However, an unrelated pair formed of a past equivalence and a future equivalence between the same categories is not an effective tool.

A pf-equivalence from X to Y will be a pair formed of a past equivalence (f, g^{−}; ε_{X}, ε_{Y}) and a future equivalence (f, g^{+}; η_{X}, η_{Y}) sharing the same functor f: X → Y, and also satisfying a further pf-coherence condition (35) linking the two pairs:

\begin{matrix}f: X → Y, & g^{−}, g^{+}: Y → X, \\ ε_{X}: g^{−}f → 1_{X}, & ε_{Y}: fg^{−} → 1_{Y} , \\ fε_{X} = ε_{Y} f: fg^{−}f → f, & ε_{X}g^{−} = g^{−}ε_{Y}: g^{−}fg^{−} → g^{−}, \\ η_{X}: 1_{X} → g^{+}f, & η_{Y}: 1_{Y} → fg^{+}, \\ fη_{X} = η_{Y} f: f → fg^{+}f, & η_{X}g^{+} = g^{+}η_{Y}: g → g^{+}fg^{+}, \end{matrix}  (34)

\xymatrix{g^{−} \ar[r]^{η_{Y}} \ar[d]_{η_{X}} & g^{−}fg^{+} \ar[d]^{ε_{X}g^{+}} \\ g^{+}fg^{−} \ar[r]_{g^{+}ε_{Y}} & g^{+} & (pf-coherence).}  (35)

This yields a natural transformation, the comparison from past to future

g: g^{−} → g^{+}: Y → X,  g = ε_{X}g^{+}.g^{−}η_{Y} = g^{+}ε_{Y} .η_{X}g^{−}.  (36)

which—when convenient—will be seen as a functor g: Y → X^{2}

g: Y → X^{2},  gy: g^{−}y → g^{+}y,  g(b) = (g^{−}b, g^{+}b).  (37)

A pf-equivalence will often be written as f: X ⟷ ← Y or f: X ⟷ ← Y :g^{α}, leaving the rest understood. It will be said to be faithful if both the past and the future equivalence which compose it are faithful. By 2.1, this is the case if and only if our data satisfy these equivalent conditions:

(i) all the components of η_{X}, η_{Y} (resp. ε_{X}, ε_{Y}) are mono (resp. epi),

(ii) f, g^{−}, g^{+} are faithful and all the components of η_{X}, η_{Y} (resp. ε_{X}, ε_{Y}) are epi (resp. mono).

Two dual types of pf-equivalences, where g^{−}, g^{+} are ‘split’ adjoint to f, will be treated below.

3.2. Composition. A pf-equivalence is not a symmetric structure. But they compose, by the composition of past equivalences and future equivalences (2.3).

Given f: X ⟷ ← Y :g^{α} (as in (34)) and a second pf-equivalence h: Y ⟷ ← Z :k^{α}

\begin{matrix}h: Y ⟷ ← Z :k^{α} (α = ±), \\ σ_{Y}: k^{−}h → 1_{Y} , σ_{Z}: hk^{−} → 1_{Z},  ζ_{Y}: 1_{Y} → k + h, ζ_{Z}: 1_{Z} → hk^{+}, \end{matrix}  (38)

their composite is:

\begin{matrix}hf: X ⟷ ← Z :g^{α}k^{α} (α = ±), \\ ε_{X}.g^{−}σ_{Y} f: g^{−}k^{−}.hf → g^{−}f → 1_{X}, \\ σ_{Z}.hε_{Y} k^{−}: hf.g^{−}k^{−} → hf.g^{−}k^{−} → 1_{Z}, … \end{matrix}  (39)

The following diagram shows that coherence holds (functors are replaced with ∗’s, in the labels of arrows)

[figure: g^{−}k^{−}; ∗ζ_{Z}; g^{−}k^{−}.hk^{+}; ∗η_{Y} ∗; ∗η_{Y} ∗; g^{−}k^{−}.hf.g^{+}k^{+}; ∗σ_{Y} ∗; g^{−}k^{+}; g^{−}k^{−}; ∗η_{Y} ∗; η_{X}∗; □; g^{−}fg^{+}k^{−}; ∗ζ_{Z}; ε_{X}∗; g^{−}f.g^{+}k^{−}hk^{+}; ∗σ_{Y} ∗; ε_{X}∗; g^{−}f.g^{+}k^{+}; ε_{X}∗; g^{+}f.g^{−}k^{−}; ∗ε_{Y} ∗; ∗ζ_{Y} ∗; g^{+}k^{−}; ∗ζ_{Z}; ∗ζ_{Y} ∗; □; g^{+}k^{−}hk^{+}; ∗σ_{Y} ∗; g^{+}k^{+}.hf.g^{−}k^{−}; ∗ε_{Y} ∗; g^{+}k^{+}.hk^{−}; ∗σ_{Z}; g^{+}k^{+}; g^{+}k^{+}] (40)

In fact, the outer square commutes, because all the inner ones do, by pf-coherence of the data (when marked with a box) or by middle-four interchange.

3.3. Lemma. [Pf-coherence] In a pf-equivalence f: X ⟷ ← Y :g^{α}, the condition of pfcoherence is redundant (follows from the rest of the axioms) whenever f is faithful or surjective on objects.

Proof. Indeed, composing the diagram (35) with the functor f, we get two diagrams whose commutativity follows from the other coherence conditions and middle-four interchange

\xymatrix{fg^{−} \ar[rr]^{fg^{−}η_{Y}} \ar[dd]_{fη_{X}g^{−}} \ar@{-->}[dr]_{ε_{Y}} &  & fg^{−}fg^{+} \ar[dd]^{fε_{X}g^{+}} & g^{−}f \ar[rr]^{g^{−}η_{Y} f} \ar[dd]_{η_{X}g^{−}f} \ar@{-->}[dr]_{ε_{X}} &  & g^{−}fg^{+}f \ar[dd]^{ε_{X}g^{+}f} \\  & 1_{Y} \ar@{-->}[dr]^{η_{Y}} &  &  & 1_{X} \ar@{-->}[dr]^{η_{X}} \\ f.g^{+}fg^{−} \ar[rr]_{fg^{+}ε_{Y}} &  & f.g^{+} & g^{+}fg^{−}f \ar[rr]_{g^{+}ε_{Y}} &  & g^{+}f}  (41)

Since a faithful functor is left-cancellable with respect to parallel natural transformations (fφ = fψ implies φ = ψ), while a functor surjective on objects is right-cancellable, the thesis follows.

3.4. Injections and projections.

(a) A pf-equivalence f: X ⟷ ← Y :g^{α} will be called a pf-injection, or pf-embedding, if the functor f is a full embedding (i.e., full, faithful and injective on objects). Pf-embeddings compose, with the composition of pf-equivalences (3.2); they will produce the ‘injective models’ of a category (4.1).

It is easy to see that a pf-embedding f: X ⟷ ← Y :g^{α} amounts to these three functors together with the two natural transformations at Y, satisfying the conditions below

ε_{Y}: fg^{−} → 1_{Y}  (the main counit),
η_{Y}: 1_{Y} → fg^{+}  (the main unit),
fg^{−}ε_{Y} = ε_{Y} fg^{−},  fg^{+}η_{Y} = η_{Y} fg^{+}.

(42)

In fact, these data can be uniquely completed to a pf-injection: there is a unique natural transformation η_{X}: 1_{X} → g^{+}f (the derived unit) such that fη_{X} = η_{Y} f: f → fg^{+}f (because the latter transformation lives in the ‘full image’ of f in Y); the other relation comes from cancelling f in f(η_{X}g^{+}) = η_{Y} fg^{+} = f(g^{+}η_{Y}). Similarly, there is one ε_{X}: g^{−}f → 1_{X} such that fε_{X} = ε_{Y} f. Finally, pf-coherence holds, by the previous Lemma.

(b) A pf-equivalence f: X ⟷ ←Y :g^{α} will be called a pf-surjection if the functor f is surjective on objects, and a pf-projection if, moreover, the associated functor g: Y → X^{2} (37) is a full embedding. The latter structure will give a ‘projective model’ of the category X (4.1).

We already know that, in a pf-surjection, pf-coherence is automatic (3.3); it is also obvious that the transformations at Y are determined by the ones at X (since ε_{Y} f = fε_{X}, η_{Y} f = fη_{X}), but here it seems to be less easy to deduce the former from the latter.

It is rather obvious that a general pf-equivalence f: X ⟷ ← Y :g^{α} can be restricted to a pf-surjection X ⟷ ← Z, replacing Y with the full subcategory Z of the objects of type fx (x ∈ X); this fact can be formulated in a more symmetric way (which is not a factorisation, generally).

3.5. Theorem. [The middle model] A pf-equivalence f: X ⟷ ← Y :g^{α} has an associated pf-surjection and an associated pf-injection

p: X ⟷ ← Z:r^{α},  i: Z ⟷ ← Y :h^{α},  (43)

where f = ip. This determines Z (the middle model), i and p up to category isomorphism. If the given pf-equivalence is faithful, so are the two associated ones. (In general, the composition of these two pf-equivalences does not give back the original one. The pf-surjection need not be a pf-projection, but this will be true in the cases of interest.)

Proof. The given units and counits will be written as in (34). Plainly, the functor f: X → Y has an essentially unique factorisation f = ip where p is surjective on objects and i: Z → Y is a full embedding: take for Z the full subcategory on the objects fx (x ∈ X).

Then, we define the functors r^{α}, h^{α} (α = ±)

r^{α} = g^{α}i: Z → X,  h^{α} = pg^{α}: Y → Z,  (44)

so that:

\begin{matrix}r^{α}p = g^{α}f, & ih^{α} = fg^{α}, \\ pr^{α} = pg^{α}i = h^{α}i, & r^{α}h^{α} = g^{α}ipg^{α} = g^{α}fg^{α}. \end{matrix}  (45)

(Here we can already note that r^{α}h^{α} need not be g^{α}.) Now, for the pf-injection, we just need to observe that the original natural transformations ε_{Y} , η_{Y} work as main counit and unit (42)

ε_{Y}: ih^{−} = fg^{−} → 1_{Y} ,  η_{Y}: 1_{Y} → ih^{+} = fg^{+},  (46)

since we already know that they commute with ih^{−} = fg^{−} and ih^{+} = fg^{+}, respectively.

On the other hand, the first pf-equivalence is completed with the natural transformations

\begin{matrix}ε_{X}: r^{−}p = g^{−}f → 1_{X}, & η_{X}: 1_{X} → r^{+}p = g^{+}f, \\ ε_{Z}: pr^{−} → 1_{Z}, & iε_{Z} = ε_{Y} i: ipr^{−} = fg^{−}i → i, \\ η_{Z}: 1_{Z} → pr^{+}, & iη_{Z} = η_{Y} i: i → ipr^{+}i = fg^{+}i, \end{matrix}  (47)

where ε_{X}, η_{X} are the original ones; ε_{Z} is a restriction of ε_{Y} (justified by the fact that ε_{Y} i: fg^{−}i = ipr^{−} → i lives in the full subcategory Z); and, similarly, η_{Z} is a restriction of η_{Y}.

Its coherence is deduced below, in brackets, from the homologous properties of the original data (recall that pf-coherence need not be checked, by 3.3)

\begin{matrix}pε_{X} = ε_{Z}p & (ipε_{X} = fε_{X} = ε_{Y} f = ε_{Y} ip = iε_{Z}p), \\ ε_{X}r^{−} = r^{−}ε_{Z} & (ε_{X}r^{−} = ε_{X}g^{−}i = g^{−}ε_{Y} i = g^{−}iε_{Z} = r^{−}ε_{Z}), \\ pη_{X} = η_{Z}p & (ipη_{X} = fη_{X} = η_{Y} f = η_{Y} ip = iη_{Z}p), \\ η_{X}r^{+} = r^{+}η_{Z} & (η_{X}r^{+} = η_{X}g^{+}i = g^{+}η_{Y} i = g^{+}iη_{Z} = r^{+}η_{Z}). \end{matrix}  (48)

Finally, let us assume that the original pf-equivalence is faithful (3.1). We know that all the components of η_{X}, η_{Y} are mono, whence the components of iη_{Z} = η_{Y} i are also, and the ones of η_{Z} as well, since i is faithful; dually for counits.

3.6. Split pf-injections. A split pf-injection, or adjoint reflexive cograph, will be a pf-equivalence i: E ⟷ ← X:p^{α} where the natural transformations p^{−}i → 1_{E} and 1_{E} → p^{+}i are identities.

So it consists of three functors i: E ⟷ ← X:p^{α} and two natural transformations ε and η such that:

i: E → X,  p^{+} ⊣ i ⊣ p^{−},
ε: ip^{−} → 1_{X} (the past counit),  η: 1_{X} → ip^{+} (the future unit),
p^{−}i = 1_{E} = p^{+}i,
p^{−}ε = 1,  εi = 1,  p^{+}η = 1,  ηi = 1.

(49)

Note that i is a full embedding, so that we do have a pf-injection; moreover, it essentially determines the rest of the structure: it embeds E as a full subcategory, reflective and coreflective, with reflector p^{+} and coreflector p^{−}. Conversely, given a full subcategory, reflective and coreflective, we can always choose the reflector so that the counit be an identity, and the coreflector so that the unit be an identity.

Pf-coherence yields one comparison p: p^{−} → p^{+} from the right adjoint to the left:

p = p^{−}η = p^{+}ε: p^{−} → p^{+}: X → E  (η.ε = ip^{−}η = ip^{+}ε: ip^{−} → ip^{+}),  (50)

(the right-hand formulas, which follow from middle-four interchange or (41), can also be useful).

Examples related with the present notions will be given in Section 5. Forgetting about smallness, there is a nice example linked with homology (which the author learned from F.W. Lawvere). Start from the embedding i: G_{∗}Ab → C_{∗}Ab of graded abelian groups into chain complexes, as complexes with a null differential. The left and right adjoints are computed, on a chain complex A = (A_{∗}, ∂_{∗}), as

p^{+}A = Coker(∂_{∗}) = A_{∗}/∂_{∗}(A∗),  p^{−}A = Ker(∂_{∗}),  (51)

and the graded group H_{∗}(A) can be defined as the image of the comparison pA: p^{−}A → p^{+}A. Note the symmetry of this presentation.

3.7. Split pf-projections. The dual notion of split pf-projection is well-known in category theory: it has been studied under the name of essential localisation [16, 2], or ‘unity and identity of adjoint opposites’ [17]; presently, the term ‘adjoint reflexive graph’ is also used by F.W. Lawvere.

It can be presented as a pf-equivalence p: X ⟷ ←M :i^{α} where the natural transformations pi^{−} → 1_{M} and 1_{M} → pi^{+} are identities. The structure consists thus of three functors and two natural transformations satisfying:

p: X → M,  i^{−} ⊣ p ⊣ i^{+},
ε: i^{−}p → 1_{X} (the past counit),  η: 1_{X} → i^{+}p (the future unit),
pi^{−} = 1_{M} = pi^{+},
pε = 1,  εi^{−} = 1,  pη = 1,  ηi^{+} = 1.

(52)

Note that i^{−} and i^{+} are full and faithful, because the past unit and the future counit are invertible. (Starting from a pair of adjunctions i^{−} ⊣ p ⊣ i^{+} in a 2-category, it is well known—but not obvious—that the unit of the first adjunction is invertible if and only if the counit of the second is; cf. [16], Prop. 2.3.)

Again, pf-coherence yields one comparison i: i^{−} → i^{+}

i = ηi^{−} = εi^{+}: i^{−} → i^{+}: M → X  (η.ε = ηi^{−}p = εi^{+}p: i^{−}p → i^{+}p).  (53)

Finally, p is obviously surjective on objects (and maps as well). Moreover, each functor i^{α} is a section, whence the comparison i: M → X^{2} is an embedding. To prove that it is full, take a morphism in X^{2}, from iy to iy′; since i^{−} and i^{+} are full (3.7), we have a commutative square

\xymatrix{i^{−}y \ar[r]^{iy} \ar[d]_{i^{−}b′} & i^{+}y \ar[d]^{i^{+}b′′} \\ i^{−}y′ \ar[r]_{iy′} & i^{+}y & i = ηi^{−} = εi^{+}.}  (54)

Applying p, and noting that the natural transformation pi is the identity, we deduce that b′ = b′′; calling b: y → y′ this morphism of M, it follows that i(b): iy → iy′ is the given square.

Again, examples will be given in Section 5. But we can already note that the forgetful functor p: Top → Set from topological spaces to sets has such a structure, with left (resp. right) adjoint provided by the discrete (resp. coarse) topology

p: Top ⟷ ← Set :i^{α},  i^{−} ⊣ p ⊣ i^{+} (ε: i^{−}p → 1, η: 1 → i^{+}p),  (55)

(so that Set is a faithful projective model of Top, as defined in 4.1).

3.8. Two structural pf-equivalences. (a) Any category X has a structural split pf-injection into X^{2}, determined by the cocylinder structure of the latter (or, equivalently, by the structure of 2 as a reflexive graph in Cat)

e: X ⟷ ← X^{2} :∂^{α},  e(x) = 1_{x}: x → x;  ∂^{α}(a: x^{−} → x^{+}) = x^{α},
ε(a: x^{−} → x^{+}) = (1, a): 1_{x^{−}} → a  (the counit),
η(a: x^{−} → x^{+}) = (a, 1): (a: x^{−} → x^{+}) → 1_{x^{+}} (the unit),
∂ = id: X^{2} → X^{2}  (the comparison);

(56)

4. Injective and projective models

Injective and projective models, defined in 4.1, will be our main tool. A pf-presentation of a category, formed of a past and a future retract (4.2), produces an injective model (4.3) and a projective one (4.6).

4.1. Definition. (a) Let i: E ⟷ ← X be a pf-embedding (i.e. a pf-equivalence where i is a full embedding, 3.4). In this situation, we say that E is an injective model of X, and that X is injectively modelled by E.

Two categories will be said to be injectively equivalent if they can be linked by a finite chain of pf-embeddings, forward or backward. Faithful pf-injections (3.1) give raise to faithful injective models and faithfully injectively equivalent categories.

(b) Similarly, a projective model M of X is given by a pf-projection p: X ⟷ ← M :r^{α} (3.4), and will generally be seen as a full subcategory r: M → X^{2}. The projective equivalence relation is generated by pf-projections. The faithful case is defined analogously.

In the rest of this section, the faithful case will generally be inserted in square brackets.

4.2. Pf-presentations. We introduce now another structure which combines past and future notions, and will then show how it produces an injective model (4.3) and a projective one (4.6).

A [faithful] pf-presentation of the category X will be a diagram consisting of a [faithful] past retract P and a [faithful] future retract F of X (which are thus a full coreflective and a full reflective subcategory, respectively)

[figure: ε: i^{−}p^{−} → 1_{X} (p^{−}i^{−} = 1, p^{−}ε = 1, εi^{−} = 1),; P; i^{−}; X; p^{+}; p^{−}; F; i^{+}; η: 1_{X} → i^{+}p^{+} (p^{+}i^{+} = 1, p^{+}η = 1, ηi^{+} = 1).]  (57)

We have thus two adjunctions i^{−} ⊣ p^{−}, p^{+} ⊣ i^{+}, and a composed one, from P to F, which is no longer split, with the following counit and unit

\begin{matrix}p^{+}εi^{+}: p^{+}i^{−}.p^{−}i^{+} → p^{+}i^{+} = 1_{F} , \\ p^{−}ηi^{−}: 1_{P} = p^{−}i^{−} → p^{−}i^{+}p^{+}i^{−} (p^{+}i^{−} ⊣ p^{−}i^{+}). \end{matrix}  (58)

4.3. Theorem. [Pf-presentations and injective models] Let a [faithful] pf-presentation of the category X be given (written as in (57)); let E be the full subcategory of X on ObP ∪ ObF and u its embedding in X.

(a) These data can be uniquely completed to a diagram with (four) commutative squares

[figure: P; i^{−}; X; p^{+}; p^{−}; F; i^{+}; X; r^{−}; r^{+}; P; j^{−}; E; q^{+}; q^{−}; u; F; j^{+}; E]  (59)

Moreover:

(b) there is a unique natural transformation ε_{E}: j^{−}q^{−} → 1_{E} such that uε_{E} = εu;

(c) there is a unique natural transformation η_{E}: 1_{E} → j^{+}q^{+} such that uη_{E} = ηu;

(d) these transformations make the lower row a [faithful] pf-presentation of E;

(e) letting r^{α} = j^{α}p^{α}: X → E (α = ±), we get a [faithful] pf-embedding

(u, r^{−}, r^{+}; ε_{E}, ε, η_{E}, η): E → X,

(and E will be called the [faithful] injective model generated by the given [faithful] pfpresentation of X).

(f) The functors ur^{α}: X → X are idempotents, with ur^{−}e = 1_{ur^{−}} = ur^{−}ε and ur^{+}η = 1_{ur^{+}} = ur^{+}η.

Proof. (a) First, we (must) take j^{+}: F ⊂ E (so that uj^{+} = i^{+}) and q^{+} = p^{+}u: E → F; and dually.

Now, we prove (b) to (d), completing the lower row of diagram (59) to a pf-presentation of E, as stated. On the right side, we already know that q^{+}j^{+} = p^{+}i^{+} = 1_{F}. Moreover, all the components of ηu: u → i^{+}p^{+}u: E → X belong to the (full) subcategory E, because both its functors take values there (since i^{+}p^{+}u = uj^{+}q^{+}); there is thus a unique natural transformation η_{E}: 1_{E} → j^{+}q^{+} such that uη_{E} = ηu, and it is easy to verify that η_{E}j^{+} = 1 and q^{+}η_{E} = 1.

(e) Then, we complete the pf-embedding letting r^{α} = j^{α}p^{α}: X → E and observe that:

ur^{+} = uj^{+}p^{+} = i^{+}p^{+},  r^{+}u = j^{+}p^{+}u = j^{+}q^{+}.  (60)

Therefore, we can take the natural transformation

η: 1_{X} → i^{+}p^{+} = ur^{+},  (61)

as main unit (42) of the pf-embedding u: E ⟷ ← X:r^{α}; the derived one is η_{E}, by (c); and similarly for counits. Finally, (f) is a straightforward consequence of i^{α}p^{α} = ur^{α}.

[The faithful case is proved in the same way. Point (d) requires a specific argument (as in 3.5): we know that all the components of η are mono, whence so are the components of uη_{E} = ηu, and also the ones of η_{E}, since u is faithful; dually for counits.]

4.4. Factorisation of adjunctions. We have already seen, in Thm. 2.5, that a future equivalence has a canonical factorisation into a future section followed by a future retraction. Similarly, we show now that an adjunction has a canonical factorisation into a past section (the embedding of a full coreflective subcategory) followed by a future retraction (the reflection onto a full reflective subcategory). Within the category of adjunctions, this factorisation is functorial (cf. [14]) and mono-epi, but we shall not need these facts.

Let f: X ⇄ Y :g be an adjunction, with η: 1 → gf and ε: fg → 1. We shall factor it through the following comma category, the graph of the adjunction

W = f|Y = X|g,  (62)

where we identify an object (x, y; u: x → gy) of the category X|g with the corresponding (x, y; v: fx → y) in f|Y. The factorisation is obvious

\xymatrix{X \ar[r]^{i^{−}} & W \ar[r]^{p^{+}} \ar[l]^{p^{−}} & Y \ar[l]^{i^{+}} & i^{−} ⊣ p^{−}, & p^{+} ⊣ i^{+},}  (63)

\begin{matrix}i^{−}(x) = (x, fx; 1: fx → fx),  p^{−}(x, y; v: fx → y) = x, \\ ε_{W}: i^{−}p^{−} → 1_{W} , \\ ε_{W} (x, y; v: fx → y) = (1_{x}, v): (x, fx; 1_{fx}) → (x, y; v: fx → y), \end{matrix}  (64)

\begin{matrix}i^{+}(y) = (gy, y; 1: gy → gy),  p^{+}(x, y; u: x → gy) = y, \\ η_{W}: 1_{W} → i^{+}p^{+}, \\ η_{W} (x, y; u: x → gy) = (u, 1_{y}): (x, y; u: x → gy) → (gy, y; 1_{gy}). \end{matrix}  (65)

In fact, composing these split adjunctions we get back the original one:

\begin{matrix}p^{+}i^{−}(x) = fx,  p^{−}i^{+}(y) = gy, \\ (p^{−}η_{W} i^{−})(x) = p^{−}η_{W} (x, fx; 1_{fx}) = p^{−}(ηx, 1_{y}) = ηx, \\ (p^{+}ε_{W} i^{+})(y) = p^{+}ε_{W} (gy, y; 1_{gy}) = p^{+}(1_{x}, εy) = εy. \end{matrix}  (66)

Functoriality can be easily checked, starting from a commutative square of adjunctions (whose rows are already factorised)

\xymatrix{X \ar[r]^{i^{−}} \ar[d]_{h} & W \ar[r]^{p^{+}} \ar[l]^{p^{−}} \ar@{.>}[d]_{r} & Y \ar[l]^{i^{+}} \ar[d]_{k} \\ X′ \ar[r]^{j^{−}} \ar[u]_{h′} & W′ \ar[r]^{q^{+}} \ar[l]^{q^{−}} \ar@{.>}[u]_{r′} & Y′ \ar[l]^{j^{+}} \ar[u]_{k′}}  (67)

\begin{matrix}i^{−} ⊣ p^{−}, & p^{+} ⊣ i^{+}, & f = p^{+}i^{−} ⊣ g = p^{−}i^{+}, \\ h ⊣ h′, & k ⊣ k′, \\ j^{−} ⊣ q^{−}, & q^{+} ⊣ j^{+}, & f′ = q^{+}j^{−} ⊣ g′ = q^{−}j^{+}. \end{matrix}  (68)

One defines the functors r, r′ as follows

\begin{matrix}r: W → W′,  r′: W′ → W, \\ r(x, y; v: fx → y) = (hx, ky; kv: f′hx = kfx → ky), \\ r′(x′, y′; u′: x′ → g′y′) = (h′x′, k′y′; h′u′: h′x′ → h′g′y′ = gk′y′). \end{matrix}  (69)

and constructs an adjunction r ⊣ r′ which gives commutative squares in (67).

A similar factorisation has been introduced in [13], for a colax-lax adjunction between double categories; the present result is likely known, but we have not been able to find a reference.

4.5. Faithful adjunctions. We shall say that the adjunction f ⊣ g is faithful if the functors f, g are faithful, or—equivalently - if the components of ε are epi and the components of η are mono. Obviously, faithful adjunctions compose.

Now, we can adapt the previous result, obtaining a similar factorisation into a faithful past section followed by a faithful future retraction. We restrict W to its full subcategory W_{0} (the faithful graph) of objects (x, y; u: x → gy) = (x, y; v: fx → y) such that

u: x → gy is mono and the corresponding v: fx → y is epi.  (70)

The functors i^{α} take values in W_{0} (every ηx is mono and corresponds to 1_{fx}). Thus, the components of ε_{W} (x, y; v) = (1_{x}, v) and η_{W} (x, y; u) = (u, 1_{y}) on such objects are, respectively, epi and mono; this proves that the restricted adjunctions are faithful.

4.6. Definition and Theorem. [Pf-presentations and projective models]

(a) Given a pf-presentation of the category X (with notation as in (57)), there is an associated projective model M of X, constructed as follows

[figure: P; i^{−}; X; p^{+}; p^{−}; f; F; i^{+}; X; X; P; j^{−}; W; q^{+}; q^{−}; F; j^{+}; W; r^{−}; r^{+}; M]  (71)

The lower row is the canonical factorisation of the composed adjunction P ⇄ F (62), through its graph, the category W, which (here) can be embedded as a full subcategory of X^{2}

W = (P |p^{−}i^{+}) = (p^{+}i^{−}|F) = (i^{−}|i^{+}) ⊂ X^{2}.  (72)

Then, there is a pf-equivalence f: X ⟷ ← W :r^{α}, with

r^{α}f = i^{α}p^{α},  j^{α} = fi^{α},  (73)

which inherits the counit ε from the adjunction i^{−} ⊣ p^{−} and the unit η from p^{+} ⊣ i^{+}; its comparison r: W → X^{2} coincides with the embedding (i^{−}|i^{+}) ⊂ X^{2}.

Finally, replacing W with the full subcategory M of objects of type fx (forx ∈ X) we have a projective model p: X ⟷ ← M. The adjunctions of the lower row can be restricted to M (since j^{α} = fi^{α}), so that P and F are also, canonically, a past and a future retract of M.

(b) If the given pf-presentation of X is faithful, proceeding as above with the faithful graph W_{0} (4.5), the full subcategory of W (and X^{2}) on the objects (x, y; w: i^{−}x → i^{+}y) such that:

p^{−}w: x → p^{−}i^{+}y is mono and p^{+}w: p^{+}i^{−}x → y is epi.  (74)

we obtain a faithful projective model p: X ⟷ ← M_{0}.

Proof. (a) The comma category W = (i^{−}|i^{+}) is a full subcategory of X^{2}, because both i^{α} are full embeddings; it has a canonical isomorphism with the graph (P |p^{−}i^{+}) = (p^{+}i^{−}|F)

\begin{matrix}(i^{−}|i^{+}) → (P |p^{−}i^{+}), & (x, y; w: i^{−}x → i^{+}y) ↦ (x, y; p^{−}w: x → p^{−}i^{+}y), \\ (P |p^{−}i^{+}) → (i^{−}|i^{+}), & (x, y; u: x → p^{−}i^{+}y) ↦ (x, y; εi^{+}y.i^{−}u: i^{−}x → i^{+}y), \\ p^{−}(εi^{+}y.i^{−}u) = u, & εi^{+}y.i^{−}p^{−}w = w.εx = w.εi^{−}p^{−}x = w. \end{matrix}  (75)

We define the three functors f: X ⟷ ← W :r^{α}

\begin{matrix}f(x) = (p^{−}x, p^{+}x; ηx.εx: i^{−}p^{−}x → i^{+}p^{+}x), \\ r^{−}(x, y; w: i^{−}x → i^{+}y) = i^{−}x,  r^{+}(x, y; w: i^{−}x → i^{+}y) = i^{+}y, \end{matrix}  (76)

and observe that they satisfy the relations (73). Then, we complete the pf-equivalence with the following counits and units (ε, η are the given ones):

\begin{matrix}ε_{X} = ε: r^{−}f = i^{−}p^{−} → 1_{X},  η_{X} = η: 1_{X} → r^{+}f = i^{+}p^{+}, \\ ε_{W}: fr^{−} → 1_{W} ,  η_{W}: 1_{W} → fr^{+}, \\ ε_{W} (x, y; w: i^{−}x → i^{+}y) = \\ (1_{x}, p^{+}w): (x, p^{+}i^{−}x; ηi^{−}x: x → i^{+}p^{+}i^{−}x) → (x, y; w: i^{−}x → i^{+}y), \\ η_{W} (x, y; w: i^{−}x → i^{+}y) = \\ (p^{−}w, 1y): (x, y; w: i^{−}x → i^{+}y) → (p^{−}i^{+}y, y; εi^{+}y: i^{−}p^{−}i^{+}y → y). \end{matrix}  (77)

The coherence conditions are easily verified. Moreover, the comparison functor r: W → X^{2} (coming from the natural transformation r = ε_{X}r^{+}.r^{−}η_{W}: r^{−} → r^{+}) coincides with the full embedding (i^{−}|i^{+}) ⊂ X^{2} (use (75))

\begin{matrix}r(x, y; w: i^{−}x → i^{+}y) = ε_{X}i^{+}y.r^{−}(p^{−}w, 1_{y}) = εi^{+}y.i^{−}p^{−}w = w, \\ r(a, b) = (i^{−}a, i^{+}b). \end{matrix}  (78)

The last assertion follows from 3.5, since M ⊂ W ⊂ X^{2} is also full in the latter.

(b) Assume that the given pf-presentation is faithful. We know (from 4.5) that the presentation of W_{0} is also faithful; moreover, the right adjoint p^{−} preserves monos and the left adjoint p^{+} preserves epis. It follows that f: X → W takes values in W_{0}. The restricted pf-equivalence X ⟷ ← W_{0} is faithful, because its units η_{X} = η and η_{W_{0}}(x, y; w) = (p^{−}w, 1_{y}) have monic components, while the counits have epi components. Finally, the associated projective model is faithful as well (3.5).

4.7. From injective to projective models. In particular, a split injective model i: E ⟷ ← X:p^{α} has an associated projective model (which is generally not split, cf. 5.5). In fact, our structure gives a pf-presentation

\xymatrix{E \ar[r]^{i} & X \ar[r]^{p^{+}} \ar[l]^{p^{−}} & E \ar[l]^{i} & ε: ip^{−} → 1_{X}, η: 1_{X} → ip^{+},}  (79)

which produces, as above, a pf-equivalence based on the comparison p: p^{−} → p^{+} as a functor

p: X ⟷ ← E^{2} :i^{α},  E^{2} = (i|i) ⊂ X^{2},  (80)

and a pf-projection p′: X ⟷ ← E′ with values in the full subcategory E′ ⊂ E^{2} whose objects are the morphisms px: p^{−}x → p^{+}x. (Example 5.5 will show that this can be a proper subcategory).

5. Minimal models of a category

In this section, pf-equivalences are used to analyse a category, via injective and projective models. The faithful case is considered at the end, in 5.7.

5.1. Ordinary skeleta. Let us briefly review the usual, non-directed notion of a skeleton (cf. [18]). A category is said to be skeletal if it has a unique object in each class of isomorphism; two equivalent skeletal categories are necessarily isomorphic.

The skeleton of a category X is a skeletal category equivalent to the former, determined up to isomorphism of categories. It always exists: choose one object in each class of isomorphic objects of X and take their full subcategory (whose embedding in X is faithful, full and essentially surjective on objects). Two categories are equivalent if and only if their skeleta are isomorphic, so that skeleta classify equivalence classes of categories.

For our present analysis, it will be useful to note two facts. First, the skeleton of a category X can be defined as a category E such that:

(a) E has an equivalent embedding into X,

(b) every equivalent embedding E′ → E is an isomorphism of categories,

where ’equivalent embedding’ denotes an equivalence of categories which is injective on objects.

Second, the uniqueness of the skeleton of a category X can be expressed as follows: given two skeleta i: E → X and j: E′ → X

(c) there is a unique mapping u: ObE → ObE′ such that, for every z ∈ E, i(z) ≅ ju(z) in X,

(d) for every choice of a family of isomorphisms λ(z): i(z) → ju(z), the mapping u has a unique extension to a functor u: E → E′ making that family a natural isomorphism λ: i → ju.

Thus, the equivalent embedding E → X is determined up to a natural isomorphism, which is not unique.

5.2. Minimal models. (a) By definition, an injective model of the category X is given by a pf-embedding i: E ⟷ ← X (4.1). We say that E is a minimal injective model of X if:

(i) E is an injective model of every injective model E′ of X, (ii) every injective model E′ of E is isomorphic to E.

We say that it is a strongly minimal injective model if it satisfies the stronger condition (i′), together with (ii): (i′) E is an injective model of every category injectively equivalent to X.

Note that we are not requiring any consistency of the embeddings. Thus, the minimal injective model of a category X is determined up to isomorphism (when existing); but the isomorphism itself is generally undetermined, and the pf-embedding E → X will not even be determined up to isomorphism, as we will see in various examples (cf. 5.5, 5.6).

Plainly, two categories having a common injective model are injectively equivalent. Moreover, strongly minimal injective models classify injective equivalence (when they exist): if the category X has a strongly minimal injective model E, then the category Y is injectively equivalent to X if and only if E is also an injective model of Y (in which case, it is also a strongly minimal injective model of the latter).

(b) Similarly, a projective model of X is given by a pf-projection p: X ⟷ ← M (4.1). We define a (strongly) minimal projective model of X as above.

We shall see that the two notions are different: a category with initial and terminal object is always projectively contractible, while it is injectively contractible if and only if it is pointed (5.4). Other comparisons are in Section 9, and in the Introduction; injective models will often give a finer analysis.

Note that, even if the projective model M is a full subcategory of X^{2}, we are not interested in the minimal injective model of the latter, which is injectively equivalent to X (3.8a).

(c) Let us begin considering the case of a groupoid X. Every full subcategory E containing at least one object in each class of isomorphic objects is an injective model (since the embedding can be completed to an adjoint equivalence, which can be viewed as a past and a future equivalence). Therefore, the ordinary skeleton of a groupoid is its minimal injective model. The same holds in the projective case.

5.3. Lemma. Let i: E ⟷ ← X:r^{α} be a pf-embedding.

(a) The functor i preserves and reflects the existence of the initial and terminal objects, as well as their being isomorphic or not.

(b) The three functors i, r^{−}, r^{+} preserve the zero object.

Proof. (a) The functor i is part of a past and a future equivalence, therefore it preserves the initial and terminal object (Lemma 2.7), their being isomorphic (obviously) or not (being full and faithful). Suppose now that X has an initial object 0 and a terminal one,

1. Then r^{−}(0) is initial and r^{+}(1) is terminal in E; moreover ir^{−}(0) ≅ 0 (because it is also initial in X) and ir^{+}(1) ≅ 1, so that 0 ≅ 1 in X if and only if r^{−}(0) ≅ r^{+}(1) in E (again because i is full and faithful). The point (b) has also been proved.

5.4. Injective and projective contractibility. We say that a category X is injectively contractible if it is injectively equivalent to 1. This condition is equivalent to the following ones:

(a) X is pointed (i.e., it has a zero object),

(b) 1 is a (split) injective model of X,

(c) 1 is a strongly minimal injective model of X.

Indeed, if X is injectively equivalent to 1 then it is pointed (because of the previous Lemma). If this is true, then we have functors i: 1 ⇄ X:p with p ⊣ i ⊣ p, so that 1 is a (split) injective model of X. In this case, strong minimality is obvious. Finally, (c) trivially implies that X is injectively equivalent to 1.

On the other hand, a category X with non-isomorphic initial and terminal object is injectively modelled by the ordinal 2 = {0 → 1}, with the obvious pf-embedding i: 2 ⟷ ← X:r^{α} (not split)

\begin{matrix}r^{−}(x) = 0, & ε_{E}(z): 0 → z, & ε(x): 0 → x, \\ r^{+}(x) = 1, & η_{E}(z): z → 1, & η(x): x → 1. \end{matrix}  (81)

This is actually the strongly minimal injective model of X. Indeed, again by the previous Lemma, every category injectively equivalent to X has an initial and terminal object which are not isomorphic, and is thus injectively modelled by 2. Second, any injective model E′ → 2 is surjective on objects (and a full embedding), whence an isomorphism.

It is interesting to note that 2, the standard interval of Cat, is not contractible in this sense.

On the other hand, on the projective side, the existence of the initial and terminal objects is sufficient (and necessary) to make a category X projectively equivalent to 1, via the split pf-projection p: X ⟷ ← 1 :i^{α}, with i^{−}(∗) = 0 and i^{+}(∗) = 1.

In all these cases, the faithful analogue restricts the categories X to preorders (as in 2.6).

5.5. The model of the ordered line. (Here, all the categories will be ordered sets, so that all coherence conditions are automatically satisfied and all equivalences are faithful.) We want to model the ordered real line r as a category; note that it is the fundamental category of the ordered topological space ↑R.

The full subcategory z of integers is a split injective model of r, with the inclusion i: z ⊂ r and

\begin{matrix}p^{−}(x) = max\{k ∈ z | k ≤ x\}, & εx: ip^{−}(x) ≤ x, & p^{−}i = id & (i ⊣ p^{−}), \\ p^{+}(x) = min\{k ∈ z | k ≥ x\}, & ηx: x ≤ ip^{+}(x), & p^{+}i = id & (p^{+} ⊣ i); \end{matrix}  (82)

(p^{−} is the integral part, and p^{+}(x) = −p^{−}(−x)).

It is indeed a minimal injective model of r. For every injective model u: E ⟷ ← r :r^{α}, E is a subset of r with the induced preorder, necessarily initial, i.e. ‘past unbounded’ (since ur^{−}(x) ≤ x), and final i.e. ‘future unbounded’; choosing an arbitrary order-preserving embedding (x_{k})_{k∈z} of z into E, unbounded both ways, we have again a split pf-injection z → E (with right and left adjoint constructed as above). Moreover, if E is an injective model of z, then it is unbounded there and necessarily order-isomorphic to it.

Of course, r contains various minimal injective models, all isomorphic but not isomorphically embedded (since the only isomorphisms of r are the identities); e.g. 2z (properly contained in z) and 1/2 + z (disjoint from z). Injective models of trees will be considered later (9.1).

By 4.7, the split pf-injection z → r has an associated pf-equivalence p: r ⟷ ← z^{2} :g^{α} with values in the order category of pairs of integers (k, k′) with k ≤ k′

p(x) = (p^{−}x, p^{+}x),  g^{−}(k, k′) = k,  g^{+}(k, k′) = k′,  (83)

which—essentially—sends a real number to the least interval [k, k′] with integral endpoints, containing it. Reducing the codomain of p to the full subcategory z′ ⊂ z^{2} of pairs (k, k′) with 0 ≤ k′ − k ≤ 1, we get the associated projective model p′: r ⟷ ← z′, which is not split (p′g^{−}(k, k′) = (k, k)).

It is interesting to note that there is no split pf-projection r → z; in fact, the preimages of integers would form a sequence of disjoint compact intervals I_{k} = [i^{−}(k), i^{+}(k)], with I_{k} (strictly) preceding I_{k+1}; but such a sequence cannot cover the line, leaving gaps ]i^{+}(k), i^{−}(k + 1)[.

5.6. The model of the directed circle. Consider now (as in 1.3) the subcategory c of the fundamental groupoid Π_{1}(S^{1}) of the circle containing all points and the homotopy classes of those paths which move ‘anticlockwise’ in the plane R^{2}.

We prove now that the minimal injective model of c is its full subcategory E at a(ny) point x, which we identify with the additive monoid N of the natural numbers. (It is the fundamental monoid of the inequilogical circle ↑\overline{S}_{e}^{1} = (↑R, ≡_{Z}) considered in 1.3).

First, we show that the embedding i: E → c has a left and a right adjoint, forming a split pf-injection

i: E → c,  p^{+} ⊣ i ⊣ p^{−},
ε: ip^{−} → 1_{c} (the past counit),  η: 1_{c} → ip^{+} (the future unit).

(84)

[figure: x; •; x; b; •; x; c; •; x; d; •]  (85)

p^{−}[b] = 1, p^{−}[c] = 0, p^{−}[d] = 1,  p^{+}[b] = 1, p^{+}[c] = 1, p^{+}[d] = 0.  (86)

Roughly speaking, both the functors p^{−}, p^{+}: c → E count the number of times that a directed path a in S^{1} crosses the point x, a number which only depends on the homotopy class [a] in c, because of our restriction on paths. But the precise definition is different: p^{−}[a] is the number of times that a reaches x from below, while p^{+}[a] is the number of times that a leaves x upwards (the examples above show the difference). Then, the counit component εx′: x → x′ is the class of the ‘least anticlockwise path’ from x to x′ (so that p^{−}(εx′) = 0 is indeed the identity of the monoid); and dually for ηx′: x′ → x (now, p^{+}(ηx′) = 0). The coherence properties (49) hold.

Now, if E′ is an injective model of c (hence a full subcategory), the full subcategory of E′ (and c) on some point x′ is pf-embedded in E′ as above, and isomorphic to E; moreover, E—having just one object—is the unique injective model of itself.

Similarly, one can prove that the minimal injective model of the fundamental category of the inequilogical torus (↑\overline{S}_{e}^{1})^{n} = (↑R^{n}, ≡_{Z^{n}}) (1.3) is the fundamental monoid at any point, isomorphic to N^{n}. (The projective model of c produced by the split pf-injection E → c is the full subcategory of the category E^{2} on the two objects 0, 1: x → x; which seems not to be of much interest.)

5.7. Minimal faithful models. The terminology of this section can be adapted to the faithful case (4.1) in the obvious way, for the injective and the projective case. For instance, we say that E is a minimal faithful injective model of X if:

(i) E is a faithful injective model of every faithful injective model E′ of X,

(ii) every faithful injective model E′ of E is isomorphic to E.

If X is balanced, every faithful pf-embedding i: E → X is essentially surjective on objects (each component ηx: x → ir^{+}(x) being an isomorphism), whence an equivalence of categories. Therefore, the minimal faithful injective model of X is simply its skeleton.

A category can have a minimal injective model and a different minimal faithful injective model. For instance, the well-known category Δ^{+} of finite ordinals (the site of augmented simplicial sets), being skeletal and balanced, is already a minimal faithful injective model (of itself), while its minimal injective model is 2 (5.4); the same happens with the category of finite cardinals (and all mappings), or the category described in 2.8d, which is not balanced.

6. Future invariant properties

In this section we investigate various properties, of morphisms and objects, which are invariant under future (or past) equivalence. They are linked with ’branching’ or ’nonbranching’ properties, as in the definition of filtered categories (cf. 6.5), and will be used in the next sections to identify and construct minimal models of categories.

6.1. Future regularity. A morphism a: x → x′ in X will be said to be V^{+}-regular if it satisfies condition (i), O^{+}-regular if it satisfies (ii), and future regular if it satisfies both:

(i) given a′: x → x′′, there is a commutative square ha = ka′ (V^{+}-regularity),

(ii) given two maps a_{i}: x′ → x′′ such that a_{1}a = a_{2}a, there is some h such that ha_{1} = ha_{2} (O^{+}-regularity),

[figure: x; a; a′; x′; h; x; a; x′; a_{1}; a_{2}; x′′; h; •; x′′; k; •]  (87)

Future regular morphisms are closed under composition (6.2), but they are not invertible, in general. The equivalence relation ∼^{+} in ObX generated by the existence of a future regular morphism between two objects will be called future regularity equivalence. The future regularity class of an object x will be written [x]^{+}.

In a category with finite colimits or with terminal object, all morphisms are future regular. In a preordered set, all arrows are O^{+}-regular, and future regularity coincides with V^{+}-regularity.

On the other hand, we shall say that the morphism a is V^{+}-branching if it is not V^{+}-regular; that it is O^{+}-branching if it is not O^{+}-regular; that it is a future branching morphism if it falls in (at least) one of the previous cases, i.e. if it is not future regular. In the category represented below, at the left, the morphism a is V^{+}-branching and O^{+}- regular, while at the right a is O^{+}-branching and V^{+}-regular

[figure: x; a; a′; x′; x; a; b; x′; a_{1}; a_{2}; (b = a_{1}a = a_{2}a).; x′′; x′′]  (88)

Dually, we have V^{−}-regular, O^{−}-regular, past regular morphisms and the corresponding branching morphisms; the past regularity equivalence ∼^{−} and its past regularity classes [x]^{−}.

6.2. Lemma.

(a) V^{+}-regular, O^{+}-regular and future regular morphisms form (wide) subcategories, containing all the isomorphisms.

(b) If a composite ba is V^{+}-regular (resp. O^{+}-regular), then the first map a (resp. the second map b) is also.

Proof. Take two consecutive morphisms in X, a: x → x′ and b: x′ → x′′.

First, let us consider the property of V^{+}-regularity. It is plainly consistent with composition. On the other hand, if ba is V^{+}-regular also a is: for every a′: x → \overline{x} there is a commutative square h(ba) = ka′, which can be rewritten as (hb).a = ka′.

Second, let us consider O^{+}-regularity. If a and b are so, take two maps b_{i}: x′′ → \overline{x} such that b_{1}(ba) = b_{2}(ba); by O^{+}-regularity of a there is some h such that hb_{1}b = hb_{2}b; then, by O^{+}-regularity of b, there is some k such that khb_{1} = khb_{2}. On the other hand, if ba is O^{+}-regular, also b is: if b_{1}b = b_{2}b, then b_{1}(ba) = b_{2}(ba) and there is some h such that hb_{1} = hb_{2}.

6.3. Theorem. [Future equivalence and regular morphisms] Given a future equivalence f: X ⇄ Y :g, with natural transformations φ: 1 → gf, ψ: 1 → fg, we have:

(a) all the components φx and ψy are future regular morphisms,

(b) the functors f and g preserve V^{+}-regular, O^{+}-regular and future regular morphisms,

(c) the functors f and g preserve V^{+}-branching, O^{+}-branching and future branching morphisms (i.e. reflect V^{+}-regular, O^{+}-regular and future regular morphisms),

Proof. (a) Take a component φx: x → gfx. Then, a map a: x → x′ gives the left commutative diagram, showing that φx is V^{+}-regular

\xymatrix{x \ar[r]^{φx} \ar[d]_{a} & gfx \ar[d]^{gfa} & x \ar[r]^{φx} \ar[dr]_{a} & gfx \ar[r]^{φgfx} \ar[d]_{a_{i}} \ar@{-->}[dr]^{gfa} & gfgfx \ar[d]^{gfa_{i}} \\ x′ \ar[r]_{φx′} & gfx′ &  & x′ \ar[r]_{φx′} & gfx′}  (89)

Moreover, given two maps a_{i}: gfx → x′ such that a_{i}.φx = a, the right diagram shows that φx′ coequalises a_{i} (as in (11)): from φgf = gfφ we deduce φx′.a_{i} = gfa_{i}.φgfx = gf(a_{i}.φ_{x}) = gf(a).

(b) Suppose that a: x → x′ is V^{+}-regular in X; we must prove that fa: fx → fx′ is V^{+}-regular in Y. Given b: fx → y, we can form the left commutative diagram in X, and then the right one, in Y

\xymatrix{x \ar[r]^{a} \ar[d]_{φx} & x′ \ar[dd]^{h′} & fx \ar[rr]^{fa} \ar[dd]_{b} \ar[dr]^{ψfx=fψx} &  & fx′ \ar[dd]^{fh′} \\ gfx \ar[d]_{gb} &  &  & fgfx \ar[d]^{fgb} \\ gy \ar[r]_{h} & x′′ & y \ar[r]_{ψy} & fgy \ar[r]_{fh} & fx′′}  (90)

Second, suppose that a: x → x′ is O^{+}-regular in X. Given two maps b_{i}: fx′ → y such that b_{i}.fa = b, we have (at the left, below): gb_{i}.φx′.a = gb_{i}.gfa.φx = gb.φx. Therefore, there exists an h in X such that the composite h.gb_{i}.φx′ does not depend on i (see the left diagram below)

\xymatrix{x \ar[r]^{a} \ar[dr]_{gb.φx} & x′ \ar[d]^{gb_{i}.φx′} &  & fx \ar[r]^{fa} \ar[dr]_{b} & fx′ \ar[r]^{ψfx′}_{fφx′} \ar[d]^{b_{i}} & fgfx′ \ar[d]^{fgb_{i}} \\  & gy \ar@{-->}[r]_{h} & x′′ &  & y \ar[r]_{ψy} & fgy \ar[r]_{fh} & fx′′}  (91)

Then, in the right diagram above, the composite fh.ψy.b_{i} = fh.fgb_{i}.ψfx′ = f(h.gb_{i}.φx′), in Y, does not depend on i either.

(c) First, given a: x → x′ in X, suppose that fa is V^{+}-regular (in Y); we must prove that a is also. Given a′: x → x′′, we can form the right commutative diagram in Y, and then the left one, in X

\xymatrix{x \ar[rr]^{a} \ar[dd]_{a′} \ar[dr]^{φx} &  & x′ \ar[d]^{φx′} & fx \ar[r]^{fa} \ar[d]_{fa′} & fx′ \ar[d]^{k′} \\  & gfx \ar[r]^{gfa} \ar[d]^{gfa′} & gfx′ \ar[d]^{gk′} & fx′′ \ar[r]_{k} & y \\ x′′ \ar[r]_{φx′′} & gfx′′ \ar[r]_{gk} & gy}  (92)

Second, let us suppose that fa is O^{+}-regular in Y; given two maps a_{i}: x′ → x′′ such that a_{i}.a = a′, there is some k such that k.fa_{i} = k′, in the right diagram; and then, in the left, (gk.φx′′).a_{i} = g(k.fa_{i}).φx′ = gk′.φx′ is independent of i

\xymatrix{x \ar[r]^{a} \ar[dr]_{a′} & x′ \ar[r]^{φx′} \ar[d]^{a_{i}} & gfx′ \ar[d]_{gfa_{i}} \ar[dr]^{gk′} &  & fx \ar[r]^{fa} \ar[dr]_{fa′} & fx′ \ar[d]^{fa_{i}} \ar[dr]^{k′} \\  & x′′ \ar[r]_{φx′′} & gfx′′ \ar[r]_{gk} & gy &  & fx′′ \ar[r]_{k} & y}  (93)

6.4. Corollary. A future equivalence f: X ⇄ Y :g induces a bijection between the quotients (ObX)/ ∼^{+} and (ObY)/ ∼^{+} (of objects up to future regularity equivalence). Therefore, the functors f and g preserve and reflect the future regularity equivalence relations ∼^{+}.

Proof. By 6.3b, we have induced mappings (ObX)/ ∼^{+}⇄ (ObY)/ ∼^{+}, which are inverses by 6.3a.

6.5. Branching points. We consider now future invariant properties of points of a category X. We have already seen a few, concerning extremal points (2.7). A point x will be said to be V^{+}-regular if it satisfies (i), O^{+}-regular if it satisfies (ii), future regular if it satisfies both:

(i) every arrow starting from x is V^{+}-regular (equivalently, two arrows starting from x can always be completed to a commutative square),

(ii) every arrow starting from x is O^{+}-regular (i.e., given an arrow a: x → x′ and two arrows a_{i}: x′ → x′′ such that a_{1}a = a_{2}a, there exists an arrow h such that ha_{1} = ha_{2}).

It is easy to verify that x is future regular in X if and only if the comma category (x|X) of arrows starting from x is filtered [18], IX.1; but this will not be used here.

We shall say that x is a V^{+}-branching point in X if it is not V^{+}-regular (i.e., if there is some arrow starting from x which is V^{+}-branching); that x is an O^{+}-branching point if it is not O^{+}-regular; that x is a future branching point if it falls in at least one of the previous cases, i.e. if it is not future regular.

Note now that, in the fundamental category C considered in the Introduction, the starting point 0 is V^{+}-branching, but the choice between the different paths starting from it can be deferred, while at the point a (also V^{+}-branching) the choice must be made. To distinguish these situations, we will say that a future branching point is effective when every future regular map starting from it is a split mono. (In the fundamental category of a preordered or ordered space, this amounts to an isomorphism or an identity, respectively).

Dually, we have the notions of V^{−}-, O^{−}- and past regular (resp. branching) point in X, and effective past branching points.

6.6. Theorem. [Future equivalence and branching points] The following properties of a point are future invariant (i.e., invariant up to future equivalence):

(a) being a V^{+}-regular, or an O^{+}-regular, or a future regular point,

(b) being a V^{+}-branching, or an O^{+}-branching, or a future branching point, or an effective one.

Proof. Let f: X ⇄ Y :g be a future equivalence, with φ: idX → gf and ψ: idY → fg.

(a) Let us take a point x which is V^{+}-regular in X, and prove that every Y -arrow b: fx → y is V^{+}-regular. Indeed, the map a = gb.φx: x → gy is V^{+}-regular, whence also fa is (by Thm. 6.3); but fa = fgb.fφx = fgb.ψfx = ψy.b, whence also the ‘first map’ b is V^{+}-regular (6.2b).

We assume now that x is O^{+}-regular, and prove that every Y-map b: fx → y is also. Now, the composite gb.φx is O^{+}-regular in X, whence the ‘second map’ gb is O^{+}-regular (6.2b), and b itself is O^{+}-regular in Y (by the reflection property, in Thm. 6.3).

(b) We take a point x in X such that fx is V^{+}-regular (i.e., not V^{+}-branching) and prove that also x is. For every a: x → x′ in X, fa: fx → fx′ is V^{+}-regular in Y; but then a is V^{+}-regular in X, by the reflection property 6.3c. The same holds replacing the prefix V^{+} with O^{+}.

Finally, let x be an effective future branching point and b: fx → y a future regular map. Then a = gb.φx: x → gy is future regular, whence a is a split mono and also fa is; but fa = fgb.fφx = fgb.ψfx = ψy.b, whence also b is a split mono.

7. Directed spectra of a category

We define now the future and the past spectrum of a category, and show that they are its least full reflective and its least full coreflective subcategories. Their join forms the pf-spectrum, a strongly minimal injective model whose embedding in the original category is essentially unique. The pf-spectrum also produces a projective model.

7.1. Least future retracts. By a replete subcategory of a category X we will mean a full subcategory which is closed (in X) under isomorphic copies of objects. If C is a full subcategory, its replete closure C′ in X has the same skeleton.

Within full subcategories of X, we define the preorder of essential inclusion C ≺ D by the inclusion C′ ⊂ D′ of their replete closures (which reduces to C ⊂ D, when X is skeletal—as it will often be the case in our applications). We are interested in a least full reflective subcategory, or least future retract F of X, for this preorder. If it exists, its replete closure is strictly determined as the least replete reflective subcategory of X (with respect to inclusion); and a category Y is future equivalent to X if and only if F is also a future retract of Y (by Thm. 2.5). Similarly for full coreflective subcategories.

One could define the future skeleton of X as the skeleton of the least future retract of X. Rather than developing this notion, we shall study a stronger one, called ‘future spectrum’, which will produce the same results and will be easier to determine, in the examples of Section 9.

The categories r and c have minimal future retracts, but do not have a least one (5.5, 5.6).

The ordered set of (replete) reflective subcategories of a category was investigated in [15] (see also its references). Such results are generally based on the existence of limits in the original category and cannot be applied here.

7.2. Spectra. Recall that we have defined, in the set of objects ObX, the equivalence relation x ∼^{+} x′ of future regularity, with equivalence classes [x]^{+} (6.1).

A future spectrum sp^{+}(X) of the category X will be a subset of objects such that:

(sp^{+}.1) sp^{+}(X) contains precisely one object, written sp^{+}(x), in every future regularity class [x]^{+}, (sp^{+}.2) for every x ∈ X there is precisely one morphism ηx: x → sp^{+}(x) in X,

(sp^{+}.3) every morphism a: x → sp^{+}(x′) factors as a = h.ηx, for a unique h: sp^{+}(x) → sp^{+}(x′).

The second condition can be equivalently written as: (sp^{+}.2′) for every x ∈ X, sp^{+}(x) is the terminal object of the full subcategory on [x]^{+}.

Also the full subcategory Sp^{+}(X) of X on this set of objects will be called the future spectrum. We shall prove that the future spectrum (when it exists) is the least future retract (7.3) and that it, as well as its embedding in the category, are determined up to a canonical isomorphism (7.5). Therefore, the future spectrum is more strictly determined than the ordinary skeleton.

Dually we have the past spectrum sp^{−}(X) and its full subcategory Sp^{−}(X).

The categories r and c, defined in 5.5, 5.6, have neither future nor past spectra. Indeed, all their maps are future regular, and all objects form a unique future regularity class, which has no terminal object; and dually their objects form a unique past regularity class, which has no initial object. It is also easy to see that a category has future spectrum 1 if and only if it is future equivalent to 1, if and only if it has a terminal object (2.6).

7.3. Theorem. [Properties of future spectra] Let F = Sp^{+}(X) be a future spectrum of the category X and i: F → X its inclusion.

(a) F is a future retract of X, with an essentially unique retraction p and unit η:

i: F ⇄ X:p,  η: 1_{X} → ip: X → X,  (94)

(b) F is the least future retract of X, with respect to essential inclusion (of full subcategories, 7.1). It is a skeletal category, whose only endomorphisms are the identities. The inclusion i: F → X preserves and reflects future regularity.

(c) Replacing some objects of sp^{+}(X) with isomorphic copies, the new subset is still a future spectrum of X.

(d) Every point of sp^{+}(X) is either maximal in X (1.5) or an effective future branching point (6.5).

Proof. (a) The inclusion i: Sp^{+}(X) → X has a left adjoint p: X → Sp^{+}(X), since (sp^{+}.3) says that ηx: x → sp^{+}(x) = ip(x) is a universal arrow from the object x to the functor i. Moreover, for x_{0} ∈ Sp^{+}(X), the counit εx_{0}: x_{0} = pi(x_{0}) → x_{0} is necessarily the identity, by (sp^{+}.2). It follows that ηi = 1 and pη = 1.

(b) Let (j, q; ζ): G → X be a future retract of X; we want to prove that Sp^{+}(X) is contained in the replete closure of G. Take an object x_{0} ∈ Sp^{+}(X); the unit ζx_{0}: x_{0} → jqx_{0} = x is future regular, whence sp^{+}(x) = x_{0} and the left composite below is the identity, by (sp^{+}.2):

ηx.ζx_{0}: x_{0} → x → x_{0},  e = ζx_{0}.ηx: x → x_{0} → x.  (95)

Now, for the right composite e, we have e.ζx_{0} = ζx_{0} = 1_{x}.ζx_{0}; since the unitcomponent ζx_{0}: x_{0} → jqx_{0} is a universal arrow from x_{0} to the full embedding j: G → X, it follows that e too is the identity.

Moreover, Sp^{+}(X) is skeletal by (sp^{+}.1) and has no endomorphisms, except the identities, by (sp^{+}.2). The last assertion follows from 6.3.

Finally, (c) is obvious. As to (d), if x_{0} ∈ sp^{+}(X) is not maximal for the path preorder in X, there is some arrow a: x_{0} → x with no arrows backwards; since x_{0} is terminal in its future regularity class, a is not future regular and x_{0} is a future branching point. Moreover, if a: x_{0} → x is future regular, then x ∼^{+} x_{0} and ηx.a = idx_{0}, whence a is a split mono.

7.4. Lemma. [Characterisation of future spectra] The following conditions on a functor i: F → X are equivalent:

(a) the functor i is an embedding and i(F) is a future spectrum of X;

(b) the category F has precisely one object in each future regularity class; the functor i is a future retract, i.e. it has a left adjoint p: X → F with pi = 1_{F} as counit; moreover the unit-component x → ip(x) is the unique X-morphism with these endpoints;

(c) the category F has precisely one object in each future regularity class and only one endomorphism for every object; the functor i can be extended to a future equivalence i: F ⇄ X:p, whose unit-component x → ip(x) is the unique X-morphism with these endpoints.

Note. The form (c) is appropriate to link future spectra with future equivalences, cf. 8.1.

Proof. Identifying F with Sp^{+}(x) and i with the inclusion, the fact that (a) implies (b) and (c) has already been proved in 7.3a. Then (c) implies (b): for every x_{0} ∈ F, x_{0} ∼^{+} pi(x_{0}) (by 6.3a) whence x_{0} = pi(x_{0}) and the unit-component x_{0} → pi(x_{0}) (of the future equivalence) is necessarily an identity. Finally, (b) implies (a): letting sp^{+}(x) = ip(x), the universal property of the unit of an adjunction gives (sp^{+}.3).

7.5. Lemma. [Uniqueness of future spectra, I] Let i: F → X and j: G → X be embeddings of future spectra of the category X.

(a) For every x_{0} ∈ F there is a unique u(x_{0}) in G such that i(x_{0}) ≅ ju(x_{0}) in X; and then, there is a unique morphism λx_{0}: i(x_{0}) → ju(x_{0}) in X; the latter is invertible.

(b) The mapping u: ObF → ObG so defined has a unique extension to a functor u: F → G making the family (λx_{0}) into an (invertible) natural transformation λ: i → ju: F → X.

Proof. Obvious. (A more complete uniqueness result will be given in 8.6.)

7.6. Spectral presentations. The spectral pf-presentation of X (cf. 4.2) will be a diagram where

[figure: ε: i^{−}p^{−} → 1_{X} (p^{−}i^{−} = 1, p^{−}ε = 1, εi^{−} = 1),; P; i^{−}; X; p^{+}; p^{−}; F; i^{+}; η: 1_{X} → i^{+}p^{+} (p^{+}i^{+} = 1, p^{+}η = 1, ηi^{+} = 1).]  (96)

(i) P is the past spectrum and F the future spectrum of X,

(ii) given x ∈ ObP and x′ ∈ ObF, if x ≅ x′ in X then x = x′ (linked choice).

Such a presentation exists if and only if X has a past spectrum and a future one, since the linked-choice condition can always be realised, replacing each object of P with its isomorphic copy in F, if any (7.3c). The set of objects produced by this linked choice will be called the pf-spectrum of X, or spectral model

sp(X) = ObP ∪ ObF = sp^{−}(X) ∪ sp^{+}(X).  (97)

The full subcategory Sp(X) on these objects will also be called the pf-spectrum of X. We prove below that it is well determined, in the same form of future spectra (7.5); and we shall prove that it is a strongly minimal injective model (8.4); it is not split, in general.

The projective model X → M associated to the spectral pf-presentation (as in 4.6) will be called the spectral projective model of X. We have already seen in the Introduction that it need not be a minimal projective model.

7.7. Theorem. [Uniqueness of pf-spectra] Two pf-spectra, i: E ⊂ X and j: E′ ⊂ X, are given.

(a) For every x_{0} ∈ E there is a unique u(x_{0}) in E′ such that i(x_{0}) ≅ ju(x_{0}) in X; and then there is a unique morphism λx_{0}: i(x_{0}) → ju(x_{0}) in X, which is invertible.

(b) The mapping u: ObE → ObE′ so defined has a unique extension to a functor u: E → E′ making the family (λx_{0}) into a natural transformation λ: i → ju : E → X, which is invertible (see the left diagram below)

[figure: E; i; u; λ; X; P; i^{−}; u^{−}; E; u; F; i^{+}; u^{+}; E′; j; X; P′; j^{−}; E′; F′; j^{+}]  (98)

(c) Let P, F be, respectively, the past and the future spectrum of X giving rise to E; and similarly P′, F′ for E′. Their embeddings and the functor u produce the commutative right diagram above, where u^{−} and u^{+} are the isomorphisms resulting from the uniqueness of these directed spectra of X (7.5).

Proof. (a) We already know (by 7.5a) that, if the point x_{0} belongs to P (resp. F), there is a unique u^{−}(x_{0}) in P′ (resp. u^{+}(x_{0}) in F′) such that x_{0} ≅ u^{α}(x_{0}) in X (α = ±); moreover, if x_{0} is in P ∩F, then u^{−}(x_{0}) ≅ x_{0} ≅ u^{+}(x_{0}), whence u^{−}(x_{0}) = u^{+}(x_{0}), because of the linked-choice condition in E′. We have thus a unique object u(x_{0}) consistent with the right diagram above.

We also have (again by 7.5a) a unique map λx_{0}: i(x_{0}) → ju(x_{0}) in X, which is an isomorphism. The points (b) and (c) follow now easily.

8. Spectra and pf-equivalence of categories

Pf-spectra are shown to be strongly minimal injective models (8.4) and to classify injective equivalence, in a strict sense (8.3).

8.1. Theorem. [Preservation of future spectra] If f: X ⇄ Y :g is a future equivalence and i: F → X is the embedding of a future spectrum, then fi: F → Y is also.

Proof. The units of the future equivalence will be written as φ: 1 → gf and ψ: 1 → fg.

Let us use the characterisation 7.4c of embeddings of future spectra, taking into account the fact that future equivalences compose (2.3). Let p: X → F be the retraction and η: 1 → ip the unit of F (7.3a). We know that F has one object in each future regularity class and only one endomorphism for every object. It remains to show that, for every y ∈ Y, the composed unit η′y = fηgy.ψy: y → fipgy is the unique morphism between these points.

Let x = ipgy ∈ i(F) and note that the composite ηgfx.φx: x → gfx = ipgfx is the identity, because x and ipgfx are equivalent up to future regularity, in i(F). Take now any map b: y → fx in Y; by naturality of ψ we have a commutative (solid) diagram

\xymatrix{y \ar[r]^{ψy} \ar[d]_{b} & fgy \ar[d]_{fgb} \ar@{-->}[dr]^{fηgy} \\ fx \ar[r]_{ψfx} & fgfx \ar[r]_{fηgfx} & fx}  (99)

where the lower row is the identity, because of the previous remark and because ψfx = fφx. Also the right triangle commutes, since ηgfx.gb: gy → x must coincide with ηgy: gy → ipgy = x. Finally, we have the thesis: b = fηgy.ψy.

8.2. Theorem. [Preservation of pf-spectra] A pf-embedding preserves and reflects pf-spectra. More precisely, assuming that the category X has a pf-spectrum i: E ⊂ X, we have the following results (writing E_{0} = ObE).

(a) Given a pf-embedding u: X → Y, u(E_{0}) is the pf-spectrum of Y.

(b) Given a pf-embedding v: Y → X, v^{−1}(E_{0}) is the pf-spectrum of Y, Proof. (a) Follows from 8.1.

(b) Y is past and future equivalent to X, whence it also has a past and a future spectrum, and therefore a pf-spectrum H_{0}, preserved by the pf-embedding Y → X. Since the pf-spectrum of X is determined up to isomorphism, v(H_{0}) coincides with E_{0}, up to isomorphic copies of objects. Since v is a full embedding, it follows that v^{−1}(E_{0}) coincides with H_{0} (up to isomorphic copies of objects), and is a pf-spectrum of Y as well.

8.3. Corollary. If the category X has a pf-spectrum E, then it is injectively equivalent to a category Y if and only if E is also a pf-spectrum of Y.

Proof. It is a straightforward consequence of the previous theorem.

8.4. Theorem. [Spectra and injective models] Given a pf-presentation of the category X, let E be the associated injective model (Thm. 4.3). Then, with the same notation of 4.3,

(a) the pf-presentation of X is spectral if and only if the same holds for E;

(b) in this case, E = Sp(X) is a strongly minimal injective model of X.

Proof. (a) Follows immediately from 8.2.

(b) Assume that the given pf-presentation is spectral, and let us show that E is a strongly minimal injective model of X. Given a category Y injectively equivalent to X, we know (8.3) that E is an injective model of Y. Secondly, given an injective model v: E′ → E, we have to prove that v is surjective on objects, hence an isomorphism. Indeed, we have the composite pf-embedding E′ → X, whence v must reach a isomorphic copy of every object of P and F; one concludes with the linked-choice condition.

8.5. Comments. Given a pf-presentation of the category X, and reconsidering the previous construction (in 8.4), one can note that:

[figure: P; i^{−}; X; p^{+}; p^{−}; r^{−}; r^{+}; F; i^{+}; P; j^{−}; E; q^{+}; q^{−}; F; j^{+}]  (100)

(a) composing the future equivalences F ⇄ X ⇄ E, one gets j^{+}: F ⇄ E:q^{+},

(b) composing the future equivalences F ⇄ E ⇄ X, one gets i^{+}: F ⇄ X:p^{+}, and symmetrically on the left-hand side.

On the other hand, the future equivalence u: E ⇄ X:r^{+} is not the composition of the future equivalences E ⇄ F ⇄ X (in general): the image of i^{+}q^{+}: E → X is ‘just’ F, instead of E.

We end this section with a second statement on the uniqueness of future spectra. It is more complete than the first (Lemma 7.5), being based on the whole structure of a future spectrum as a future retract; yet, it seems to be less useful than the first.

8.6. Theorem. [Uniqueness of future spectra, II] Two future spectra of the category X are given, as future retracts:

i: F ⇄ X:p,  j: G ⇄ X:q  (η: 1_{X} → ip, η′: 1_{X} → jq).  (101)

(a) We have: qip = q and qη = 1q; dually, pjq = p and pη′ = 1_{p}.

(b) There is a unique functor u: F → G such that up = q, namely u = qi, and it is an isomorphism.

(c) There is a unique natural transformation λ: i → ju: F → X, namely λ = η′i, and it is invertible.

[figure: X; p; F; i; u; λ; X; X; q; G; j; X]  (102)

Proof. (a) To prove that qip = q, let us begin noting that this is true on every object x ∈ X, because ip(x) ∼^{+} x (by 6.3a) and qip(x) = q(x). Now, the natural transformation qη: q → qip has general component qη(x): qx → qipx = qx; but there is a unique map from qx to itself, in the future spectrum G, namely the identity of qx. It follows that qip = q is also true on maps, and qη = 1_{q}.

(b) Uniqueness is plain: up = q implies u = qi. Existence follows from (a): taking u = qi: F → G, we have up = qip = q. Symmetrically, there is a unique functor v: G → F such that vq = p; and then u and v are inverses.

(c) We do have a natural transformation λ = η′i: i → jqi = ju. Its component λ(x_{0}): i(x_{0}) → jqi(x_{0}) is the unique X-morphism between such objects (because they are future regular equivalent and the second is in G). But there is also a unique X-morphism backwards jqi(x_{0}) → i(x_{0}), because i(x_{0}) is in F; and their composites must be identities.

9. A gallery of spectra and models

After considering pf-spectra of preorders (9.1), we will construct the pf-spectrum of the fundamental category of various ordered topological spaces; a preordered space is dealt with in 9.5. All these pf-spectra yield faithful injective models, except in 9.8. We end with a few hints to applications (9.9). Speaking of branching points, the term ‘effective’ (defined in 6.5) will generally be understood, unless we want to stress this fact.

9.1. Future spectra of preorders. Let C be a preorder category. All morphisms are O^{+}-regular (6.1), so that future regularity coincides with V^{+}-regularity and is always faithful. Explicitly, the ‘arrow’ x ≺ x′ is future regular in C if, whenever x ≺ x′′ there exists some upper bound \overline{x} (x′ ≺ \overline{x} and x′′ ≺ \overline{x}).

In this case, the existence (and choice) of a future spectrum sp^{+}(C) (which is necessarily faithful) amounts to these conditions:

(i) each future regularity class of objects [x]^{+} has a maximum (determined up to ≃), and we choose one, called max[x]^{+} (if C is ordered, the choice is determined),

(ii) if x ≺ x′ in C, then max[x]^{+} ≺ max[x′]^{+}.

Every finite tree C has a spectrum. Indeed, C is past contractible, its root as past spectrum: P = {0}; its future spectrum F can be obtained omitting any point which has precisely one immediate successor. In the example below (ordered rightward), the points of the future spectrum are marked with a bigger bullet; the spectral injective model E = P ∪ F is shown at the right

[figure: C; E; 0; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]  (103)

The associated projective model, the full subcategory E′ ⊂ E^{2} on the objects 0 < y (y ∈ F), is isomorphic to F (and not isomorphic to E, unless P ⊂ F).

9.2. Modelling an ordered space. Directed homotopy for preordered topological spaces has been recalled in Section 1. In the sequel, we will generally consider ordered topological spaces X with minimum (0) and maximum (1) and study the pf-spectrum of the fundamental category C = ↑Π_{1}(X). The latter inherits a privileged ‘starting point’ 0 (a minimal point, but possibly not the unique one, cf. 9.6) and a privileged ‘ending point’ 1 (which is maximal in C). Furthermore, recall that C is skeletal (when X is ordered), so that the future spectrum—if it exists—is the least full (i.e. replete) reflective subcategory of C, strictly determined as a subset of C. Objects of C (i.e., points of X) will be denoted by letters x, a, b, c...; arrows of C (i.e. ‘homotopy classes’ of paths of X) by Greek letters α, β, γ …

Consider, in the category pTop, the (compact) ordered space X: a subspace of the standard ordered square ↑[0, 1]^{2} obtained by taking out two open squares (marked with a cross), as in the left figure below

[figure: X; E; M; Z; ×; ×; ×; ×; ×; ×; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; 0; c′; a′; a; c; 1; b′; b; 0; 1]  (104)

The fundamental category C = ↑Π_{1}(X) is easy to determine (see 1.1). We shall prove that its pf-spectrum is the full subcategory E, on eight vertices (where the two cells marked with a cross do not commute, while the central one does), while the associated projective model is M and the category Z is just a coarse model (of all three).

First, we show that the category C = ↑Π_{1}(X) has a past spectrum

[figure: P; F; ×; ×; ×; ×; •; •; •; •; •; •; •; •; 0; a; c; b; c′; a′; b′; 1]  (105)

In fact, there are four past-regularity classes of objects, each having an initial object:

[c]^{−} = {x | x ≥ c}  (unmarked),
[a]^{−} = {x | x ≥ a} \ [c]^{−},  (marked with dots),
[b]^{−} = {x | x ≥ b} \ [c]^{−}  (marked with dots),
[0]^{−} = X \ ([c]^{−} ∪ [a]^{−} ∪ [b]^{−})  (unmarked),

(106)

where a, b, c are effective V^{−}-branching points and 0 is the global minimum, weakly initial in C.

These four points form the past spectrum sp^{−}(C) = {0, a, b, c}, as is easily verified with the characterisation 7.4b: take the full subcategory P ⊂ C on these objects (represented in the same picture), its embedding i^{−}: P ⊂ C and the projection p^{−} sending each point x ∈ C to the minimum of its past regularity class. Now i^{−} ⊣ p^{−}, with a counit-component ε(x): i^{−}p^{−}(x) → x which is uniquely determined in ↑Π_{1}(X), since—within each of the four zones described above—there is at most one homotopy class of paths between two given points.

Symmetrically, we have the future spectrum: the full subcategory F ⊂ C in the right figure above, on the following four objects (each of them a maximum in its future regularity class):

- 1 (the global maximum, weakly terminal); a′, b′, c′ (V^{+}-branching points).

The projection p^{+} (left adjoint to i^{+}: F ⊂ C) sends each point x ∈ C to the maximum of its future regularity class (i.e. the lowest distinguished vertex p^{+}(x) ≥ x); the unitcomponent η(x): x → i^{+}p^{+}(x) is, again, uniquely determined in ↑Π_{1}(X).

Globally, we have constructed a spectral pf-presentation of C (7.6); this generates the skeletal injective model E, as the full subcategory of C on sp(C) = {0, a, b, c, a′, b′, c′, 1}. The full subcategory Z ⊂ E on the objects 0, 1 is isomorphic to the past spectrum of F, as well as to the future spectrum of P, hence coarse equivalent (2.3) to C and E.

Comments. The pf-spectrum E provides a category with the same past and future behaviour as C. This can be read as follows:

(a) the action begins at the ‘starting point’ 0, the minimum, from where we can only move to c′;

(b) c′ is an (effective) V^{+}-branching point, where we choose: either the upper/middle way or the lower/middle one;

(c) the first choice leads to a′, a further V^{+}-branching point where we choose between the upper or the middle way; similarly, the second choice leads to the V^{+}-branching point b′, where we choose between the lower or the middle way (the same as before);

(d) the first bifurcation considered in (c) is reunited at a, the second at b (V^{−}-branching points);

(e) the resulting ‘paths’ come together at c (the last V^{−}-branching point);

(f) from where we can only move to the ‘ending point’ 1, the maximum.

The ‘coarse model’ Z only says that in C there are three homotopically distinct ways of going from 0 to 1, and looses relevant information on the branching structure of C. The projective model is studied below.

9.3. The projective model. For the same category C = ↑Π_{1}(X), the spectral projective model M, represented in the right figure below, is the full subcategory of C^{2} on the 9 arrows displayed in the left figure

[figure: M; α; β; γ; γ′; δ; δ′; σ′; σ; σ′′; α; β; γ; γ′; δ; δ′; σ′′; σ; σ′; α; γ; σ′; γ′; σ; δ; σ′′; δ′; β; ×; ×; ×; ×; ×; ×] (107)

The projection f(x) = (p^{−}x, p^{+}x; p^{−}ηx) (74), from X = ObC to ObM ⊂ MorC, has thus nine equivalence classes, analytically defined below, in (108), and ‘sketched’ in the middle figure above (the solid lines are meant to suggest that a certain boundary segment belongs to a certain region, as made precise below); in each of these regions, the morphism f(x) is constant, and equal to α, β, …

f^{−1}(α) = [0, 1/5]^{2},  f^{−1}(β) = [4/5, 1]^{2}  (closed in X),
f^{−1}(γ) =]1/5, 3/5]×[0, 1/5],  f^{−1}(γ′) = [0, 1/5]×]1/5, 3/5],
f^{−1}(δ) = [4/5, 1]×[2/5, 4/5[,  f^{−1}(δ′) = [2/5, 4/5[×[4/5, 1],
f^{−1}(σ) = X∩]1/5, 4/5[^{2}  (open in X),
f^{−1}(σ′) = X ∩ (]3/5, 1]×[0, 2/5[)  (open in X),
f^{−1}(σ′′) = X ∩ ([0, 2/5[×]3/5, 1])  (open in X).

(108)

The interpretation of the projective model M is practically the same as above, in 9.2, with some differences:

(i) in M there is no distinction between the starting point and the first future branching, as well as between the ending point and the last past branching;

(ii) the different paths produced by the obstructions are ‘distinguished’ in M by three new intermediate objects: σ, σ′, σ′′.

Note also that—here and in many cases—one can also embed M in C, by choosing a suitable point of a suitable path in each homotopy class α, β, …; but there is no canonical way of doing so. In order to compare the injective model E and the projective model M, the examples below will make clear that distinguishing 0 from c′ (or c from 1) carries some information (like distinguishing the initial from the terminal object, in the injective model 2 of a non-pointed category having both, cf. 5.4). According to applications, one may decide whether this information is useful or redundant.

9.4. Variations. (a) Consider the previous ordered space X (9.2) together with the spaces X′ and X′′, obtained by taking out, from the ordered square ↑[0, 1]^{2}, two open squares placed in different positions, ‘at’ the boundary

X  X_{′}  X_{′′} ×  ×  ×  ×  ×  ×  (109)

[figure: E; E′; E′′; ×; ×; ×; ×; ×; ×; ×; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; 0; c′; c; 1; 0; c; 1; 0; 1]  (110)

The pf-spectra E, E′ and E′′ distinguish these situations: in the second case the starting point 0 is an effective future branching point, and we must make a choice from the very beginning (either the upper/middle way or the middle/lower one); in the last case, this remains true and moreover the ending point is an effective past branching point. The projective models of these three spectra coincide (with the category M of 9.3).

(b) The following examples show similar situations, with a different injective (and projective) model. We start again from a (compact) ordered space X_{i} ⊂ ↑[0, 1]^{2}, obtained by taking out two open squares

[figure: X_{1}; P_{1}; E_{1}; Z_{1}; ×; ×; ×; ×; ×; ×; •; •; •; •; •; •; •; •; •; •; 0; a; b; 0; a′; a; b′; b; 1; 0; 1]  (111)

[figure: X_{2}; P_{2}; E_{2}; Z_{2}; ×; ×; ×; ×; ×; ×; •; •; •; •; •; •; •; •; •; 0; a; b; 0; a′; a; b′; b; 1; 0; 1] (112)

In both cases, the past spectrum of the fundamental category C_{i} = ↑Π_{1}(X_{i}) is the full subcategory P_{i} on three objects: 0 (the minimum), a, b (V^{−}-branching points), as shown above. The future spectrum is symmetric. The pf-spectrum, generated by the previous presentation, is the full subcategory E_{i} on the pf-spectrum sp(C_{i}) = {0, a, b, a′, b′, 1}. Coarse models of C_{i} are given by the categories Z_{i} generated by the graphs above; in particular, Z_{1} has four arrows from 0 to 1.

In the second case, E_{2} is better represented ‘abstractly’, to avoid the partial superposition of paths in the former embedding; the central cell commutes

\xymatrix{ & b′ \ar[rr] \ar[rr] & × & b \ar[r] & 1 \\ 0 \ar[r] & a′ \ar[u] \ar[rr] \ar[rr] & × & a \ar[u] &  & E_{2}}  (113)

9.5. A preordered space. The compact space X ⊂ [0, 1]^{2} represented below is now equipped with the preorder: (x, y) ≺ (x′, y′) if y ≤ y′. All points having the same vertical coordinate are equivalent (and the topological spaces considered in (104), (111), with this preorder, would give the same results.)

The fundamental category C = ↑Π_{1}(X) is no longer skeletal. Let us choose m = (1/2, 0) as a minimum of X (weakly initial in C) and m′ = (1/2, 1) as a maximum

[figure: X; P; E; Z; ×; ×; ×; ×; ×; ×; •; •; •; •; •; •; •; •; •; •; m; a; b; m; m′; 0; 1] (114)

Now, the past spectrum of the fundamental category C = ↑Π_{1}(X) is the full subcategory P ⊂ C on three objects: m (a minimum), a = (1/2, 2/5), b = (1/2, 4/5) (V^{−}- branching points), as in the central figure above; of course, all of them can be equivalently moved, horizontally. The future spectrum is symmetric: a′ = (1/2, 1/5), b′ = (1/2, 3/5) and m′. The pf-spectrum is the full subcategory E on these six points (or any equivalent sextuple). It is isomorphic to the pf-spectrum E_{1} of (111).

9.6. The Swiss flag. Let us come back to ordered spaces. The following situation is often analysed as a basic one, in concurrency: the ‘Swiss flag’ X ⊂ ↑[0, 1]^{2}. See [4, 5, 6, 7] for a description of ‘the conflict of resources’ which it depicts, and [5], p. 84, for an analysis of the fundamental category which leads to a ‘category of components’ similar to the projective model we get here

[figure: X; E; Z; ×; •; •; •; •; •; •; •; •; •; •; 0; a; d; d′; b′; a′; c′; b; c; 1; 0; 1]  (115)

Proceeding as above, the fundamental category C = ↑Π_{1}(X) has an injective model E and a coarse model Z. Now, the past spectrum is the full subcategory P ⊂ C represented below

[figure: P; F; ×; ×; •; •; •; •; •; •; •; •; •; •; •; 0; a′; c′; b; c; 1; 0; a; d; d′; b′; 1]  (116)

The past spectrum sp^{−}(C) = {0, a′, a, b, c, c′} contains two minimal points 0, a′ (note that the starting point 0 is not a minimum for ≺) and three V^{−}-branching points (b, c, c′). Similarly, the future spectrum is the full subcategory F ⊂ C in the right figure above, on the future spectrum sp^{+}(C) = {a, d, d′, b′, 1}. The pf-spectrum of C is the full subcategory category E on sp(C) = sp^{−}(C) ∪ sp^{+}(C).

The spectral projective model M is shown below, under the same conventions as in

[figure: ×; ×; ×; σ′; σ′′; σ′; σ′′; α; γ; σ′′; γ′; μ; ν; δ; σ′; δ′; β]  (117)

9.7. A three dimensional case. Consider now the ordered compact space X ⊂ ↑[0, 1]^{3} represented below (the complement of ]1/3, 2/3[^{2}×]2/3, 1])

[figure: X; E; 0; b; a; 1; •; •; •; •; 0; a; b; 1; h; h′; u; v; (uh = vh = h′)]  (118)

Then C = ↑Π_{1}(X) is past contractible (0 is the initial object and past spectrum); it has future retract F formed of three points: 1 (the maximum, weakly terminal), a (an O^{+}-branching point), b (V^{+}-branching). The associated injective model (4.3) is the category E, embedded as the full subcategory on the objects 0, a, b, 1.

9.8. Faithful and non faithful spectra. The situation is very different for the ordered compact space X ⊂ ↑[0, 1]^{3} of the figure below (taking out an open cube in central position)

[figure: X; 0; a; a′; b; b′; 1; •; •; •; •; •; •; X = ↑[0, 1]^{3} \ A; A = ]1/3, 2/3[^{3}.]  (119)

The fundamental category C = ↑Π_{1}(X) has an initial and a terminal object, 0 and 1. Therefore, C has pf-spectrum 2 (5.4), which is not faithful: indeed, C is not a preorder, since C(x, y) has two arrows for

x < y,  a < x < a′,  b < y < b′,  x_{3}, y_{3} ∈ ]1/3, 2/3[.  (120)

Similar examples can be obtained by permutation of the coordinates.

Faithful directed equivalence should allow for a finer analysis; yet it does not seem simple to build a faithful injective or projective model: it seems reasonable that this should be at least countable, like the minimal injective model of the ordered line (5.5).

9.9. Some hints to applications. Applications of Directed Algebraic Topology to concurrency are well developed; the interested reader can begin from the references cited in the Introduction and see how the examples above can be interpreted in this domain. Here we want to hint to other possibilities, like the analysis of directed images, traffic networks and space-time models.

Consider the subspace X ⊂ R × [−1, 1] obtained by taking out two open squares (marked with a cross). It is equipped with the order relation (122)

[figure: X; p; v′; v′′; v; ×; ×; •; •; •; •; •; •; •; •; a_{1}; a; b; c; d; d_{1}; d_{2}; …; …]  (121)

(x, y) ≤ (x′, y′) ⇔ |y′ − y| ≤ x′ − x,  (122)

whose ‘cone of the future’ at a point p is shown above.

First, this ordered spaces can be viewed as representing a stream with two islands; the stream moves rightward, with velocity v. The order relation expresses the fact that the observer can move, with respect to the stream, with an upper bound for scalar velocity (namely |v′| ≤ |v|.2^{−1/2}), so that the composed velocity v′′ can at most form an angle of 45^{∘} with the direction of the stream, as shown above, at the right.

Secondly, one can view the horizontal coordinate as time, the vertical one as position in a 1-dimensional physical medium and the order as the possibility of going from (x, y) to (x′, y′) with velocity ≤ 1 (with respect to a ‘rest frame’, linked with the medium). The two forbidden squares are now linear obstacles in the medium, with a limited duration in time (first expanding and then contracting).

The fundamental category ↑Π_{1}(X) reveals obstructions (islands, temporary obstacles...). A minimal injective model E of the fundamental category is given by the full subcategory on the points marked above, in (121). E is generated by the following countable graph (under no conditions)

\xymatrix{… a_{2} \ar[r] & a_{1} \ar[r] & a \ar[r] \ar[r] & b \ar[r] & c \ar[r] \ar[r] & d \ar[r] & d_{1} \ar[r] & d_{2} …}  (123)

The analysis is similar to the one of (111). Moving the obstructions, one can get results similar to other previous cases (9.2, etc.); the fundamental category will detect whether these obstructions occur one after the other (as above) or ‘sensibly’ at the same time (as in 9.2).

Finally, the present analysis of a category through minimal past and future models has unexpectedly appeared to be related with notions recently introduced by A.C. Ehresmann [3], for investigating biosystems, neural systems, etc.—the ’root’ and ’coroot’ of a category. Such relations, having likely at their basis a common purpose of studying non-reversible phenomena, will be examined in a sequel.

References

[1] A. Bauer, L. Birkedal and D.S. Scott, Equilogical spaces, Theoretical Computer Science 315, (2004), 35–59.

[2] F. Borceux and M. Korostenski, Open localizations, J. Pure Appl. Algebra 74, (1991), 229–238.

[3] A.C. Ehresmann, Localization of universal problems. Local colimits, Appl. Categ. Structures 10, (2002), 157–172.

[4] L. Fajstrup, E. Goubault and M. Raussen, Algebraic topology and concurrency, Preprint 1999.

[5] L. Fajstrup, M. Raussen, E. Goubault and E. Haucourt, Components of the fundamental category, Appl. Categ. Structures 12, (2004), 81–108.

[6] P. Gaucher and E. Goubault, Topological deformation of higher dimensional automata, Preprint 2001.

   http://arXiv.org/abs/math.AT/0107060

[7] E. Goubault, Geometry and concurrency: a user’s guide, in: Geometry and concurrency, Math. Structures Comput. Sci. 10, (2000), no. 4, pp. 411–425.

[8] M. Grandis, Cubical homotopical algebra and cochain algebras, Ann. Mat. Pura Appl. 170, (1996) 147–186.

[9] M. Grandis, Higher fundamental functors for simplicial sets, Cah. Topol. Géom. Différ. Catég. 42, (2001), 101–136.

[10] M. Grandis, Directed homotopy theory, I. The fundamental category, Cah. Topol. Géom. Différ. Catég. 44, (2003), 281–316.

[11] M. Grandis, Directed combinatorial homology and noncommutative tori (The breaking of symmetries in algebraic topology), Math. Proc. Cambridge Philos. Soc., to appear. [Dip. Mat. Univ. Genova, Preprint 480 (2003).] [12] M. Grandis, Inequilogical spaces, directed homology and noncommutative geometry,

Homology Homotopy Appl. 6, (2004), 413–437.

   http://www.rmi.acnet.ge/hha/volumes/2004/n1a21/v6n1a21.pdf

[13] M. Grandis and R. Paré, Adjoints for double categories, Cah. Topol. Géom. Diff. Catég. 45, (2004), 193–240.

[14] G. Janelidze and W. Tholen, Functorial factorization, well–pointedness and separability, J. Pure Appl. Algebra 142, (1999), 99–130.

[15] G.M. Kelly, On the ordered set of reflective subcategories, Bull. Austral. Math. Soc. 36, (1987), 137–152.

[16] G.M. Kelly and F. W. Lawvere, On the complete lattice of essential localizations, Actes du Colloque en l’Honneur du Soixantième Anniversaire de R. Lavendhomme (Louvain–la-Neuve, 1989). Bull. Soc. Math. Belg. Sér. A 41, (1989), 289–319.

[17] F.W. Lawvere, Unity and identity of opposites in calculus and physics, The European Colloquium of Category Theory (Tours, 1994), Appl. Categ. Structures 4, (1996), 167– 174.

[18] S. Mac Lane, Categories for the working mathematician, Springer, Berlin 1971.

[19] G. Rosolini, Equilogical spaces and filter spaces, Categorical studies in Italy (Perugia, 1997). Rend. Circ. Mat. Palermo (2) Suppl. No. 64, (2000), 157–175.

[20] D. Scott, A new category? Domains, spaces and equivalence relations, Unpublished manuscript (1996).

   http://www.cs.cmu.edu/Groups/LTC/

Dipartimento di Matematica Università di Genova Via Dodecaneso 35 16146-Genova, Italy

Email: grandis@dima.unige.it

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/15/4/15-04.{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, Postscript and PDF. Details will be e-mailed to new subscribers. 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.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX 2ε 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 http://www.tac.mta.ca/tac/. You may also write to tac@mta.ca to receive details by e-mail.

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

TEXnical editor. Michael Barr, McGill University: mbarr@barrs.org

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@mathstat.uottawa.ca 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: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com

Ezra Getzler, Northwestern University: getzler(at)math(dot)northwestern(dot)edu

Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au 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.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 Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@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 Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca