Theory and Applications of Categories, Vol. 11, No. 7, 2003, pp. 148–184.

RESOLUTIONS BY POLYGRAPHS

FRANÇOIS MÉTAYER

ABSTRACT. A notion of resolution for higher-dimensional categories is defined, by using polygraphs, and basic invariance theorems are proved.

1. Introduction

Higher-dimensional categories naturally appear in the study of various rewriting systems. A very simple example is the presentation of Z/2Z by a generator a and the relation aa → 1. These data build a 2-category X :

\xymatrix{X_{0} & X_{1} \ar[l]^{t_{0}} \ar[l]_{s_{0}} & X_{2} \ar[l]^{t_{1}} \ar[l]_{s_{1}}}

where X_{0} = {•} has a unique 0-cell, X_{1} = {a^{n}/n ≥ 0} and X_{2} consists of 2-cells a^{n} → a^{p}, corresponding to different ways of rewriting a^{n} to a^{p} by repetitions of aa → 1, up to suitable identifications. 1-cells compose according to a^{n} ∗_{0} a^{p} = a^{n+p}, and 2-cells compose vertically, as well as horizontally, as shown on Figure 1, whence the 2-categorical structure on X.

[figure: •; a^{n}; a^{p}; a^{q}; •; •; a^{n}; a^{p}; •; a^{q}; a^{r}; •]

Figure 1: composition of 2-cells

In this setting, we recover the original monoidal structure of Z/2Z by collapsing the 2-cells (see [4]) to identities. Likewise, tree-rewriting systems could be expressed in the framework of 3-categories. Thus we start from the fact that many structures of interest are in fact n-categories, while computations in these structures take place in (n+1)-categories.

On the other hand, if a monoid can be presented by a finite, noetherian and confluent rewriting system, then its homology groups are finitely generated, as proved by Squier and others (see [15, 1, 11, 13]). Precisely, it is shown how to build a free resolution of Z by ZM-modules by using a complete (i.e. finite, noetherian and confluent) presentation (Σ, R) of the monoid M. Subsequently, the notion of derivation type was introduced: roughly speaking, one asks if the equivalence between rewriting paths with the same source and target can be generated by a finite number of basic deformations. It turns out that this property is independent of the (finite) presentation chosen, and that it implies homological finiteness in dimension 3 (see [16, 12, 8]).

Received by the editors 2002-3-28 and, in revised form, 2003-5-1.

Transmitted by John Baez. Published on 2003-5-9.

2000 Mathematics Subject Classification: 18D05.

Key words and phrases: n-category, polygraph, resolution, homotopy, homology.

\begin{matrix}c \\ ◯ \end{matrix} François Métayer, 2003. Permission to copy for private use granted.

As regards ∞-categories, homology can be defined through simplicial nerves (see [17, 6]). However, this does not lead to easy computations. What we would like to do is to extract structural invariants from particular presentations. The present work is a first step in this vast program: by using Burroni’s idea of polygraph, we propose a definition of resolution for ∞-categories, which can be seen as a non-commutative analogue of a free resolution in homological algebra. These new resolutions generalize in arbitrary dimensions the constructions which already appear in the study of derivation types.

The main result (Theorem 5.1) establishes a strong equivalence between any two resolutions of the same category, and yields homological invariance as a consequence (Theorem 6.1).

All the material we present here was elaborated in collaboration with Albert Burroni, whose companion paper [5] will be released very soon.

2. Graphs and Categories

2.1. Basic definitions. Polygraphs have been defined by Burroni in [4]. Let us briefly recall the main steps of his construction: a graph X is given by a diagram

\xymatrix{X_{0} & X_{1} \ar[l]^{t_{0}} \ar[l]_{s_{0}}}

X_{0} is the set of vertices–or 0-cells–X_{1} the set of oriented edges–or 1-cells–and the applications s_{0}, t_{0} are respectively the source and target. We usually denote x^{1} : x^{0} → y^{0} in case the 1-cell x^{1} has source x^{0} and target y^{0}. More generally, an n-graph, also known as globular set will be defined by a diagram

[figure: X_{0}; X_{1}; t_{0}; s_{0}; t_{1}; s_{1}; …; X_{n}; t_{n−1}; s_{n−1}]  (1)

with relations

s_{i}s_{i+1} = s_{i}t_{i+1} t_{i}s_{i+1} = t_{i}t_{i+1}

Figure 2 conveys the geometric meaning of these equations.

If diagram (1) is not bounded on the right, we get an ∞-graph. Elements of X_{i} are called i-cells and will be denoted by x^{i}. By

x^{i+1} : x_{0}^{i} → x_{1}^{i}

[figure: ssx; sx; tx; x; ttx]

Figure 2: cell

we mean that x^{i+1} has i-dimensional source x_{0}^{i} and target x_{1}^{i}.

For i ≥ 1, two i-cells x^{i} and y^{i} are called parallel if they have the same source and the same target. This is denoted by x^{i} ∥ y^{i}. Also any two 0-cells are considered to be parallel.

A morphism ϕ : X → Y between n-graphs X and Y is a family of maps ϕ_{i} : X_{i} → Y_{i} commuting with source and target:

\xymatrix{X_{i} \ar[d]_{ϕ_{i}} & X_{i+1} \ar[l]^{t_{i}} \ar[l]_{s_{i}} \ar[d]^{ϕ_{i+1}} \\ Y_{i} & Y_{i+1} \ar[l]^{t_{i}} \ar[l]_{s_{i}}}

Warning: for simplicity, in all diagrams, double arrows will stand for source and target maps, except otherwise mentioned. Throughout this paper, the “commutativity” of a diagram containing such arrows means in fact the separate commutativity of two diagrams, obtained by keeping either all source maps or all target maps.

The category of n-graphs (∞-graphs) will be denoted by Grph_{n} (Grph_{∞}). Let X be an ∞-graph, and 0 ≤ i < j, put

s_{ij} = s_{i}s_{i+1} … s_{j−1}
t_{ij} = t_{i}t_{i+1} … t_{j−1}

thus defining a new graph X_{ij} for each pair i < j:

\xymatrix{X_{i} & X_{j} \ar[l]^{t_{ij}} \ar[l]_{s_{ij}}}

The following data determine a structure of ∞-category on X:

• For all x^{j}, y^{j} in X_{j} such that s_{ij}y^{j} = t_{ij}x^{j} a composition x^{j} ∗_{i} y^{j} ∈ X_{j}:

\xymatrix{x^{j} ∗_{i} y^{j} : & x^{i} \ar[r]^{x^{j}} & y^{i} \ar[r]^{y^{j}} & z^{i}}

We write composition in the order of the arrows, for no reason but personal convenience. For simplicity, the index j does not appear on the symbol ∗_{i}.

[figure: •; x^{k}; y^{k}; •; u^{k}; v^{k}; •]

Figure 3: exchange

• For each x^{i} ∈ X_{i}, a cell id^{j}(x^{i}) ∈ X_{j}, the j-dimensional identity on x^{i}.

• The compositions and identities just defined make each X_{ij} a category.

• The X_{ij}’s are compatible, precisely, for each 0 < i < j < k, x^{k}, y^{k}, u^{k} and v^{k}

(x^{k} ∗_{j} y^{k}) ∗_{i} (u^{k} ∗_{j} v^{k}) = (x^{k} ∗_{i} u^{k}) ∗_{j} (y^{k} ∗_{i} v^{k})  (2)

provided the first member exists: this is the exchange rule (see Figure 3).

Also for all x^{i},

id^{k}(x^{i}) = id^{k}(id^{j}(x^{i}))  (3)

Finally, for all i < j < k and i composable j-cells x^{j}, y^{j},

id^{k}(x^{j} ∗_{i} y^{j}) = id^{k}(x^{j}) ∗_{i} id^{k}(y^{j})  (4)

These properties allow the following notations:

• For each j-cell x^{j}, and i < j, s_{ij}x^{j} = x_{0}^{i} and t_{ij}x^{j} = x_{1}^{i}.

• In expressions like x^{i} ∗_{l} y^{j} (i < j), x^{i} means in fact id^{j}(x^{i}). Let i < j and y^{j} = id^{j}(x^{i}), and e ∈ {0, 1}. With the previous notations:

y_{e}^{k} = id^{k}(x^{i}) (i < k < j)
= x^{i} (k = i)
= x_{e}^{k}  (0 ≤ k < i)

The morphisms between ∞-categories are the morphisms of underlying ∞-graphs which preserve the additional structure. Now ∞-categories and morphisms build a category Cat_{∞}. By restricting the construction to dimensions ≤ n we obtain n-categories, and the corresponding Cat_{n}. For each ∞-category X, we denote by X^{n} the n-category obtained by restriction to cells of dimension ≤ n.

2.2. Alternative notations. Explicit labels for dimensions make our formulas difficult to read. Hence the need for an alternative notation: let X be an ∞-category, the source and target maps from X_{i+1} to X_{i} will be denoted in each dimension by d_{−} and d_{+} respectively. If j = i + k, s_{ij} and t_{ij} from X_{j} to X_{i} will be denoted by d_{−}^{k} and d_{+}^{k}, the exponent means here iteration, not dimension.

Likewise, the identity id^{i+1} from X_{i+1} to X_{i} will be denoted by I in each dimension, and if j = i + k, id^{j} : X_{i} → X_{j} becomes I^{k}. Here again the exponent denotes iteration. Both families of notations will be used freely throughout the paper, sometimes together.

2.3. Example. An important example is the ∞-category BA associated to a complex A of abelian groups (see [3], [6]).

\xymatrix{A_{0} & A_{1} \ar[l]_{∂_{0}} & … \ar[l]_{∂_{1}} & A_{n} \ar[l]_{∂_{n−1}} & … \ar[l]_{∂_{n}}}

The set of k-cells is

(BA)_{k} = ∏_{i=0}^{i=k} A_{i}

The source and target maps from (BA)_{k+1} to (BA)_{k} are given by

s(a_{0}, …, a_{k+1}) = (a_{0}, …, a_{k})
t(a_{0}, …, a_{k+1}) = (a_{0}, …, a_{k} + ∂_{k}a_{k+1})

which easily defines an ∞-graph. To make it an ∞-category, we define the identities by:

id(a_{0}, …, a_{k}) = (a_{0}, …, a_{k}, 0)

and, given 0 ≤ j < k, \overline{a} = (a_{0}, …, a_{k}) ∈ (BA)_{k} and \overline{b} = (b_{0}, …, b_{k}) ∈ (BA)_{k} such that t_{jk}\overline{a} = s_{jk}\overline{b}, we define their composition along dimension j by:

\overline{a} ∗_{j} \overline{b} = (a_{0}, …, a_{j}, a_{j+1} + b_{j+1}, …, a_{k} + b_{k})

We leave the verification of the axioms of ∞-categories as an exercise. In fact the category of chain complexes is equivalent to the category of abelian group objects in Cat_{∞}.

3. Polygraphs

3.1. Formal definition. It is now possible to define polygraphs, following [4]. For all n ≥ 0, there is a category Cat_{n}^{+} given by the pullback:

\xymatrix{Cat_{n}^{+} \ar[r] \ar[d] & Grph_{n+1} \ar[d]^{V_{n}} \\ _{Cat_{n}} \ar[r]^{U_{n}} & _{Grph_{n}}}

\xymatrix{S_{0} \ar[d] & S_{1} \ar[d] \ar[dl] \ar[dl] & S_{2} \ar[d] \ar[dl] \ar[dl] & S_{3} \ar[dl] \ar[dl] \\ S_{0}^{∗} & S_{1}^{∗} \ar[l] \ar[l] & S_{2}^{∗} \ar[l] \ar[l] & ⋯ \ar[l] \ar[l]}

Figure 4: polygraph

where U and V are obvious forgetful functors. An object of Cat_{n}^{+} amounts to an ncategory with extra (n + 1)-cells making it an (n + 1)-graph. We get a forgetful functor W_{n+1} from Cat_{n+1} to Cat_{n}^{+} factorizing the arrows from Cat_{n+1} to Cat_{n} and Grph_{n+1}:

[figure: Cat_{n+1}; W_{n+1}; _{Cat{+ \atop n}}; _{Grph_{n+1}}; V_{n}; _{Cat_{n}}; U_{n}; _{Grph_{n}}]

It can be shown that W_{n+1} has a left-adjoint L_{n+1}. Thus L_{n+1}(X) is the free (n + 1)- category generated by the n-category X with additional (n + 1)-cells.

An n-polygraph S is a sequence S^{(i)}, where S^{(0)} is a set and for each 1 ≤ i ≤ n, S^{(i)} belongs to Cat_{i−1}^{+}, and built by the following induction process. First chose any set S_{0} and define S^{(0)} = S_{0}. Suppose i ≥ 1 and S^{(i)} already defined as an object in Cat_{i−1}^{+}, or a set if i = 0. We get an i-category L_{i}(S^{(i)}), and denote by S_{i}^{∗} the set of its i-cells. Then S^{(i+1)} is determined by choosing a set S_{i+1} of (i + 1)-cells with source and target maps:

\xymatrix{S_{i}^{∗} & S_{i+1} \ar[l]^{t_{i}} \ar[l]_{s_{i}}}

defining an (i + 1)-graph in L_{i}(S^{(i)}). We have just defined an object of Cat_{i}^{+}, which completes the induction.

Thus an n-polygraph is entirely determined by successive choices of sets S_{i} together with corresponding source and target maps (Figure 4).

The bottom row in Figure 4 determines the ∞-category S^{∗} = QS generated by S. Here should be emphasized that the i-category L_{i}(S^{(i)}) has the same k-cells as S^{(i)}

itself for all k < i. Moreover let

η_{S^{(i)}} : S^{(i)} → W_{i}L_{i}S^{(i)}

be the unit of the adjunction on the object S^{(i)}. It is a morphism in Cat_{i−1}^{+} whose components in dimensions k < i are just identities. As for the i-component, it is the inclusion of generators:

j_{i} : S_{i} → S_{i}^{∗}

These are of course, in each dimension, the vertical arrows on Figure 4.

As a consequence of the above remark, the universal property of polygraphs will be used in the sequel as follows : given a polygraph S, an (n + 1)-category X, a family of maps ϕ_{i} : S_{i}^{∗} → X_{i} for i ∈ {0, …, n} defining a morphism in Cat_{n}, and a map f_{n+1} : S_{n+1} → X_{n+1} defining together with the ϕ_{i}’s a morphism in Cat_{n}^{+}, there is a unique ϕ_{n+1} : S_{n+1}^{∗} → X_{n+1} making the family (ϕ_{i})_{0≤i≤n+1} a morphism in Cat_{n+1} and such that the following triangle commutes:

\xymatrix{S_{n+1} \ar[r]^{j_{n+1}} \ar[dr]_{f_{n+1}} & S_{n+1}^{∗} \ar[d]^{ϕ_{n+1}} \\  & X_{n+1}}

A morphism f between polygraphs S and T amounts to a sequence of maps f_{i} : S_{i} → T_{i} making everything commute. f induces a morphism Qf in Cat_{∞}. We get a category Pol of polygraphs and morphisms, as well as a functor Q:

\xymatrix{Pol \ar[r]^{Q} & Cat_{∞}}

3.2. A small example. The 2-category we associated in the introduction to the usual presentation of Z/2Z is in fact generated by the following polygraph:

\xymatrix{S_{0} \ar[d] & S_{1} \ar[d] \ar[dl] \ar[dl] & S_{2} \ar[d] \ar[dl] \ar[dl] \\ S_{0}^{∗} & S_{1}^{∗} \ar[l] \ar[l] & S_{2}^{∗} \ar[l] \ar[l]}

with S_{0} = {•}, S_{1} = {a} where a is a loop:

\xymatrix{a \ar[d] \\ •}

and S_{2} = {aa → 1} where aa → 1 is a 2-cell:

[figure: •; a; •; a; id^{1}(•); •]

3.3. Linearization. Now with each polygraph S we may associate an abelian complex (ZS, ∂): (ZS)_{i} will be simply the free abelian group ZS_{i} on the generators S_{i}. ∂ will be defined together with a linearization map λ_{i} : (QS)_{i} → (ZS)_{i} in each dimension such that the following diagram commutes (the unlabeled arrow is of course the inclusion of generators):

\xymatrix{S_{i} \ar[r]^{j_{i}} \ar[dr] & (QS)_{i} \ar[d]^{λ_{i}} \\  & (ZS)_{i}}

and, for each x^{i} ∈ (QS)_{i}:

∂_{i−1}λ_{i}x^{i} = λ_{i−1}t_{i−1}x^{i} − λ_{i−1}s_{i−1}x^{i}  (5)

In fact, when representing x^{i} by an expression built from cells of S_{0}, …, S_{i} with compositions and identities, λ_{i}x^{i} will be simply the linear combination of the non-degenerate i-cells occurring in this expression, that is those in S_{i}. In particular, all identities are send to zero.

The idea is to build simultaneously the desired complex ZS and the ∞-category BZS (see example 2.3) together with a morphism QS → BZS, by induction on the dimension.

The precise induction hypothesis on n is as follows: for each i ≤ n there is a unique map λ_{i} : (QS)_{i} → (ZS)_{i} such that (i) the above triangle commutes (ii) ∂_{i} defined by (5) makes (ZS, ∂) an n-complex, and (iii) the family (ϕ_{i})_{0≤i≤n} given by

ϕ_{i} = λ_{0}s_{0i} × … × λ_{i−1}s_{(i−1)i} × λ_{i}

determines a morphism of n-categories:

\xymatrix{(QS)_{0} \ar[d]_{ϕ_{0}} & (QS)_{1} \ar[d]_{ϕ_{1}} \ar[l] \ar[l] & … \ar[l] \ar[l] & (QS)_{n} \ar[d]_{ϕ_{n}} \ar[l] \ar[l] \\ (BZS)_{0} & (BZS)_{1} \ar[l] \ar[l] & … \ar[l] \ar[l] & (BZS)_{n} \ar[l] \ar[l]}

Now the right hand side of (5) is still defined for i = n + 1 and x^{n+1} ∈ S_{n+1}. We may extend it by linearity to ZS_{n+1}, thus extending ZS to an (n+1)-complex. Whence a map f_{n+1} : S_{n+1} → (BZS)_{n+1} making the following square commutative:

\xymatrix{(QS)_{n} \ar[d]_{ϕ_{n}} & S_{n+1} \ar[l]^{t_{n}} \ar[l]_{s_{n}} \ar[d]^{f_{n+1}} \\ (BZS)_{n} & (BZS)_{n+1} \ar[l]^{t_{n}} \ar[l]_{s_{n}}}

The universal property of polygraphs then gives a unique ϕ_{n+1} : (QS)_{n+1} → (BZS)_{n+1}, which extends the previous ϕ′_{i}s to a morphism of (n+1)-categories. Let π be the projection (BZS)_{n+1} → ZS_{n+1}, and define λ_{n+1} = πϕ_{n+1}. λ_{n+1} satisfies properties (i), (ii) and (iii) in dimension n + 1, and is the unique such map. Hence the result.

Finally, if S and T are polygraphs, an u is a morphism of ∞-categories, u : QS → QT, it has a linearization (Figure 5) from ZS to ZT. Precisely, there is a unique Z-linear map ũ : ZS → ZT, such that for each x^{i} ∈ (QS)_{i},

ũ_{i}λ_{i}x^{i} = λ_{i}u_{i}x^{i}  (6)

\xymatrix{S_{i} \ar[d] \ar[dr] \\ (QS)_{i} \ar[r]^{λ_{i}} \ar[d]_{u_{i}} & ZS_{i} \ar[d]^{ũ_{i}} \\ (QT)_{i} \ar[r]^{λ_{i}} & ZT_{i} \\ T_{i} \ar[u] \ar[ur]}

Figure 5: linearization

In fact, the right member of (6) defines a map S_{i} → ZT_{i}, which uniquely extends by linearity to ZS_{i}. Now (6) follows by induction on the complexity of x^{i}.

4. Resolutions

We introduce here the central notion of resolution for ∞-categories. As we shall see, invariants of an ∞-category can be computed from a particular resolution, which compares to the role of resolutions in homological algebra.

4.1. Definition. let X be an ∞-category. A resolution of X is a pair (S, ϕ) where S is a polygraph and ϕ is a morphism QS → X in Cat_{∞} such that

1. For all i ≥ 0, ϕ_{i} : S_{i}^{∗} → X_{i} is surjective.

2. For all i ≥ 0 and all x^{i}, y^{i} ∈ S_{i}^{∗}, if x^{i} ∥ y^{i} and ϕ_{i}x^{i} = ϕ_{i}y^{i} then there exists z^{i+1} ∈ S_{i+1}^{∗} such that z^{i+1} : x^{i} → y^{i} and ϕ_{i+1}z^{i+1} = id^{i+1}(ϕ_{i}x^{i}).

Intuitively, think of the cells in S_{i+1} as generators for X_{i+1} as well as relations for X_{i}. We refer to the second condition as the stretching property. A similar notion appears in [14] where it is called étirement.

Likewise an n-resolution is given by ϕ : QS → X where S is an n-polygraph, and in the Definition 4.1, condition (1) holds for i ≤ n and (2) for i ≤ n − 1.

4.2. Standard resolution. We now turn to a standard resolution for an arbitrary X in Cat_{∞}. Let us define an n-resolution of X by induction on n, in such a way that the (n + 1)-resolution extends the n-resolution.

• For n = 0, we simply take S_{0} = X_{0} and ϕ_{0} is the identity map S_{0}^{∗} → X_{0}. This is clearly a 0-resolution of X.

• Suppose (S, ϕ) is an n-resolution of X, and define S_{n+1} as the set of tuples c^{n+1} = (z^{n+1}, x^{n}, y^{n}) where z^{n+1} ∈ X_{n+1}, x^{n}, y^{n} ∈ S_{n}^{∗}, x^{n} ∥ y^{n} and z^{n+1} : ϕ_{n}x^{n} → ϕ_{n}y^{n}. We may define f_{n+1} : S_{n+1} → X_{n+1} by ϕ_{n+1}c^{n+1} = z^{n+1}, and source and target maps S_{n+1} → S_{n}^{∗} by s_{n}c^{n+1} = x^{n} and t_{n}c^{n+1} = y^{n}. The universal property of polygraphs gives then S_{n+1}^{∗} and ϕ_{n+1} : S_{n+1}^{∗} → X_{n+1} extending the previous data to an (n + 1)-resolution of X (see Figure 6).

\xymatrix{S_{n} \ar[d] & S_{n+1} \ar[d] \ar[dl] \ar[dl] \ar[dd]^{f_{n+1}} \\ S_{n}^{∗} \ar[d]_{ϕ_{n}} & S_{n+1}^{∗} \ar[l] \ar[l] \ar[d]_{ϕ_{n+1}} \\ X_{n} & X_{n+1} \ar[l] \ar[l]}

Figure 6: universal property

Thus

4.3. Proposition. Each ∞-category X has a resolution.

The polygraph underlying this standard resolution will be denoted by P X, and the corresponding morphism by ϵ^{X} : QP X → X.

Now let u be a morphism between ∞-categories X and Y, we may define a morphism P u between the polygraphs P X and P Y, by:

(P u)_{0} = u_{0}  (7)
(P u)_{k+1}(z^{k+1}, x^{k}, y^{k}) = (u_{k+1}z^{k+1}, (QP u)_{k}x^{k}, (QP u)_{k}y^{k})  (8)

where (z^{k+1}, x^{k}, y^{k}) denotes a cell in (P X)_{k+1}, that is z^{k+1} ∈ X_{k+1}, x^{k}, y^{k} ∈ (QP X)_{k} and

z^{k+1} : ϵ_{k}^{X}x^{k} → ϵ_{k}^{X}y^{k}

The soundness of this definition is shown by considering the diagram:

\xymatrix{(P X)_{n+1} \ar[dd] \ar@{.>}[rrr] \ar[ddr] \ar[ddr] &  &  & (P Y)_{n+1} \ar[dd] \ar[ddl] \ar[ddl] \\  & (P X)_{n} \ar[r]^{(P u)_{n}} \ar[d] & (P Y)_{n} \ar[d] \\ (QP X)_{n+1} \ar[dd]_{ϵ_{n+1}^{X}} \ar[r] \ar[r] & (QP X)_{n} \ar[d]_{ϵ_{n}^{X}} \ar[r]^{(QP u)_{n}} & (QP Y)_{n} \ar[d]^{ϵ_{n}^{Y}} & (QP Y)_{n} \ar[dd]^{ϵ_{n+1}^{Y}} \ar[l] \ar[l] \\  & X_{n} \ar[r]_{u_{n}} & Y_{n} \\ X_{n+1} \ar[rrr]_{u_{n+1}} \ar[ur] \ar[ur] &  &  & Y_{n+1} \ar[ul] \ar[ul]}

We make the induction hypothesis that P u has been defined up to the dimension n in such a way that the inner squares commute. Then there is a unique arrow from (P X)_{n+1} to (P Y)_{n+1} (dotted line) making the whole diagram commutative, and it satisfies (8). Whence a map:

\xymatrix{(QP X)_{n+1} \ar[r]^{(QP u)_{n+1}} & (QP Y)_{n+1}}

such that the following diagram also commutes:

\xymatrix{(P X)_{n+1} \ar[r]^{(P u)_{n+1}} \ar[d] & (P Y)_{n+1} \ar[d] \\ (QP X)_{n+1} \ar[r]^{(QP u)_{n+1}} \ar[d]_{ϵ_{n+1}^{X}} & (QP Y)_{n+1} \ar[d]^{ϵ_{n+1}^{X}} \\ X_{n+1} \ar[r]^{u_{n+1}} & Y_{n+1}}

This gives the required property up to the dimension n+1. The uniqueness of the solution easily shows that P is in fact a functor:

\xymatrix{Cat_{∞} \ar[r]^{P} & Pol}

and the previous diagrams also show that the arrows

\xymatrix{QP X \ar[r]^{ϵ^{X}} & X}

define a natural transformation ϵ : QP → I. In fact:

4.4. Proposition. Q is left-adjoint to P.

Proof. We already have a natural transformation ϵ : QP → I. It remains to check that each ϵ^{X} is universal from Q to X, in other words, that for each polygraph S and each g : QS → X there is a unique f : S → P X such that the triangle

\xymatrix{ & QP X \ar[d]^{ϵ^{X}} \\ QS \ar[r]_{g} \ar@{-->}[ur]^{Qf} & X}

commutes.

We prove by induction on the dimension k that there is a unique family (f_{0}, …, f_{k}), such that the maps f_{i} : S_{i} → (P X)_{i} define a morphism of k-polygraphs and, for all 0 ≤ i ≤ k, the triangle

\xymatrix{ & QP X_{i} \ar[d]^{ϵ_{i}^{X}} \\ QS_{i} \ar[r]_{g_{i}} \ar[ur]^{(Qf)_{i}} & X}

commutes.

For k = 0, QS_{0} = S_{0}, (QP X)_{0} = (P X)_{0} = X_{0}, and ϵ_{0}^{X} is the identity, so that f_{0} = g_{0} is the only solution.

Suppose now that f has been defined up to the dimension k, satisfying the required properties, and consider the following diagram:

\xymatrix{S_{k+1} \ar@{.>}[rrrr]^{f_{k+1}} \ar[ddddd]_{j_{k+1}^{S}} \ar[ddr] \ar[ddr] &  &  &  & (P X)_{k+1} \ar[ddddd]^{j_{k+1}^{P X}} \ar[ddl] \ar[ddl] \\  & S_{k} \ar[rr]^{f_{k}} \ar[d]^{j_{k}^{S}} &  & (P X)_{k} \ar[d]_{j_{k}^{P X}} \\  & (QS)_{k} \ar[rr]^{(Qf)_{k}} \ar[dr]_{g_{k}} &  & (QP X)_{k} \ar[dl]^{ϵ_{k}^{X}} \\  &  & X_{k} \\  &  & X_{k+1} \ar[u] \ar[u] \\ (QS)_{k+1} \ar@{.>}[rrrr]_{(Qf)_{k+1}} \ar[urr]^{g_{k+1}} \ar[uuur] \ar[uuur] &  &  &  & (QP X)_{k+1} \ar[ull]_{ϵ_{k+1}^{X}} \ar[uuul] \ar[uuul]}

Dotted arrows have not been defined yet but the remaining part is commutative. Now each f_{k+1} such that the upper quadrangle (S_{k+1}, (QS)_{k}, (QP X)_{k}, (P X)_{k+1}) commutes extends (f_{0}, …, f_{k}) to a morphism of (k + 1)-polygraphs, hence determines a unique (Qf)_{k+1} making the outer square commute. Now diagram chasing shows that there is a unique choice for which the bottom triangle also commutes, namely:

f_{k+1}u^{k+1} = (g_{k+1}j_{k+1}^{S}u^{k+1}, (Qf)_{k}su^{k+1}, (Qf)_{k}tu^{k+1})  (9)

where u^{k+1} ∈ S_{k+1}.

4.5. Lifting. A key property of resolutions is that they lift morphisms. We begin with the following technical lemma.

4.6. Lemma. Let (S, ϕ) be a resolution of X and k ≥ 0. Let c^{k+1} ∈ X_{k+1} and x_{0}^{k}, x_{1}^{k} two parallel cells of S_{k}^{∗} such that ϕ_{k}x_{0}^{k} = c_{0}^{k} and ϕ_{k}x_{1}^{k} = c_{1}^{k}. There exists z^{k+1} ∈ S_{k+1}^{∗} such that ϕ_{k+1}z^{k+1} = c^{k+1}, z_{0}^{k} ∥ x_{0}^{k} and z_{1}^{k} ∥ x_{1}^{k}.

Proof. Let c^{k+1} as in the hypotheses of the lemma and consider for each integer l, 0 ≤ l ≤ k, the property (P_{l}) For each pair x_{0}^{l}, x_{1}^{l} of parallel l-cells of S_{l}^{∗} such that ϕ_{l}x_{e}^{l} = c_{e}^{l}, e = 0, 1, there exists

z^{k+1} such that ϕ_{k+1}z^{k+1} = c^{k+1} and z_{e}^{l} ∥ c_{e}^{l}. Let us prove P_{l} by induction on l ≤ k. P_{0} holds: take any antecedent of c^{k+1} by ϕ_{k+1} (surjectivity), and recall that all 0-cells are parallel to each other.

Suppose now that P_{l} holds for l < k, and let x_{0}^{l+1} ∥ x_{1}^{l+1} with ϕ_{l}x_{e}^{l+1} = c_{e}^{l+1}. By defining x_{0}^{l} = s_{l}x_{e}^{l+1} and x_{1}^{l} = t_{l}x_{e}^{l+1}, we get x_{0}^{l} ∥ x_{1}^{l}, and ϕ_{l}x_{e}^{l} = c_{e}^{l} because ϕ is a morphism.

By the induction hypothesis, we may chose z^{k+1} above c^{k+1} in such a way that z_{e}^{l} ∥ x_{e}^{l}. Point 2 in Definition 4.1 gives a^{l+1} : x_{0}^{l} → z_{0}^{l} and b^{l+1} : z_{1}^{l} → x_{1}^{l} such that

ϕ_{l+1}a^{l+1} = id^{l+1}(ϕ_{l}x_{0}^{l}) = id^{l+1}(ϕ_{l}z_{0}^{l}) = id^{l+1}(c_{0}^{l})
ϕ_{l+1}b^{l+1} = id^{l+1}(ϕ_{l}x_{1}^{l}) = id^{l+1}(ϕ_{l}z_{1}^{l}) = id^{l+1}(c_{1}^{l})

Let

w^{k+1} = id^{k+1}(a^{l+1}) ∗_{l} z^{k+1} ∗_{l} id^{k+1}(a^{l+1})

We first get

ϕ_{k+1}w^{k+1} = ϕ_{k+1}z^{k+1} = c^{k+1}

on the other hand

w_{0}^{l+1} = a^{l+1} ∗_{l} z_{0}^{l+1} ∗_{l} b^{l+1}
w_{1}^{l+1} = a^{l+1} ∗_{l} z_{1}^{l+1} ∗_{l} b^{l+1}

so that, for e = 0, 1,

s_{l}w_{e}^{l+1} = s_{l}a^{l+1} = x_{0}^{l} = s_{l}x_{e}^{l+1}
t_{l}w_{e}^{l+1} = t_{l}b^{l+1} = x_{1}^{l} = t_{l}x_{e}^{l+1}

and w_{e}^{l+1} ∥ x_{e}^{l+1}. Whence w^{k+1} satisfies the conditions of P_{l+1}.

Thus P_{l} holds for all integers l ≤ k, and especially for k itself, but P_{k} is precisely the claim of the lemma.

As a corollary of Lemma 4.6, resolutions have a strong lifting property: if x_{0}^{k} ∥ x_{1}^{k} and ϕ_{k}x_{0}^{k} ∼ ϕ_{k}x_{1}^{k}, then x_{0}^{k} ∼ x_{1}^{k}. It is enough to prove that ϕ_{k}x_{0}^{k}R_{k}ϕ_{k}x_{1}^{k} implies x_{0}^{k} ∼ x_{1}^{k}. Lemma 4.6 gives z^{k+1} such that ϕ_{k+1}z^{k+1} = c^{k+1} and z_{e}^{k} ∥ x_{e}^{k}. On the other hand ϕ_{k}x_{e}^{k} = c_{e}^{k} = ϕ_{k}z_{e}^{k}, whence a^{k+1} : x_{0}^{k} → z_{0}^{k} and b^{k+1} : z_{1}^{k} → x_{1}^{k} by the stretching property. Thus

a^{k+1} ∗_{k} z^{k+1} ∗_{k} b^{k+1} : x_{0}^{k} → x_{1}^{k}

and x_{0}^{k} ∼ x_{1}^{k}.

It is now possible to prove the desired lifting property.

4.7. Proposition. Let X be an ∞-category, S and T polygraphs, ϕ : QS → X a morphism and ψ : QT → X a resolution. Then there is a morphism u : QS → QT such that ψu = ϕ (Figure 7).

\xymatrix{QS \ar[r]^{u} \ar[dr]_{ϕ} & QT \ar[d]^{ψ} \\  & X}

Figure 7: lifting

Proof. We build u_{0}, u_{1}, … by induction on the dimension.

We first choose u_{0} : S_{0}^{∗} → T_{0}^{∗} such that ψ_{0}u_{0} = ϕ_{0}. This is possible because of the surjectivity of ψ_{0}.

Suppose now that u has been defined up to dimension k, with

ψ_{i}u_{i} = ϕ_{i} for 0 ≤ i ≤ k

We want a map u_{n+1} : S_{n+1}^{∗} → T_{n+1}^{∗} extending the given data to a morphism in Cat_{n+1}. By the universal property of polygraphs, it suffices to define u_{n+1} on the set S_{n+1} of generators. Let then x^{k+1} ∈ S_{k+1}. As x_{0}^{k} ∥ x_{1}^{k}, we also have u_{k}x_{0}^{k} ∥ u_{k}x_{1}^{k} and Lemma 4.6 yields z^{k+1} ∈ T_{k+1}^{∗} such that

ψ_{k+1}z^{k+1} = ϕ_{k+1}x^{k+1}  (10)

and

z_{e}^{k} ∥ u_{k}x_{e}^{k} for e = 0, 1  (11)

By successively applying s_{k} and t_{k} to the members of (10), we get:

ψ_{k}u_{k}x_{0}^{k} = ϕ_{k}x_{0}^{k} = s_{k}ϕ_{k+1}x^{k+1} = s_{k}ψ_{k+1}z^{k+1} = ψ_{k}z_{0}^{k}
ψ_{k}u_{k}x_{1}^{k} = ϕ_{k}x_{1}^{k} = t_{k}ϕ_{k+1}x^{k+1} = t_{k}ψ_{k+1}z^{k+1} = ψ_{k}z_{1}^{k}

and, by (11), there are cells a^{k+1} : u_{k}x_{0}^{k} → z_{0}^{k} and b^{k+1} : z_{1}^{k} → x_{1}^{k} such that

ψ_{k+1}a^{k+1} = id^{k+1}(ψ_{k}u_{k}x_{0}^{k}) = id^{k+1}(ψ_{k}z_{0}^{k})
ψ_{k+1}b^{k+1} = id^{k+1}(ψ_{k}u_{k}x_{1}^{k}) = id^{k+1}(ψ_{k}z_{1}^{k})

It is now possible to define

u_{k+1}x^{k+1} = a^{k+1} ∗_{k} z^{k+1} ∗_{k} b^{k+1}

Thus

s_{k}u_{k+1}x^{k+1} = u_{k}x_{0}^{k}
t_{k}u_{k+1}x^{k+1} = u_{k}x_{1}^{k}

Hence u_{k+1} extends u to a morphism up to dimension k + 1. Moreover

ψ_{k+1}u_{k+1}x^{k+1} = (ψ_{k+1}a^{k+1}) ∗_{k} (ψ_{k+1}z^{k+1}) ∗_{k} (ψ_{k+1}b^{k+1})
= id^{k+1}(ψ_{k}u_{k}x_{0}^{k}) ∗_{k} (ϕ_{k+1}x^{k+1}) ∗_{k} id^{k+1}(ψ_{k}u_{k}x_{1}^{k})
= ϕ_{k+1}x^{k+1}

which proves the property in dimension k + 1.

5. Homotopy theorem

In Proposition 4.7, the lifting morphism u is of course not unique. Two such morphisms are however “homotopic”, which of course needs a precise definition. For doing this, we associate to each ∞-category X a new ∞-category HX, consisting very roughly of higherdimensional paths in X. The details of the construction are found in appendix A. For the moment, the reader should look at Figure 11, as well as to the formulas (26) and (27), which give the source and target of the cells involved.

5.1. Theorem. Let X be an ∞-category, S and T polygraphs, ϕ : QS → X a morphism and ψ : QT → X a resolution. If u, v are morphisms QS → QT such that ψu = ψv = ϕ, then there is a morphism h : QS → HQT such that u = a_{+} h and v = a_{−} h (Figure 8).

Proof. We build, in each dimension i, a map h_{i} : (QS)_{i} → (HQT)_{i} such that h becomes a morphism QS → HQT and, for each i, a_{+}^{i} h_{i} = u_{i} and a_{−}^{i} h_{i} = v_{i}. We proceed by induction on the dimension.

Let x^{0} ∈ (QS)_{0} = S_{0}. u_{0}x^{0} ∥ v_{0}x^{0} and ψ_{0}u_{0}x^{0} = ψ_{0}v_{0}x^{0} = ϕ_{0}x^{0} by hypothesis. (T, ψ) being a resolution, there is a 1-cell w^{1} ∈ (QT)_{1} such that

w^{1} : u_{0}x^{0} → v_{0}x^{0}

\xymatrix{ & HQT \ar[d]^{a_{−}} \ar[d]_{a_{+}} \\ QS \ar@{-->}[ur]^{h} \ar[dr]_{ϕ} \ar[r]^{u} \ar[r]_{v} & QT \ar[d]^{ψ} \\  & X}

Figure 8: homotopy

and

ψ_{1}w^{1} = id^{1}(ψ_{0}u_{0}x^{0})

By definition of HQT, w^{1} ∈ (HQT)_{0} and [w^{1}] = w^{1} ∈ (QT)_{1}. We may define

h_{0}x^{0} = w^{1}

Thus

a_{+}^{0} h_{0}x^{0} = d_{−}[w^{1}] = u_{0}x^{0}
a_{−}^{0} h_{0}x^{0} = d_{+}[w^{1}] = v_{0}x^{0}

and we are done in dimension 0.

Suppose now that we have defined, for each 0 ≤ i ≤ n, a map

h_{i} : (QS)_{i} → (HQT)_{i}

in such a way that (h_{0}, …, h_{n}) is a morphism of n-categories, and for each 0 ≤ i ≤ n,

a_{+}^{i} h_{i} = u_{i}  (12)
a_{−}^{i} h_{i} = v_{i}  (13)

and for each x^{i} ∈ (QS)_{i},

ψ_{i+1}[h_{i}x^{i}] = id^{i+1}(ψ_{i}u_{i}x^{i})  (14)

We now define h_{n+1} : (QS)_{n+1} → (HQT)_{n+1} extending the previous data to a morphism of (n + 1)-category, satisfying (12), (13) and (14) up to i = n + 1. We first define a map

k_{n+1} : S_{n+1} → (QHT)_{n+1}

Let x^{n+1} ∈ S_{n+1} and consider the following expressions:

E = u_{n+1}x^{n+1} ∗_{0} [h_{0}x_{+}^{0}] ∗_{1} … ∗_{n} [h_{n}x_{+}^{n}]  (15)
F = [h_{n}x_{−}^{n}] ∗_{n} … ∗_{1} [h_{0}x_{−}^{0}] ∗_{0} v_{n+1}x^{n+1}  (16)

By induction hypothesis, E and F denote parallel cells in (QT)_{n+1}, and

ψ_{n+1}E = ψ_{n+1}u_{n+1}x^{n+1} = ϕ_{n+1}x^{n+1}
ψ_{n+1}F = ψ_{n+1}v_{n+1}x^{n+1} = ϕ_{n+1}x^{n+1}

so that there is a cell w^{n+2} ∈ (QT)_{n+2} with source E, target F, and

ψ_{n+2}w^{n+2} = id^{n+2}(ψ_{n+1}u_{n+1}x^{n+1})

We may then define

k_{n+1}x^{n+1} = (h_{n}x_{+}^{n}, h_{n}x_{−}^{n}, u_{n+1}x^{n+1}, v_{n+1}x^{n+1}, w^{n+2})  (17)

But E and F are easily seen to be T_{−}^{n+1} k_{n+1}x^{n+1} and T_{+}^{n+1} k_{n+1}x^{n+1} respectively, so that k_{n+1}x^{n+1} belongs to (HQT)_{n+1}. Note that

a_{+}^{n+1} k_{n+1} = u_{n+1}  (18)
a_{−}^{n+1} k_{n+1} = v_{n+1}  (19)

and

ψ_{n+2}[k_{n+1}x^{n+1}] = id^{n+2}(ψ_{n+1}u_{n+1}x^{n+1})  (20)

Moreover, k_{n+1} extends the h_{i}’s to a morphism in Cat_{n}^{+}. By the definition of polygraphs, there is a unique h_{n+1} : (QS)_{n+1} → (HQT)_{n+1} making (h_{i})_{0≤i≤n+1} a morphism in Cat_{n+1} and such that the following diagram commutes:

\xymatrix{S_{n+1} \ar[r]^{j_{n+1}} \ar[dr]_{k_{n+1}} & (QS)_{n+1} \ar[d]^{h_{n+1}} \\  & (HQT)_{n+1}}

It remains to check that (18) and (19) extend to h_{n+1}, and that (14) still holds for i = n+1.

As for (18) and (19), just remember that every cell in (QS)_{n+1} is a composite of elements of S_{n+1} and identities on cells in (QS)_{n}, and that morphisms preserve composition and identities. Thus

a_{+}^{n+1} h_{n+1} = u_{n+1}  (21)
a_{−}^{n+1} h_{n+1} = v_{n+1}  (22)

Let us show that

ψ_{n+2}[h_{n+1}x^{n+1}] = id^{n+2}(ψ_{n+1}u_{n+1}x^{n+1})  (23)

for each x^{n+1} ∈ (QS)_{n+1}.

If x^{n+1} ∈ j_{n+1}S_{n+1}, (23) is exactly (20) and we are done.

If x^{n+1} = Ix^{n} for some x^{n} ∈ (QS)_{n},

ψ_{n+2}[h_{n+1}x^{n+1}] = ψ_{n+2}[h_{n+1}Ix^{n}]
= ψ_{n+2}[Ih_{n}x^{n}]
= ψ_{n+2}I[h_{n}x^{n}]
= Iψ_{n+1}[h_{n}x^{n}]
= I id^{n+1}(ψ_{n}u_{n}x^{n})
= id^{n+2}(Iψ_{n}u_{n}x^{n})
= id^{n+2}(ψ_{n+1}u_{n+1}x^{n+1})

Suppose finally that (23) holds for i-composable cells x^{n+1} and y^{n+1}, and check that it still holds for z^{n+1} = x^{n+1} ∗_{i} y^{n+1}. Let k = n + 1 − i.

ψ_{n+2}[h_{n+1}z^{n+1}] = ψ_{n+2}[h_{n+1}x^{n+1} ∗_{i} h_{n+1}y^{n+1}]
= (ψ_{n+2} S_{−}^{i+1} d_{−}^{k−1}h_{n+1}x^{n+1} ∗_{i} ψ_{n+2}[h_{n+1}y^{n+1}]) ∗_{i+1}
(ψ_{n+2}[h_{n+1}x^{n+1}] ∗_{i} ψ_{n+2} S_{+}^{i+1} d_{+}^{k−1}h_{n+1}y^{n+1})
= (ψ_{n+2} S_{−}^{i+1} d_{−}^{k−1}h_{n+1}x^{n+1} ∗_{i} id^{n+2}(ψ_{n+1}u_{n+1}y^{n+1})) ∗_{i+1}
(id^{n+2}(ψ_{n+1}u_{n+1}x^{n+1}) ∗_{i} ψ_{n+2} S_{+}^{i+1} d_{+}^{k−1}h_{n+1}y^{n+1})

But

S_{−}^{i+1} d_{−}^{k−1}h_{n+1}x^{n+1} = S_{−}^{i+1} h_{i+1}x_{−}^{i+1}

so that

ψ_{n+2} S_{−}^{i+1} d_{−}^{k−1}h_{n+1}x^{n+1} = ψ_{n+2}I^{k} a_{+}^{i+1} h_{i+1}x_{−}^{i+1}
= I^{k}ψ_{i+1} a_{+}^{i+1} h_{i+1}x_{−}^{i+1}
= I^{k}ψ_{i+1}u_{i+1}x_{−}^{i+1}

by using the expression of S_{−}^{i+1}, (14) and (21).

On the other hand

id^{n+2}(ψ_{n+1}u_{n+1}x^{n+1}) = Iψ_{n+1}u_{n+1}x^{n+1}

and

d_{−}^{k}Iψ_{n+1}u_{n+1}x^{n+1} = ψ_{i+1}u_{i+1}x_{−}^{i+1}

The same argument shows that

ψ_{n+2} S_{+}^{i+1} d_{+}^{k−1}h_{n+1}y^{n+1} = I^{k}ψ_{i+1}u_{i+1}y_{+}^{i+1}

and

d_{+}^{k} id^{n+2}(ψ_{n+1}u_{n+1}y^{n+1}) = ψ_{i+1}u_{i+1}y_{+}^{i+1}

By applying exchange, we get

ψ_{n+2}[h_{n+1}z^{n+1}] = id^{n+2}(ψ_{n+1}u_{n+1}x^{n+1}) ∗_{i} id^{n+2}(ψ_{n+1}u_{n+1}y^{n+1})
= id^{n+2}(ψ_{n+1}u_{n+1}z^{n+1})

6. Homological invariance

This section is devoted to the proof of the following corollary of Theorem 5.1.

6.1. Theorem. Let X be an ∞-category, and (S, ϕ), (T, ψ) resolutions of X. The complexes ZS and ZT have the same homology.

Thus H_{∗}(X) can be defined as H_{∗}(ZS), where S is any polygraphic resolution of X.

Proof. Let ϕ : QS → X a morphism, and (T, ψ) a resolution of X, and u, v two morphisms QS → QT with ψu = ψv = ϕ. By Theorem 5.1, there is an h : QS → HQT such that u = a_{+} h and v = a_{−} h. The key point is that, when linearizing these equations, one gets an algebraic homotopy between ũ and ṽ (see 3.3).

We will define, for each i ≥ 0, a Z-linear map θ_{i+1} : ZS_{i} → ZT_{i+1} such that

ũ_{i} − ṽ_{i} = ∂θ_{i+1} + θ_{i}∂  (24)

where θ_{0} = 0 by convention (see Figure 9).

[figure: ZS_{i−1}; ṽ_{i−1}; ũ_{i−1}; θ_{i}; ZS_{i}; ∂; ṽ_{i}; ũ_{i}; θ_{i+1}; ZS_{i+1}; ∂; ṽ_{i+1}; ũ_{i+1}; ZT_{i−1}; ZT_{i}; ∂; ZT_{i+1}; ∂]

Figure 9: algebraic homotopy

Now for each i ≥ 0, we have a map [ ] : (HQT)_{i} → (QT)_{i+1} (see appendix A) so that we may also define a map

x^{i} ↦ λ_{i+1}[h_{i}x^{i}]

from S_{i} to ZT_{i+1}, which extends by linearity to θ_{i+1} : ZS_{i} → ZT_{i+1}. Let us assume for the moment that θ_{i+1} just defined satisfies

θ_{i+1}λ_{i}x^{i} = λ_{i+1}[h_{i}x^{i}]  (25)

for all x^{i} ∈ (QS)_{i} (see Figure 10).

We will return to (25) in Lemma 6.2 below.

Let us now evaluate ∂θ_{i+1}x^{i} for x^{i} ∈ S_{i}. First

∂θ_{i+1}x^{i} = ∂λ_{i+1}[h_{i}x^{i}]
= λ_{i}t_{i}[h_{i}x^{i}] − λ_{i}s_{i}[h_{i}x^{i}]

\xymatrix{S_{i} \ar[d] & (HQT)_{i} \ar[d]^{[ ]} \\ (QS)_{i} \ar@{-->}[ur]^{h_{i}} \ar[d]_{λ_{i}} & (QT)_{i+1} \ar[d]^{λ_{i+1}} \\ ZS_{i} \ar[r]_{θ_{i+1}} & ZT_{i+1}}

Figure 10: commutation of θ

by using (5). But from the construction of H,

t_{i}[h_{i}x^{i}] = T_{+}^{i} h_{i}x^{i}
= [d_{−}h_{i}x^{i}] ∗_{i−1} ⋯ ∗_{1} [d_{−}^{i}h_{i}x^{i}] ∗_{0} a_{−}^{i} h_{i}x^{i}

In the last expression, only the two terms [d_{−}h_{i}x^{i}] and a_{−}^{i} h_{i}x^{i} are non-degenerate, the other ones are identities on cells of dimension < i. As linearization kills degenerate cells, we get

λ_{i}t_{i}[h_{i}x^{i}] = λ_{i}[d_{−}h_{i}x^{i}] + λ_{i} a_{−}^{i} h_{i}x^{i}
= λ_{i}[d_{−}h_{i}x^{i}] + λ_{i}u_{i}x^{i}
= λ_{i}[d_{−}h_{i}x^{i}] + ũ_{i}x^{i}

Likewise

λ_{i}s_{i}[h_{i}x^{i}] = ṽ_{i}x^{i} + λ_{i}[d_{+}h_{i}x^{i}]

Thus

∂θ_{i+1}x^{i} = ũ_{i}x^{i} − ṽ_{i}x^{i} + A

where

A = λ_{i}[d_{−}h_{i}x^{i}] − λ_{i}[d_{+}h_{i}x^{i}]

Now, by using the fact that h commutes with d_{+} and d_{−}, together with (25) and the linearity of θ_{i}, we get

A = λ_{i}[d_{−}h_{i}x^{i}] − λ_{i}[d_{+}h_{i}x^{i}]
= λ_{i}[h_{i−1}d_{−}x^{i}] − λ_{i}[h_{i−1}d_{+}x^{i}]
= θ_{i}λ_{i−1}d_{−}x^{i} − θ_{i}λ_{i−1}d_{+}x^{i}
= θ_{i}(λ_{i−1}d_{−}x^{i} − λ_{i−1}d_{+}x^{i})
= −θ_{i}∂λ_{i}x^{i}

and (24) follows, first for x^{i} ∈ S_{i}, then for any x^{i} ∈ ZS_{i} by linearity.

In the case where (S, ϕ) and (T, ψ) are both resolutions of X we conclude by familiar arguments that ũ induces an isomorphism on homology.

It remains to check the small but crucial point of the equation (25). In the hypotheses of Theorem 6.1, we establish the following lemma:

6.2. Lemma. For each i ≥ 0, there is a Z-linear map θ_{i+1} : ZS_{i} → ZT_{i+1} such that (25), that is, for each x^{i} ∈ (QS)_{i},

θ_{i+1}λ_{i}x^{i} = λ_{i+1}[h_{i}x^{i}]

Proof. Define θ_{i+1} as in the proof of Theorem 6.1. Then we show (25) by induction on the complexity of x^{i}.

• If x^{i} ∈ S_{i}, this is just the definition of θ_{i+1};

• if x^{i} = id^{i}(x^{j}), where j < i, λ_{i}x^{i} = 0, and the left member of (25) is zero by linearity of θ_{i+1}. On the other hand, h is a morphism, hence h_{i}x^{i} = id^{i}(h_{j}x^{j}), and by (44) [h_{i}x^{i}] = id^{i+1}([h_{j}x^{j}]), so that λ_{i+1}[h_{i}x^{i}] = 0 and we are done in this case;

• if x^{i} = y^{i} ∗_{j} z^{i} for smaller cells y^{i} and z^{i}, and j < i, the induction hypothesis gives

θ_{i+1}λ_{i}x^{i} = θ_{i+1}λ_{i}y^{i} + θ_{i+1}λ_{i}z^{i}
= λ_{i+1}[h_{i}y^{i}] + λ_{i+1}[h_{i}z^{i}]

On the other hand, as h is a morphism

λ_{i+1}[h_{i}x^{i}] = λ_{i+1}[h_{i}y^{i} ∗_{j} h_{i}z^{i}]

Now the equation (47) of appendix A shows how [ ] behaves with respect to composition. In particular, only terms within brackets are non-degenerated, the other ones being killed by linearization, whence

λ_{i+1}[h_{i}y^{i} ∗_{j} h_{i}z^{i}] = λ_{i+1}[h_{i}y^{i}] + λ_{i+1}[h_{i}z^{i}]

and we are done again.

Thus the lemma is proved.

Let us point out that (25) is the only place of our argument where we really need h as a morphism between ∞-categories, not just between ∞-graphs.

7. Conclusion

As we indicated before, works on finite derivation types are a main source of the present notion of resolution. Precisely, if we consider a monoid X as a particular case of ∞- category, it has finite derivation type if and only if it has a resolution (S, ϕ) with finite S_{3}. This immediately suggests a notion of finite derivation type in any dimension, but we need invariance properties of this notion, presumably based on Theorem 5.1.

Another remark is that our resolutions are still too big for practical computations Therefore, generalized versions of Squier’s theorems should be established, and will be the subject of further work.

Let us simply point out for the moment that the relationship between finiteness and confluence becomes much more intricate in dimensions ≥ 2 than in the case of string rewriting, so that even asking the correct questions seems far from obvious.

Finally, very similar motivations and techniques appear in recent works on concurrency, and we expect fruitful interactions in that direction (see [9, 10]).

Acknowledgment

I wish to thank Albert Burroni for his invaluable help.

A. A category of paths

Given an ∞-category X, we define an ∞-graph HX with identities and compositions and show how HX becomes itself an ∞-category. We define sets (HX)_{n} by induction, together with maps:

\xymatrix{(HX)_{n−1} & (HX)_{n} \ar[l]^{d_{−}} \ar[l]_{d_{+}}}

\xymatrix{(HX)_{n} \ar[r]^{a_{+}^{n}} \ar[r]_{a_{−}^{n}} & X_{n}}

\xymatrix{(HX)_{n} \ar[r]^{[ ]} & X_{n+1}}

Figure 11 gives an insight into H in small dimensions. In particular the cylinder represents [x^{2}], which has to be oriented from the front to the bottom (dotted lines). Similar pictures already appear in [2], and since then in many works (see for instance chapter 3 of [7]), though in a different context: we stress here the fact that the cells of HX are built from material already present in X. Also the construction is carried out in arbitrary dimensions.

From the above symbols we may build the following formal expressions which play a crucial role in the construction:

T_{−}^{0} x = a_{+}^{0} x
T_{+}^{0} x = a_{−}^{0} x
T_{−}^{1} x = a_{+}^{1} x ∗_{0} [d_{+}x]
T_{+}^{1} x = [d_{−}x] ∗_{0} a_{−}^{1} x

and for n ≥ 2

T_{−}^{n} x = a_{+}^{n} x ∗_{0} [d_{+}^{n}x] ∗_{1} [d_{+}^{n−1}x] ∗_{2} ⋯ ∗_{n−1} [d_{+}x]  (26)
T_{+}^{n} x = [d_{−}x] ∗_{n−1} ⋯ ∗_{2} [d_{−}^{n−1}x] ∗_{1} [d_{−}^{n}x] ∗_{0} a_{−}^{n} x  (27)

[figure: •; a_{−}^{0} x^{0}; •; a_{+}^{0} x^{0}; [x^{0}]; •; _{a_{−}^{0} d_{−}x^{1}}; •; ^{a_{+}^{0} d_{−}x^{1}}; [d_{−}x^{1}]; •; ^{a_{+}^{0} d_{+}x^{1}}; a_{+}^{1} x^{1}; •; _{a_{−}^{0} d_{+}x^{1}}; [d_{+}x^{1}]; a_{−}^{1} x^{1}; [x^{1}]]

[figure: •; •; •; •; a_{−}^{2} x^{2}; •; [d_{−}^{2}x^{2}]; •; •; •; a_{+}^{2} x^{2}; [d_{+}^{2}x^{2}]; [d_{+}x^{2}]; [d_{−}x^{2}]]

Figure 11: HX in dimension 0, 1, 2

Why the signs on the right hand side of (26) and (27) do no agree with the one of the left hand side will be explained later. Eventually T_{−}^{k} and T_{+}^{k} become maps (HX)_{k} → X_{k}. Also the following truncated expressions will be useful for technical purposes:

T_{−}^{n,l} x = a_{+}^{n} x ∗_{0} [d_{+}^{n}x] ∗_{1} [d_{+}^{n−1}x] ∗_{2} ⋯ ∗_{n−l} [d_{+}^{l}x]  (28)
T_{+}^{n,l} x = [d_{−}^{l}x] ∗_{n−l} ⋯ ∗_{2} [d_{−}^{n−1}x] ∗_{1} [d_{−}^{n}x] ∗_{0} a_{−}^{n} x  (29)

for each l ∈ {1, …, n+1}. As the case is of particular importance we define S_{−}^{n} x = T_{−}^{n,2} x and S_{+}^{n} x = T_{+}^{n,2} x.

For n = 0, (HX)_{0} will be simply X_{1}, [ ] is the identity. When we write [x] it is the cell of X_{1} we have in mind. For instance a_{+}^{0} and a_{−}^{0} are defined by:

a_{+}^{0} x = d_{−}[x]  (30)
a_{−}^{0} x = d_{+}[x]  (31)

here d_{−} and d_{+} are of course the source and target on X_{1}. Notice that T_{−}^{0} and T_{+}^{0} define maps (HX)_{0} → X_{0}, because they are just a_{+}^{0} and a_{−}^{0} in this case.

A.1. Induction step. Suppose we have defined so far an n-category

\xymatrix{(HX)_{0} & (HX)_{1} \ar[l]^{d_{−}} \ar[l]_{d_{+}} & … \ar[l]^{d_{−}} \ar[l]_{d_{+}} & (HX)_{n} \ar[l]^{d_{−}} \ar[l]_{d_{+}}}

with maps [ ], a_{+}^{k}, a_{−}^{k} satisfying the following conditions:

(H1) a_{+} and a_{−} define morphisms of n-graphs, that is for all signs ϵ, ϵ′ and each index 0 ≤ i ≤ n − 1 we get a commutative diagram

[figure: (HX)_{i}; _{a{i \atop ϵ′}}; (HX)_{i+1}; ^{d^{ϵ}}; _{a{i+1 \atop ϵ′}}; X_{i}; X_{i+1}; _{d_{ϵ}}]

(H2) For each i ∈ {0, …, n} and x ∈ (HX)_{i}, the expressions T_{−}^{i} x and T_{+}^{i} x are well defined, they denote i-cells in X and [x] is an (i + 1)-cell in X such that

\xymatrix{T_{−}^{i} x \ar[r]^{[x]} & T_{+}^{i} x}  (32)

We extend these data to an (n + 1)-graph by defining a set (HX)_{n+1} and morphisms

\xymatrix{(HX)_{n} & (HX)_{n+1} \ar[l]^{d_{−}} \ar[l]_{d_{+}}}

as follows: a cell x in (HX)_{n+1} is a 5-tuple

(x_{+}^{n}, x_{−}^{n}, v_{+}^{n+1}, v_{−}^{n+1}, w^{n+2})  (33)

whose components are subject to the following conditions:

(C0) x_{+}^{n} and x_{−}^{n} are parallel cells in (HX)_{n}.

(C1) v_{+}^{n+1} and v_{−}^{n+1} are (n + 1)-cells in X_{n} such that

\xymatrix{a_{+}^{n} x_{−}^{n} \ar[r]^{v_{+}^{n+1}} & a_{+}^{n} x_{+}^{n}}
\xymatrix{a_{−}^{n} x_{−}^{n}0 \ar[r]^{v_{−}^{n+1}} & a_{−}^{n} x_{+}^{n}}

We define d_{+}x = x_{+}^{n}, d_{−}x = x_{−}^{n}, a_{+}^{n+1} x = v_{+}^{n+1} and a_{−}^{n+1} x = v_{−}^{n+1}. As a consequence condition (H1) still holds for i = n.

(C2) w^{n+2} is an (n + 2)-cell in X_{n+2} such that

\xymatrix{T_{−}^{n+1} x \ar[r]^{w^{n+2}} & T_{+}^{n+1} x}

and [x] = w^{n+2} so that (32) still holds for i = n + 1.

That we get an (n + 1)-graph is obvious from the definition of d_{+} and d_{−}, and the induction hypothesis. Notice that the above definitions do not guarantee that (HX)_{n+1} ≠ ∅. Now we need to define (n + 1)-dimensional identities on i-cells as well as i-dimensional composites of (n + 1)-cells, for all 0 ≤ i ≤ n, and check that these operations match the axioms of (n + 1)-category.

A.2. Some properties of T_{+} and T_{−}.

A.3. Lemma. For all x ∈ (HX)_{n+1}

d_{−} T_{−}^{n+1} x = T_{−}^{n} d_{−}x
d_{+} T_{−}^{n+1} x = T_{+}^{n} d_{+}x
d_{−} T_{+}^{n+1} x = T_{−}^{n} d_{−}x
d_{+} T_{+}^{n+1} x = T_{+}^{n} d_{+}x

Proof. Let n ≥ 1 and x be in (HX)_{n+1}. Consider

T_{−}^{n+1} x = a_{+}^{n+1} x ∗_{0} [d_{+}^{n+1}x] ∗_{1} ⋯ ∗_{n} [d_{+}x]  (34)

The construction of (HX)_{n+1} requires that this composite be defined as a cell in X_{n+1}. a_{+}^{n+1} x ∈ X_{n+1} and for each i ∈ {2, …, n + 1}, [d_{+}^{i}x] denotes here the (n + 1)-dimensional identity on a cell in X_{n+2−i}, so that for i ≥ 2

d_{−}[d_{+}^{i}x] = d_{+}[d_{+}^{i}x] = [d_{+}^{i}x]  (35)

Thus

d_{−} T_{−}^{n+1} x = d_{−}(a_{+}^{n+1} x ∗_{0} [d_{+}^{n+1}x] ∗_{1} ⋯ ∗_{n−1} [d_{+}^{2}x])
= d_{−} a_{+}^{n+1} x ∗_{0} d_{−}[d_{+}^{n+1}x] ∗_{1} ⋯ ∗_{n−1} d_{−}[d_{+}^{2}x]
= a_{+}^{n} d_{−}x ∗_{0} [d_{+}^{n+1}x] ∗_{1} ⋯ ∗_{n−1} [d_{+}^{2}x]
= a_{+}^{n} d_{−}x ∗_{0} [d_{+}^{n}d_{+}x] ∗_{1} ⋯ ∗_{n−1} [d_{+}d_{+}x]
= T_{−}^{n} d_{−}x

As regards the second equality

d_{+} T_{−}^{n+1} x = d_{+}[d_{+}x] = T_{+}^{n} d_{+}x  (36)

from the definition of [ ] on (HX)_{n}.

By symmetry we get the two remaining equalities as well.

Also, for all 0 < k < l and all signs ϵ, ϵ′, we get

d_{ϵ}^{k} T_{ϵ′}^{n,l} = T_{ϵ′}^{n−k,l−k} d_{ϵ}^{k}  (37)

as in the proof of Lemma A.3. The next lemma shows that our formal expression define actual cells:

A.4. Lemma. Suppose we are given x_{+}^{n}, x_{−}^{n} two parallel cells in (HX)_{n}, as well as v_{+}^{n+1}, v_{−}^{n+1} satisfying (C1). Then

v_{+}^{n+1} ∗_{0} [d_{+}^{n}x_{+}^{n}] ∗_{1} [d_{+}^{n−1}x_{+}^{n}] ∗_{2} ⋯ ∗_{n} [x_{+}^{n}]  (38)

and

[x_{−}^{n}] ∗_{n} ⋯ ∗_{2} [d_{−}^{n−1}x_{−}^{n}] ∗_{1} [d_{−}^{n}x_{−}^{n}] ∗_{0} v_{−}^{n+1}  (39)

are well defined and denote (n + 1)-cells in X.

Proof. Let us prove that (38) is well defined; define

u_{i} = v_{+}^{n+1} ∗_{0} [d_{+}^{n}x_{+}^{n}] ∗_{1} [d_{+}^{n−1}x_{+}^{n}] ∗_{2} ⋯ ∗_{i} [d_{+}^{n−i}x_{+}^{n}]  (40)

we show by induction on i that u_{i} is well defined for i ∈ {0, …, n}.

u_{0} = v_{+}^{n+1} ∗_{0} [d_{+}^{n}x_{+}^{n}] where [d_{+}^{n}x_{+}^{n}] is in fact a (n + 1)-identity on a 1-cell. Thus

d_{−}^{n+1}[d_{+}^{n}x_{+}^{n}] = d_{−}[d_{+}^{n}x_{+}^{n}]  (41)

On the other hand

d_{+}^{n+1}v_{+}^{n+1} = d_{+}^{n}d_{+}v_{+}^{n+1} = d_{+}^{n} a_{+}^{n} x_{+}^{n} = a_{+}^{0} d_{+}^{n}x_{+}^{n} = d_{−}[d_{+}^{n}x_{+}^{n}]  (42)

using (C1) and (30). As a consequence, v_{+}^{n+1} and [d_{+}^{n}x_{+}^{n}] are 0-composable and u_{0} is well defined and belongs to X_{n+1}.

Suppose now that u_{i} is well defined for an i < n. Because all factors but v_{+}^{n+1} and [x_{+}^{n}] are identities, we get

d_{+}^{n−i}u_{i} = d_{+}^{n−i}v_{+}^{n+1} ∗_{0} [d_{+}^{n}x_{+}^{n}] ∗_{1} ⋯ ∗_{i} [d_{+}^{n−i}x_{+}^{n}]
= d_{+}^{n−i−1} a_{+}^{n} x_{+}^{n} ∗_{0} [d_{+}^{n}x_{+}^{n}] ∗_{1} ⋯ ∗_{i} [d_{+}^{n−i}x_{+}^{n}]
= a_{+}^{i+1} d_{+}^{n−i−1}x_{+}^{n} ∗_{0} [d_{+}^{n}x_{+}^{n}] ∗_{1} ⋯ ∗_{i} [d_{+}^{n−i}x_{+}^{n}]
= T_{−}^{i+1} d_{+}^{n−i−1}x_{+}^{n}

Now

d_{−}^{n−i}[d_{+}^{n−i−1}x_{+}^{n}] = d_{−}[d_{+}^{n−i−1}x_{+}^{n}] = T_{−}^{i+1} d_{+}^{n−i−1}x_{+}^{n}

It shows that u_{i} is (i + 1)-composable with [d_{+}^{n−i−1}x_{+}^{n}], and that u_{i+1} is well defined. This gives the result for (38). (39) is proved accordingly.

A.5. Construction of identity cells. As a consequence, for each x^{n} ∈ (HX)_{n}, we may define a cell in (HX)_{n+1} which eventually becomes the identity on x^{n}. Precisely:

x^{n+1} = (x^{n}, x^{n}, v_{+}^{n+1}, v_{−}^{n+1}, w^{n+2})  (43)

where

v_{+}^{n+1} = id^{n+1}(a_{+}^{n} x^{n})
v_{−}^{n+1} = id^{n+1}(a_{−}^{n} x^{n})

and

w^{n+2} = id^{n+2}([x^{n}])  (44)

The first four components clearly satisfy (C0-1). On the other hand Lemma A.4 proves that the expressions

v_{+}^{n+1} ∗_{0} [d_{+}^{n}x^{n}] ∗_{1} [d_{+}^{n−1}x^{n}] ∗_{2} ⋯ ∗_{n} [x^{n}]

and

[x^{n}] ∗_{n} ⋯ ∗_{2} [d_{−}^{n−1}x^{n}] ∗_{1} [d_{−}^{n}x^{n}] ∗_{0} v_{−}^{n+1}

are well-defined. But they are exactly T_{−}^{n+1} x^{n+1} and T_{+}^{n+1} x^{n+1}. Now a closer inspection of the formulas shows that in this particular case:

T_{−}^{n+1} x^{n+1} = id^{n+1}(T_{−}^{n} x^{n}) ∗_{n} [x^{n}]
T_{+}^{n+1} x^{n+1} = [x^{n}] ∗_{n} id^{n+1}(T_{+}^{n} x^{n})

but d_{−}[x^{n}] = T_{−}^{n} x^{n} and d_{+}[x^{n}] = T_{+}^{n} x^{n}, so that

T_{−}^{n+1} x^{n+1} = T_{−}^{n+1} x^{n+1} = [x^{n}]

and

\xymatrix{T_{−}^{n+1} x^{n+1} \ar[r]^{w^{n+2}} & T_{+}^{n+1} x^{n+1}}

Thus (HX)_{n+1} contains at least as many cells as (HX)_{n}.

For readability, the previous construction will be denoted by the same symbol, say I, in each dimension; here for instance

x^{n+1} = Ix^{n}

furthermore, if x^{i} ∈ (HX)_{i}, and k ≥ 0, I^{k}x^{i} will be the (i + k)-cell built from x^{i} by k successive applications of the construction. Thus the symbol I behaves very much like d_{+} and d_{−}. Notice also that, for each l ≤ k,

d_{+}^{l}I^{k}x = d_{−}^{l}I^{k}x = I^{k−l}x

A.6. Composition of cells. Now we have to define the i-dimensional composition between cells in (HX)_{n+1} in such a way that we get an n + 1-category. Suppose this has been done up to (HX)_{n}. Suppose in addition that for each 0 ≤ i < m ≤ n and i-composable m-cells u and v, the composite w = u ∗_{i} v satisfies:

[w] = (S_{−}^{i+1} d_{−}^{l−1}u ∗_{i} [v]) ∗_{i+1} ([u] ∗_{i} S_{+}^{i+1} d_{+}^{l−1}u)  (45)

where l = m − i. Where the above equation comes from will be explained during the induction process. Take now x, y two cells in (HX)_{n+1}. Let k ∈ {1, …, n + 1} and i = n + 1 − k. x and y will be i-composable iff

d_{+}^{k}x = d_{−}^{k}y

Recall that

x = (d_{+}x, d_{−}x, a_{+}^{n+1} x, a_{−}^{n+1} x, [x])
y = (d_{+}y, d_{−}y, a_{+}^{n+1} y, a_{−}^{n+1} y, [y])

We define z = x ∗_{i} y component by component:

• If k = 1, i = n

d_{+}z = d_{+}y d_{−}z = d_{−}x

If k > 1, d_{+}^{k−1}d_{+}x = d_{+}^{k}x = d_{−}^{k}y = d_{−}^{k−1}d_{+}y so that d_{+}x and d_{+}y are i-composable. Likewise d_{−}x and d_{−}y are i-composable and we may define

d_{+}z = d_{+}x ∗_{i} d_{+}y d_{−}z = d_{−}x ∗_{i} d_{−}y

• By (H1)

d_{+}^{k} a_{+}^{n+1} x = a_{+}^{i} d_{+}^{k}x = a_{+}^{i} d_{−}^{k}y = d_{−}^{k} a_{+}^{n+1} y

hence a_{+}^{n+1} x and a_{+}^{n+1} y are i-composable, and the same holds for a_{−}^{n+1} x and a_{−}^{n+1} y such that we may define

a_{+}^{n+1} z = a_{+}^{n+1} x ∗_{i} a_{+}^{n+1} y  a_{−}^{n+1} z = a_{−}^{n+1} x ∗_{i} a_{−}^{n+1} y  (46)

• Recall that [x] : T_{−}^{n+1} x → T_{+}^{n+1} x. Lemma A.3 shows that

d_{+}^{k}[x] = d_{+}^{k−1}d_{+}[x]
= d_{+}^{k−1} T_{+}^{n+1} x
= T_{+}^{n−k+2} d_{+}^{k−1}x
= [d_{−}^{k}x] ∗_{n+1−k} S_{+}^{n−k+2} d_{+}^{k−1}x
= [d_{−}^{k}x] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}x

Likewise d_{−}^{k}[x] = S_{−}^{i+1} d_{−}^{k−1} ∗_{i} [d_{+}^{k}x] and the same relations hold for [y]. But here d_{+}^{k}x = d_{−}^{k}y, so that [x] and [y] look like:

[figure: •; S_{−}^{i+1} d_{−}^{k−1}x; [d_{−}^{k}x]; •; S_{−}^{i+1} d_{−}^{k−1}y; [d_{+}^{k}x]; [d_{−}^{k}y]; [x]; •; [d_{+}^{k}y]; [y]; •; S_{+}^{i+1} d_{+}^{k−1}x; •; S_{+}^{i+1} d_{+}^{k−1}y; •]

the above diagram being drawn in the 2-category:

\xymatrix{X_{i} & X_{i+1} \ar[l]^{d_{−}} \ar[l]_{d_{+}} & X_{n+2} \ar[l]^{d_{−}^{k}} \ar[l]_{d_{+}^{k}}}

It is then possible to define:

[z] = (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} [y]) ∗_{i+1} ([x] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)  (47)

We are now able to prove the following A.7. Proposition. The 5-tuple

(d_{+}z, d_{−}z, a_{+}^{n+1} z, a_{−}^{n+1} z, [z])

satisfies the conditions (C0), (C1), and (C2).

Proof. This is straightforward for (C0) and (C1). As for (C2) we know that [z] ∈ X_{n+2} and we must show that d_{+}[z] = T_{+}^{n+1} z and d_{−}[z] = T_{−}^{n+1} z. We consider two cases (1) k = 1 and (2) k > 1.

Case 1 . Suppose k = 1. Then i = n and (47) becomes

[z] = (S_{−}^{n+1} x ∗_{n} [y]) ∗_{n+1} ([x] ∗_{n} S_{+}^{n+1} y)

hence

d_{−}[z] = d_{−}(S_{−}^{n+1} x ∗_{n} [y])
= S_{−}^{n+1} x ∗_{n} d_{−}[y]
= S_{−}^{n+1} x ∗_{n} T_{−}^{n+1} y
= S_{−}^{n+1} x ∗_{n} S_{−}^{n+1} y ∗_{n} [d_{+}y]

But [d_{+}^{l}x] = [d_{+}^{l}y] for each l ∈ {2, …, n + 1} and they are all identities in S_{−}^{n+1} x, S_{−}^{n+1} y. Also a_{−}^{n+1} z = a_{−}^{n+1} x ∗_{n} a_{−}^{n+1} y and the exchange rule applies, giving

d_{−}[z] = T_{−}^{n+1} z

Likewise d_{+}[z] = T_{+}^{n+1} z and we get the result.

Case 2 . Suppose k > 1. Here

d_{−}[z] = (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} T_{−}^{n+1} y) ∗_{i+1} (T_{−}^{n+1} x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)  (48)
d_{+}[z] = (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} T_{+}^{n+1} y) ∗_{i+1} (T_{+}^{n+1} x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)  (49)

and we have to prove that these expressions are respectively T_{−}^{n+1} z and T_{+}^{n+1} z. But this is the particular case l = 1 in the next lemma.

A.8. Lemma. Let x, y, z be as above, and k ≥ 2. Then

(S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} T_{−}^{n+1,l} y) ∗_{i+1} (T_{−}^{n+1,l} x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y) = T_{−}^{n+1,l} z
(S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} T_{+}^{n+1,l} y) ∗_{i+1} (T_{+}^{n+1,l} x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y) = T_{+}^{n+1,l} z

for all l ∈ 1, …, k − 1.

Proof. By induction on k − 1 − l. Let us first examine the case l = k − 1. We notice that

T_{−}^{n+1,k+1} x ∗_{i} T_{−}^{n+1,k+1} y = T_{−}^{n+1,k+1} z  (50)

because a_{+}^{n+1} z = a_{+}^{n+1} x ∗_{i} a_{+}^{n+1} y and [d_{+}^{m}x] = [d_{+}^{m}y] = [d_{+}^{m}z] for all m ≥ k + 1, and are all identities in (50). Let

A = (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} T_{−}^{n+1,k−1} y) ∗_{i+1} (T_{−}^{n+1,k−1} x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)

By using the exchange rule and the properties of the identities we get

A = (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} T_{−}^{n+1,k−1} y) ∗_{i+1}
(((T_{−}^{n+1,k+1} x ∗_{i} [d_{+}^{k}x]) ∗_{i+1} [d_{+}^{k−1}x]) ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)
= (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} T_{−}^{n+1,k−1} y) ∗_{i+1} (T_{−}^{n+1,k+1} x ∗_{i} [d_{+}^{k}x] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)
∗_{i+1}([d_{+}^{k−1}x] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)
= (T_{−}^{n+1,k+1} x ∗_{i} T_{−}^{n+1,k−1} y) ∗_{i+1} ([d_{+}^{k−1}x] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)

Hence

A = (T_{−}^{n+1,k+1} x ∗_{i} ((T_{−}^{n+1,k+1} y ∗_{i} [d_{+}^{k}y]) ∗_{i+1} [d_{+}^{k−1}y])) ∗_{i+1}
([d_{+}^{k−1}x] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)
= (T_{−}^{n+1,k+1} x ∗_{i} T_{−}^{n+1,k+1} y ∗_{i} [d_{+}^{k}y]) ∗_{i+1}
(S_{−}^{i+1} d_{+}^{k−1}x ∗_{i} [d_{+}^{k−1}y]) ∗_{i+1} ([d_{+}^{k−1}x] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)
= T_{−}^{n+1,k+1} z ∗_{i} [d_{+}^{k}z] ∗_{i+1} [d_{+}^{k−1}z]
= T_{−}^{n+1,k−1} z

by (45) and (50). We get the result in case l = k − 1. Suppose now the relation holds for an index l such that 1 < l ≤ k − 1, we must evaluate

B = (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} T_{−}^{n+1,l−1} y) ∗_{i+1} (T_{−}^{n+1,l−1} x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)

Repeated applications of the exchange rule give:

B = (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} (T_{−}^{n+1,l} y ∗_{n+1−l+1} [d_{+}^{l−1}y])) ∗_{i+1}
((T_{−}^{n+1,l} x ∗_{n+1−l+1} [d_{+}^{l−1}x]) ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)
= ((S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} T_{−}^{n+1,l} y) ∗_{n+1−l+1} (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} [d_{+}^{l−1}y])) ∗_{i+1}
((T_{−}^{n+1,l} x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y) ∗_{n+1−l+1} ([d_{+}^{l−1}x] ∗_{i} S_{+}^{i+1} d_{−}^{k−1}y))
= ((S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} T_{−}^{n+1,l} y) ∗_{i+1} (T_{−}^{n+1,l} x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)) ∗_{n+1−l+1}
((S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} [d_{+}^{l−1}y]) ∗_{i+1} ([d_{+}^{l−1}x] ∗_{i} S_{+}^{i+1} d_{−}^{k−1}y))
= T_{−}^{n+1,l} z ∗_{n+1−l+1} [d_{+}^{l−1}z]
= T_{−}^{n+1,l−1} z

which is the result for l − 1.

By symmetry, the relations on T_{+}^{n+1,l} z hold as well.

A.9. Properties of the composition. We now check that the composition of cells we just defined satisfies all the axioms of (n + 1)-categories.

A.9.1. Associativity. Taking first x, y and z as in the previous section, and i ∈ {0, …, n}:

S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} S_{−}^{i+1} d_{−}^{k−1}y = S_{−}^{i+1} d_{−}^{k−1}z  (51)
S_{+}^{i+1} d_{−}^{k−1}x ∗_{i} S_{+}^{i+1} d_{−}^{k−1}y = S_{+}^{i+1} d_{−}^{k−1}z  (52)

Just notice that for all j ∈ {k + 1, …, n + 1},

[d_{+}^{j}x] = [d_{+}^{j}y] = [d_{+}^{j}z]

and are all identities in the expressions of (51). Repeated applications of the exchange rule plus (46) give the result, and likewise for (52). Now the associativity of ∗_{i} on (HX)_{n+1} directly follows from (51), (52) and the composition formula (47).

A.9.2. Identities. We now verify that the cells Ix actually behave like identities. Let i ≤ n and k = n+1−k. Let x be a cell in (HX)_{i}, y a cell in (HX)_{n+1}, such that d_{−}^{k}y = x. Thus d_{+}^{k}I^{k}x = x = d_{−}^{k}y, and I^{k}x, y are i-composable.

Let z = I^{k}x ∗_{i} y. We have to show that z = y. But both cells clearly agree on their first four components, so that we only need to prove [z] = [y]. Now by (47),

[z] = (S_{−}^{i+1} d_{−}^{k−1}I^{k}x ∗_{i} [y]) ∗_{i+1} ([I^{k}x] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)

With A = S_{−}^{i+1} d_{−}^{k−1}I^{k}x and B = [I^{k}x] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y,

[z] = (A ∗_{i} [y]) ∗_{i+1} B  (53)

We first evaluate A; formally:

A = S_{−}^{i+1} d_{−}^{k−1}I^{k}x
= S_{−}^{i+1} Ix
= a_{+}^{i+1} Ix ∗_{0} [d_{+}^{i+1}Ix] ∗_{1} … ∗_{i−1} [d_{+}^{2}Ix]
= a_{+}^{i} x ∗_{0} [d_{+}^{i}x] ∗_{1} … ∗_{i−1} [d_{+}x]
= T_{−}^{i} x

whose value in (53) is the (n + 2)-identity on T_{−}^{i} x. On the other hand

d_{−}^{k+1}[y] = d_{−}^{k}d_{−}[y] = d_{−}^{k} T_{−}^{n+1} y = T_{−}^{n−k+1} d_{−}^{k}y = T_{−}^{i} x

Hence A ∗_{i} [y] = [y], and [z] becomes [y] ∗_{i+1} B.

Let us evaluate B:

B = [I^{k}x] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y
= [x] ∗_{i} [d_{−}^{2}d_{+}^{k−1}y] ∗_{i−1} … ∗_{1} [d_{−}^{i+1}d_{+}^{k−1}y] ∗_{0} a_{−}^{i+1} d_{+}^{k−1}y
= [x] ∗_{i} [d_{−}x] ∗_{i−1} … ∗_{1} [d_{−}^{i}x] ∗_{0} a_{−}^{i+1} d_{+}^{k−1}y

which denotes in fact an (n + 2)-identity in (53). On the other hand,

d_{+}^{k}[y] = d_{+}^{k−1}d_{+}[y]
= d_{+}^{k−1} T_{+}^{n+1} y
= T_{+}^{i+1} d_{+}^{k−1}y
= [d_{−}d_{+}^{k−1}y] ∗_{i} … [d_{−}^{i+1}d_{+}^{k−1}y] ∗_{0} a_{−}^{i+1} d_{+}^{k−1}y
= [x] ∗_{i} [d_{−}x] ∗_{i−1} … ∗_{1} [d_{−}^{i}x] ∗_{0} a_{−}^{i+1} d_{+}^{k−1}y

so that B is the (n + 2)-identity on d_{+}^{k}[y], whence [y] ∗_{i+1} B = [y], and we get the desired result. Of course the same holds for identities on the right.

We finally show that for i-composable n-cells x^{n}, y^{n} in (HX)_{n},

I(x^{n} ∗_{i} y^{n}) = Ix^{n} ∗_{i} Iy^{n}

Again the equality is obvious on the first four components. As regards the last component, taking l = n − i and applying (45) gives:

[I(x^{n} ∗_{i} y^{n})] = id^{n+2}([x^{n} ∗_{i} y^{n}])
= id^{n+2}((S_{−}^{i+1} d_{−}^{l−1}x^{n} ∗_{i} [y^{n}]) ∗_{i+1} ([x^{n}] ∗_{i} S_{+}^{i+1} d_{+}^{l−1}y^{n}))
= (id^{n+2}(S_{−}^{i+1} d_{−}^{l−1}x^{n}) ∗_{i} id^{n+2}([y^{n}])) ∗_{i+1}
(id^{n+2}([x^{n}]) ∗_{i} id^{n+2}(S_{+}^{i+1} d_{+}^{l−1}y^{n}))
= (S_{−}^{i+1} d_{−}^{l−1}id^{n+1}(x^{n}) ∗_{i} [Iy^{n}]) ∗_{i+1}
([Ix^{n}] ∗_{i} S_{+}^{i+1} d_{+}^{l−1}id^{n+1}(y^{n}))
= [Ix^{n} ∗_{i} Iy^{n}]

A.9.3. Exchange. We prove here that HX satisfies the exchange rule.

Let x, y, z, t be cells in (HX)_{n+1}, and 0 ≤ i < j < n + 1. Define k = n + 1 − i and l = n + 1 − j. We suppose that

d_{+}^{k}x = d_{+}^{k}z = d_{−}^{k}y = d_{−}^{k}t
d_{+}^{l}x = d_{−}^{l}z
d_{+}^{l}y = d_{−}^{l}t

such that the following composites are well defined in (HX)_{n+1}:

A = (x ∗_{i} y) ∗_{j} (z ∗_{i} t)
B = (x ∗_{j} z) ∗_{i} (y ∗_{j} t)

and we have to prove that A = B. Here again the equality on the first four components is easy: it remains to prove [A] = [B].

First

[B] = (S_{−}^{i+1} d_{−}^{k−1}(x ∗_{j} z) ∗_{i} [y ∗_{j} t]) ∗_{i+1} ([x ∗_{j} z] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}(y ∗_{j} t))  (54)

Notice that d_{−}^{k−1}(x ∗_{j} z) = d_{−}^{k−1}x and d_{+}^{k−1}(y ∗_{j} t) = d_{+}^{k−1}t, and these are identities in (54). By using the exchange rule and (47), [B] rewrites in the form:

(T ∗_{j+1} Y) ∗_{i+1} (Z ∗_{j+1} X)  (55)

where

X = ([x] ∗_{j} S_{+}^{j+1} d_{+}^{l−1}z) ∗_{i} S_{+}^{i+1} d_{+}^{l−1}t
Y = S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} ([y] ∗_{j} S_{+}^{j+1} d_{+}^{l−1}t)
Z = (S_{−}^{j+1} d_{−}^{l−1}x ∗_{j} [z]) ∗_{i} S_{+}^{i+1} d_{+}^{k−1}t
T = S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} (S_{−}^{j+1} d_{−}^{l−1}j ∗_{j} [t])

But i + 1 < j + 1 so that the exchange rule applies and we get

[B] = (T ∗_{i+1} Z) ∗_{j+1} (Y ∗_{i+1} X)  (56)

Let us evaluate T ∗_{i+1} Z: by distributing the identities,

T ∗_{i+1} Z = (U ∗_{j} U′) ∗_{i+1} (V ∗_{j} V′)  (57)

where

U = S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} S_{−}^{j+1} d_{−}^{l−1}y
U′ = S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} [t]
V = S_{−}^{j+1} d_{−}^{l−1}x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}t
V′ = [z] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}t

Here the argument splits in two cases:

Case 1 . Suppose i + 1 < j. By applying exchange to (57):

T ∗_{i+1} Z = (U ∗_{i+1} V) ∗_{j+1} (U′ ∗_{i+1} V′)  (58)

First

U′ ∗_{i+1} V′ = (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} [t]) ∗_{i+1} ([z] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}t)
= (S_{−}^{i+1} d_{−}^{k−1}z ∗_{i} [t]) ∗_{i+1} ([z] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}t)
= [z ∗_{i} t]

because S_{−}^{i+1} d_{−}^{k−1}x = S_{−}^{i+1} d_{−}^{k−1}z On the other hand

U ∗_{i+1} V = (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} S_{−}^{j+1} d_{−}^{l−1}y) ∗_{i+1} (S_{−}^{j+1} d_{−}^{l−1}x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}t)
= (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} S_{−}^{j+1} d_{−}^{l−1}y) ∗_{i+1} (S_{−}^{j+1} d_{−}^{l−1}x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}y)
= S_{−}^{j+1} d_{−}^{l−1}(x ∗_{i} y)

because S_{+}^{i+1} d_{+}^{k−1}t = S_{+}^{i+1} d_{+}^{k−1}y, and the last step is a particular case of Lemma A.8.

Now

T ∗_{i+1} Z = S_{−}^{j+1} d_{−}^{l−1}(x ∗_{i} y) ∗_{j} [z ∗_{i} t]

and of course the same arguments show that

Y ∗_{i+1} X = [x ∗_{i} y] ∗_{j} S_{+}^{j+1} d_{+}^{l−1}(z ∗_{i} t)

such that

[B] = [(x ∗_{i} y) ∗_{j} (z ∗_{i} t)] = [A]

Case 2 . Suppose i + 1 = j. Here

T ∗_{i+1} Z = T ∗_{j} Z
= (U ∗_{j} U′) ∗_{j} (V ∗_{j} V′)
= U ∗_{j} (U′ ∗_{j} V) ∗_{j} V′

and we rewrite U′ ∗_{j} V as Ṽ ∗_{j} Ũ′ where

Ũ′ = S_{−}^{i+1} d_{−}^{k−1}z ∗_{i} [t]
Ṽ = T_{−}^{j+1,3} d_{−}^{l−1}x ∗_{i} T_{−}^{j} d_{−}^{l}t

In fact

V = S_{−}^{j+1} d_{−}^{l−1}x ∗_{i} S_{+}^{i+1} d_{+}^{k−1}t
= T_{−}^{j+1,3} d_{−}^{l−1}x ∗_{i} [d_{+}^{l+1}x] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}t
= T_{−}^{j+1,3} d_{−}^{l−1}x ∗_{i} T_{+}^{i+1} d_{+}^{k−1}t

but d_{−}^{l} T_{−}^{j+1,3} d_{−}^{l−1}x = S_{−}^{i+1} d_{−}^{k−1}x and d_{+}^{l}[t] = T_{+}^{i+1} d_{+}^{k−1}t such that exchange may be applied to U′ ∗_{j} V, giving

U′ ∗_{j} V = (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} [t]) ∗_{j} (T_{−}^{j+1,3} d_{−}^{l−1}x ∗_{i} T_{+}^{i+1} d_{+}^{k−1}t)
= T_{−}^{j+1,3} d_{−}^{l−1}x ∗_{i} [t]
= (T_{−}^{j+1,3} d_{−}^{l−1}x ∗_{i} T_{−}^{j} d_{−}^{l}t) ∗_{j} (S_{−}^{i+1} d_{−}^{k−1}z ∗_{i} [t])

The last equality comes from

d_{−}^{l+1}[t] = T_{−}^{j} d_{−}^{l}t

and

d_{+}^{l+1} T_{−}^{j+1,3} d_{−}^{l−1}x = S_{−}^{i+1} d_{+}^{l}x = S_{−}^{i+1} d_{−}^{k−1}z

Now

Ũ′ ∗_{j} V′ = (S_{−}^{i+1} d_{−}^{k−1}z ∗_{i} [t]) ∗_{j} ([z] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}t)
= (S_{−}^{i+1} d_{−}^{k−1}z ∗_{i} [t]) ∗_{i+1} ([z] ∗_{i} S_{+}^{i+1} d_{+}^{k−1}t)

This proves

Ũ′ ∗_{j} V′ = [z ∗_{i} t]  (59)

Finally

U ∗_{j} Ṽ = (S_{−}^{i+1} d_{−}^{k−1}x ∗_{i} S_{−}^{j+1} d_{−}^{l−1}y) ∗_{j} (T_{−}^{j+1,3} d_{−}^{l−1}x ∗_{i} T_{−}^{j} d_{−}^{l}t)  (60)

But (37) gives

d_{−}^{l+1} T_{−}^{j+1,3} d_{−}^{l−1}x = d_{−} T_{−}^{j+1,3} d_{−}^{l−1}x
= T_{−}^{j,2} d_{−}^{k−1}x
= S_{−}^{i+1} d_{−}^{k−1}x

and also

d_{+}^{l+1} S_{−}^{j+1} d_{−}^{l−1}y = d_{+} S_{−}^{j+1} d_{−}^{l−1}y
= d_{+} T_{−}^{j+1,2} d_{−}^{l−1}y
= T_{−}^{j} d_{+}^{l}y
= T_{−}^{j} d_{−}^{l}t

Thus exchange may be applied to (60), so that

U ∗_{j} Ṽ = T_{−}^{j+1,3} d_{−}^{l−1}x ∗_{i} S_{−}^{j+1} d_{−}^{l−1}y
= T_{−}^{j+1,3} d_{−}^{l−1}x ∗_{i} T_{−}^{j+1,3} d_{−}^{l−1}y ∗_{i} [d_{+}^{l+1}y]
= T_{−}^{j+1,3} d_{−}^{l−1}(x ∗_{i} y) ∗_{i} [d_{+}^{l+1}y]

because of (50) and finally

U ∗_{j} Ṽ = S_{−}^{j+1} d_{−}^{l−1}(x ∗_{i} y)  (61)

by using

d_{+}^{l+1}y = d_{+}^{l+1}(x ∗_{i} y)

Now (59) and (61) show that

T ∗_{i+1} Z = U ∗_{j} (U′ ∗_{j} V) ∗_{j} V′
= U ∗_{j} (Ṽ ∗_{j} Ũ′) ∗_{j} V′
= (U ∗_{j} Ṽ) ∗_{j} (Ũ′ ∗_{j} V′)
= S_{−}^{j+1} d_{−}^{l−1}(x ∗_{i} y) ∗_{i+1} [z ∗_{i} t]

By symmetry

Y ∗_{i+1} X = [x ∗_{i} y] ∗_{j} S_{+}^{j+1} d_{+}^{l−1}(z ∗_{i} t)

so that in this case again

[B] = [(x ∗_{i} y) ∗_{j} (z ∗_{i} t)] = [A]

References

[1] D. Anick. On the homology of associative algebras. Trans.Am.Math.Soc., 296:641– 659, 1986.

[2] J. Bénabou. Introduction to bicategories. In Reports of the Midwest Category Seminar, volume 47, pages 1–77, 1967.

[3] D. Bourn. Another denormalization theorem for abelian chain complexes. Journal of Pure and Applied Algebra, 66(3):229–249, 1990.

[4] A. Burroni. Higher-dimensional word problems with applications to equational logic. Theoretical Computer Science, 115:43–62, 1993.

[5] A. Burroni. Présentations des ∞-catégories. application: les orientaux simpliciaux et cubiques. manuscript, 2001.

[6] A. Burroni and J. Penon. Une construction d’un nerf des ∞-catégories. In Catégories, Algèbres, Esquisses et Néo-Esquisses, pages 45–55. Université de Caen, 1994.

[7] S. Crans. On Combinatorial Models for Higher Dimensional Homotopies. PhD thesis, Universiteit Utrecht, 1995.

[8] R. Cremanns and F. Otto. Finite derivation type implies the homological finiteness condition F P_{3}. J.Symb.Comput, 18(2):91–112, 1994.

[9] P. Gaucher. Homotopy invariants of higher dimensional categories and concurrency in computer science. Mathematical Structures in Computer Science, 10(4):481–524, 2000.

[10] E. Goubault. Geometry and concurrency: A user’s guide. Mathematical Structures in Computer Science, 10(4):411–425, 2000.

[11] Y. Kobayashi. Complete rewriting systems and homology of monoid algebras. Journal of Pure and Applied Algebra, 65(3):263–275, 1990.

[12] Y. Lafont. A new finiteness condition for monoids presented by complete rewriting systems. Journal of Pure and Applied Algebra, 98(3):229–244, 1995.

[13] Y. Lafont and A. Prouté. Church-Rosser property and homology of monoids. Mathematical Structures in Computer Science, 1(3):297–326, 1991.

[14] J. Penon. Approche polygraphique des ∞-catégories non strictes. Cahiers de Topologie et Géométrie Différentielle Catégoriques, 40:31–80, 1999.

[15] C. Squier. Word problems and a homological finiteness condition for monoids. Journal of Pure and Applied Algebra, 49:201–217, 1987.

[16] C. Squier, F. Otto, and Y. Kobayashi. A finiteness condition for rewriting systems. Theoretical Computer Science, 131:271–294, 1994.

[17] R. Street. The algebra of oriented simplexes. Journal of Pure and Applied Algebra, 49:283–335, 1987.

Équipe PPS, Université Paris 7-CNRS, 2 pl. Jussieu, Case 7014 F75251 Paris Cedex 05

Email: metayer@logique.jussieu.fr

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/11/7/11-07.{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, Robert Rosebrugh,

rrosebrugh@mta.ca.

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

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: 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, Palo Alto Research Center: paiva@parc.xerox.com 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@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 Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz 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