Homology, Homotopy and Applications, vol.6(1), 2004, pp.175–200

OMEGA-CATEGORIES AND CHAIN COMPLEXES

RICHARD STEINER

(communicated by Ronald Brown)

Abstract

There are several ways to construct omega-categories from combinatorial objects such as pasting schemes or parity complexes. We make these constructions into a functor on a category of chain complexes with additional structure, which we call augmented directed complexes. This functor from augmented directed complexes to omega-categories has a left adjoint, and the adjunction restricts to an equivalence on a category of augmented directed complexes with good bases. The omega-categories equivalent to augmented directed complexes with good bases include the omega-categories associated to globes, simplexes and cubes; thus the morphisms between these omega-categories are determined by morphisms between chain complexes. It follows that the entire theory of omega-categories can be expressed in terms of chain complexes; in particular we describe the biclosed monoidal structure on omega-categories and calculate some internal homomorphism objects.

1. Introduction

This paper is a contribution to the theory of strict ω-categories. In the past, ω-categories have been constructed from combinatorial structures such as pasting schemes, parity complexes or directed complexes; see Johnson [6], Power [9], Steiner [10] and Street [12]. The constructions are not really functorial, although there are ways to produce non-obvious morphisms; see Crans-Steiner [4]. The combinatorial structures can be regarded as bases for chain complexes, as observed by Kapranov and Voevodsky in [7]. We will reinterpret the constructions as a functor on a category of chain complexes with additional structure called augmented directed complexes, and we will show that the functor has a left adjoint. The adjunction is related to the well-known equivalence between the categories of chain complexes and of ω-categories in the category of abelian groups; see Brown-Higgins [3] for instance.

In the earlier treatments, it is shown that combinatorial structures which are in a suitable sense loop-free produce free ω-categories. The functorial version of this result says that the adjunction restricts to equivalences between certain pairs of full

Received March 11, 2004, revised April 27, 2004; published on May 12, 2004. 2000 Mathematics Subject Classification: 18D05. Key words and phrases: Omega-category, augmented directed complex. \begin{matrix}c \\ ◯ \end{matrix} 2004, Richard Steiner. Permission to copy for private use granted.

subcategories. The augmented directed complexes concerned are free chain complexes with good bases, and the corresponding ω-categories have good sets of generators. These ω-categories include those associated to globes, simplexes and cubes, which determine the entire theory of ω-categories (see Al-Agl-Brown-Steiner [1], Al-Agl-Steiner [2] and Street [11]); thus the theory of ω-categories can be described in terms of chain complexes. In particular the biclosed monoidal structure on ωcategories can be described in terms of chain complexes, and we will calculate some internal homomorphism objects. Homomorphisms between these ω-categories have been studied by Gaucher in his work on higher-dimensional automata [5].

The adjunction between ω-categories and augmented directed complexes is described in Section 2, bases for augmented directed complexes are described in Section 3, generating sets for ω-categories are described in Section 4, the equivalences between subcategories are described in Section 5, relations with earlier work are described in Section 6, and the applications to the theory of ω-categories are described in Section 7.

2. The adjunction

In this section we describe the adjunction between ω-categories and augmented directed complexes. First we define the categories involved. For ω-categories we use the following description and notation.

Definition 2.1. An ω-category is a set with unary source and target operators d_{0}^{−}, d_{0}^{+}, d_{1}^{−}, d_{1}^{+}, … and not everywhere defined binary composition operators

(x, y) ↦ x #_{0} y, (x, y) ↦ x #_{1} y, …

such that the following hold:

(i) x #_{n} y is defined if and only if d_{n}^{+}x = d_{n}^{−}y;

(ii) for every x there exists n such that d_{n}^{−}x = d_{n}^{+}x = x;

(iii) for any x,

d_{m}^{β}d_{n}^{α}x = \begin{cases}d_{m}^{β}x & if m < n, \\ d_{n}^{α}x & if m ⩾ n; \end{cases}

(iv) for any x,

d_{n}^{−}x #_{n} x = x #_{n} d_{n}^{+}x = x;

(v) if x #_{n} y is defined then

d_{m}^{α}(x #_{n} y) = d_{m}^{α}x = d_{m}^{α}y = d_{m}^{α}x #_{n} d_{m}^{α}y for m < n,
d_{n}^{−}(x #_{n} y) = d_{n}^{−}x,
d_{n}^{+}(x #_{n} y) = d_{n}^{+}y,
d_{m}^{α}(x #_{n} y) = d_{m}^{α}x #_{n} d_{m}^{α}y for m > n;

(vi) for any n,

(x #_{n} y) #_{n} z = x #_{n} (y #_{n} z)

if either side is defined; (vii) if m < n then

(x #_{n} y) #_{m} (x′ #_{n} y′) = (x #_{m} x′) #_{n} (y #_{m} y′)

when the left side is defined.

A morphism of ω-categories is a function commuting with the source, target and composition operators. The category of ω-categories is denoted ω-cat.

Let C be an ω-category. It generates an ω-category object C′ in the category of abelian groups, which is equivalent to a nonnegatively graded chain complex K by [3]. On C′ there are two pieces of additional structure: the homomorphism C′ → Z induced by the morphism from C to the one-element ω-category, and the submonoid generated by the image of C (a submonoid of an abelian group is a subset containing zero and closed under addition). Correspondingly, it turns out that the chain complex K is augmented and has a distinguished submonoid in each chain group. A chain complex with this kind of additional structure will be called an augmented directed complex.

Definition 2.2. An augmented directed complex K is an augmented chain complex (K_{n}, ∂, ε) of abelian groups concentrated in nonnegative dimensions, together with a distinguished submonoid K_{n}^{∗} of the chain group K_{n} for each n. A morphism of augmented directed complexes from K to L is an augmentation-preserving chain map f: K → L such that f(K_{n}^{∗}) ⊂ L_{n}^{∗} for each n. The category of augmented directed complexes is denoted ADC.

Similar structures have been studied by Patchkoria in [8].

In order to construct the functor from ω-cat to ADC, we first recall the standard filtration for an ω-category.

Proposition 2.3. Let C be an ω-category. Then C is the union of an increasing sequence of sub-ω-categories denoted C_{0} ⊂ C_{1} ⊂ …, where

C_{n} = d_{n}^{−}C = d_{n}^{+}C = { x ∈ C : d_{n}^{−}x = x } = { x ∈ C : d_{n}^{+}x = x }.

Proof. The four definitions for C_{n} are consistent because d_{n}^{β}d_{n}^{α} = d_{n}^{α}. The C_{n} are sub-ω-categories by Definition 2.1(iii) and (vi). They form an increasing sequence because d_{n}^{α} = d_{n+1}^{β}d_{n}^{α}, and C is the union of the sub-ω-categories by Definition 2.1(ii).

The filtration of Proposition 2.3 is such that the composition operators #_{m} are trivial in C_{n} for m ⩾ n; thus C_{n} is an n-category.

We now use the filtration to construct a functor from ω-cat to ADC.

Definition 2.4. The functor λ: ω-cat → ADC is defined as follows. Let C be an ω-category. Then the chain group (λC)_{n} for n ⩾ 0 is generated by elements [x]_{n} for x ∈ C_{n} subject to relations

[x #_{m} y]_{n} = [x]_{n} + [y]_{n} for m < n,

the boundary homomorphism ∂: (λC)_{n+1} → (λC)_{n} for n ⩾ 0 is given by

∂[x]_{n+1} = [d_{n}^{+}x]_{n} − [d_{n}^{−}x]_{n},

the augmentation ε: (λC)_{0} → Z is given by

ε[x]_{0} = 1,

the distinguished submonoid (λC)_{n}^{∗} is the submonoid generated by the elements [x]_{n}.

To justify this definition, we make the following observations. First, if x ∈ C_{n+1} then the d_{n}^{α}x are members of C_{n}, so the difference [d_{n}^{+}x]_{n} − [d_{n}^{−}x]_{n} is a member of (λC)_{n}. If x #_{n} y is a composite in C_{n+1} then

[d_{n}^{+}(x#_{n}y)]_{n}−[d_{n}^{−}(x#_{n}y)]_{n} = [d_{n}^{+}y]_{n}−[d_{n}^{−}x]_{n} = ([d_{n}^{+}x]_{n}−[d_{n}^{−}x]_{n})+([d_{n}^{+}y]_{n}−[d_{n}^{−}y]_{n})

because d_{n}^{+}x = d_{n}^{−}y, and if x #_{m} y is a composite in C_{n+1} with m < n then

[d_{n}^{+}(x #_{m} y)]_{n} − [d_{n}^{−}(x #_{m} y)]_{n} = [d_{n}^{+}x #_{m} d_{n}^{+}y]_{n} − [d_{n}^{−}x #_{m} d_{n}^{−}y]_{n}
= ([d_{n}^{+}x]_{n} + [d_{n}^{+}y]_{n}) − ([d_{n}^{−}x]_{n} + [d_{n}^{−}y]_{n})
= ([d_{n}^{+}x]_{n} − [d_{n}^{−}x]_{n}) + ([d_{n}^{+}y]_{n} − [d_{n}^{−}y]_{n});

therefore ∂: (λC)_{n+1} → (λC)_{n} is a well-defined homomorphism. There are no relations on (λC)_{0}, so ε: (λC)_{0} → Z is a well-defined homomorphism. The composites ∂∂: (λC)_{n+2} → (λC)_{n} are trivial because d_{n}^{α}d_{n+1}^{−} = d_{n}^{α}d_{n+1}^{+}, and the composite ε∂: (λC)_{1} → Z is obviously trivial. Finally, λ is obviously functorial.

We make the following observation.

Proposition 2.5. If C is an ω-category and x ∈ C_{m} with m < n, then [x]_{n} = 0 in (λC)_{n}.

Proof. This holds because

[x]_{n} = [x #_{m} d_{m}^{+}x]_{n} = [x #_{m} x]_{n} = [x]_{n} + [x]_{n}.

We will now go from chain complexes to ω-categories. We first define a functor μ from arbitrary chain complexes to ω-categories in the category of abelian groups. It is the equivalence given implicitly in [3], and it may also be regarded an additive version of Street’s construction [12].

Definition 2.6. The functor μ from chain complexes to ω-categories in the category of abelian groups is defined as follows. Let K be a chain complex. Then μK is the abelian group of double sequences

x = (x_{0}^{−}, x_{0}^{+}, x_{1}^{−}, x_{1}^{+}, …)

such that

x_{n}^{−} ∈ K_{n} and x_{n}^{+} ∈ K_{n},
x_{n}^{−} = x_{n}^{+} = 0 for all but finitely many values of n,
x_{n}^{+} − x_{n}^{−} = ∂x_{n+1}^{−} = ∂x_{n+1}^{+} for n ⩾ 0;

if x ∈ μK then

d_{n}^{α}x = (x_{0}^{−}, x_{0}^{+}, …, x_{n−1}^{−}, x_{n−1}^{+}, x_{n}^{α}, x_{n}^{α}, 0, 0, …);

if d_{n}^{+}x = d_{n}^{−}y = z, say, in μK then

x #_{n} y = x − z + y
= (x_{0}^{−}, y_{0}^{+}, …, x_{n}^{−}, y_{n}^{+}, x_{n+1}^{−} + y_{n+1}^{−}, x_{n+1}^{+} + y_{n+1}^{+}, …).

It is straightforward to check that μ is a well-defined functor. We extend the filtration of μK given in Proposition 2.3 by writing (μK)_{−1} = 0, and we get the following result.

Proposition 2.7. Let K be a chain complex and let n be a nonnegative integer. Then x_{n}^{−} = x_{n}^{+} for x ∈ (μK)_{n}, and the homomorphism x ↦ x_{n}^{α}: (μK)_{n} → K_{n} fits into a natural split short exact sequence

0 → (μK)_{n−1} → (μK)_{n} → K_{n} → 0.

Proof. If x ∈ (μK)_{n} then x = d_{n}^{α}x, so x_{n}^{−} = x_{n}^{+}. For x ∈ μK, one finds that x ∈ (μK)_{n} if and only if x_{m}^{−} = x_{m}^{+} = 0 for all m > n, and it follows that the homomorphism x ↦ x_{n}^{α}: (μK)_{n} → K_{n} has kernel (μK)_{n−1}. This means that there is a natural exact sequence 0 → (μK)_{n−1} → (μK)_{n} → K_{n}. To complete the proof we need a natural splitting homomorphism K_{n} → (μK)_{n}. For n = 0 we use the homomorphism

x ↦ (x, x, 0, 0, …),

and for n > 0 we can use the homomorphism

x ↦ (0, 0, …, 0, ∂x, x, x, 0, 0, …).

We now use the additional structure on an augmented directed complex to define a functor from ADC to ω-cat.

Definition 2.8. The functor ν: ADC → ω-cat is defined as follows. Let K be an augmented directed complex. Then νK is the sub-ω-category of μK consisting of the elements

(x_{0}^{−}, x_{0}^{+}, x_{1}^{−}, x_{1}^{+}, …)

such that

x_{n}^{−} ∈ K_{n}^{∗} and x_{n}^{+} ∈ K_{n}^{∗} for all n,
εx_{0}^{−} = εx_{0}^{+} = 1.

It is straightforward to check that Definition 2.8 gives a well-defined functor from augmented directed complexes to ω-categories: if K is an augmented directed complex then νK is a subset of μK closed under the ω-category operations. Obviously νK is not a subgroup of μK.

Finally in this section, we show that λ is left adjoint to ν. First we describe the unit of the adjunction.

Definition 2.9. The natural transformation η: C → νλC for an ω-category C is defined by the formula

ηx = ([d_{0}^{−}x]_{0}, [d_{0}^{+}x]_{0}, [d_{1}^{−}x]_{1}, [d_{1}^{+}x]_{1}, …).

In order to justify this definition, we first show that ηx ∈ νλC for x ∈ C. Indeed, it is clear that [d_{n}^{α}x]_{n} ∈ (λC)_{n}^{∗} and ε[d_{0}^{α}x]_{0} = 1, and we also have

∂[d_{n+1}^{α}x]_{n+1} = [d_{n}^{+}d_{n+1}^{α}x]_{n} − [d_{n}^{−}d_{n+1}^{α}x]_{n} = [d_{n}^{+}x]_{n} − [d_{n}^{−}x]_{n},

so it suffices to show that [d_{n}^{α}x]_{n} = 0 for n sufficiently large. But by Proposition 2.3 there exists p such that d_{n}^{α}x ∈ C_{p} for all n, and it then follows from Proposition 2.5 that [d_{n}^{α}x]_{n} = 0 for n > p.

We must also show that η: C → νλC is a morphism of ω-categories. But we get ηd_{n}^{α}x = d_{n}^{α}ηx because [d_{m}^{β}d_{n}^{α}x]_{m} = [d_{m}^{β}x]_{m} for m < n, because [d_{n}^{β}d_{n}^{α}x]_{n} = [d_{n}^{α}x]_{n}, and because [d_{m}^{β}d_{n}^{α}x]_{m} = [d_{n}^{α}x]_{m} = 0 for m > n by Proposition 2.5. We also get η(x#_{n} y) = ηx#_{n} ηy because [d_{m}^{−}(x#_{n} y)]_{m} = [d_{m}^{−}x]_{m} and [d_{m}^{+}(x#_{n} y)]_{m} = [d_{m}^{+}y]_{m} for m ⩽ n and because [d_{m}^{α}(x #_{n} y)]_{m} = [d_{m}^{α}x #_{n} d_{m}^{α}y]_{m} = [d_{m}^{α}x]_{m} + [d_{m}^{α}y]_{m} for m > n. It follows that η is a morphism of ω-categories, and it is clear that η is natural.

Next we describe the counit. We denote this by π rather than ε, in order to avoid confusion with augmentations.

Definition 2.10. The natural transformation π: λνK → K is defined for an augmented directed complex K by the formula

π[x]_{n} = x_{n}^{−} = x_{n}^{+}.

To justify this definition, observe first that x_{n}^{−} = x_{n}^{+} for x ∈ (νK)_{n} by Proposition 2.7. The formula π[x]_{n} = x_{n}^{−} = x_{n}^{+} gives a well-defined homomorphism π: (λνK)_{n} → K_{n} because if m < n then (x #_{m} y)_{n}^{α} = x_{n}^{α} + y_{n}^{α}. We get a chain map because

∂π[x]_{n+1} = ∂x_{n+1}^{α} = x_{n}^{+}−x_{n}^{−} = (d_{n}^{+}x)_{n}^{+}−(d_{n}^{−}x)_{n}^{−} = π([d_{n}^{+}x]_{n}−[d_{n}^{−}x]_{n}) = π∂[x]_{n+1}.

This chain map is augmentation-preserving because επ[x]_{0} = εx_{0}^{α} = 1 = ε[x]_{0} for x ∈ (νK)_{0}, and we get π(λνK)_{n}^{∗} ⊂ K_{n}^{∗} because x_{n}^{α} ∈ K_{n}^{∗} for x ∈ νK. Therefore π: λνK → K is a morphism of augmented directed complexes. It is clearly natural.

The main theorem is now as follows.

Theorem 2.11. The functors λ: ω-cat → ADC and ν: ADC → ω-cat form an adjoint pair with unit η: id → νλ and counit π: λν → id.

Proof. We must show that

(πλ) ∘ (λη) = id: λ → λ

and

(νπ) ∘ (ην) = id: ν → ν.

Let C be an ω-category. The generators of (λC)_{n} have the form [x]_{n} with x ∈ C_{n}. For these generators, d_{n}^{α}x = x, so

π(λη)[x]_{n} = π[ηx]_{n}
= π[([d_{0}^{−}x]_{0}, [d_{0}^{+}x]_{0}, [d_{1}^{−}x]_{1}, [d_{1}^{+}x]_{1}, …)]_{n}
= [d_{n}^{α}x]_{n}
= [x]_{n};

therefore (πλ) ∘ (λη) = id.

Now let K be an augmented directed complex and let x be a member of νK. Then

(νπ)ηx = (νπ)([d_{0}^{−}x]_{0}, [d_{0}^{+}x]_{0}, [d_{1}^{−}x]_{1}, [d_{1}^{+}x]_{1}, …)
= (π[d_{0}^{−}x]_{0}, π[d_{0}^{+}x]_{0}, π[d_{1}^{−}x]_{1}, π[d_{1}^{+}x]_{1}, …)
= ((d_{0}^{−}x)_{0}^{−}, (d_{0}^{+}x)_{0}^{+}, (d_{1}^{−}x)_{1}^{−}, (d_{1}^{+}x)_{1}^{+}, …)
= (x_{0}^{−}, x_{0}^{+}, x_{1}^{−}, x_{1}^{+}, …)
= x;

therefore (νπ) ∘ (ην) = id.

This completes the proof.

3. Bases for augmented directed complexes

We will now consider augmented directed complexes with bases. We essentially recover the examples constructed in earlier treatments such as [6], [9], [10] and [12].

Definition 3.1. Let K be an augmented directed complex. A basis for K is a set B ⊂ ⨆_{n} K_{n} such that each K_{n} is a free abelian group with basis B ∩ K_{n} and each K_{n}^{∗} is the submonoid of K_{n} generated by B ∩ K_{n}.

Suppose that K is an augmented directed complex with a basis. We make K_{n} into a partially ordered abelian group by the rule

x ⩽ y ⟺ y − x ∈ K_{n}^{∗}.

The basis elements in K_{n} can be characterised as the minimal non-zero elements in K_{n}^{∗}, and it follows that K has only one basis. Note also that K_{n} is a lattice: any two elements x and y have a least upper bound x ∨ y and a greatest lower bound x ∧ y. If x is an element of K_{n+1}, then there are unique elements ∂^{−}x, ∂^{+}x ∈ K_{n}, the negative and positive parts of ∂x, such that

∂x = ∂^{+}x − ∂^{−}x, ∂^{−}x ∧ ∂^{+}x = 0;

indeed, if ∂x is expressed as a linear combination of distinct basis elements, then ∂^{+}x is the sum of the terms with positive coefficients and −∂^{−}x is the sum of the terms with negative coefficients.

Let b be a basis element for K. We denote the dimension of b by |b|, so that b ∈ K_{|b|}. We then define elements ⟨b⟩_{n}^{−} and ⟨b⟩_{n}^{+} in K_{n} by downward recursion as follows:

⟨b⟩_{n}^{α} = \begin{cases}0 & for n > |b|, \\ b & for n = |b|, \\ ∂^{α}⟨b⟩_{n+1}^{α} & for n < |b|. \end{cases}

It is straightforward to check that this produces an element ⟨b⟩ of μK; in fact we can make the following definition.

Definition 3.2. Let K be an augmented directed complex with a basis and let b be a basis element. Then the atom associated to b is the element ⟨b⟩ of μK such that ⟨b⟩_{n}^{α} = 0 for n > |b|, such that ⟨b⟩_{|b|}^{α} = b, and such that ⟨b⟩_{n}^{−} ∧ ⟨b⟩_{n}^{+} = 0 for n < |b|. The dimension of the atom ⟨b⟩ is the dimension of the corresponding basis element b.

From Proposition 2.7 we deduce the following result.

Proposition 3.3. Let K be an augmented directed complex with a basis. Then the atoms form a basis for the abelian group μK, the n-dimensional atoms form a basis for (μK)_{n}/(μK)_{n−1}, and the atoms of dimension greater than n form a basis for μK/(μK)_{n}.

If ⟨b⟩ is an atom, then ⟨b⟩_{n}^{α} ∈ K_{n}^{∗} for all n by construction. An atom ⟨b⟩ is therefore in νK if and only if ε⟨b⟩_{0}^{−} = ε⟨b⟩_{0}^{+} = 1. This leads us to the following definition.

Definition 3.4. A basis B for an augmented directed complex is unital if ε⟨b⟩_{0}^{−} = ε⟨b⟩_{0}^{+} = 1 for every b ∈ B.

For the equivalence theorem of Section 5 we need bases which are unital and are also loop-free in the sense of the following definition.

Definition 3.5. A basis B for an augmented directed complex is loop-free if there are partial orderings ⩽_{0}, ⩽_{1}, … on B such that a <_{n} b whenever ⟨a⟩_{n}^{+} ∧ ⟨b⟩_{n}^{−} > 0 and |a|, |b| > n.

Note that the partial orderings ⩽_{n} are quite different from the partial orderings on the individual chain groups.

In practice, one usually has a stronger condition.

Definition 3.6. A basis B for an augmented directed complex is strongly loop-free if there is a partial ordering ⩽_{N} on B such that a <_{N} b whenever a ⩽ ∂^{−}b or ∂^{+}a ⩾ b.

The two notions of loop-freeness are related as follows.

Proposition 3.7. If a basis for an augmented directed complex is strongly loop-free, then it is loop-free.

Proof. Let ⩽_{N} be a partial ordering with the property required for strong loopfreeness. For each n, we will show that ⩽_{N} has the property required for ⩽_{n} in the definition of loop-freeness. In other words, we suppose that ⟨a⟩_{n}^{+} ∧ ⟨b⟩_{n}^{−} > 0 with |a|, |b| > n for some n, and we show that a <_{N} b. Indeed we can choose a basis element c with ⟨a⟩_{n}^{+} ⩾ c and c ⩽ ⟨b⟩_{n}^{−}, and we will show that a <_{N} c <_{N} b.

To show that c <_{N} b, observe that, by the construction of ⟨b⟩, we must have c ⩽ ∂^{−}c′ for some basis element c′ with c′ ⩽ ⟨b⟩_{n+1}^{−}, and we than have c <_{N} c′. If n + 1 < |b| then we repeat this argument, and eventually we get c <_{N} … <_{N} c′′ with c′′ ⩽ ⟨b⟩_{|b|}^{−}. But ⟨b⟩_{|b|}^{−} = b, so c′′ = b, and we have got c <_{N} b as claimed. The proof that a <_{N} c is similar.

Example 3.8. Let K be the chain complex of a simplicial set. Then K is an augmented chain complex with a distinguished basis, so it can be regarded as an augmented directed complex with a basis. In particular, let Δ[p] be the chain complex of the standard p-simplex, so that Δ[p] has the following structure: the basis elements are the ordered (n + 1)-tuples of integers (v_{0}, …, v_{n}) with 0 ⩽ v_{0} < v_{1} < … < v_{n} ⩽ p; the dimension of (v_{0}, …, v_{n}) is n; the boundary ∂: Δ[p]_{n} → Δ[p]_{n−1} is given by

∂ = ∂_{0} − ∂_{1} + ∂_{2} − … + (−1)^{n}∂_{n},

where

∂_{i}(v_{0}, …, v_{n}) = (v_{0}, …, v_{i−1}, v_{i+1}, …, v_{n});

the augmentation is given by ε(v_{0}) = 1. For m ⩽ n one finds that

⟨(v_{0}, …, v_{n})⟩_{m}^{α} = ∑ ∂_{i(1)} … ∂_{i(n−m)}(v_{0}, …, v_{n}),

where the sum runs over (n − m)-tuples such that 0 ⩽ i(1) < … < i(n − m) ⩽ n and the parities (−)^{i(1)}, …, (−)^{i(n−m)} form the alternating sequence α, −α, α, . . .. We have therefore recovered Street’s oriented simplexes [11]. The basis is unital, because ⟨(v_{0}, …, v_{n})⟩_{0}^{−} = (v_{0}) and ⟨(v_{0}, …, v_{n})⟩_{0}^{+} = (v_{n}). The basis is also strongly loop-free under the total ordering given recursively as follows: (v_{0}, …, v_{n}) <_{N} (w_{0}, …, w_{m}) if

v_{0} < w_{0},

or if

v_{0} = w_{0} and n = 0 and m > 0,

or if

v_{0} = w_{0} and n > 0 and m > 0 and (v_{1}, …, v_{n}) >_{N} (w_{1}, …, w_{m}).

Example 3.9. Let B be a finite non-empty totally ordered set in which each element b is assigned a nonnegative integer dimension |b|. Suppose also that the initial and final elements have dimension 0 and that adjacent elements have dimensions differing by 1. For b ∈ B with |b| > 0, let δ^{−}b be the last element of dimension |b| − 1 to come before b, and let δ^{+}b be the first element of dimension |b| − 1 to come after b; the hypotheses ensure that these elements exist. The hypotheses also ensure that the elements between δ^{−}b and δ^{+}b have dimension at least |b|, and for |b| > 1 it follows that δ^{α}δ^{−}b = δ^{α}δ^{+}b. By taking ∂b = δ^{+}b − δ^{−}b for |b| > 0 and εb = 1 for |b| = 0 we define an augmented directed complex with basis B. Clearly ⟨b⟩_{n}^{α} is a basis element for n ⩽ |b|, so the basis is unital. It is also strongly loop-free under the original total ordering.

In particular, let p be a nonnegative integer and let the sequence of dimensions of the elements of B be

0, 1, …, p − 1, p, p − 1, …, 1, 0.

Then the augmented directed complex is called the p-dimensional globe and denoted G[p]. Let x denote the p-dimensional basis element; then d_{p}^{−}⟨x⟩ = d_{p}^{+}⟨x⟩ = ⟨x⟩, and the atoms other than ⟨x⟩ are the elements d_{i}^{α}⟨x⟩ for i < p.

A p-dimensional globe is in a sense free on a p-dimensional generator. In a similar way we can get an augmented directed complex G[p; n] free on a #_{n}-composable pair of p-dimensional elements: we take the sequence of dimensions of the elements of B to run from 0 up to p, then down to min{p, n}, then up to p, then down to 0. Let the p-dimensional basis elements in order be x and y (they coincide if p ⩽ n); then d_{p}^{−}⟨x⟩ = d_{p}^{+}⟨x⟩ = ⟨x⟩, d_{p}^{−}⟨y⟩ = d_{p}^{+}⟨y⟩ = ⟨y⟩, and d_{n}^{+}⟨x⟩ = d_{n}^{−}⟨y⟩. The atoms other than ⟨x⟩ and ⟨y⟩ are the d_{i}^{α}⟨x⟩ and d_{i}^{α}⟨y⟩ for i < p, with the identifications d_{i}^{α}⟨x⟩ = d_{i}^{α}⟨y⟩ for i < min{p, n} and with the identification d_{n}^{+}⟨x⟩ = d_{n}^{−}⟨y⟩ if n < p.

There is a similar augmented directed complex G[p; n, n] free on a #_{n}-composable triple of p-dimensional elements: the sequence of dimensions is now from 0 up to p, down to min{p, n}, up to p, down to min{p, n}, up to p, down to 0. For m < n there is also an augmented directed complex G[p; n, m, n] free on a composable quadruple of p-dimensional elements in the configuration (x #_{n} y) #_{m} (x′ #_{n} y′) of Definition 2.1(vii): the sequence of dimensions is now from 0 up to p, down to min{p, n}, up to p, down to min{p, m}, up to p, down to min{p, n}, up to p, down to 0.

Example 3.10. The category of augmented chain complexes has a symmetric monoidal structure under the tensor product (K, L) ↦ K ⊗ L, where

(K ⊗ L)_{n} = ⨁_{i} K_{i} ⊗ L_{n−i},

∂(x ⊗ y) = ∂x ⊗ y + (−1)^{|x|}x ⊗ ∂y, ε(x ⊗ y) = (εx)(εy) for |x| = |y| = 0

(we write |x| = i if x ∈ K_{i}, etc.). The identity object is the 0-dimensional globe G[0] of Example 3.9. We extend this structure to a monoidal structure on augmented directed complexes as follows: (K ⊗ L)_{n}^{∗} is the submonoid of (K ⊗ L)_{n} generated by the elements x ⊗ y with x ∈ K_{i}^{∗} and y ∈ L_{n−i}^{∗}. Note that the monoidal structure on augmented directed complexes is not symmetric: the standard switch morphism x ⊗ y ↦ (−1)^{|x| |y|}(y ⊗ x) does not always map (K ⊗ L)_{n}^{∗} into (L ⊗ K)_{n}^{∗}.

Suppose now that K and L are augmented directed complexes with bases A and B. Then K ⊗ L has a basis C consisting of the elements a ⊗ b for a ∈ A and b ∈ B.

One finds that

⟨a ⊗ b⟩_{n}^{α} = ∑_{i=0}^{n}⟨a⟩_{i}^{α} ⊗ ⟨b⟩_{n−i}^{(−)^{i}α};

in particular ⟨a ⊗ b⟩_{0}^{α} = ⟨a⟩_{0}^{α} ⊗ ⟨b⟩_{0}^{α}. If A and B are unital, then it follows that C is unital. Similarly, if A and B are strongly loop-free under partial orderings ⩽_{N}, then C is strongly loop-free under the partial ordering ⩽_{N} such that a ⊗ b ⩽_{N} a′ ⊗ b′ for

a <_{N} a′,

or for

a = a′ and |a| even and b ⩽_{N} b′,

or for

a = a′ and |a| odd and b ⩾_{N} b′.

In particular, for p ⩾ 0, let Q[p] be the chain complex of the p-dimensional cube. Then Q[p] is the p-fold tensor power of the one-dimensional globe G[1], so Q[p] is an augmented directed complex with a strongly loop-free unital basis.

4. Bases for ω-categories

We will now describe bases for ω-categories, corresponding to bases for augmented directed complexes. The required properties can be described directly in terms of ω-categories, but it is often easier to work in the augmented directed complexes got by applying λ.

We begin with a particular kind of generating set, analogous to a spanning set. Recall that if C is an ω-category then C_{n} is the sub-ω-category d_{n}^{−}C = d_{n}^{+}C.

Definition 4.1. An ω-category C is composition-generated by a subset E if each member e of E is assigned a nonnegative integer dimension |e| and if for n ⩾ 0 the sub-ω-category C_{n} is generated under the composition operations #_{m} by the elements of E of dimension at most n.

Composition-generation should be distinguished from ordinary generation, where one uses the operations d_{m}^{α} as well as the composition operations.

Note that if e is a composition-generator for an ω-category C then e ∈ C_{|e|}, so that d_{n}^{α}e = e for n ⩾ |e|.

There are standard forms for the elements of ω-categories with compositiongenerators, as follows.

Proposition 4.2. Let C be an ω-category with a set of composition-generators and let x be a member of C. Then x is a generator or x has an expression x = x_{1} #_{r} … #_{r} x_{k} with r ⩾ 0 and k ⩾ 2 such that the x_{i} are composites of generators, each x_{i} has exactly one factor of dimension greater than r, and at most one of the x_{i} has a factor of dimension greater than r + 1.

Proof. It suffices to prove the result when x is a composite, say x = y #_{n} z, in which y and z have expressions of the required form. If the expression for y involves no factors of dimension greater than n, then y is an identity for #_{n} by Definition 2.1(v), so x = z and the result therefore holds for x. A similar argument applies if the expression for z involves no factors of dimension greater than n.

From now on, assume that the expressions for y and z both involve factors of dimension greater than n. Let r be the largest integer such that the expressions for y and z together involve more than one factor of dimension greater than r; thus r ⩾ n. Suppose that the expressions for y and z have k and l factors respectively of dimension greater than r; thus k + l ⩾ 2. Then there is a decomposition

y = y_{1} #_{r} … #_{r} y_{k} #_{r} d_{r}^{+}y #_{r} … #_{r} d_{r}^{+}y,

with l appearances of d_{r}^{+}y, such that y_{i} has exactly one factor of dimension greater than r (if k = 0 then y = d_{r}^{+}y, so this holds trivially; if k = 1 we take y_{1} = y; if k > 1 then y_{1} #_{r} … #_{r} y_{k} is the given expression for y). Similarly there is a decomposition

z = d_{r}^{−}z #_{r} … #_{r} d_{r}^{−}z #_{r} z_{1} #_{r} … #_{r} z_{l},

with k factors equal to d_{r}^{−}z, such that z_{j} has exactly one factor of dimension greater than r. The choice of r ensures that the y_{i} and z_{j} have at most one factor of dimension r + 1 between them. If now n = r then the desired decomposition of x = y #_{r} z is given by

x = y_{1} #_{r} … #_{r} y_{k} #_{r} z_{1} #_{r} … #_{r} z_{l};

if n < r then Definition 2.1(vii) gives

x = (y_{1} #_{r} … #_{r} y_{k} #_{r} d_{r}^{+}y #_{r} … #_{r} d_{r}^{+}y) #_{n} (d_{r}^{−}z #_{r} … #_{r} d_{r}^{−}z #_{r} z_{1} #_{r} … #_{r} z_{l})

= (y_{1} #_{n} d_{r}^{−}z) #_{r} … #_{r} (y_{k} #_{n} d_{r}^{−}z) #_{r} (d_{r}^{+}y #_{n} z_{1}) #_{r} … #_{r} (d_{r}^{+}y #_{n} z_{l}),

which is a decomposition of the required form because d_{r}^{−}z and d_{r}^{+}y are composites of generators of dimension at most r.

This completes the proof.

Composition-generators for an ω-category C produce generators for (λC)_{n} and (λC)_{n}^{∗} as follows.

Proposition 4.3. Let C be an ω-category with a set of composition-generators E. Then the abelian group (λC)_{n} and the submonoid (λC)_{n}^{∗} are generated by the elements [e]_{n} for e an n-dimensional element of E.

Proof. The abelian group (λC)_{n} and the submonoid (λC)_{n}^{∗} are generated by the elements [x]_{n} for x ∈ C_{n}, and the elements of C_{n} are the composites of the members of E of dimension at most n. If m ⩾ n then the elements of C_{n} are identities for #_{m}, because d_{m}^{β}d_{n}^{α} = d_{n}^{α}; it therefore suffices to use the composition operators #_{m} for m < n. These operations become addition in (λC)_{n}, so (λC)_{n} and (λC)_{n}^{∗} are generated by the elements [e]_{n} for e ∈ E with |e| ⩽ n. Finally [e]_{n} = 0 for |e| < n by Proposition 2.5; therefore (λC)_{n} and (λC)_{n}^{∗} are generated by the elements [e]_{n} for e ∈ E with |e| = n.

We now define a basis for an ω-category C in terms of a basis for the augmented directed complex λC.

Definition 4.4. A basis for an ω-category C is a set of composition-generators E such λC has a basis and the function e ↦ [e]_{|e|} maps E bijectively onto the basis for λC.

Because of Proposition 4.3, a composition-generating set E is a basis if and only if the elements [e]_{|e|} for e ∈ E are distinct and linearly independent.

Let C be an ω-category with a basis E. Then λC has a basis B, and we can use properties of B to define properties of E.

Definition 4.5. Let E be a basis for an ω-category C. Then (i) E is atomic if [d_{n}^{−}e]_{n} ∧ [d_{n}^{+}e]_{n} = 0 for e ∈ E and n < |e|; (ii) E is loop-free if the basis for λC is loop-free; (iii) E is strongly loop-free if the basis for λC is strongly loop-free.

The point of atomicity is as follows.

Proposition 4.6. Let E be an atomic basis for an ω-category C. Then ηe = ⟨[e]_{|e|}⟩ for each e in E, and the basis for λC is unital.

Proof. Recall from Definition 2.9 that (ηe)_{n}^{α} = [d_{n}^{α}e]_{n} for all n and α. If n > |e| then [d_{n}^{α}e]_{n} = [e]_{n} = 0 by Proposition 2.5. If n = |e| then [d_{n}^{α}e]_{n} = [e]_{|e|}. By comparing Definition 4.5(i) with Definition 3.2, we now see that ηe = ⟨[e]_{|e|}⟩. Since ηe ∈ νλC, it follows that ε⟨[e]_{|e|}⟩_{0}^{α} = ε(ηe)_{0}^{α} = 1; therefore the basis for λC is unital. This completes the proof.

Example 4.7. Let p be a nonnegative integer, and let F [p] be the ω-category with the following presentation: there is a single generator u and there are relations d_{p}^{−}u = d_{p}^{+}u = u. The ω-categories F [p] represent the elements of ω-categories, in the sense that there are natural bijections between hom(F [p], C) and C_{p}. We have d_{i}^{α}u = u for i ⩾ p. Using Definition 2.1(iii) and (v), we see that F [p] is compositiongenerated by u and the elements d_{i}^{α}u for i < p.

Now let G[p] be the p-dimensional globe with p-dimensional basis element x as in Example 3.9. The atom ⟨x⟩ in νG[p] satisfies the relations d_{p}^{−}⟨x⟩ = d_{p}^{+}⟨x⟩ = ⟨x⟩, so there is a morphism F [p] → νG[p] given by u ↦ ⟨x⟩. The adjoint λF [p] → G[p] maps the generators [u]_{p} and [d_{i}^{α}u]_{i} for λF [p] (see Proposition 4.3) bijectively to the basis elements for G[p], and it follows that the morphism λF [p] → G[p] is an isomorphism. It then follows that the elements u and d_{i}^{α}u form a basis for F [p], and one can check that this basis is atomic. It is also strongly loop-free, because the basis for G[p] is strongly loop-free.

There are similar ω-categories F [p; n], F [p; n, n] and F [p; n, m, n] (where m < n) corresponding to the other augmented directed complexes of Example 3.9. These ω-categories all have strongly loop-free atomic bases. There is a presentation for F [p; n] given by

⟨ u, v : d_{p}^{α}u = u, d_{p}^{α}v = v, d_{n}^{+}u = d_{n}^{−}v ⟩,

there is a presentation for F [p; n, n] given by

⟨ u, v, w : d_{p}^{α}u = u, d_{p}^{α}v = v, d_{p}^{α}w = w, d_{n}^{+}u = d_{n}^{−}v, d_{n}^{+}v = d_{n}^{−}w ⟩,

and there is a presentation for F [p; n, m, n] given by

⟨ u, v, u′, v′ : d_{p}^{α}u = u, d_{p}^{α}v = v, d_{p}^{α}u′ = u′, d_{p}^{α}v′ = v′,
d_{n}^{+}u = d_{n}^{−}v, d_{m}^{+}v = d_{m}^{−}u′, d_{n}^{+}u′ = d_{n}^{−}v′ ⟩.

5. The adjoint equivalence

From Definition 4.4, Definition 4.5 and Proposition 4.6, if an ω-category C has a loop-free atomic basis then λC has a loop-free unital basis. We will now show that ω-categories with loop-free atomic bases and augmented directed complexes with loop-free unital bases are equivalent under the adjoint functors λ and ν.

We begin by considering decompositions in νK, where K is an augmented directed complex with a basis. The basic existence result is as follows.

Proposition 5.1. Let K be an augmented directed complex with a basis and let x be a member of νK which is congruent to a non-trivial sum of atoms modulo (μK)_{r} for some r ⩾ 0, say

x ≡ ⟨b_{1}⟩ + … + ⟨b_{k}⟩ mod (μK)_{r}

with k ⩾ 1. If ⟨b_{i}⟩_{r}^{+} ∧ ⟨b_{j}⟩_{r}^{−} = 0 for i > j, then there is a decomposition

x = x_{1} #_{r} … #_{r} x_{k}

with x_{i} ∈ νK such that x_{i} ≡ ⟨b_{i}⟩ mod (μK)_{r}.

Proof. The congruence gives

x = ⟨b_{1}⟩ + … + ⟨b_{k}⟩ + z

for some z ∈ (μK)_{r}; thus d_{r}^{α}z = z. For 1 ⩽ i ⩽ k let x_{i} be the element of μK given by

x_{i} = d_{r}^{+}[⟨b_{1}⟩ + … + ⟨b_{i−1}⟩] + ⟨b_{i}⟩ + d_{r}^{−}[⟨b_{i+1}⟩ + … + ⟨b_{k}⟩] + z,

and for 1 ⩽ i ⩽ k − 1 let

y_{i} = d_{r}^{+}[⟨b_{1}⟩ + … + ⟨b_{i}⟩] + d_{r}^{−}[⟨b_{i+1}⟩ + … + ⟨b_{k}⟩] + z.

Then d_{r}^{+}x_{i} = y_{i} = d_{r}^{−}x_{i+1} because d_{r}^{β}d_{r}^{α} = d_{r}^{α}, and we also have

x = x_{1} − y_{1} + x_{2} − y_{2} + … + x_{k},

so there is a decomposition

x = x_{1} #_{r} … #_{r} x_{k}

in μK. It is clear that x_{i} ≡ ⟨b_{i}⟩ mod (μK)_{r}, and it remains to show that x_{i} ∈ νK. We must therefore show that ε(x_{i})_{0}^{α} = 1 and that (x_{i})_{n}^{α} ⩾ 0.

As to the augmentation, we have ε(d_{r}^{β}⟨b_{j}⟩)_{0}^{α} = ε⟨b_{j}⟩_{0}^{α} for all j and β, so ε(x_{i})_{0}^{α} = εx_{0}^{α} = 1.

As to the (x_{i})_{n}^{α}, if n < r then (x_{i})_{n}^{α} = x_{n}^{α} ⩾ 0, and if n > r then (x_{i})_{n}^{α} = ⟨b_{i}⟩_{n}^{α} ⩾ 0; it therefore remains to consider the case n = r. Now (x_{1})_{r}^{−} = x_{r}^{−} ⩾ 0 and (x_{k})_{r}^{+} = x_{r}^{+} ⩾ 0, and for 1 ⩽ i ⩽ k − 1 we have

(x_{i})_{r}^{+} = (x_{i+1})_{r}^{−} = x_{r}^{−} + [⟨b_{1}⟩_{r}^{+} + … + ⟨b_{i}⟩_{r}^{+}] − [⟨b_{1}⟩_{r}^{−} + … + ⟨b_{i}⟩_{r}^{−}]
= x_{r}^{+} + [⟨b_{i+1}⟩_{r}^{−} + … + ⟨b_{k}⟩_{r}^{−}] − [⟨b_{i+1}⟩_{r}^{+} + … + ⟨b_{k}⟩_{r}^{+}].

But x_{r}^{α} ⩾ 0, ⟨b_{j}⟩_{r}^{α} ⩾ 0, and

[⟨b_{1}⟩_{r}^{−} + … + ⟨b_{i}⟩_{r}^{−}] ∧ [⟨b_{i+1}⟩_{r}^{+} + … + ⟨b_{k}⟩_{r}^{+}] = 0,

so (x_{i})_{r}^{α} ⩾ 0 in all cases. This completes the proof.

To find situations in which Proposition 5.1 can be applied, we use the following result.

Proposition 5.2. Let K be an augmented directed complex with a basis and let x be a member of νK.

(i) If x ≡ 0 mod (μK)_{r+1} then

x ≡ ⟨c_{1}⟩ + … + ⟨c_{l}⟩ mod (μK)_{r}

for some (r + 1)-dimensional atoms ⟨c_{1}⟩, …, ⟨c_{l}⟩.

(ii) If x ≡ m⟨a⟩ mod (μK)_{r+1} for some positive integer m and for some atom ⟨a⟩ with |a| > r + 1, then

x ≡ m⟨a⟩ + ⟨c_{1}⟩ + … + ⟨c_{l}⟩ mod (μK)_{r}

for some (r + 1)-dimensional atoms ⟨c_{1}⟩, …, ⟨c_{l}⟩.

(iii) If x = y #_{r} z for some y, z ∈ νK such that y ≡ ⟨a⟩ and z ≡ ⟨b⟩ mod (μK)_{r} with |a|, |b| > r and ⟨a⟩_{r}^{+} ∧ ⟨b⟩_{r}^{−} = 0, then

x ≡ ⟨a⟩ + ⟨b⟩ + ⟨c_{1}⟩ + … + ⟨c_{l}⟩ mod (μK)_{r−1}

for some r-dimensional atoms ⟨c_{1}⟩, …, ⟨c_{l}⟩.

Proof. (i) Since x ∈ (μK)_{r+1}, we have x_{r+1}^{−} = x_{r+1}^{+} = w for some w ∈ K_{r+1}. Since x ∈ νK, we have w ⩾ 0, so that w is a sum of (r + 1)-dimensional basis elements c_{1} + … + c_{l}. It now follows that x ≡ ⟨c_{1}⟩ + … + ⟨c_{l}⟩ mod (μK)_{r}, as required.

(ii) Here x − m⟨a⟩ is in (μK)_{r+1}. As in the proof of part (i), we get x_{r+1}^{−} − m⟨a⟩_{r+1}^{−} = x_{r+1}^{+} − m⟨a⟩_{r+1}^{+} = w for some w ∈ K_{r+1}, and it suffices to show that w ⩾ 0. But this holds because x_{r+1}^{−} ⩾ 0, x_{r+1}^{+} ⩾ 0 and ⟨a⟩_{r+1}^{−} ∧ ⟨a⟩_{r+1}^{+} = 0.

(iii) Here

x_{r}^{−} − ⟨a⟩_{r}^{−} − ⟨b⟩_{r}^{−} = x_{r}^{+} − ⟨a⟩_{r}^{+} − ⟨b⟩_{r}^{+} = z_{r}^{−} − ⟨a⟩_{r}^{+} − ⟨b⟩_{r}^{−} = w

for some w ∈ K_{r}, since x ≡ y + z ≡ ⟨a⟩ + ⟨b⟩ mod (μK)_{r}, since x_{r}^{+} = z_{r}^{+}, and since z − ⟨b⟩ ∈ (μK)_{r}. As before, it suffices to show that w ⩾ 0. But this holds because x_{r}^{−} ⩾ 0, x_{r}^{+} ⩾ 0, z_{r}^{−} ⩾ 0 and

⟨a⟩_{r}^{−} ∧ ⟨a⟩_{r}^{+} = ⟨b⟩_{r}^{−} ∧ ⟨b⟩_{r}^{+} = ⟨a⟩_{r}^{+} ∧ ⟨b⟩_{r}^{−} = 0.

To construct decompositions we use Proposition 5.2(i) together with the case m = 1 of Proposition 5.2(ii). It is convenient to make the following definition.

Definition 5.3. Let K be an augmented directed complex with a basis, and let x be a member of νK. Then the decomposition index of x is the smallest integer r ⩾ −1 such that x is congruent to zero or an atom modulo (μK)_{r+1}.

In Definition 5.3, note that the decomposition index exists because x ≡ 0 mod (μK)_{n} for all sufficiently large n.

By combining Propositions 5.1 and 5.2 we get the following result, analogous to part of Proposition 4.2.

Proposition 5.4. Let K be an augmented directed complex with a loop-free basis, and let x be a member of (νK)_{n} with decomposition index r ⩾ 0. Then there is a decomposition

x = x_{1} #_{r} … #_{r} x_{k}

with x_{i} ∈ (νK)_{n} and x_{i} ≡ ⟨b_{i}⟩ mod (μK)_{r}, where ⟨b_{1}⟩, …, ⟨b_{k}⟩ is a list of atoms such that k ⩾ 2, such that |b_{i}| > r for all i, such that |b_{i}| > r + 1 for at most one value of i, and such that ⟨b_{i}⟩_{r}^{+} ∧ ⟨b_{j}⟩_{r}^{−} = 0 for i > j.

Proof. We have x congruent to zero or an atom modulo (μK)_{r+1}. By Proposition 5.2(i) or (ii) there is a congruence

x ≡ ⟨b_{1}⟩ + … + ⟨b_{k}⟩ mod (μK)_{r}

for some list of atoms ⟨b_{i}⟩ with |b_{i}| > r for each i and with |b_{i}| > r + 1 for at most one value of i. Since the decomposition index is r, we have k ⩾ 2. Since the basis is loop-free we can assume the list ordered so that ⟨b_{i}⟩_{r}^{+} ∧ ⟨b_{j}⟩_{r}^{−} = 0 for i > j. By Proposition 5.1 there is a decomposition x = x_{1} #_{r} … #_{r} x_{k} with x_{i} ∈ νK and x_{i} ≡ ⟨b_{i}⟩ mod (μK)_{r}. Finally, |b_{i}| ⩽ n for each i, because x ∈ (νK)_{n}, and it follows that x_{i} ∈ (νK)_{n}. This completes the proof.

To complete the analogy with Proposition 4.2 we give the following result.

Proposition 5.5. Let K be an augmented directed complex with a unital basis, and let x be a member of (νK)_{n} with decomposition index −1. Then x is an atom of dimension at most n.

Proof. We have x congruent to zero or an atom modulo (μK)_{0}. By Proposition 5.2(i) or (ii) there is a congruence

x ≡ ⟨b_{1}⟩ + … + ⟨b_{k}⟩ mod (μK)_{−1}

for some atoms ⟨b_{i}⟩. Since (μK)_{−1} = 0, this congruence is an equality, and it follows that

εx_{0}^{α} = ε⟨b_{1}⟩_{0}^{α} + … + ε⟨b_{k}⟩_{0}^{α}.

But εx_{0}^{α} = 1 because x ∈ νK, and ε⟨b_{i}⟩_{0}^{α} = 1 for each i because the basis is unital, so k = 1. This means that x is equal to the atom ⟨b_{1}⟩. The dimension of ⟨b_{1}⟩ is at most n because x ∈ (νK)_{n}.

We can now prove one half of the equivalence.

Theorem 5.6. Let K be an augmented directed complex with a loop-free unital basis. Then νK has a loop-free atomic basis consisting of its atoms, and the counit π: λνK → K is an isomorphism.

Proof. First we show that νK is composition-generated by its atoms. Indeed the atoms of dimension at most n lie in (νK)_{n} because the basis is unital, so the composites of atoms of dimension at most n lie in (νK)_{n}. Conversely, let x be a member of (νK)_{n} of decomposition index r. If r ⩾ 0, then x is a composite of members of (νK)_{n} with lower decomposition index by Proposition 5.4, and if r = −1 then x is an atom of dimension at most n by Proposition 5.5. It follows by induction on r that x is a composite of atoms of dimension at most n. Therefore νK is composition-generated by its atoms.

Next we show that π: λνK → K is an isomorphism. For each n ⩾ 0 we must show that π: (λνK)_{n} → K_{n} is an isomorphism with π[(λνK)_{n}^{∗}] = K_{n}^{∗}. Now it follows from Proposition 4.3 that (λνK)_{n} and (λνK)_{n}^{∗} are generated as abelian group and submonoid by the elements [⟨b⟩]_{n} for |b| = n. The images of these elements under π are the n-dimensional basis elements, which generate K_{n} and K_{n}^{∗} as abelian group and submonoid freely. It follows that π: (λνK)_{n} → K_{n} is an isomorphism with π[(λνK)_{n}^{∗}] = K_{n}^{∗} as required.

Finally we show that the atoms form a basis for νK with the desired properties by verifying the conditions of Definitions 4.4 and 4.5. We have already shown that the atoms composition-generate νK. The elements [⟨b⟩]_{|b|} form a basis for λνK, because their images under the isomorphism π: λνK → K form a basis for K, so the function ⟨b⟩ ↦ [⟨b⟩]_{|b|} is a bijection from the set of atoms to a basis for λνK. The atoms therefore form a basis for νK. We have [d_{n}^{−}⟨b⟩]_{n} ∧[d_{n}^{+}⟨b⟩]_{n} = 0 for n < |b| because

π[d_{n}^{−}⟨b⟩]_{n} ∧ π[d_{n}^{+}⟨b⟩]_{n} = ⟨b⟩_{n}^{−} ∧ ⟨b⟩_{n}^{+} = 0;

therefore the basis for νK is atomic. The basis for λνK is loop-free because λνK ≅ K; therefore the basis for νK is loop-free. This completes the proof.

Conversely, if C is an ω-category with a loop-free atomic basis, then we want the unit η: C → νλC to be an isomorphism. More generally, we will prove the following result.

Theorem 5.7. Let C be an ω-category composition-generated by a set E, let K be an augmented directed complex with a loop-free unital basis, and let θ: C → νK be a morphism which restricts to a dimension-preserving bijection from E to the atoms of νK. Then θ is an isomorphism.

In a sense, Theorem 5.7 says that νK is freely composition-generated by its atoms. To prove it, we will show that the decompositions in Proposition 5.4 are as nearly as possible uniquely determined. We begin with the following observation.

Proposition 5.8. Let K be an augmented directed complex. If

x_{1} #_{r} … #_{r} x_{k} = y_{1} #_{r} … #_{r} y_{k}

in μK and if x_{i} ≡ y_{i} mod (μK)_{r} for 1 ⩽ i ⩽ k, then x_{i} = y_{i} for 1 ⩽ i ⩽ k.

Proof. We have

(x_{1} − y_{1}) #_{r} … #_{r} (x_{k} − y_{k}) = 0

and x_{1} − y_{1} ∈ (μK)_{r}, so

x_{1} − y_{1} = d_{r}^{−}(x_{1} − y_{1}) = d_{r}^{−}(0) = 0,

and it follows that x_{1} = y_{1}. We then have d_{r}^{−}(x_{2} −y_{2}) = d_{r}^{+}(x_{1} −y_{1}) = 0, so x_{2} = y_{2} by a similar argument, and so on.

Because of Proposition 5.8, the decomposition in Proposition 5.4 is uniquely determined by the ordered list of atoms ⟨b_{1}⟩, …, ⟨b_{k}⟩. Up to permutation this list is determined by x, because x ≡ ⟨b_{1}⟩ + … + ⟨b_{k}⟩ mod (μK)_{r}; however, it may be possible to reorder the list.

In particular, suppose that k = 2, so that x ≡ ⟨b_{1}⟩ + ⟨b_{2}⟩ mod (μK)_{r} with min{|b_{1}|, |b_{2}|} = r + 1. Suppose further that r > 0, and that x has a #_{r−1}- decomposition x = x_{1}^{∗} #_{r−1} x_{2}^{∗} with x_{1}^{∗} ≡ ⟨b_{1}⟩ and x_{2}^{∗} ≡ ⟨b_{2}⟩ mod (μK)_{r}. Then it follows from Definition 2.1(iv) and (vii) that there are #_{r}-decompositions

x = (x_{1}^{∗} #_{r−1} d_{r}^{−}x_{2}^{∗}) #_{r} (d_{r}^{+}x_{1}^{∗} #_{r−1} x_{2}^{∗}) = (d_{r}^{−}x_{1}^{∗} #_{r−1} x_{2}^{∗}) #_{r} (x_{1}^{∗} #_{r−1} d_{r}^{+}x_{2}^{∗})

with (x_{1}^{∗} #_{r−1} d_{r}^{α}x_{2}^{∗}) ≡ ⟨b_{1}⟩ and (d_{r}^{α}x_{1}^{∗} #_{r−1} x_{2}^{∗}) ≡ ⟨b_{2}⟩ mod (μK)_{r}. For elements of this type, one can therefore transpose the atoms. We will now show that any two consecutive atoms in the ‘wrong’ order can be transposed in this way.

Proposition 5.9. Let K be an augmented directed complex with a loop-free unital basis. Suppose that x = y#_{r} z is a composite in νK with y ≡ ⟨a⟩ and z ≡ ⟨b⟩ modulo (μK)_{r}, where ⟨a⟩ and ⟨b⟩ are atoms such that |a|, |b| > r and ⟨a⟩_{r}^{+} ∧ ⟨b⟩_{r}^{−} = 0. Then r > 0 and there is a decomposition x = y^{∗} #_{r−1} z^{∗} or x = z^{∗} #_{r−1} y^{∗} in νK with y^{∗} ≡ ⟨a⟩ and z^{∗} ≡ ⟨b⟩ modulo (μK)_{r}.

Proof. By Proposition 5.2(iii),

x ≡ ⟨a⟩ + ⟨b⟩ + ⟨c_{1}⟩ + … + ⟨c_{l}⟩ mod (μK)_{r−1}

for some r-dimensional atoms ⟨c_{i}⟩. If r = 0 then this congruence is an equality and we get εx_{0}^{α} = l + 2 > 1, which is absurd. Therefore r > 0. Since the basis is loopfree we can order the list ⟨a⟩, ⟨b⟩, ⟨c_{1}⟩, …, ⟨c_{l}⟩ so that Proposition 5.1 applies. We get a decomposition x = x_{1} #_{r−1} … #_{r−1} x_{l+2} in νK such that modulo (μK)_{r−1} the factors are congruent to ⟨a⟩, ⟨b⟩, ⟨c_{1}⟩, …, ⟨c_{l}⟩ in some order. Modulo (μK)_{r} it follows that one of the factors is congruent to ⟨a⟩, another factor is congruent to ⟨b⟩, and the others are congruent to zero. By grouping the factors appropriately, we get a decomposition x = y^{∗} #_{r−1} z^{∗} or x = z^{∗} #_{r−1} y^{∗} of the required form.

In the proof of Theorem 5.7, we show that elements of νK have unique inverse images by induction on their decomposition indices. In the inductive step we use the following lemma.

Lemma 5.10. Let K be an augmented directed complex with a loop-free unital basis, let C be an ω-category, let r be a nonnegative integer, and let θ: C → νK be a morphism such that elements of νK with decomposition index less than r have unique inverse images in C. If ξ = η #_{r} ζ is a composite in C such that θ(η) ≡ ⟨a⟩ and θ(ζ) ≡ ⟨b⟩ modulo (μK)_{r}, where ⟨a⟩ and ⟨b⟩ are atoms such that |a|, |b| > r and ⟨a⟩_{r}^{+} ∧ ⟨b⟩_{r}^{−} = 0, then there is a decomposition ξ = ζ′ #_{r} η′ in C such that θ(ζ′) ≡ ⟨b⟩ and θ(η′) ≡ ⟨a⟩ modulo (μK)_{r}.

Proof. By Proposition 5.9, r > 0 and there is a decomposition θ(ξ) = y^{∗} #_{r−1} z^{∗} or θ(ξ) = z^{∗}#_{r−1}y^{∗} in νK with y^{∗} ≡ ⟨a⟩ and z^{∗} ≡ ⟨b⟩ modulo (μK)_{r}. For definiteness, suppose that θ(ξ) = y^{∗} #_{r−1} z^{∗}. Then y^{∗} and z^{∗} have decomposition indices less than r, so they have unique inverse images η^{∗} and ζ^{∗}. We now get

θ(d_{r−1}^{+}η^{∗}) = d_{r−1}^{+}y^{∗} = d_{r−1}^{−}z^{∗} = θ(d_{r−1}^{−}ζ^{∗}),

and the element d_{r−1}^{+}y^{∗} = d_{r−1}^{−}z^{∗} clearly has decomposition index less than r−1, so d_{r−1}^{+}η^{∗} = d_{r−1}^{−}ζ^{∗} by the uniqueness part of the hypothesis. It follows that η^{∗} and ζ^{∗} have a composite η^{∗} #_{r−1} ζ^{∗}. We now have θ(ξ) = θ(η^{∗} #_{r−1} ζ^{∗}), and we claim that ξ = η^{∗} #_{r−1} ζ^{∗}. Indeed it follows from Definition 2.1(vii) that

θ(η) #_{r} θ(ζ) = θ(ξ) = θ(η^{∗} #_{r−1} ζ^{∗}) = θ(η^{∗} #_{r−1} d_{r}^{−}ζ^{∗}) #_{r} θ(d_{r}^{+}η^{∗} #_{r−1} ζ^{∗})

with

θ(η) ≡ ⟨a⟩ ≡ y^{∗} ≡ θ(η^{∗}) ≡ θ(η^{∗} #_{r−1} d_{r}^{−}ζ^{∗}) mod (μK)_{r}

and

θ(ζ) ≡ ⟨b⟩ ≡ z^{∗} ≡ θ(ζ^{∗}) ≡ θ(d_{r}^{+}η^{∗} #_{r−1} ζ^{∗}) mod (μK)_{r},

so θ(η) = θ(η^{∗} #_{r−1} d_{r}^{−}ζ^{∗}) and θ(ζ) = θ(d_{r}^{+}η^{∗} #_{r−1} ζ^{∗}) by Proposition 5.8. Clearly θ(η) and θ(ζ) have decomposition indices less than r, so η = η^{∗} #_{r−1} d_{r}^{−}ζ^{∗} and ζ = d_{r}^{+}η^{∗} #_{r−1} ζ^{∗} by the uniqueness part of the hypothesis. Using Definition 2.1(vii) again, we get ξ = η #_{r} ζ = η^{∗} #_{r−1} ζ^{∗} as claimed. It now follows that

ξ = (d_{r}^{−}η^{∗} #_{r−1} ζ^{∗}) #_{r} (η^{∗} #_{r−1} d_{r}^{+}ζ^{∗}) = ζ′ #_{r} η′,

say, with θ(ζ′) ≡ θ(ζ^{∗}) ≡ ⟨b⟩ and θ(η′) ≡ θ(η^{∗}) ≡ ⟨a⟩ modulo (μK)_{r}. This completes the proof.

Proof of Theorem 5.7. We show that θ is an isomorphism by showing that each element x of νK has a unique inverse image under θ. We use induction on the decomposition index of x.

Suppose first that x has decomposition index −1. By Proposition 5.5, x is an atom. From Proposition 4.2, we see that the inverse images of x must be generators. Since θ maps the set of generators bijectively onto the set of atoms, it follows that x has a unique inverse image.

Now suppose that x has decomposition index r ⩾ 0. By Proposition 5.4 there is a decomposition

x = x_{1} #_{r} … #_{r} x_{k}

with k ⩾ 2, with x_{i} ∈ νK, and with x_{i} ≡ ⟨b_{i}⟩ mod (μK)_{r}, such that |b_{i}| > r for all i, such that |b_{i}| > r +1 for at most one value of i, and such that ⟨b_{i}⟩_{r}^{+} ∧⟨b_{j}⟩_{r}^{−} = 0 for i > j. The x_{i} clearly have decomposition indices less than r, so they have unique inverse images ξ_{i} by the inductive hypothesis. As in the proof of Lemma 5.10,

θ(d_{r}^{+}ξ_{i−1}) = d_{r}^{+}x_{i−1} = d_{r}^{−}x_{i} = θ(d_{r}^{−}ξ_{i})

and the decomposition index of d_{r}^{+}x_{i−1} = d_{r}^{−}x_{i} is less than r, so d_{r}^{+}ξ_{i−1} = d_{r}^{−}ξ_{i} by the uniqueness part of the inductive hypothesis, and it follows that there is a composite

ξ = ξ_{1} #_{r} … #_{r} ξ_{k}.

Then ξ is an inverse image for x.

To complete the proof, let ξ′ be any inverse image for x; we must show that ξ′ = ξ. We can express ξ′ as in Proposition 4.2. From the form of x, this must mean that ξ′ = ξ′_{1} #_{r} … #_{r} ξ′_{k} with the θ(ξ′_{i}) congruent to the ⟨b_{i}⟩ in some order modulo (μK)_{r}. By repeated application of Lemma 5.10, we can change back to the original order. This gives us a decomposition

ξ′ = ξ′′_{1} #_{r} … #_{r} ξ′′_{k}

with θ(ξ′′_{i}) ≡ ⟨b_{i}⟩ ≡ x_{i} mod (μK)_{r} for each i. Since θ(ξ′) = x = x_{1} #_{r} … #_{r} x_{k}, it follows from Proposition 5.8 that θ(ξ′′_{i}) = x_{i} for each i. But the x_{i} have unique inverse images ξ_{i}, so ξ′′_{i} = ξ_{i} for each i, and it follows that ξ′ = ξ. This completes the proof.

The main theorem is now as follows.

Theorem 5.11. The adjoint functors λ: ω-cat → ADC and ν: ADC → ω-cat restrict to adjoint equivalences between the full subcategories consisting of ω-categories with loop-free atomic bases and of augmented directed complexes with loop-free unital bases. Under these equivalences, ω-categories with strongly loop-free atomic bases correspond to augmented directed complexes with strongly loop-free unital bases.

Proof. By Theorem 5.6, if K is an augmented directed complex with a loop-free unital basis then νK has a loop-free atomic basis and the counit π: λνK → K is an isomorphism.

Conversely, let C be an ω-category with a loop-free atomic basis E. By Definitions 4.4 and 4.5, the function e ↦ [e]_{|e|} maps E bijectively to a loop-free basis for λC. By Proposition 4.6 this basis is unital, so λC has a loop-free unital basis. By Proposition 4.6 again, the unit η: C → νλC sends the generator e to the atom ⟨[e]_{|e|}⟩. It follows that η maps the generators of C bijectively to the atoms of νλC and preserves dimensions. By Theorem 5.7, η: C → νλC is an isomorphism.

Finally, strongly loop-free atomic bases correspond to strongly loop-free unital bases by Definition 4.5(iii).

This completes the proof.

6. Relations with earlier work

In this section we compare our construction ν with other constructions of ωcategories.

We first observe that Theorem 5.11 serves to characterise certain ω-categories: if K is an augmented directed complex with a loop-free basis and if C is an ω-category with an atomic basis such that λC ≅ K, then C must be isomorphic to νK. This shows that the various constructions are essentially equivalent. For example, let C be the ω-category associated to the p-simplex in [2], [10] or [11]; then C must be isomorphic to νΔ[p], where Δ[p] is as in Example 3.8.

The ω-categories associated to loop-free structures in earlier treatments have presentations of particular types. The analogous result for the functor ν is as follows.

Theorem 6.1. Let K be an augmented directed complex with a loop-free unital basis. Then the ω-category νK has a presentation as follows: the generators are the atoms; for each atom ⟨b⟩ there are relations d_{|b|}^{−}⟨b⟩ = d_{|b|}^{+}⟨b⟩; for each positivedimensional atom ⟨b⟩ there are relations d_{|b|−1}^{−}⟨b⟩ = w^{−}(b) and d_{|b|−1}^{+}⟨b⟩ = w^{+}(b), where the w^{α}(b) are expressions for the d_{|b|−1}^{α}⟨b⟩ as composites of atoms of dimension less than |b|.

Proof. It follows from Theorem 5.5 that νK is composition-generated by its atoms, and the atoms therefore satisfy relations of the form described. Let C be the ωcategory generated by the atoms subject to these relations; then there is a canonical morphism θ: C → νK, and we must show that it is an isomorphism. Because of Theorem 5.7, it suffices to show that the atoms composition-generate C. Because of Definition 2.1(iii) and (v), C is composition-generated by the elements d_{n}^{α}⟨b⟩ for ⟨b⟩ an atom. It therefore suffices to show that in C each element d_{n}^{α}⟨b⟩ is a composite of atoms of dimension at most n. We do this by induction on |b|. Indeed, if n < |b| then d_{n}^{α}⟨b⟩ = d_{n}^{α}d_{|b|−1}^{α}⟨b⟩ = d_{n}^{α}w^{α}(b), and w^{α}(b) is a composite of atoms of dimension less than |b|, so the result holds by the inductive hypothesis and Definition 2.1(v), and if n ⩾ |b| then d_{n}^{α}⟨b⟩ = d_{n}^{α}d_{|b|}^{α}⟨b⟩ = d_{|b|}^{α}⟨b⟩ = ⟨b⟩, so the result holds trivially. This completes the proof.

The constructions corresponding to ν in earlier treatments are described combinatorially in terms of sets rather than algebraically. We will now show that νK can be described combinatorially when K has a loop-free unital basis B, in the sense that the elements of νK are determined by subsets of B.

Theorem 6.2. Let K be an augmented directed complex with a loop-free unital basis and let x be a member of νK.

(i) If x is a sum of atoms then x is an atom.

(ii) If x ≡ m_{1}⟨b_{1}⟩ + … + m_{k}⟨b_{k}⟩ mod (μK)_{r} for some r ⩾ −1, with |b_{i}| > r and with m_{i} > 0 for all i, then m_{i} = 1 for all i.

(iii) Each term x_{n}^{α} of x is a sum of distinct basis elements.

Proof. (i) Suppose that x = ⟨b_{1}⟩ + … + ⟨b_{k}⟩. Then εx_{0}^{α} = ε⟨b_{1}⟩_{0}^{α} + … + ε⟨b_{k}⟩_{0}^{α}. But εx_{0}^{α} = 1 because x ∈ νK, and ε⟨b_{i}⟩_{0}^{α} = 1 for each i because the basis is unital, so k = 1. This means that x is equal to the atom ⟨b_{1}⟩.

(ii) The proof is by induction on r. In the case r = −1 the result follows from part (i). From now on, suppose that r ⩾ 0. We may assume that k ⩾ 1 (otherwise there is nothing to prove). We have ⟨b_{i}⟩_{r}^{+} ∧ ⟨b_{i}⟩_{r}^{−} = 0 for each i, because |b_{i}| > r. Since the basis is loop-free, we can assume the list ⟨b_{1}⟩, …, ⟨b_{k}⟩ ordered so that ⟨b_{i}⟩_{r}^{+} ∧ ⟨b_{j}⟩_{r}^{−} = 0 for i > j. By applying Proposition 5.1 and grouping the factors, we get a decomposition x = x_{1} #_{r} … #_{r} x_{k} with x_{i} ∈ νK and x_{i} ≡ m_{i}⟨b_{i}⟩ modulo (μK)_{r}. By Proposition 5.2(ii),

x_{i} ≡ m_{i}⟨b_{i}⟩ + ⟨c_{1}⟩ + … + ⟨c_{l}⟩ mod (μK)_{r−1}

for some r-dimensional atoms ⟨c_{1}⟩, …, ⟨c_{l}⟩. By the inductive hypothesis, m_{i} = 1 as required.

(iii) We have x_{n}^{α} ⩾ 0 because x ∈ νK, so x_{n}^{α} = m_{1}b_{1} + … + m_{k}b_{k} for some positive integers m_{i} and some n-dimensional basis elements b_{i}. It now suffices to show that m_{i} = 1 for each i, and this follows from part (ii) because

d_{n}^{α}x ≡ m_{1}⟨b_{1}⟩ + … + m_{k}⟨b_{k}⟩ mod (μK)_{n−1}.

7. The structure of the category of ω-categories

The ω-categories F [p], F [p; n], F [p; n, n] and F [p; n, m, n] of Example 4.7 represent the elements, operations and defining identities of ω-categories; in particular F [p; n, n] and F [p; n, m, n] are what one needs for the identities of Definition 2.1(vi) and (vii). One can therefore use these ω-categories to give a ‘globular’ description of ω-cat. There are also simplicial and cubical descriptions, using the ω-categories νΔ[p] and νQ[p] coming from Examples 3.8 and 3.10; see [1], [2], [11]. All of these descriptions are based on ω-categories with strongly loop-free atomic bases. Because of Theorem 5.11, one can express these descriptions in terms of augmented directed complexes; thus the theory of ω-categories can be expressed in terms of chain complexes. We will now use the globular description to get results on monoidal structures. The main novelty is the functoriality; see Theorem 7.6 in particular.

We first make the following observation.

Theorem 7.1. Every ω-category is the colimit of a small diagram of ω-categories with strongly loop-free atomic bases.

Proof. Let C be an ω-category. By Proposition 2.3, C is the union of the increasing sequence of sub-ω-categories C_{p}, where

C_{p} = d_{p}^{−}C = d_{p}^{+}C = { x ∈ C : d_{p}^{−}x = x } = { x ∈ C : d_{p}^{+}x = x }.

The structure of C is given by the unary operations d_{n}^{α} and the not everywhere defined binary composition operations #_{n}. Now the elements and #_{n}-composable pairs in C_{p} are represented by the ω-categories F [p] and F [p; n] of Example 4.7, and it follows that C is the colimit of a small diagram in which the objects are copies of the F [p] and F [p; n]. Indeed, one needs a copy of F [p] for each element of C_{p}; one needs a copy of F [p; n] for each #_{n}-composable pair in C_{p}; and one needs morphisms to determine the inclusions C_{p−1} → C_{p}, the operations d_{n}^{α}, and the composition operations #_{n}. The result now holds since, by Example 4.7, the F [p] and F [p; n] have strongly loop-free atomic bases.

From Example 3.10, the category of augmented directed complexes with strongly loop-free unital bases has a monoidal structure based on the usual tensor product of chain complexes. From Theorem 5.11 we immediately get the following consequence.

Proposition 7.2. There is a monoidal structure on the full subcategory of ω-cat consisting of ω-categories with strongly loop-free atomic bases. It is equivalent via λ and ν to the monoidal structure on the full subcategory of ADC consisting of atomic directed complexes with strongly loop-free unital bases.

We now use Theorem 7.1 to get a monoidal structure on the category of ωcategories.

Theorem 7.3. There is a colimit-preserving functor

(C, C′) ↦ C ⊗ C′: ω-cat × ω-cat → ω-cat

extending the tensor product on ω-categories with strongly loop-free atomic bases. This functor is unique up to natural equivalence, and it determines a monoidal structure on ω-cat.

Proof. Because of Theorem 7.1, it makes sense to define the functor by

C ⊗ C′ = colim(F ⊗ F′),

where the colimit is taken over the morphisms F → C and F′ → C′ whose domains have strongly loop-free atomic bases. It is clear that this functor preserves colimits and that it extends the tensor product on ω-categories with strongly loop-free atomic bases. It is also clear that these properties determine the functor up to natural equivalence. We get a monoidal structure on ω-cat because we are starting from a monoidal structure on the subcategory.

We now wish to show that the monoidal structure on ω-cat is biclosed. We will use the following result.

Theorem 7.4. Let F be the category of ω-categories with strongly loop-free atomic bases. Then an ω-category is naturally equivalent under the functor C ↦ hom(−, C) to a contravariant set-valued functor on F which takes colimits in ω-cat to limits in the category of sets.

Proof. If C is an ω-category, then hom(−, C) is a contravariant set-valued functor on ω-cat taking colimits to limits. It follows that the restriction hom(−, C)|F is a contravariant set-valued functor on F taking colimits in ω-cat to limits in the category of sets. The axioms of ω-category theory (Definition 2.1) reduce to these properties of hom(−, C)|F: indeed it suffices to take the ω-categories F [p], F [p; n], F [p; n, n] and F [p; n, m, n] of Example 4.7, all of which are in F. The result follows.

The category F of Theorem 7.4 is equivalent under λ to a subcategory of ADC by Theorem 5.11, so Theorem 7.4 yields a description of ω-categories in terms of chain complexes. Note in particular that λ takes colimits in ω-cat to colimits in ADC because it is a left adjoint.

From Theorem 7.4, in the standard way, we get the following result.

Theorem 7.5. The monoidal structure on ω-cat is biclosed.

Proof. Given ω-categories C and D, we must find ω-categories HOM(C, D) and HOM′(C, D) such that there are natural equivalences

hom(−, HOM(C, D)) ≅ hom(−⊗C, D), hom(−, HOM′(C, D)) ≅ hom(C ⊗−, D).

But it follows from Theorem 7.3 that hom(− ⊗ C, D) is a contravariant set-valued functor on ω-cat taking colimits to limits, and it then follows from Theorem 7.4 that hom(− ⊗ C, D) is naturally equivalent to hom(−, HOM(C, D)) for some ω-category HOM(C, D). The construction of HOM′(C, D) is similar.

The category of chain complexes has a well-known closed symmetric monoidal structure, and one can check that this induces a biclosed monoidal structure on augmented directed complexes. Indeed, let K and L be augmented directed complexes. If n > 0 then

HOM(K, L)_{n} = ∏_{m} hom(K_{m}, L_{m+n}),

while HOM(K, L)_{0} consists of the pairs (f, εf) such that f ∈ ∏_{m} hom(K_{m}, L_{m}) is a chain map from K to L and εf is an integer with (εf)(εx) = ε(fx) for x ∈ K_{0}. If f ∈ ∏_{m} hom(K_{m}, L_{m+n}), then we write f_{m} for the component of f in hom(K_{m}, L_{m+n}). The boundary on HOM(K, L)_{n} is given by

(∂f)_{m} = \begin{cases}∂ ∘ f_{m} − (−1)^{n}f_{m−1} ∘ ∂ & if m > 0, \\ ∂ ∘ f_{m} & if m = 0, \end{cases}

and by ε(∂f) = 0 in the case n = 1. The augmentation on HOM(K, L)_{0} is given by (f, εf) ↦ εf. The submonoid HOM(K, L)_{n}^{∗} is given by the elements f of ∏_{m} hom(K_{m}, L_{m+n}) such that f_{m}(K_{m}^{∗}) ⊂ L_{m+n}^{∗} for all m. The definition of HOM′(K, L) is the same as for HOM(K, L), except that the boundary formula changes to

(∂f)_{m} = \begin{cases}(−1)^{m}(∂ ∘ f_{m} − f_{m−1} ∘ ∂) & if m > 0, \\ ∂ ∘ f_{m} & if m = 0. \end{cases}

The biclosed monoidal structures on augmented directed complexes and ω-cate-gories are related as follows.

Theorem 7.6. Let K and L be augmented directed complexes such that K has a strongly loop-free unital basis. Then there are natural isomorphisms

ν HOM(K, L) ≅ HOM(νK, νL), ν HOM′(K, L) ≅ HOM′(νK, νL).

Proof. We give the proof for the first of these isomorphisms. Because of Theorem 7.4, it suffices to show that there are natural bijections

hom(F, ν HOM(K, L)) ≅ hom(F, HOM(νK, νL))

for F an ω-category with a strongly loop-free atomic basis. But

hom(F, ν HOM(K, L)) ≅ hom(λF, HOM(K, L)) ≅ hom(λF ⊗ K, L)

and

hom(F, HOM(νK, νL)) ≅ hom(F ⊗ νK, νL) ≅ hom(λ(F ⊗ νK), L)

because λ is left adjoint to ν, and λF ⊗ K ≅ λ(F ⊗ νK) by Proposition 7.2. The result follows.

References

[1] F. A. Al-Agl, R. Brown and R. Steiner, Multiple categories: the equivalence of a globular and a cubical approach, Adv. Math. 170 (2002), no. 1, 71–118.

[2] F. A. Al-Agl and R. Steiner, Nerves of multiple categories, Proc. London Math. Soc. (3) 66 (1993), no. 1, 92–128.

[3] R. Brown and P. J. Higgins, Cubical abelian groups with connections are equivalent to chain complexes, Homology Homotopy Appl. 5(2003), no. 1, 49–52.

[4] S. E. Crans and R. Steiner, Presentations of omega-categories by directed complexes, J. Austral. Math. Soc. Ser. A 63(1997), no. 1, 47–77.

[5] P. Gaucher, Combinatorics of branchings in higher dimensional automata, Theory Appl. Categ. 8(2001), no. 12, 324–376.

[6] M. Johnson, The combinatorics of n-categorical pasting, J. Pure Appl. Algebra 62(1989), no. 3, 211–225.

[7] M. M. Kapranov and V. A. Voevodsky, Combinatorial-geometric aspects of polycategory theory: pasting schemes and higher Bruhat orders (list of results), Cahiers Topologie Géom. Différentielle Catég. 32(1991), no. 1, 11–27.

[8] A. Patchkoria, Chain complexes of cancellative semimodules, Bull. Georgian Acad. Sci. 162(2000), no. 2, 206–208.

[9] A. J. Power, An n-categorical pasting theorem, in Category theory (Como, 1990), 326–358, Lecture Notes in Math. 1488 Springer, Berlin, 1991.

[10] R. Steiner, The algebra of directed complexes, Appl. Categ. Structures 1(1993), no. 3, 247–284.

[11] R. Street, The algebra of oriented simplexes, J. Pure Appl. Algebra 49(1987), no. 3, 283–335.

[12] R. Street, Parity complexes, Cahiers Topologie Géom. Différentielle Catég. 32(1991), no. 4, 315–343; Corrigenda, Cahiers Topologie Géom. Différentielle Catég. 35(1994), no. 4, 359–361.

This article may be accessed via WWW at http://www.rmi.acnet.ge/hha/ or by anonymous ftp at

ftp://ftp.rmi.acnet.ge/pub/hha/volumes/2004/n1a12/v6n1a12.(dvi,ps,pdf)

Richard Steiner r.steiner@maths.gla.ac.uk

Department of Mathematics, University of Glasgow, University Gardens, Glasgow, Scotland G12 8QW