Theory and Applications of Categories, Vol. 9, No. 5, 2001, pp. 92–105.

CLASSIFYING SPACES OF CATEGORIES AND TERM REWRITING

MAURIZIO G. CITTERIO

ABSTRACT. In this paper we show how collapsing schemes can give us information on the homotopy type of the classifying space of a small category, when this category is presented by a complete rewrite system.

1. Introduction

Given a small category C, the classifying space BC of C is constructed by assigning to C its nerve NC and then taking the geometric realization BC = |NC| of the simplicial set NC. The definition of the geometric realization functor | | is relatively plain and it is well-known that the space |X| associated to a simplicial set X is a CW-complex whose ncells correspond to non degenerate n-simplices of X ([Mil57]). But simplicial sets tend to be very large objects and the number of non degenerate simplices is usually much greater than the number of cells which are necessary to describe the homotopy type of realization. Can we reduce this number? Kenneth S. Brown and Ross Geoghegan ([BG84], [Bro92]) introduced the notion of collapsing scheme. This scheme distinguishes a class of non degenerate simplices of a simplicial set X, which are called the essential simplices of X. The main theorem on collapsing schemes states that the geometric realization |X| of the simplicial set X has the homotopy type of a CW-complex E(X) whose n-cells correspond to essential n-simplices of X. When we consider a “complete presentation” of a monoid M (i.e. a presentation given by a complete rewrite system), then the classifying space of M can be obtained as the geometric realization of a simplicial set X. The paper [Bro92] shows that this simplicial set X is canonically endowed with a collapsing scheme.

We recall the definition of collapsing scheme in Section 2. Then we show that simplicial sets endowed with collapsing schemes form a category CSet^{Δ^{op}} and that the construction E can be viewed as a functor E : CSet^{Δ^{op}} → Top into the category of topological spaces and maps. Moreover, the canonical homotopy equivalence |X| → E(X) is a natural transformation q : | | ⇒ E from the geometric realization to the functor E. In Section 3, we recall basic definitions and facts on rewrite systems (main references are [ES87], [Str96]). We reach the main result in Section 4: a functorial extension to categories of the construction given by K. S. Brown for monoids. The power of this technique is emphasized by an example, where we give a one-line proof of the fact that the classifying space of a free category is (up to homotopy) the geometric realization of its generating graph.

Received by the editors 2000 December 12 and, in revised form, 2001 December 9.

Published on 2001 December 16 in the volume of articles from CT2000.

2000 Mathematics Subject Classification: 18G30, 55P15.

Key words and phrases: Collapsing scheme, simplicial set, classifying space, rewrite system.

\begin{matrix}c \\ ◯ \end{matrix} Maurizio G. Citterio, 2001. Permission to copy for private use granted.

This paper is only a small part of a wider work (whose starting point is [Cit00]) on collapsing schemes and their applications to bisimplicial sets and classifying spaces of 2-categories.

2. Collapsing schemes

Let X be a simplicial set whose face operators are denoted by d, and degenerate operators by s. We shall write D for the graded set of degenerate simplices (i.e. the simplices which are in the image of s), and X^{nd} = X − D for the graded set of non-degenerate simplices. Assume that non-degenerate simplices have been partitioned into three classes: E = {essential simplices}, R = {redundant simplices}, C = {collapsible simplices}. We shall say that (E, R, C) is a partition of X^{nd} and write X^{nd} = E ⊔ R ⊔ C (equivalently (E, R, C, D) is a partition of X and X = E ⊔ R ⊔ C ⊔ D); this means that for every n ≥ 0 we have X_{n}^{nd} = E_{n} ⊔ R_{n} ⊔ C_{n}.

Writing [m] = {0, 1, …, m} for the standard finite set with m + 1 elements, assume that there exist functions c_{n} : R_{n} → C_{n+1} and ι_{n} : R_{n} → [n + 1] such that, for every redundant n-simplex τ we have d_{ι_{n}(τ)}c_{n}(τ) = τ. Functions c_{n} and ι_{n} define the following relation >_{R_{n}} on R_{n}:

τ >_{R_{n}} τ′ (τ, τ′ ∈ R_{n}) if and only if τ′ = d_{j}c_{n}(τ) (j ≠ ι_{n}(τ))

and we say that τ′ is an immediate predecessor of τ. The relation >_{R_{n}} is said to be noetherian (or terminating or well-founded) when there is no infinite descending chain τ > τ′ > τ′′ > … of redundant n-simplices.

2.1. Definition. A collapsing scheme C = (E, R, C; c, ι) on a simplicial set X consists of

1. a partition (E, R, C, D) of X with C_{0} empty

2. a function c_{n} : R_{n} → C_{n+1} for every n ≥ 0

3. a function ι_{n} : R_{n} → [n + 1] for every n ≥ 0 and axioms

CS1. ∀n ≥ 0, the function c_{n} : R_{n} → C_{n+1} is a bijection and d_{ι_{n}}c_{n} = id_{R_{n}} CS2. ∀n ≥ 0, the immediate predecessor relation >_{R_{n}} is noetherian.

The axiom CS2 implies that a chain of redundant simplices cannot include twice the same redundant simplex. In particular, for any τ ∈ R_{n}, we cannot have τ > τ and there exists no index i ≠ ι(τ) such that τ = d_{i}c(τ). We say that the redundant τ is the free face of the collapsible σ = c_{n}(τ). The axiom CS1 implies that every redundant simplex is the free face of a unique collapsible simplex.

Since every redundant simplex has only finitely many immediate predecessors, there cannot exist arbitrarily long descending chains. The maximum length of a chain τ >_{R_{n}} τ′ >_{R_{n}} ⋯ starting from τ will be called the height of τ and written h(τ).

2.2. Theorem. [K. S. Brown] Let X be a simplicial set with a collapsing scheme C. The geometric realization |X| of X admits a canonical quotient CW-complex E, whose cells are in 1–1 correspondence with essential simplices of X. The quotient map q_{X} : |X| → E is a homotopy equivalence; it maps each open essential cell of |X| homeomorphically onto the corresponding open cell of E and it maps each collapsible (n + 1)-cell into the n-skeleton of E.

We present here the proof of [Bro92] mainly because we shall need the constructions and notations. It also describes the geometry of collapsing schemes. We shall use the same notation for simplices of the simplicial set and corresponding cells of the geometric realization; as usual we shall identify degenerate cells with cells of lower dimension.

Proof. The geometric realization of a simplicial set X endowed with a collapsing scheme can be viewed as the colimit of the sequence of topological spaces and cofibrations

\xymatrix{X0^{e} \ar@{^{(}->}[r]^{j_{0}} & X0^{+} \ar@{^{(}->}[r] & X1^{e} \ar@{^{(}->}[r]^{j_{1}} & ⋯ \ar@{^{(}->}[r] & Xn^{e} \ar@{^{(}->}[r]^{j_{n}} & Xn^{+} \ar@{^{(}->}[r] & Xn+1^{e} \ar@{^{(}->}[r]^{j_{n+1}} & ⋯}

where X0^{e} consists of essential 0-cells, Xn^{+} is obtained from Xn^{e} by adjoining redundant n-cells and collapsible (n + 1)-cells, and Xn+1^{e} is obtained from Xn^{+} by adjoining essential (n + 1)-cells. The description of this filtration is the key of the proof. After CS2, if R_{n} is not empty, there exist redundant n-simplices whose height is 1. Let τ be one of them. Clearly the faces of τ are (n − 1)-cells and so we can adjoin it to Xn^{e} obtaining the space Xn^{e}(τ). Let c_{n}(τ) be the collapsible of τ. Observe that the faces of c_{n}(τ) are τ ∈ Xn^{e}(τ) and either essential or collapsible or degenerate n-cells which are in Xn^{e}. This means that Xn^{e} is a strong deformation retract of the space Xn^{e}(τ, c_{n}(τ)) obtained from Xn^{e}(τ) by adjoining c_{n}(τ). Chosen a retraction (collapsing map) from the geometric simplex Δ^{n+1} onto its boundary deprived of the open ι(τ)-face Λ_{ι(τ)}^{n+1}, this induces an elementary retraction Xn^{e}(τ, c_{n}(τ)) → Xn^{e} which collapses the (n + 1)-cell c_{n}(τ) onto its boundary deprived of the open free face τ^{∘}. Since c_{n} : R_{n} → C_{n+1} is a bijection, Xn^{e} is a deformation retract of the space Xn^{e,1} obtained from Xn^{e} by adjoining all the redundant ncells with height one and the corresponding collapsible (n+1)-cells. Gluing the elementary retraction, we get a homotopy inverse of the inclusion Xn^{e} ↪ Xn^{e,1}. Let Xn^{e,k} be the space obtained from Xn^{e} by attaching all the redundant n-cells with height less or equal to k and the corresponding collapsible cells. Observe that, given a redundant τ′ with height k + 1, every face of its collapsible c_{n}(τ′) other than its free face τ′ is either an immediate predecessor of τ′ (hence with height less or equal to k) or else is essential, collapsible or degenerate. These faces are therefore already present in Xn^{e,k} and we can proceed as above. We have factored the inclusion j_{n} : Xn^{e} ↪ Xn^{+} as a sequence of strong deformation retracts

Xn^{e} ⊆ Xn^{e,1} ⊆ Xn^{e,2} ⊆ ⋯ ⊆ Xn^{e,k} ⊆ Xn^{e,k+1} ⊆ ⋯

Observe that, fixed for any i ∈ [n + 1] a collapsing map Δ^{n+1} → Λ_{i}^{n+1}, retractions Xn^{e,k+1} → Xn^{e,k} are canonically given. This proves that the cofibration j_{n} is a homotopy equivalence with a canonical homotopy inverse r_{n}.

\xymatrix{Xn^{e} \ar@{^{(}->}[r]^{j_{n}} & Xn^{+} \ar[l]^{r_{n}}}

We finally consider the diagram

[figure: X0^{e}; j_{0}; X0^{+}; r_{0}; X1^{e}; j_{1}; \overline{r_{0}}; X1^{+}; \overline{r_{0}}r_{1}; X2^{e}; j_{2}; \overline{\overline{r_{0}}r_{1}}; X2^{e}; \overline{\overline{r_{0}}r_{1}}r_{2}; ⋯; E_{0}; E_{0}; E_{1}; E_{1}; E_{2}; E_{2}; ⋯]

where E_{0} = X0^{e}, the space E_{n+1} is the push-out E_{n} +_{X_{n}^{+}} Xn+1^{e} and overlined maps are induced by push-outs; horizontal maps are cofibration, while vertical maps are homotopy equivalences. The colimit of this diagram gives us the required canonical projection q_{X} : |X| → E(X).

2.3. Example. Consider the category C that we picture below without drawing composites and identities

\xymatrix{x & y \ar[l]^{c} \ar[l]_{a} & z \ar[l]^{d} \ar[l]_{b}}

The classifying space BC of C is a CW-complex whose cells are in 1-1 correspondence with non-degenerate simplices of the nerve NC :

(NC)_{0}^{nd} = {x, y, z} ,  (NC)_{1}^{nd} = {a, b, c, d, ab, ad, cb, cd} ,
(NC)_{2}^{nd} = {(a, b), (a, d), (c, b), (c, d)} ,  (NC)_{n}^{nd} = ∅ (n ≥ 3),

then BC is a space which has surely the same homotopy type as S^{1} ∨ S^{1}. The following collapsing scheme makes this intuition rigorous:

E_{n} R_{n} ⟶^{c_{n}} C_{n+1}
n = 0 z y ↦  d
x ↦  c
n = 1 a, b fg ↦ (f, g)
n ≥ 2 -  -  -  -

where f ∈ {a, c}, g ∈ {b, d} and ι_{n} = 1 (constant function) for every n. Now we can state that BC ∼ S^{1} ∨ S^{1}, since it has the same homotopy type as a CW-complex with one 0-cell and two 1-cells.

Observe that identifications need some care when we want to construct the geometric realization of a simplicial set starting from a collapsing scheme; even in this simple example (with the obvious meaning of symbols) d_{1}a = x is not essential, but it is identified with z collapsing first c over y and then d over x.

2.4. Example. Any (small) category with terminal object is contractible.

Let C be a category with a terminal object ∗ (i.e. for any object x ∈ C, there exists a unique arrow x → ∗). A collapsing scheme (E, R, C; c, ι) on the nerve of C is defined by

E_{0} = {∗}, R_{0} = ObjC − {∗} and, for n ≥ 1, E_{n} = ∅, R_{n} = {x_{0} ⟵^{f_{1}} ⋯ ⟵^{f_{n}} x_{n} : x_{0} ≠ ∗},

C_{n} = {∗ ← x_{1} ⟵^{f_{2}} ⋯ ⟵^{f_{n}} x_{n}} with c_{n}(x_{0} ⟵^{f_{1}} ⋯ ⟵^{f_{n}} x_{n}) = ∗ ← x_{0} ⟵^{f_{1}} ⋯ ⟵^{f_{n}} x_{n} and

ι_{n} = 0 (constant function). Clearly c_{n} is a bijection and any redundant n-simplex τ has height h(τ) = 1 since for i ≠ 0, d_{i}c(τ) is either collapsible or degenerate. CS1 and CS2 are verified and BC ∼ E(NC) is contractible.

Simplicial sets endowed with a collapsing scheme are the objects of the category CSet^{Δ^{op}} whose arrows are C-morphisms defined as follows.

Writing C^{X} = (E^{X}, R^{X}, C^{X}; c^{X}, ι^{X}) for a collapsing scheme on the simplicial sets X, and writing f|_{S} for the graded function obtained from a simplicial function f : X → Y by restricting it to the graded subset S of X, we say that 2.5. Definition. A C-morphism f : C^{X} → C^{Y} is a simplicial function f : X → Y such that

1. f respects the partitions, i.e. Imf|_{E^{X}} ⊆ E^{Y} , Imf|_{R^{X}} ⊆ R^{Y} , Imf|_{C^{X}} ⊆ C^{Y} ;

2. f commutes with c and ι , i.e. ∀x ∈ R^{X}, fc^{X}(x) = c^{Y} f(x) , ι^{Y} f(x) = ι^{X}(x).

We are going to show the functoriality of the construction E : CSet^{Δ^{op}} → Top and the naturality of the canonical projection q : | | ⇒ E (where the geometric realization functor is defined from CSet^{Δ^{op}} by composing it with the functor which forgets collapsing schemes). We first need to state some lemmas. 2.6. Lemma. Any C-morphism f : C^{X} → C^{Y} preserves the immediate predecessor relation and the height of redundant simplices.

Going back to the construction introduced in the proof of Theorem 2.2, we emphasize the following observation. 2.7. Lemma. Let C^{X} and C^{Y} be collapsing schemes for the simplicial sets X and Y. If f : X → Y is a simplicial function such that Imf|_{E^{X}} ⊆ E^{Y} ∪D^{Y} and Imf|_{C^{X}} ⊆ C^{Y} ∪D^{Y}, then f gives rise to the following commutative diagram of spaces and maps, where fn^{e} and fn^{+} are restrictions of the geometric realization |f| of f.

\xymatrix{X0^{e} \ar@{^{(}->}[r]^{j_{0}^{X}} \ar[d]_{f_{0}^{e}} & X0^{+} \ar@{^{(}->}[r] \ar[d]_{f_{0}^{+}} & X1^{e} \ar@{^{(}->}[r]^{j_{1}^{X}} \ar[d]_{f_{1}^{e}} & ⋯ \ar@{^{(}->}[r] & Xn^{e} \ar@{^{(}->}[r]^{j_{n}^{X}} \ar[d]_{f_{n}^{e}} & Xn^{+} \ar@{^{(}->}[r] \ar[d]_{f_{n}^{+}} & Xn+1^{e} \ar@{^{(}->}[r]^{j_{n+1}^{X}} \ar[d]_{f_{n+1}^{e}} & ⋯ \\ Y0^{e} \ar@{^{(}->}[r]_{j_{0}^{Y}} & Y0^{+} \ar@{^{(}->}[r] & Y1^{e} \ar@{^{(}->}[r]_{j_{1}^{Y}} & ⋯ \ar@{^{(}->}[r] & Yn^{e} \ar@{^{(}->}[r]_{j_{n}^{Y}} & Yn^{+} \ar@{^{(}->}[r] & Yn+1^{e} \ar@{^{(}->}[r]_{j_{n+1}^{Y}} & ⋯}

The colimit of the diagram is |f| : |X| → |Y |.

For any cofibration j_{n}^{X} : Xn+1^{e} ↪ Xn^{+}, we have introduced a canonical retract r_{n}^{X} : Xn^{+} → Xn+1^{e}. A C-morphism verifies the hypotheses of Lemma 2.7 and

2.8. Lemma. Any C-morphism f : C^{X} → C^{Y} commutes with r, i.e. fn^{e}r_{n}^{X} = r_{n}^{Y} fn^{+} for any n.

We are now ready to draw the following diagram which arises from a C-morphism f : C^{X} → C^{Y}.

[figure: E_{0}^{X}; e_{0}; E_{0}^{X}; e_{0}; E_{1}^{X}; e_{1}; E_{1}^{X}; e_{1}; E_{2}^{X}; e_{2}; ⋯; X0^{e}; j_{0}^{X}; f_{0}^{e}; X0^{+}; r_{0}^{X}; f_{0}^{+}; X1^{e}; \overline{r_{0}^{X}}; j_{1}^{X}; f_{1}^{e}; X1^{+}; \overline{r_{0}^{X}}r_{1}^{X}; f_{1}^{+}; X2^{e}; \overline{\overline{r_{0}^{X}}r_{1}^{X}}; f_{2}^{e}; ⋯; E_{0}^{Y}; E_{0}^{Y}; E_{1}^{Y}; E_{1}^{Y}; E_{2}^{Y}; ⋯; Y0^{e}; j_{0}^{Y}; Y0^{+}; r_{0}^{Y}; Y1^{e}; \overline{r_{0}^{Y}}; j_{1}^{Y}; Y1^{+}; \overline{r_{0}^{Y}} r_{1}^{Y}; Y2^{e}; \overline{\overline{r_{0}^{Y}} r_{1}^{Y}}; ⋯]  (1)

The upper and the lower parts are the constructions for C^{X} and C^{Y} described in the proof of Theorem 2.2. Defined the map e_{0} : E_{0}^{X} → E_{0}^{Y} as e_{0} := f0^{e} : X0^{e} → Y0^{e}, the first cube (the one with index zero) commutes. The map e_{1} : E_{1}^{X} → E_{1}^{Y} is induced by the push-outs which are the upper and the lower squares of the second cube. So the third cube (with index one) commutes and we can iterate. Thus we obtain the commutative diagram

\xymatrix{E_{0}^{X} \ar@{^{(}->}[r] \ar[d]_{e_{0}} & E_{1}^{X} \ar@{^{(}->}[r] \ar[d]_{e_{1}} & E_{2}^{X} \ar@{^{(}->}[r] \ar[d]_{e_{2}} & E_{3}^{X} \ar@{^{(}->}[r] \ar[d]_{e_{3}} & ⋯ \\ E_{0}^{Y} \ar@{^{(}->}[r] & E_{1}^{Y} \ar@{^{(}->}[r] & E_{2}^{Y} \ar@{^{(}->}[r] & E_{3}^{Y} \ar@{^{(}->}[r] & ⋯}

whose colimit is a map Ef : E^{X} → E^{Y}.

2.9. Proposition. The assignment [figure: f; Ef] defines a functor

E : CSet^{Δ^{op}} → Top

and the canonical projection q_{X} : |X| → E^{X} is a natural transformation

q : | | ⇒ E : CSet^{Δ^{op}} → Top .

Proof. The functoriality of E comes from standard properties of colimits (i.e. the functoriality of coLim). The naturality of the canonical projection q arises from the diagram

\xymatrix{|X| \ar[d]_{|f|} \ar[r]^{q_{X}} & E^{X} \ar[d]^{Ef} \\ |Y | \ar[r]_{q_{Y}} & E^{Y}}

obtained as colimit of diagram (1).

3. Term rewriting for categories

In this section we recall definitions and basic facts on term rewriting for categories. 3.1. Graphs, words and free categories. An n-graph G consists of n + 1 sets G_{i} and n pairs of functions s_{i}, t_{i} : G_{i+1} → G_{i} such that s_{i−1}s_{i} = s_{i−1}t_{i} and t_{i−1}s_{i} = t_{i−1}t_{i} for every i < n.

\xymatrix{G : G_{0} & G_{1} \ar[l]^{s_{0}} \ar[l]_{t_{0}} & G_{2} \ar[l]^{s_{1}} \ar[l]_{t_{1}} & ⋯ \ar[l]^{s_{2}} \ar[l]_{t_{2}} & G_{n} \ar[l]^{s_{n−1}} \ar[l]_{t_{n−1}}}

Elements of G_{0} are called objects (or vertices or points); elements of G_{1} are called arrows (or edges); elements of G_{i} are called i-arrows. The functions s and t are called source and target. We can picture an arrow f ∈ G_{1} as t_{0}(f) ⟵^{f} s_{0}(f) . A typical picture of a 2-arrow α ∈ G_{2} will be

[figure: x; y; g; f; α]

where f, g ∈ G_{1} and x, y ∈ G_{0} with f = s_{1}α, g = t_{1}α and x = t_{0}f = t_{0}g = t_{0}s_{1}(α) = t_{0}t_{1}(α), y = s_{0}f = s_{1}g = s_{0}s_{1}(α) = s_{0}t_{1}(α).

A morphism φ : G → G′ of n-graphs is an (n+1)-tuple (φ_{i})_{0}^{n} of functions φ_{i} : G_{i} → G′_{i} such that φ_{i}t_{i} = t_{i}φ_{i+1} and φ_{i}s_{i} = s_{i}φ_{i+1} for every i < n. The category n-Graph consists of n-graphs and morphisms of n-graphs. Observe that 0-Graph is the category of sets, while 1-Graph is the category Graph of graphs.

We can get a graph by truncating an n-graph G; in particular, we shall write sk_{i,i+1}G for the graph

\xymatrix{sk_{i,i+1}G : G_{i} & G_{i+1} \ar[l]^{s_{i}} \ar[l]_{t_{i}}} 0 ≤ i < n

A pair of adjoint functors links the category of graphs and the category of small categories. The forgetful functor U : Cat → Graph assigns the underlying graph C : C_{0} ⇇ C_{1} to the small category C, where C_{0} is the set of objects, C_{1} is the set of arrows of C, source and target are domain and codomain. The left adjoint F : Graph → Cat of U assigns the free category F G to a graph G. Objects of F G are the objects of G,

while arrows of F G are words in G, described as follows. Given a graph \xymatrix{G : G_{0} & G_{1} \ar[l]^{s} \ar[l]_{t}}, a word (or path) w of length l(w) = m is an alignment w = (x_{0}, f_{1}, x_{1}, f_{2}, ⋯, f_{m}, x_{m}) = (f_{1}, f_{2}, ⋯, f_{m}) where x_{∗} ∈ G_{0}, f_{∗} ∈ G_{1}, x_{0} = t(f_{1}), s(f_{i}) = x_{i} = t(f_{i+1}) (1 ≤ i < m), x_{m} = s(f_{m}).

w = \xymatrix{x_{0} & x_{1} \ar[l]_{f_{1}} & ⋯ \ar[l]_{f_{2}} & x_{m} \ar[l]_{f_{m}}} = [figure: f_{1}; ⋯; f_{2}; f_{m}]

An empty word w is a word of length zero; this means that w = (x_{0}) and there exits exactly one empty word for every object of G_{0}. A word of length one (that is an element of G_{1}) may also be called letter and G_{1} may be called the alphabet. We thus obtain a new graph (the underlying graph of the category F G)

\xymatrix{F G : G_{0} & F G_{1} \ar[l]^{s} \ar[l]_{t}}

where F G_{1} is the set of words of finite length and s and t are defined by s(f_{1}, f_{2}, …, f_{m}) = s(f_{m}) and t(f_{1}, f_{2}, …, f_{m}) = t(f_{1}). Two words w and w′ are composable when s(w) = t(w′) and their composition w ∘_{F G} w′ is the concatenation ww′

w ∘_{F G} w′ = (f_{1}, …, f_{m}) ∘_{F G} (g_{1}, …, g_{k}) = (f_{1}, …, f_{m}, g_{1}, …, g_{k}) = ww′.

Empty words are the identities. Observe that a letter f ∈ G_{1} is a word of length one in F G_{1}, thus a word w can be written as

w = (f_{1}, f_{2}, …, f_{m}) = f_{1}f_{2} ⋯ f_{m} = f_{1} ∘_{F G} f_{2} ∘_{F G} ⋯ ∘_{F G} f_{m} .

A word w′ is a sub-word of a word w (w′ ⊆ w) when w = uw′v (u and v words). A non-empty word w′ is a proper sub-word of w (w′ ⊂ w) when either u or v is not empty. A non-empty word w′ is an initial sub-word of w when w = w′v. Observe that if w = (x_{0}, f_{1}, x_{1}, f_{2}, ⋯, f_{m}, x_{m}), then any empty word (x_{i}) with 0 ≤ i ≤ m is a sub-word of w.

3.2. Rewrite systems. A rewrite system R = (G, R) is a 2-graph such that sk_{01}R is the free category F G over the graph G

\xymatrix{R : G_{0} & F G_{1} \ar[l]^{s_{0}} \ar[l]_{t_{0}} & R \ar[l]^{s_{1}} \ar[l]_{t_{1}}}

R is called the set of rewrite rules. A morphism of rewrite systems φ : R → R′ is a pair φ = (φ_{G}, φ_{R}) where φ_{G} = (φ_{0}, φ_{1}) : G → G′ is a morphism of graphs and φ_{R} : R → R′ is a function such that (F φ_{G}, φ_{R}) is a morphism of 2-graphs. We write RS for the category of rewrite systems.

The whiskering wR of a rewrite system R = (G, R) is the 2-graph

\xymatrix{wR : G_{0} & F G_{1} \ar[l]^{s_{0}} \ar[l]_{t_{0}} & wR \ar[l]^{s′_{1}} \ar[l]_{t′_{1}}}

where wR = {(u, α, v) ∈ F G_{1} × R × F G_{1} : s_{0}(u) = t_{0}t_{1}(α), s_{0}s_{1}(α) = t_{0}(v)} is the set of reductions (or applications of rewrite rules, or elementary derivations, or whiskered 2arrows). Source and target are defined by s′_{1}(u, α, v) = u(s_{1}α)v and t′_{1}(u, α, v) = u(t_{1}α)v. A whiskered 2-arrow (u, α, v) may be viewed as the “horizontal composition” of α with u (on left) and v (on right).

[figure: x; y; u(t_{1}α)v; u(s_{1}α)v; (u,α,v); =; x; y; u; z; t_{1}α; s_{1}α; α; t; v]

When no ambiguity occurs, we write uαv (or also u∘_{F G} α ∘_{F G} v) instead of (u, α, v), while, given a reduction p = (u, α, v), we write u′pv′ (or also u′ ∘_{F G} p ∘_{F G} v′) for (u′u, α, vv′).

The derivation scheme dR of a rewrite system R = (G, R) is the 2-graph

\xymatrix{dR : G_{0} & F G_{1} \ar[l]^{s_{0}} \ar[l]_{t_{0}} & dR \ar[l]^{s′′_{1}} \ar[l]_{t′′_{1}}}

where dR is the set of paths of elementary derivations (called chains of reductions or simply derivations).

[figure: .; u_{m}; .; α_{m}; .; u_{m−1}; .; α_{m−1}; .; ⋮; .; v_{1}; v_{2}; v_{m−1}; v_{m}; .; u_{2}; .; α_{2}; .; u_{1}; .; α_{1}]

A derivation is then a sequence ((u_{1}, α_{1}, v_{1}), (u_{2}, α_{2}, v_{2}), ⋯, (u_{m}, α_{m}, v_{m})) of elementary derivations (u, α, v) ∈ wR such that

u_{i}(s_{1}α_{i})v_{i} = s′_{1}(u_{i}, α_{i}, v_{i}) = t′_{1}(u_{i+1}, α_{i+1}, v_{i+1}) = u_{i+1}(t_{1}α_{i+1})v_{i+1}.

Source and target of a derivation are defined by

s′′_{1}((u_{1}, α_{1}, v_{1}), ⋯, (u_{m}, α_{m}, v_{m})) = s′_{1}(u_{m}, α_{m}, v_{m}) = u_{m}(s_{1}α_{m})v_{m}
t′′_{1}((u_{1}, α_{1}, v_{1}), ⋯, (u_{m}, α_{m}, v_{m})) = t′_{1}(u_{1}, α_{1}, v_{1}) = u_{1}(t_{1}α_{1})v_{1}.

Observe that sk_{12}(dR) is the underlying graph of the category F sk_{12}(wR), when we admit that a derivation can be empty.

A rewrite system R is said to be

• confluent when, for any pair of derivations p : w ⇒ u, p′ : w ⇒ u′ in dR, there exist chains of reductions q : u ⇒ w′, q′ : u′ ⇒ w′ in dR;

• terminating when there is no infinite chain of reductions;

• complete when it is both confluent and terminating.

Before listing some basic facts on rewrite systems, we recall that a word is irreducible when it is not the source of any reduction.

• Sub-words of irreducible words are irreducible.

• Empty sub-words of an irreducible word are irreducible.

• In a complete rewrite system R = (G, R), any word w ∈ F G_{1} can be reduced to a unique irreducible \overline{w} ∈ F G_{1} by a (not necessarily unique) derivation.

• In a complete rewrite system, any empty word is irreducible.

Complete rewrite systems are the objects of the category CRS, whose arrows are those morphisms of rewrite systems which send irreducible words to irreducible words. Observe that CRS is not a full subcategory of RS.

3.3. Categories of normal forms and presentations of categories. Given a rewrite system R = (G, R), and its derivation scheme dR, one usually defines a relation P on the set F G_{1} of words by saying that (w, w′) ∈ P when there exists a derivation form w to w′. The quotient F G_{1}/P̃ of F G_{1} modulo the equivalence relation P̃ generated by P is the set π_{0}(sk_{12}dR) of connected components of sk_{12}dR. An element of the set π_{0}(sk_{12}(dR)) is therefore a class [w] of words belonging to F G_{1}, and w̃ ∈ [w] if and only if then there exist reductions (not necessarily in the same direction) connecting w̃ and w (e.g. w ⇒⇐ ⋯ ⇒⇒⇐ w̃ ). Since a reduction has been defined as a 2-arrow of a 2-graph, all the words in an equivalence class have the same source and target. Writing s_{0}[w] = s_{0}(w) and t_{0}[w] = t_{0}(w), we obtain the graph

\xymatrix{QR : G_{0} & π_{0}(sk_{12}(dR)). \ar[l]^{s_{0}} \ar[l]_{t_{0}}}

If p : w ⇒ w̃ is a reduction and a word w′ is composable on right (or on left) with w, then we have a reduction pw′ : ww′ ⇒ w̃w′ (or w′p : w′w ⇒ w′w̃). This means that a composition law is well defined by [w] ∘_{QR} [w′] = [w ∘_{F G} w′] = [ww′] and the graph QR is indeed a category: the quotient category of the rewrite system R = (G, R). It is well-known that Q is a functor Q : RS → Cat.

A presentation of a (small) category C is a rewrite system R such that the quotient category QR is isomorphic to C.

From QR we obtain the graph of normal forms by choosing a representative for any class [w] of equivalent words. When the rewrite system R is complete, there exists a canonical choice. Let IF G_{1} be the subset of F G_{1} consisting of irreducible words of the complete rewrite system R = (G, R) and let q̄: IF G_{1} → π_{0} (sk_{12}(dR)) be the restriction to IF G_{1} of the quotient function q : F G_{1} → π_{0}(sk_{12}(dR)), q(w) = [w]. Remember now that the completeness of R gives us a function r : F G_{1} → IF G_{1} which assigns to a word w ∈ F G_{1} the corresponding irreducible word r(w) = \overline{w}. It is easy to show that q̄ is a bijection whose inverse is (well-defined by) r̄[w] = r(w). The graph of normal forms IR of a complete rewrite system R

\xymatrix{IR : G_{0} & IF G_{1} \ar[l]^{s_{0}} \ar[l]_{t_{0}}}

is therefore isomorphic to the graph QR. The concatenation of irreducible words is not, a priori, an irreducible word, but we can introduce a composition in IR by defining w ∘_{IR} w′ = r(ww′) = \overline{ww′}. This makes q̄ and r̄ isomorphisms between the quotient category QR and the category of normal forms IR. Therefore the category IR comes from QR by choosing, for each class [w], the unique irreducible word \overline{w} ∈ [w] as normal form and defining a composition such that IR results isomorphic to the category QR. In this way we have defined a functor I : CRS → Cat.

A complete presentation of a (small) category C is a rewrite system R such that the category of normal forms IR is isomorphic to C.

We observed that in a complete rewrite system any object is irreducible, when we think of it as a word of length zero. A priori it is not true that any (1-)arrow is irreducible, but one can easily show that “reducible letters can always be deleted from the alphabet”. In fact, given a complete rewrite system R, there exists a complete rewrite system R^{∗} = (G^{∗}, R^{∗}) such that IR = IR^{∗} and G_{1}^{∗} ⊆ IF G_{1}^{∗}. For this reason one can consider only complete rewrite systems where every letter is irreducible.

4. Collapsing schemes and rewrite systems

We are going to define a canonical collapsing scheme on the nerve NIR of the category of normal forms IR of a complete rewrite system R. When R is a complete presentation of a small category C, then the collapsed space E(NIR) is (up to homotopy) the classifying space BC of C. It is useful to remark now that, given two irreducible words w and w′, we will use both the notations ww′ and w ∘w′, but with different meanings: ww′ = w ∘_{F G} w′ is the concatenation in F G, while w ∘ w′ = w ∘_{IR} w′ is the composition in IR. In particular, the nerve of IR is defined by

(NIR)_{0} = G_{0} , (NIR)_{n} = {(w_{1}, …, w_{n}) : w_{i} ∈ IF G_{1}, s_{0}w_{i} = t_{0}w_{i+1}}

d_{i}(w_{1}, ⋯, w_{n}) = \begin{cases}(w_{2}, …, w_{n}) & i = 0 \\ (w_{1}, …, w_{i} ∘ w_{i+1}, …, w_{n}) & 0 < i < n \\ (w_{1}, …, w_{n−1}) & i = n \end{cases}

s_{i}(w_{1}, …, w_{n}) = (w_{1}, …, w_{i}, id, w_{i+1}, w_{n})

where id is the empty word id = (s_{0}w_{i}) = (t_{0}w_{i+1}).

Here is the construction of the canonical collapsing scheme of NIR.

• Any 0-simplex is essential, that is E_{0} = G_{0} and R_{0} = C_{0} = ∅.

• An n-simplex τ = (w_{1}, …, w_{n}) is essential when it satisfies the following three conditions:

ES1. w_{1} ∈ G_{1} ∩ IF G_{1} (i.e. w_{1} is an irreducible letter);

ES2. w_{i}w_{i+1} (1 ≤ i < n) is reducible;

ES3. the sub-word of w_{i}w_{i+1} (1 ≤ i < n) obtained by deleting the last letter is irreducible.

When a non-degenerate τ is not essential, we may have

1. w_{1} ∉ G_{1} ∩ IF G_{1}. Since the irreducible word w_{1} has length l(w_{1}) ≥ 2, we can write w_{1} = gw′_{1} with g ∈ G_{1} ∩ IF G_{1}. Now τ = (gw′_{1}, w_{2}, …, w_{n}) is redundant with c_{n}(τ) = (g, w′_{1}, w_{2}, …, w_{n}) and ι_{n}(τ) = 1;

2. w_{1} ∈ G_{1} ∩ IF G_{1}. Let e be the largest index such that (w_{1}, …, w_{e−1}) is essential (we will call this (e − 1)-simplex the essential front face of τ).

2.1. If w_{e−1}w_{e} is irreducible, then τ is collapsible.

2.2. If w_{e−1}w_{e} is reducible, then some proper initial sub-word of w_{e−1}w_{e} must be reducible (otherwise (w_{1}, …, w_{e−1}, w_{e}) would be essential). τ is redundant with c_{n}(τ) = (w_{1}, …, w_{e−1}, w′_{e}, w′′_{e}, w_{e+1}, …, w_{n}) and ι_{n}(τ) = e where w′_{e} is the smallest initial sub-word of w_{e} such that w_{e−1}w′_{e} is reducible.

4.1. Proposition. The above data define a collapsing scheme on the nerve N(IR) of the category of normal forms of a complete rewrite system R.

Proof. Axiom CS1 is trivially checked.

Given a simplex τ = (w_{1}, w_{2}, …, w_{n}), the word of τ is defined as w(τ) = w_{1}w_{2} ⋯ w_{n}. We prove that CS2 holds, showing that each descending chain τ_{1} >_{Rn} τ_{2} >_{Rn} ⋯ of redundant simplices gives rise to a chain of words w(τ_{1}) ⪰ w(τ_{2}) ⪰ ⋯; the two chains have the same length, but the second one is necessarily finite.

We introduce the relation > on the set F G_{1} of words saying that w > w′ if and only if either w ⊃ w′ (i.e. w′ is a proper sub-word of w) or there exists a reduction q ∈ wR such that q : w ⇒ w′. Observe that we have

\xymatrix{w_{1} ⊃ w_{2} \ar@{=>}[r]^{q} & w_{3}} if and only if \xymatrix{w_{1} = uw_{2}v \ar@{=>}[r]^{uqv} & uw_{3}v ⊃ w_{3}} ;

in any chain w > w_{1} > w_{2} > ⋯, we can thus move the symbols ⇒ on the left and obtain a chain of the same length

w_{1} ⇒ w′_{2} ⇒ ⋯ ⇒ w′_{k} ⊃ w′_{k+1} ⊃ ⋯ ⊃ w′_{k+h} (k, h ≤ +∞) .

Since the rewrite system R is terminating, there is no infinite chain of reductions and k must be finite. Any word w ∈ F G_{1} has finite length, so h is finite too. The relation > and its transitive closure ≻ are terminating.

Let τ and τ′ be two redundant n-simplices with τ >_{Rn} τ′; if σ = c_{n}(τ) = (w_{1}, …, w_{n+1}), then, for an index j ≠ ι_{n}(τ),

τ = d_{ι_{n}(τ)}(σ) = (w_{1}, …, w_{i−1}, w_{i}w_{i+1}, w_{i+2}, …, w_{n+1}) ,

τ′ = d_{j}(σ) = \begin{cases}(w_{2}, …, w_{n+1}) & j = 0, \\ (w_{1}, …, w_{j} ∘ w_{j+1}, …, w_{n+1}) & 0 < j < n + 1, \\ (w_{1}, …, w_{n}) & j = n + 1. \end{cases}

If j = 0 or j = n + 1, then w(τ) ⊃ w(τ′) and w(τ) ≻ w(τ′). If 0 < j < n + 1 and w_{j}w_{j+1} is reducible, there exists a chain of reductions q : w_{j}w_{j+1} ⇒⇒ ⋯ ⇒ w_{j} ∘ w_{j+1}. So (w_{1} ⋯ w_{j−1})q(w_{j+2} ⋯ w_{n+1}) is a derivation w_{1} ⋯ w_{j−1}(w_{j}w_{j+1})w_{j+2} ⋯ w_{n+1} ⇒ w_{1} ⋯ w_{j−1}(w_{j} ∘ w_{j+1})w_{j+2} ⋯ w_{n+1} and w(τ) ≻ w(τ′). If 0 < j < n + 1 and w_{j}w_{j+1} is irreducible, we have w(τ) = w(τ′). Observe that, since (w_{1}, …, w_{i−1}, w_{i}) is the essential front face of σ, we may have w_{j}w_{j+1} irreducible only if i < j < n + 1 and thus the essential front face of τ′ has at least dimension i, while the one of τ is (w_{1}, …, w_{i−1}).

From a descending chain τ_{1} >_{Rn} τ_{2} >_{Rn} ⋯ of redundant simplices, we get a chain of words w(τ_{1}) ⪰ w(τ_{2}) ⪰ ⋯, where ⪰ is the reflexive closure of ≻. Since ≻ is terminating, the chain of words must be of the form w(τ_{1}) ⪰ ⋯ ⪰ w(τ_{k}) = w(τ_{k+1}) = ⋯ with k finite. On the other hand we have observed that if τ >_{Rn} τ′ implies w(τ) = w(τ′), then the dimension of the essential front face of τ′ is higher than the dimension of the essential front face of τ. Since such dimension is bounded by n, the chain w(τ_{1}) ⪰ ⋯ ⪰ w(τ_{k})=w(τ_{k+1})= ⋯ =w(τ_{k+h}) is finite and CS2 holds.

4.2. Example. The category Δ_{e} of ordinal numbers and order preserving surjective functions has the following presentation. The graph G has G_{0} as the set of ordinal numbers, while the set G_{1} consist of the order preserving elementary surjective functions

σ_{i}(x) = \begin{cases}x & (x ≤ i) ; \\ x − 1 & (x > i) . \end{cases}

We obtain the free category on G by considering the concatenations of these functions. Observe that an order preserving surjective function may be written in different ways as the composition of these elementary functions; for any of these possibilities we want to choose a “normal form”. On the free category F G, consider the set of rewrite rules given by

σ_{i}σ_{j} ⇒ σ_{j−1}σ_{i} (i < j) .

We obtain in this way a complete rewrite system whose normal forms are words of the type

σ_{i_{1}}σ_{i_{2}} ⋯ σ_{i_{s}}  with  i_{1} ≥ i_{2} ≥ ⋯ ≥ i_{s} .

The quotient category is the category Δ_{e}. For the canonical collapsing scheme of this rewrite system, we have that all the ordinal numbers are the essential 0-simplices. The essential 1-simplices are the elementary functions σ_{i}, while all the normal forms of length greater than one are redundant 1-simplices. For example σ_{3}σ_{2}σ_{1} is redundant and its collapsible is the 2-simplex (σ_{3}, σ_{2}σ_{1}). The essential n-simplex has the form

(σ_{i_{1}}, σ_{i_{2}}, ⋯, σ_{i_{n}})  with  i_{1} < i_{2} < ⋯ < i_{n} .

4.3. Example. A free category C is presented by a rewrite system (G, R) with R empty. (G, ∅) is surely complete and the collapsing scheme is very simple. Since no word of F G_{1} is reducible, after condition ES2, there are no essential n-simplices with n > 1 and we have

E_{0} = G_{0} , E_{1} = G_{1} , E_{n} = ∅ (n ≥ 2).

Using other words, the classifying space of a free category generated by the graph G has the homotopy type of the topological graph |G| (the geometric realization of G). For example, the category C in Example 2.3 is the free category on the graph pictured there and thus BC has the same homotopy type as

•  •  •

4.4. Proposition. There exists a functor K such that the following diagram commutes

[figure: CRS; I; K; CSet^{Δ^{op}}; U; Cat; N; Set_{Δ_{op}}]

Proof. The functor K assigns to a complete rewrite system the collapsing scheme defined above. Now remember that a morphism of rewrite systems preserves the length of words and sends reducible words to reducible words. A morphism of complete rewrite systems sends also irreducible to irreducible and the rest of the proof is immediate.

References

[BG84] K. S. Brown and R. Geoghegan, An infinite-dimensional torsion-free F P_{∞} group, Invent. Math. 77 (1984), 367–381.

[Bro92] K. S. Brown, The geometry of rewriting systems: a proof of the Anick-Groves-Squier theorem, Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989), Springer, MSRI 23, New York, 1992, pp. 137–163.

[Cit00] M. G. Citterio, Classifying spaces of categories and term rewriting, Ph.D. thesis, II University of Rome “Tor Vergata”, March 2000.

[ES87] S. Eilenberg and R. Street, Rewrite systems, algebraic structures and higher-order categories, Handwritten manuscript, 1987.

[Mil57] J. Milnor, The geometric realization of a semi-simplicial complex, Ann. Math. 65 (1957), no. 2, 357–362.

[Str96] R. Street, Categorical structures, Handbook of algebra, Vol. 1, North-Holland, Amsterdam, 1996, pp. 529–577.

Department of Mathematics “F. Enriques”, University of Milano, Italy

Email: citterio@mat.unimi.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/9/n5/n5.{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 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 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 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 Andrew Pitts, University of Cambridge: Andrew.Pitts@cl.cam.ac.uk 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: walters@fis.unico.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca