Theory and Applications of Categories, Vol. 11, No. 3, 2003, pp. 75–106.

THE BRANCHING NERVE OF HDA AND THE KAN CONDITION

PHILIPPE GAUCHER

ABSTRACT. One can associate to any strict globular ω-category three augmented simplicial nerves called the globular nerve, the branching and the merging semi-cubical nerves. If this strict globular ω-category is freely generated by a precubical set, then the corresponding homology theories contain different informations about the geometry of the higher dimensional automaton modeled by the precubical set. Adding inverses in this ω-category to any morphism of dimension greater than 2 and with respect to any composition laws of dimension greater than 1 does not change these homology theories. In such a framework, the globular nerve always satisfies the Kan condition. On the other hand, both branching and merging nerves never satisfy it, except in some very particular and uninteresting situations. In this paper, we introduce two new nerves (the branching and merging semi-globular nerves) satisfying the Kan condition and having conjecturally the same simplicial homology as the branching and merging semi-cubical nerves respectively in such framework. The latter conjecture is related to the thin elements conjecture already introduced in our previous papers.

Contents

1 Introduction 75 2 Preliminaries 82 3 The negative semi-path ω-category of a non-contracting ω-category 85 4 The semi-path ω-category of the hypercube 89 5 Simplicial cut 95 6 Thin elements in simplicial cuts and reduced homology 96 7 Regular cut 97 8 The branching semi-globular nerve 99 9 Comparison with the branching semi-cubical nerve 101 10 Concluding discussion 103 11 Acknowledgments 104

1. Introduction

An ω-categorical model for higher dimensional automata (HDA) was first proposed in [13], followed by [9] for a first homological approach using these ideas and cubical models

Received by the editors 2001-07-27 and, in revised form, 2003-02-25. Transmitted by Ross Street. Published on 2003-02-28. 2000 Mathematics Subject Classification: 55U10, 18G35, 68Q85. Key words and phrases: cubical set, thin element, Kan complex, branching, higher dimensional

automata, concurrency, homology theory.

\begin{matrix}c \\ ◯ \end{matrix} Philippe Gaucher, 2003. Permission to copy for private use granted.

of topological spaces as in [2].

The papers [6, 8] demonstrate that the formalism of strict globular ω-categories (see Definition 2.1) freely generated by precubical sets (see below) provides a suitable framework for the introduction of new algebraic tools devoted to the study of deformations of HDA. In particular, three augmented simplicial nerves are introduced in our previous papers : the globular nerve N^{gl}, the branching semi-cubical nerve N^{−} and the merging semicubical nerve N^{+}. Any ω-category freely generated by precubical sets is actually a noncontracting ω-category (see Definition 2.4 and [8] where a precubical set is called semicubical set) and most of the theorems known so far are expressible in this wider framework, hence the importance of the latter notion. In this paper as well, most of the results will be stated in the wider framework of non-contracting ω-categories.

A precubical set is a cubical set as in [2] but without degeneracy maps of any kind. It is easy to view such an object as a contravariant functor from some small category □^{pre} to the category of sets. The objects of □^{pre} are the nonnegative integers. The small category □^{pre} is then the quotient of the free category generated by the arrows δ_{i}^{α} : m → m + 1 for m ⩾ 0, 1 ⩽ i ⩽ m + 1 and α ∈ {−, +} by the relations δ_{j}^{β}δ_{i}^{α} = δ_{i}^{α}δ_{j−1}^{β} for i < j and α ∈ {−, +}.

Now let K = (K_{n})_{n⩾0} be a precubical set. Let I^{n} be the n-dimensional cube viewed as a strict globular ω-category (see the reminder in Section 2). Then the strict globular ω-category freely generated by K is by definition the colimit F (K) := ∫^{n∈□^{pre}} K_{n}.I^{n} where the notation K_{n}.I^{n} means the coproduct of “cardinal of K_{n}” copies of I^{n}. This construction induces a functor from the category of precubical sets (with the natural transformations of functors as morphisms) to the category ωCat of strict globular ω-categories. This functor is of course left adjoint to the precubical nerve functor from ωCat to the category of precubical sets. Any strict ω-category freely generated by a precubical set is necessarily non-contracting.

Non-contracting ω-categories freely generated by precubical sets encode the algebraic properties of execution paths and of higher dimensional homotopies between them in HDA. Indeed, the 0-morphisms represent the states of the HDA, the 1-morphisms the non-constant execution paths, and the p-morphisms with p ⩾ 2 the higher dimensional homotopies between them. R. Cridlig presents in [3] an implementation with CaML of the semantics of a real concurrent language in terms of precubical sets, demonstrating the relevance of this approach.

However, in such an ω-category C = F (K), if H is an homotopy (that is a 2-morphism) from an execution path (that is a 1-morphism) γ_{1} to an execution path γ_{2}, then it is natural to pose the existence of an opposite homotopy H^{−1} from γ_{2} to γ_{1}, that is satisfying H^{−1} ∗_{1} H = γ_{2} and H ∗_{1} H^{−1} = γ_{1}. So any 2-morphism should be invertible with respect to ∗_{1}. Now let us suppose that we are considering an ω-category with a 3-morphism A from the 2-morphism s_{2}A to the 2-morphism t_{2}A. Let (s_{2}A)^{−1} (resp. (t_{2}A)^{−1}) be the inverse of s_{2}A (resp. t_{2}A) with respect to ∗_{1}. If there are no holes between s_{2}A and t_{2}A because of A, then it is natural to think that there are no holes either between (s_{2}A)^{−1} and (t_{2}A)^{−1} : therefore there should exist a 3-morphism A′ such that s_{2}A′ = (s_{2}A)^{−1} and t_{2}A′ = (t_{2}A)^{−1}. Then s_{2}(A ∗_{1} A′) = s_{2}A ∗_{1} (s_{2}A)^{−1} = s_{1}A. Therefore it is natural to assume A ∗_{1} A′ to be 1-dimensional and so the equality A ∗_{1} A′ = s_{1}A should hold. This means that not only a 3-morphism should be invertible with respect to ∗_{2}, because if there is a 3-dimensional homotopy from s_{2}A to t_{2}A, then there should exist a 3-dimensional homotopy from t_{2}A to s_{2}A, but also with respect to ∗_{1}. However the inverses of A with respect to ∗_{1} and ∗_{2} do not have any computer-scientific reason to be equal.

What we mean is that it is natural from a computer-scientific point of view to deal with non-contracting ω-categories whose corresponding path ω-category ℙC (see Definition 2.6) is a strict globular ω-groupoid (see Definition 3.7). One would like to emphasize the fact that it is out of the question to suppose that the whole ω-category C is an ωgroupoid because in our applications, the 1-morphisms of C are never invertible, due to the irreversibility of time.

Let ωCat_{1} be the category of non-contracting ω-categories with the non-contracting ω-functors as morphisms. Let ωCat_{1}^{Kan} be the full and faithful subcategory of ωCat_{1} whose objects are the non-contracting ω-categories C such that ℙC is a strict globular ω-groupoid. The forgetful functor from ωCat_{1}^{Kan} to ωCat_{1} commutes with limits. One can easily check that both categories ωCat_{1} and ωCat_{1}^{Kan} are complete. So by standard categorical arguments (for example the solution set condition [10]), this latter functor admits a left adjoint C ↦ Ĉ from ωCat_{1} to ωCat_{1}^{Kan}.

What we claim is that it is then natural from a computer-scientific point of view to deal with ω-categories like { \atop F (K)} where K is a precubical set. But what do the three homology theories H^{gl}, H^{−} and H^{+} corresponding to the simplicial nerves N^{gl}, N^{−} and N^{+} become? To understand the answer given in Theorem 1.7, we need to recall in an informal way the thin elements conjecture which already showed up in [7].

If C^{gl} (resp. C^{±}) is the unnormalized chain complex associated to N^{gl} (resp. N^{±}) and if CR^{gl} (resp. CR^{±}) is the chain complex which is the quotient of C^{gl} (resp. C^{±}) by the subcomplex generated loosely speaking by the elements without volume (the so-called thin elements, cf. Section 6), then

1.1. Conjecture. [7] (The thin elements conjecture) Let K be a precubical set. Then the chain complex morphisms C^{gl}(F (K)) → CR^{gl}(F (K)) and C^{±}(F (K)) → CR^{±}(F (K)) induce isomorphisms in homology.

As a matter of fact, it is also natural to think that

1.2. Conjecture. [7] (The thin elements conjecture) Let G be a globular set. Let 𝔽G be the free strict globular ω-category generated by G (see Section 3). Then the chain complex morphisms C^{gl}(𝔽G) → CR^{gl}(𝔽G) and C^{±}(𝔽G) → CR^{±}(𝔽G) induce isomorphisms in homology.

As explained in [7], the thin elements conjecture is closely related to the presence or not of relations like “a ∗ b = c ∗ d” with (a, b) ≠ (c, d) in the composition laws of C. Therefore it is plausible to think that 1.3. Conjecture. (The extended thin elements conjecture) Let K be a precubical set. Then the chain complex morphisms

C^{gl}({ \atop F (K)}) → CR^{gl}({ \atop F (K)})

and

C^{±}({ \atop F (K)}) → CR^{±}({ \atop F (K)})

induce isomorphisms in homology.

Conjecture 1.3 can also be formulated for free ω-categories generated by globular sets. In fact, one can even put forward a slightly more general statement :

1.4. Conjecture. Le C be a strict globular non-contracting ω-category such that the chain complex morphisms C^{gl}(C) → CR^{gl}(C) and C^{±}(C) → CR^{±}(C) induce isomorphisms in homology. Then the chain complex morphisms C^{gl}(Ĉ) → CR^{gl}(Ĉ) and C^{±}(Ĉ) → CR^{±}(Ĉ) induce isomorphisms in homology as well.

Chain complexes CF^{±} called the formal branching and the formal merging complexes were introduced in [7] (cf. Definition 7.7). The formal globular complex CF^{gl} was introduced in [8] : the only difference with Definition 7.7 is that the relation x = x ∗_{0} y is removed.

1.5. Definition. [8] Let C be a non-contracting ω-category. If X is a set, let ℤX be the free abelian group generated by the set X. Let tr^{n−1}C be the set of morphisms of C of dimension at most n − 1. Let

• CF_{0}^{gl}(C) := ℤC_{0} ⊗ ℤC_{0} ≅ ℤ(C_{0} × C_{0})

• CF_{1}^{gl}(C) := ℤC_{1}

• CF_{n}^{gl}(C) = ℤC_{n}/{x ∗_{1} y = x + y, …, x ∗_{n−1} y = x + y mod ℤtr^{n−1}C} for n ⩾ 2

with the differential map s_{n−1} − t_{n−1} from CF_{n}^{gl}(C) to CF_{n−1}^{gl}(C) for n ⩾ 2 and s_{0} ⊗ t_{0} from CF_{1}^{gl}(C) to CF_{0}^{gl}(C) where s_{i} (resp. t_{i}) is the i-dimensional source (resp. target) map. This chain complex is called the formal globular complex. The associated homology is denoted by HF^{gl}(C) and is called the formal globular homology of C.

Using results of [7, 8], we already know that the folding operators (cf. Section 7) of respectively the globular nerve and the branching/merging semi-cubical nerves induce morphisms of chain complexes CF^{gl}(C) → CR^{gl}(C) and CF^{±}(C) → CR^{±}(C) which are onto for any strict non-contracting globular ω-category C. The following conjectures were then put forward :

1.6. Conjecture. [7, 8] The folding operators (cf. Section 7) of respectively the globular nerve and the branching/merging semi-cubical nerves induce quasi-isomorphisms of chain complexes

CF^{gl}(C) → CR^{gl}(C)

and

CF^{±}(C) → CR^{±}(C)

for any strict non-contracting globular ω-category C.

We can now answer the question above.

1.7. Theorem. Let K be a precubical set. Assume that Conjecture 1.1, Conjecture 1.3 and Conjecture 1.6 above hold. Then the morphisms of chain complexes

C^{gl}(F (K)) → C^{gl}({ \atop F (K)})

and

C^{±}(F (K)) → C^{±}({ \atop F (K)})

induce isomorphisms in homology.

Proof. Let us consider the following commutative diagram :

\xymatrix{H^{gl}(F (K)) \ar[d] \ar[r]^{≅} & HR^{gl}(F (K)) \ar[d] & HF^{gl}(F (K)) \ar[l]_{≅} \ar[d] \\ H^{gl}({ \atop F (K)}) \ar[r]^{≅} & HR^{gl}({ \atop F (K)}) & HF^{gl}({ \atop F (K)}) \ar[l]_{≅}}

By an easy calculation, one can check that the linear map HF^{gl}(F (K)) → HF^{gl}({ \atop F (K)}) is an isomorphism. Hence the result for the globular homology. The argument is similar for both branching and merging semi-cubical homology theories.

What do we get by working with { \atop F (K)} instead of F (K)? The globular nerve becomes Kan. Indeed its simplicial part is nothing else but the simplicial nerve of the path ωcategory ℙ{ \atop F (K)} of { \atop F (K)} which turns out to be a strict globular ω-groupoid [8].

So now we can ask the question : do the branching and merging semi-cubical nerves N^{−}({ \atop F (K)}) and N^{+}({ \atop F (K)}) satisfy the Kan condition as well? The answer is : almost never. A counterexample is given at the end of [8]. Let us recall it. Consider the 2-source of R(000) in Figure 1 where R(0+0) is removed. Consider both inclusion ω-functors from I^{2} to respectively R(−00) and R(00−). Then the Kan condition fails because one cannot make the sum of R(−00) and R(00−) since R(0 + 0) is removed.

The purpose of this paper is to find two new augmented simplicial nerves of noncontracting ω-category N^{gl^{−}}(C) and N^{gl^{+}}(C) called the branching and merging semiglobular nerves such that the following statements hold :

1. there exist natural morphisms of chain complexes C^{−}(C) → C^{gl^{−}}(C), CR^{−}(C) → CR^{gl^{−}}(C), C^{+}(C) → C^{gl^{+}}(C) and CR^{+}(C) → CR^{gl^{+}}(C) for any non-contracting ωcategory C such that the following squares of chain complexes are commutative :

\xymatrix{C^{−}(C) \ar[d] \ar[r] & C^{gl^{−}}(C) \ar[d] & C^{+}(C) \ar[d] \ar[r] & C^{gl^{+}}(C) \ar[d] \\ CR^{−}(C) \ar[r] & CR^{gl_{−}}(C) & CR^{+}(C) \ar[r] & CR^{gl_{+}}(C)}

2. If C is an object of ωCat_{1}^{Kan}, then the simplicial sets N^{gl^{−}}(C) and N^{gl^{+}}(C) satisfy the Kan condition.

3. The new simplicial nerves N^{gl^{−}} and N^{gl^{+}} fit the formalism of regular cut, as the old branching and merging nerves do. As a consequence, there exist folding operators Φ^{gl^{±}} and □_{n}^{gl^{±}} inducing morphisms of chain complexes CF^{gl^{±}}(C) = CF^{±}(C) → CF^{gl^{±}}(C) which are onto (and conjecturally quasi-isomorphisms) for any strict noncontracting ω-category C.

4. There exist two morphisms of augmented simplicial sets N^{gl} → N^{gl^{−}} and N^{gl} → N^{gl^{+}} which do what we want, that is associating in homology to any empty oriented globe its corresponding branching and merging areas of execution paths (as in [8]) : cf. Figure 2 in Section 9.

Let K be a precubical set. Then there will exist a commutative diagram

\xymatrix{H^{gl^{±}}(F (K)) \ar[d] \ar[r]^{≅} & HR^{gl^{±}}(F (K)) \ar[d] & HF^{±}(F (K)) \ar[l]_{≅} \ar[d] \\ H^{gl^{±}}({ \atop F (K)}) \ar[r]^{≅} & HR^{gl_{±}}({ \atop F (K)}) & HF^{±}({ \atop F (K)}) \ar[l]_{≅}}

where the isomorphisms are conjectural. Notice that the formal branching (resp. merging) homology associated to the branching (resp. merging) semi-globular nerve is the same as that associated to the branching (resp. merging) semi-cubical nerve. In particular, for a strict globular ω-category freely generated by a precubical set, the branching (resp. merging) semi-globular and semi-cubical homologies conjecturally coincide.

The reader may find that a lot of conjectures remain to be proved. This is certainly true but they require new ideas to be resolved and the computer-scientific motivations are helpless. The study of HDA provides new combinatorial conjectures (exactly as in [7, 8]) which need new ideas to be proved.

How to construct the branching semi-globular nerve N^{gl^{−}}(C) (and by symmetry the merging semi-globular nerve N^{gl^{+}}(C))? We already said that the formal homology theory associated to the branching semi-globular nerve is expected to be the same as that of the branching semi-cubical nerve. And the formal branching complex of a given ω-category C is exactly the formal globular complex of an ω-category “C/(x = x ∗_{0} y)” where “C/(x = x ∗_{0} y)” would be an ω-category associated to C in which the relation x = x ∗_{0} y is forced (for dim(x) ⩾ 1).

So loosely speaking, the branching semi-globular nerve of a strict globular ω-category C will be the globular nerve of “C/(x = x ∗_{0} y)”. Looking back to our counterexample, one sees that R(−00) and R(00−) become composable because in “C/(x = x ∗_{0} y)”, t_{1}R(−00) = s_{1}R(00−) = R(−0−). The construction of “C/(x = x ∗_{0} y)” is concretely implemented in Section 3. The corresponding globular nerve will be called the branching semi-globular cut N^{gl^{−}}(C) of C.

The organization of the paper is as follows. Section 2 recalls our conventions of notations and also Steiner’s formulas in ω-complexes : these formulas are indeed crucial for several proofs of this paper. In Section 3, the construction of “C/(x = x ∗_{0} y)” (it is called the negative semi-path ω-category ℙ^{−}C of C) is presented. Some elementary facts about the latter are proved. In Section 4, the technical core of the paper, the negative semi-path ω-category of the hypercube is completely calculated in any dimension (see Theorem 4.9 and Corollary 4.10). This calculation will indeed be fundamental to construct in Section 9 the canonical natural transformation from the branching semi-cubical cut to the branching semi-globular cut. Section 5 exposes a generalization of the notion of simplicial cut initially introduced in [8]. The reason of this generalization is that the branching semi-globular cut does not exactly match the old definition. Section 6 then recalls the notion of thin elements and at last Section 7 the notion of regular cut. The latter definition is necessary to construct the folding operators. Each definition introduced in Section 5, Section 6 and Section 7 is illustrated with the case of the branching semicubical situation (i.e. the old definition of the branching complex). At last the definition of the branching semi-globular nerve in Section 8 and the comparison with the branching semi-cubical nerve in Section 9.

Of course all constructions of this paper may be applied to the case of the merging nerve in an obvious way. The Kan version of the merging nerve will be called the merging semi-globular nerve. Figure 2 is a recapitulation of all simplicial constructions obtained so far (including these of this paper).

This work is part of a research project which aims at setting up an appropriate algebraic setting for the study deformations of HDA which leave invariant their computerscientific properties. See [5] for a sketch of a description of the project.

Let us conclude by some remarks about the terminology. A lot of functors have been introduced so far and some coherence in their naming is necessary. Let C be a noncontracting globular ω-category.

1. ℙC is the path ω-category of C.

2. ℙ^{−}C is the negative semi-path ω-category of C and ℙ^{+}C its positive semi-path ωcategory.

3. For α ∈ {−, +}, ℙ^{α}C is the semi-path ω-category of C.

4. The nerve N^{−}(C) is the branching semi-cubical nerve of C and N^{+}(C) its merging semi-cubical nerve. Without further precision about α ∈ {−, +}, N^{α}(C) is the semi-cubical nerve. It is called corner nerve in previous publications.

5. The simplicial homology shifted by one of the branching semi-cubical nerve is called the branching semi-cubical homology and the simplicial homology shifted by one of the merging semi-cubical nerve is called the merging semi-cubical homology.

6. The nerve N^{gl^{−}}(C) is the branching semi-globular nerve of C and N^{gl^{+}}(C) its merging semi-globular nerve. Without further precision about α ∈ {−, +}, N^{gl^{α}}(C) is the semi-globular nerve.

7. The simplicial homology shifted by one of the branching semi-globular nerve is called the branching semi-globular homology and is denoted by H_{n+1}^{gl^{−}}(C) := H_{n}(N^{gl^{−}}(C)) ; the simplicial homology shifted by one of the merging semi-globular nerve is called the merging semi-globular homology and is denoted by H_{n+1}^{gl^{+}}(C) := H_{n}(N^{gl^{+}}(C)).

2. Preliminaries

The reader who is familiar with papers [6, 7, 8] may want to skip this section.

2.1. Definition. [1, 16, 14] An ω-category is a set A endowed with two families of maps (s_{n} = d_{n}^{−})_{n⩾0} and (t_{n} = d_{n}^{+})_{n⩾0} from A to A and with a family of partially defined 2-ary operations (∗_{n})_{n⩾0} where for any n ⩾ 0, ∗_{n} is a map from {(a, b) ∈ A × A, t_{n}(a) = s_{n}(b)} to A ((a, b) being carried over a ∗_{n} b) which satisfies the following axioms for all α and β in {−, +}:

1. d_{m}^{β}d_{n}^{α}x = \begin{cases}d_{m}^{β}x if m < n \\ d_{n}^{α}x if m ⩾ n \end{cases}

2. s_{n}x ∗_{n} x = x ∗_{n} t_{n}x = x

3. if x ∗_{n} y is well-defined, then s_{n}(x ∗_{n} y) = s_{n}x, t_{n}(x ∗_{n} y) = t_{n}y and for m ≠ n, d_{m}^{α}(x ∗_{n} y) = d_{m}^{α}x ∗_{n} d_{m}^{α}y

4. as soon as the two members of the following equality exist, then (x ∗_{n} y) ∗_{n} z = x ∗_{n} (y ∗_{n} z)

5. if m ≠ n and if the two members of the equality make sense, then (x∗_{n}y)∗_{m}(z∗_{n}w) = (x ∗_{m} z) ∗_{n} (y ∗_{m} w)

6. for any x in A, there exists a natural number n such that s_{n}x = t_{n}x = x (the smallest of these numbers is called the dimension of x and is denoted by dim(x)).

We will sometimes use the notations d_{n}^{−} := s_{n} and d_{n}^{+} = t_{n}. If x is a morphism of an ω-category C, we call s_{n}(x) the n-source of x and t_{n}(x) the n-target of x. The category of all ω-categories (with the obvious morphisms) is denoted by ωCat. The corresponding morphisms are called ω-functors.

Roughly speaking, our ω-categories are strict, globular and contain only morphisms of finite dimension. If C is an object of ωCat, then tr^{n}C denotes the set of morphisms of C of dimension at most n and C_{n} the set of morphisms of dimension exactly n. The map tr^{n} induces for any n ⩾ 0 a functor from ωCat to itself.

2.2. Definition. Let C be an ω-category. Then C is said non-contracting if and only if for any morphism x of C of dimension at least 1, then s_{1}x and t_{1}x are 1-dimensional.

2.3. Definition. Let f be an ω-functor from C to D. The morphism f is non-contract-ing if for any 1-dimensional x ∈ C, the morphism f(x) is a 1-dimensional morphism of D (a priori, f(x) could be either 0-dimensional or 1-dimensional).

2.4. Notation. The category of non-contracting ω-categories with the non-contracting ω-functors is denoted by ωCat_{1}.

2.5. Notation. If C is a non-contracting ω-category, one can consider the ω-category ℙC such that (ℙC)_{i} := C_{i+1}, ∗_{i}^{ℙC} = ∗_{i+1}^{C}, ∗_{i}^{ℙC} = ∗_{i+1}^{C} and ∗_{i}^{ℙC} = ∗_{i+1}^{C} for any i ⩾ 0. The n-source (resp. the n-target, the n-dimensional composition law) of ℙC will still be denoted by s_{n+1} (resp. t_{n+1}, ∗_{n+1}) to avoid possible confusion.

2.6. Definition. The ω-category ℙC is called the path ω-category of C. The mapping ℙ yields a functor from ωCat_{1} to ωCat.

Fundamental examples of ω-categories are the ω-category associated to the n-dimens-ional cube and the one associated to the n-dimensional simplex (the former is denoted by I^{n} and the latter by Δ^{n}). Both families of ω-categories can be characterized in the same way. The first step consists of labeling all faces of the n-cube and of the n-simplex. For the n-cube, this consists of considering all words of length n in the alphabet {−, 0, +}, one word corresponding to the barycenter of a face (with 00 … 0 (n times) =: 0_{n} corresponding to its interior). As for the n-simplex, its faces are in bijection with strictly increasing sequences of elements of {0, 1, …, n}. A sequence of length p + 1 will be of dimension p. If x is a face, let R(x) be the set of subfaces of x (including x) seen respectively as a sub-cube or a sub-simplex. If X is a set of faces, then let R(X) = ⋃_{x∈X} R(x). Notice that R(X ∪ Y) = R(X) ∪ R(Y), R(X ∩ Y) = R(X) ∩ R(Y) and R({x}) = R(x). Then I^{n} and Δ^{n} are the unique ω-categories such that the underlying set is a subset of {R(X), X set of faces} satisfying the following properties :

1. For x a p-dimensional face of I^{n} (resp. Δ^{n}) with p ⩾ 1, s_{p−1}(R(x)) = R(s_{x}) and t_{p−1}(R(x)) = R(t_{x}) where s_{x} and t_{x} are the sets of faces defined below.

2. If X and Y are two elements of I^{n} (resp. Δ^{n}) such that t_{p}(X) = s_{p}(Y) for some p, then X ∪ Y belongs to I^{n} (resp. Δ^{n}) and X ∪ Y = X ∗_{p} Y.

Only the definitions of s_{x} and t_{x} differ between the construction of the family of Δ^{n} and that of I^{n}. Let us give the computation rule in some examples. For the cube, the i-th zero is replaced by (−)^{i} (resp. (−)^{i+1}) for s_{x} (resp. t_{x}). For example, one has s_{0+00} = {-+00, 0++0, 0+0-} and t_{0+00} = {++00, 0+-0, 0+0+}. For the simplex, s_{(04589)} = {(4589), (0489), (0458)} (the elements in odd position are removed) and t_{(04589)} = {(0589), (0459)} (the elements in even position are removed).

One can also notice that if X is an element of I^{n} or Δ^{n}, then X = R(X). Both Δ^{n} and I^{n} are examples of ω-complexes in the sense of [15] where the atoms are

the elements of the form R({x}) where x is a face of Δ^{n} (resp. I^{n}). In such situations, Steiner’s paper [15] proves that the calculation rules are very simple and that they can be summarized as follows :

1. If X and Y are two elements of I^{n} (resp. Δ^{n}) such that t_{p}(X) = s_{p}(Y) for some p, then not only X ∪ Y belongs to I^{n} (resp. Δ^{n}) and X ∪ Y = X ∗_{p} Y but also t_{p}(X) = s_{p}(Y) = X ∩ Y.

2. For x a p-dimensional face of I^{n} (resp. Δ^{n}) with p ⩾ 0, set ∂^{−}R(x) := s_{p−1}R(x) = R(s_{x}) if p > 0 and ∂^{−}R(x) := ∅ if p = 0 and set ∂^{+}R(x) := t_{p−1}R(x) = R(t_{x}) if p > 0 and ∂^{+}R(x) := ∅ if p = 0 ; then for any X in I^{n} (resp. Δ^{n}), then

d_{n}^{α}X = ( ⋃_{a∈X,dim(a)⩽n}R(a)) \ ( ⋃_{b∈X,dim(b)=n+1} (R(b)\∂^{α}R(b)))

with d_{n}^{−} = s_{n} and d_{n}^{+} = t_{n}.

In a simplicial set, the face maps are always denoted by ∂_{i}, the degeneracy maps by ϵ_{i}. Here are the other conventions about simplicial sets and simplicial homology theories (see for example [11] for further information) :

1. Sets : category of sets

2. Sets^{Δ^{op}} : category of simplicial sets

3. Sets_{+}^{Δ^{op}} : category of augmented simplicial sets

4. Comp : category of chain complexes of abelian groups

5. C(A) : unnormalized chain complex of the simplicial set A

6. H_{∗}(A) : simplicial homology of a simplicial set A

7. Ab : category of abelian groups

8. Id : identity map

9. ℤS: free abelian group generated by the set S

3. The negative semi-path ω-category of a non-contracting ω-category

Before going further in the construction of the negative semi-path ω-category of a noncontracting ω-category, one needs to recall some well-known facts about globular sets [17]. Let us consider the small category Glob defined as follows : the objects are all natural numbers and the arrows are generated by s and t in Glob(m, m−1) for any m > 0 and by the relations s ∘ s = s ∘ t, t ∘ s = t ∘ t. By definition, a globular set is a covariant functor from Glob to the category of sets Sets. Let us denote by G_{ω} the corresponding category. Let 𝕌 be the forgetful functor from ωCat to G_{ω}. One can prove by standard categorical arguments the existence of a left adjoint 𝔽 for 𝕌 (see [12] for an explicit construction of this left adjoint).

3.1. Definition. If G is a globular set, then the ω-category 𝔽G is called the free ω-category generated by the globular set G.

Let C be a non-contracting ω-category. Let us denote by R^{−} the equivalence relation which is the reflexive, symmetric and transitive closure of the subset

{(x, x ∗_{0} y); (x, y, x ∗_{0} y) ∈ ℙC × ℙC × ℙC}

of ℙC × ℙC. Now consider the underlying globular set 𝕌ℙC of the path ω-category of a non-contracting ω-category C. Since C is non-contracting, s_{i}(ℙC) ⊂ ℙC and t_{i}(ℙC) ⊂ ℙC for any i ⩾ 1 and the maps s_{i} and t_{i} from ℙC to itself pass to the quotient for i ⩾ 1 because s_{i}(x ∗_{0} y) = s_{i}x ∗_{0} s_{i}y and t_{i}(x ∗_{0} y) = t_{i}x ∗_{0} t_{i}y for any i ⩾ 1.

Let ϕ : 𝕌ℙC → 𝕌ℙC/R^{−} be the canonical morphism of globular sets induced by R^{−}. The identity map 𝕌ℙC → 𝕌ℙC provides the canonical morphism of ω-categories η_{ℙC} : 𝔽𝕌ℙC → ℙC, η being the counit of the adjunction (𝔽, 𝕌). Then let us consider the following pushout in ωCat :

[figure: 𝔽 (𝕌ℙC); 𝔽(ϕ); η_{ℙC}; 𝔽 (𝕌ℙC/R^{−}); A; ℙC; h^{−}; ℙ^{−}C]

3.2. Definition. Let C be a non-contracting ω-category. The ω-category ℙ^{−}C defined above is called the negative semi-path ω-category of C.

The negative semi-path ω-category ℙ^{−}C of C intuitively contains the germs of nonconstant execution paths of C beginning in the same way and the germs of higher dimensional homotopies between them. The construction above yields a functor ℙ^{−} : ωCat_{1} → ωCat and a natural transformation h^{−} : ℙ → ℙ^{−} between functors from ωCat_{1} to ωCat.

3.3. Proposition. Consider the construction of ℙ^{−}C above. Then any element of ℙ^{−}C is a composite of elements of the form A(x) with x ∈ 𝔽 (𝕌ℙC/R^{−}).

Proof. First let us make a short digression. Let \xymatrix{C \ar[r]^{f} \ar[r]_{g} & D} be a pair of ω-functors f and

g from an ω-category C to an ω-category D. Then the coequalizer h : D → E of f and g always exists in ωCat and any element of E is a composite of elements of the form h(x) where x runs over D (otherwise take the image of D in the coequalizer : this image still satisfies the universal property of the equalizer).

Since the canonical ω-functor h^{−} ⊕ A : ℙC ⊕ 𝔽 (𝕌ℙC/R^{−}) → ℙ^{−}C is the coequalizer of 𝔽(ϕ) and η_{ℙC}, the previous remark does apply (the symbol ⊕ meaning the direct sum in ωCat, which coincides with the disjoint union). But h^{−} ⊕ A identifies any element of ℙC with an element of 𝔽 (𝕌ℙC/R^{−}) therefore any element of ℙ^{−}C is a composite of elements of the form A(x) with x running over 𝔽 (𝕌ℙC/R^{−}).

3.4. Theorem. [Universal property satisfied by ℙ^{−}] Let C be a non-contracting ωcategory. Let D be an object of ωCat. Let μ : ℙC → D be an ω-functor such that for any x, y ∈ ℙC, xR^{−}y implies μ(x) = μ(y) in D. Then there exists a unique ω-functor μ̂ : ℙ^{−}C → D such that μ = μ̂ ∘ h^{−}.

Proof. Let μ : ℙC → D be an ω-functor such that for any x, y ∈ ℙC, xR^{−}y implies μ(x) = μ(y) in D. Then μ induces a morphism of globular sets 𝕌(μ) : 𝕌ℙC → 𝕌D and by hypothesis, 𝕌(μ) gives rise to a morphism of globular sets { \atop 𝕌(μ)} : 𝕌ℙC/R^{−} → 𝕌D such that { \atop 𝕌(μ)} ∘ ϕ = 𝕌(μ). Then the composite

\xymatrix{𝔽(𝕌ℙC/R^{−}) \ar[r]^{𝔽({ \atop 𝕌(μ)})} & 𝔽𝕌D \ar[r]^{η_{D}} & D}

yields an ω-functor from 𝔽(𝕌ℙC/R^{−}) to D. Since η : 𝔽𝕌 → Id_{ωCat} is a natural transformation, one gets the commutative diagram

\xymatrix{𝔽𝕌(ℙC) \ar[r]^{𝔽𝕌(μ)} \ar[d]_{η_{ℙC}} & 𝔽𝕌(D) \ar[d]_{η_{D}} \\ ℙC \ar[r]^{μ} & D}

so the equality η_{D} ∘ 𝔽𝕌(μ) = μ ∘ η_{ℙC} holds. Therefore η_{D} ∘ 𝔽({ \atop 𝕌(μ)}) ∘ 𝔽(ϕ) = η_{D} ∘ 𝔽𝕌(μ) = μ ∘ η_{ℙC}. One then obtains the commutative diagram

[figure: 𝔽 (𝕌ℙC); 𝔽(ϕ); η_{ℙC}; 𝔽 (𝕌ℙC/R^{−}); A; η_{D}∘𝔽({ \atop 𝕌(μ)}); ℙC; h^{−}; μ; ℙ^{−}C; D]

Therefore there exists a unique natural transformation μ̂ : ℙ^{−}C → D such that μ̂ ∘ A = η_{D} ∘ 𝔽({ \atop 𝕌(μ)}) and such that μ̂ ∘ h^{−} = μ, i.e. making the following diagram commutative :

[figure: 𝔽 (𝕌ℙC); 𝔽(ϕ); η_{ℙC}; 𝔽 (𝕌ℙC/R^{−}); A; 𝔽({ \atop 𝕌(μ)}); ℙC; h^{−}; μ; ℙ^{−}C; μ̂; 𝔽𝕌D; η_{D}; D]

Suppose that there exists another ν : ℙ^{−}C → D such that ν ∘ h^{−} = μ. Proving that ν = μ̂ is equivalent to proving that ν ∘ A = μ̂ ∘ A by Proposition 3.3. So one is reduced to checking the equality ν ∘ A = η_{D} ∘ 𝔽({ \atop 𝕌(μ)}). The ω-functor 𝔽(ϕ) is clearly surjective on the underlying sets. Therefore proving ν ∘ A = η_{D} ∘ 𝔽({ \atop 𝕌(μ)}) is equivalent to proving

ν ∘ A ∘ 𝔽(ϕ) = η_{D} ∘ 𝔽({ \atop 𝕌(μ)}) ∘ 𝔽(ϕ). But one has ν ∘ A ∘ 𝔽(ϕ) = ν ∘ h^{−} ∘ η_{ℙC} = μ ∘ η_{ℙC} =

η_{D} ∘ 𝔽({ \atop 𝕌(μ)}) ∘ 𝔽(ϕ), which concludes the proof.

By convention, in any of the above ω-categories arising from C, the n-source (resp. the n-target, the n-dimensional composition law) will be still denoted by s_{n+1}, (resp. t_{n+1}, ∗_{n+1}), like for ℙC. The calculation rules in ℙ^{−}C are summarized in the following theorem :

3.5. Theorem. [Calculation rules in ℙ^{−}C] Let C be a non-contracting ω-category. Then any element of ℙ^{−}C is a composite of elements of the form h^{−}(x). Moreover if x and y are two elements of ℙC such that x ∗_{p} y exists in ℙC for some p ⩾ 1, then h^{−}(x ∗_{p} y) = h^{−}(x) ∗_{p} h^{−}(y). And if x and y are two elements of ℙC such that x ∗_{0} y exists in ℙC, then h^{−}(x ∗_{0} y) = h^{−}(x).

Proof. By Proposition 3.3, any element of ℙ^{−}C is a composite of elements of the form A(x) with x ∈ 𝔽 (𝕌ℙC/R^{−}). Since 𝔽(ϕ) is clearly surjective on the underlying sets, any element of ℙ^{−}C is a composite of elements of the form A ∘ 𝔽(ϕ)(x) = h^{−}(η_{ℙC}(x)) with x ∈ 𝔽 (𝕌ℙC). So any element of ℙ^{−}C is a composite of elements of the form h^{−}(x) with x running over ℙC. The last part of the statement of the theorem is a consequence of the fact that h^{−} is an ω-functor and of the universal property satisfied by ℙ^{−}C.

Loosely speaking, the ω-category ℙ^{−}C is the quotient of the free ω-category generated by the equivalence classes of R^{−} in 𝕌ℙC by the calculation rules of C. The calculation rules in ℙ^{−}C are more explicitly described as follows.

1. If x and y are two morphisms of ℙC such that xR^{−}y, then ϕ(x) = ϕ(y) and therefore x and y give rise to the same element in ℙ^{−}C: in other terms h^{−}(x) = h^{−}(y).

2. If x and y are two morphisms of ℙC such that t_{p}xR^{−}s_{p}y for some p ⩾ 1, then ϕ(t_{p}x) = ϕ(s_{p}y) and the corresponding elements can be composed in ℙ^{−}C. Therefore h^{−}(x) ∗_{p} h^{−}(y) exists although x ∗_{p} y does not necessarily exist in ℙC.

[figure: +0−; 0−−; −0−; −−0; 0+−; −+0; 00−; −0+; −00]

Figure 1: Part of the 2-source of the 3-cube

3. If moreover x and y are two elements of ℙC such that this time t_{p}x = s_{p}y for some p ⩾ 1, then h^{−}(x) ∗_{p} h^{−}(y) is the image of x ∗_{p} y by h^{−}, and therefore h^{−}(x ∗_{p} y) = h^{−}(x) ∗_{p} h^{−}(y).

4. If x and y are two morphisms of ℙC such that x ∗_{0} y ∈ ℙC, then h^{−}(x ∗_{0} y) = h^{−}(x).

3.6. Proposition. Let C be a non-contracting ω-category. The 0-source map s_{0} of C induces C_{0}-gradings on 𝔽𝕌ℙC, 𝔽(𝕌ℙC/R^{−}), ℙC and therefore on ℙ^{−}C as well. Let us denote by G^{α,−}𝔽𝕌ℙC, G^{α,−}𝔽(𝕌ℙC/R^{−}), G^{α,−}ℙC and ℙ_{α}^{−}C the fiber of s_{0} in the respective ω-categories over α ∈ C_{0}. Then one has the pushout

[figure: G^{α,−}𝔽 (𝕌ℙC); G^{α,−}𝔽 (𝕌ℙC/R^{−}); G^{α,−}ℙC; ℙ_{α}^{−}C]

Proof. This is due to the fact that s_{0}(x ∗_{0} y) = s_{0}x for any x, y ∈ ℙC.

As an example, consider the ω-category C of Figure 1 which is a part of the 2-source side of the 3-cube. The underlying set of the ω-category ℙ_{R(−−−)}^{−}C is equal to

{h^{−}(R(− − 0)), h^{−}(R(−0−)), h^{−}(R(0 − −)), h^{−}(R(−00)), h^{−}(R(00−)), h^{−}(R(−00)) ∗_{1} h^{−}(R(00−))}

Notice that h^{−}(R(−00)) and h^{−}(R(00−)) become composable in ℙ^{−}C, although they are not composable in the initial ω-category C.

Now let us recall the notion of strict globular ω-groupoid :

3.7. Definition. [2] Let C be a strict globular ω-category. Then C is a strict globular ω-groupoid if and only if for any p-morphism A of C with p ⩾ 1 and any r ⩾ 0, then there exists A′ (a priori depending on r) such that A∗_{r}A′ = s_{r}A = t_{r}A′ and A′∗_{r}A = s_{r}A′ = t_{r}A.

3.8. Theorem. Let C be a non-contracting ω-category. If ℙC is a strict globular ω-groupoid, then ℙ^{−}C is a strict globular ω-groupoid as well.

Proof. Any element X of ℙ^{−}C is a composite of elements h^{−}(x_{i}) for i = 1, …, n by Theorem 3.5. For a given X, let us call the smallest possible n the length of X. Now we check by induction on n the property P (n) : “for any X ∈ ℙ^{−}C of length at most n, for any r ⩾ 1, there exists Y such that X ∗_{r} Y = s_{r}X = t_{r}Y and Y ∗_{r} X = s_{r}Y = t_{r}X”. For n = 1, this is an immediate consequence of the fact that ℙC is an ω-groupoid. Now suppose P (n) proved for n = n_{0} with n_{0} ⩾ 1. Let X be an element of ℙ^{−}C of length n_{0} + 1. Then X = X_{1} ∗_{p} X_{2} for some p ⩾ 1 and with X_{1} and X_{2} of length at most n_{0}. Let r ⩾ 1. Let Y_{1} (resp. Y_{2}) be an inverse of X_{1} (resp. X_{2}) for ∗_{r}. If r ≠ p, then (X_{1} ∗_{p} X_{2}) ∗_{r} (Y_{1} ∗_{p} Y_{2}) = s_{r}X_{1} ∗_{p} s_{r}X_{2} = s_{r}(X_{1} ∗_{p} X_{2}) so Y_{1} ∗_{p} Y_{2} is a solution. If r = p, then (X_{1} ∗_{p} X_{2}) ∗_{p} (Y_{2} ∗_{p} Y_{1}) = s_{p}X_{1}, so Y_{2} ∗_{p} Y_{1} is now a solution.

3.9. Definition. For C a non-contracting ω-category, the ω-category ℙ^{−}C is called the negative semi-path ω-category of C.

In the sequel, all non-contracting ω-categories C will be supposed to have a path ω-category ℙC which is a strict globular ω-groupoid.

4. The semi-path ω-category of the hypercube

Some ω-functors will be constructed in this section using the classical tool of filling of shells.

4.1. Definition. In a simplicial set A, a n-shell is a family (x_{i})_{i=0,...,n+1} of (n + 2) n-simplexes of A such that for any 0 ⩽ i < j ⩽ n + 1, ∂_{i}x_{j} = ∂_{j−1}x_{i}.

4.2. Proposition. [8] Let C be a non-contracting ω-category. Consider a n-shell

(x_{i})_{i=0,...,n+1}

of the globular simplicial nerve of C. Then

1. The labeling defined by (x_{i})_{i=0,...,n+1} yields an ω-functor x (and necessarily exactly one) from Δ^{n+1}\{(01 … n + 1)} to ℙC.

2. Let u be a morphism of C such that

s_{n}u = x (s_{n}R((01 … n + 1)))

and

t_{n}u = x (t_{n}R((01 … n + 1)))

Then there exists one and only one ω-functor still denoted by x from Δ^{n+1} to ℙC such that for any 0 ⩽ i ⩽ n + 1, ∂_{i}x = x_{i} and x((01 … n + 1)) = u.

If (σ_{0} < ⋯ < σ_{r}) is a face of Δ^{n}, then let

ϕ_{n}^{−}(((σ_{0} < ⋯ < σ_{r})) = k_{1} … k_{n+1}

where k_{σ_{i}+1} = 0 and the other k_{j} are equal to −. For n = 2, the set map ϕ looks as follows :

ϕ_{2}^{−} : (012) ↦ 000
ϕ_{2}^{−} : (01) ↦ 00 −
ϕ_{2}^{−} : (02) ↦ 0 − 0
ϕ_{2}^{−} : (12) ↦ −00
ϕ_{2}^{−} : (0) ↦ 0 − −
ϕ_{2}^{−} : (1) ↦ −0 −
ϕ_{2}^{−} : (2) ↦ − − 0

If x is a face of I^{n+1} which belongs to the image of ϕ_{n}^{−}, then denote by x^{⊥} the unique face of Δ^{n} such that ϕ_{n}^{−}(x^{⊥}) = x. Notice that for any face y of Δ^{n}, then ϕ_{n}^{−}(y)^{⊥} = y.

4.3. Proposition. Let us denote by Δ_{i}^{n} for i = 0, …, n and n ⩾ 1 the ω-subcategory of Δ^{n} obtained by keeping only the strictly increasing sequences (σ_{0} < ⋯ < σ_{r}) of {0, 1, …, n} such that i ∉ {σ_{0}, …, σ_{r}}. Then the set map

(σ_{0} < ⋯ < σ_{ℓ} < î ⩽ σ_{ℓ+1} < … σ_{r}) ↦ (σ_{0} < ⋯ < σ_{ℓ} < σ_{ℓ+1} + 1 < … σ_{r} + 1)

(the notation (σ_{0} < ⋯ < σ_{ℓ} < î ⩽ σ_{ℓ+1} < … σ_{r}) above means that we are considering (σ_{0} < ⋯ < σ_{ℓ} < σ_{ℓ+1} < … σ_{r}) but with the additional information that i ⩽ σ_{ℓ+1}) from the set of faces of Δ^{n−1} to Δ_{i}^{n} induces an isomorphism of ω-categories Δ^{n−1} ≅ Δ_{i}^{n}.

Proof. Both ω-categories Δ^{n−1} and Δ_{i}^{n} are freely generated by ω-complexes whose atoms are clearly in bijection. Moreover by Steiner’s formulae recalled in Section 2, the algebraic structure of Δ^{n−1} and Δ_{i}^{n} is completely characterized by the ∂^{−} and ∂^{+} operators, which are obviously preserved by the mapping.

4.4. Proposition. Let us denote by I_{j}^{n+1} for j = 1, …, n + 1 and n ⩾ 1 the ωsubcategory of I^{n+1} obtained by keeping only the words k_{1} … k_{n+1} such that k_{j} = −. Then the set map

ℓ_{1} … ℓ_{n} ↦ ℓ_{1} … ℓ_{j−1} − ℓ_{j} … ℓ_{n}

from the set of faces of I^{n} to I_{j}^{n+1} induces an isomorphism of ω-categories I^{n} ≅ I_{j}^{n+1}.

Proof. Same proof as for Proposition 4.3.

4.5. Definition. One calls valid expression of I^{n+1} (resp. Δ^{n}) a composite of faces of I^{n+1} (resp. Δ^{n}) of strictly positive dimension which makes sense with respect to the calculation rules of I^{n+1}. For example R(−0) ∗_{0} R(0−) is not a valid expression of I^{2}, whereas R(−0) ∗_{0} R(0+) is valid (the latter being equal to s_{1}R(00)).

Let \underline{A} be a valid expression of I^{n+1}. Suppose that s_{0}\underline{A} = R(−_{n+1}). Let us define by induction on the number of faces appearing in \underline{A} an expression \underline{A}^{⊥} using the composition laws and variables in Δ^{n} (we do not know yet whether the latter expression is valid or not in Δ^{n}) :

• if \underline{A} is equal to one face x of I^{n+1}, then this face is necessarily in the image of ϕ_{n}^{−} and one can set \underline{A}^{⊥} := x^{⊥}.

• if \underline{A} = \underline{B} ∗_{0} \underline{C}, then set \underline{A}^{⊥} := \underline{B}^{⊥}.

• if \underline{A} = \underline{B} ∗_{r} \underline{C} for some r ⩾ 1, then set \underline{A}^{⊥} = \underline{B}^{⊥} ∗_{r−1} \underline{C}^{⊥}.

One sees immediately by induction that whenever a face x of I^{n+1} such that s_{0}x = R(−_{n+1}) appears in \underline{A}, then x^{⊥} appears in \underline{A}^{⊥} because in a situation like \underline{A} = \underline{B} ∗_{0} \underline{C}, there cannot be any such face in the expression \underline{C} (since \underline{A} is valid !).

If X is a set of faces of I^{n+1}, let X^{⊥} = R ({y^{⊥}, y ∈ X ∩ Im(ϕ_{n}^{−})}). In the case where X does not contain any element of Im(ϕ_{n}^{−}), then X^{⊥} = ∅. If \underline{A} is a valid expression of I^{n+1}, then \underline{A} = R(\{y variable appearing in \underline{A}\}) because I^{n+1} is an ω-complex. If in addition \underline{A}^{⊥} is a valid expression of Δ^{n} such that s_{0}\underline{A} = R(−_{n+1}), then the two meanings of \underline{A}^{⊥} coincide. If X and Y are two sets of faces of I^{n+1}, then it is obvious that X^{⊥} ∪ Y^{⊥} = (X ∪ Y)^{⊥}, X^{⊥} ∩ Y^{⊥} = (X ∩ Y)^{⊥} and X^{⊥}\Y^{⊥} = (X\Y)^{⊥}.

4.6. Proposition. Let a be a face of I^{n+1}. Then

(∂^{−}R(a))^{⊥} = ∂^{−}R(a^{⊥})

and

(∂^{+}R(a))^{⊥} = ∂^{+}R(a^{⊥}).

Proof. If a is a 0-dimensional face of I^{n+1}, then both sides of the equalities are equal to the empty set. Let us then suppose that a is at least of dimension 1. If a does not belong to the image of ϕ_{n}^{−}, then both sides are again empty. So suppose that a ∈ Im(ϕ_{n}^{−}). Then a = k_{1} … k_{n+1} where {k_{1}, …, k_{n+1}} ⊂ {−, 0}. Let {i_{1} < ⋯ < i_{s}} = {i ∈ [1, n + 1], k_{i} = 0}. Then (∂^{−}R(a))^{⊥} = R ({k_{1} … [(−)]_{i_{2k+1}} … k_{n+1}, 1 ⩽ 2k + 1 ⩽ s})^{⊥} by definition of ∂^{−} in I^{n+1} and by definition of (−)^{⊥} where the notation k_{1} … [α]_{i} … k_{n+1} means that k_{i} is replaced by α. On the other hand, ∂^{−}R(a^{⊥}) = ∂^{−}R((i_{1}−1 < ⋯ < i_{s}−1)) = (∂^{−}R(a))^{⊥}.

4.7. Proposition. For any valid expression \underline{A} of I^{n+1} such that s_{0}\underline{A} = R(−_{n+1}), then \underline{A}^{⊥} is a valid expression of Δ^{n}.

Proof. We are going to prove by induction on r the statement P (r) : “for any valid expression \underline{A} of I^{n+1} with at most r variables such that s_{0}\underline{A} = R(−_{n+1}), the expression \underline{A}^{⊥} is valid in Δ^{n}.” If r = 1, then \underline{A} = R(\{x\}) for some face x of I^{n+1} ∩ Im(ϕ_{n}^{−}). So \underline{A}^{⊥} = R(\{x^{⊥}\}) which is necessarily a valid expression in Δ^{n}. So P (1) holds. Let us suppose that P (r) is proved for r ⩽ r_{0} and let us consider a valid expression \underline{A} of I^{n+1} with r_{0} + 1 variables. Then \underline{A} = \underline{B} ∗_{m} \underline{C} with \underline{B} and \underline{C} being valid expressions having less than r_{0} variables. By the induction hypothesis, both \underline{B}^{⊥} and \underline{C}^{⊥} are valid expressions of Δ^{n}. If m = 0, then by construction \underline{A}^{⊥} = \underline{B}^{⊥} and there is nothing to prove. Otherwise by construction again, \underline{A}^{⊥} = \underline{B}^{⊥}∗_{m−1} \underline{C}^{⊥}. Then by Steiner’s formulae and by Proposition 4.6,

t_{m−1}(\underline{B}^{⊥}) = (  ⋃_{a∈\underline{B}^{⊥},dim(a)⩽m−1} R(a)) \ (  ⋃_{b∈\underline{B}^{⊥},dim(b)=m} (R(b)\∂^{−}R(b)))

= (  ⋃_{a∈\underline{B}^{⊥},dim(a)⩽m−1} R(ϕ_{n}^{−}(a))^{⊥}) \ (  ⋃_{b∈\underline{B}^{⊥},dim(b)=m} (R(ϕ_{n}^{−}(b))^{⊥}\∂^{−}R(ϕ_{n}^{−}(b))^{⊥}))

= (  ⋃_{a∈\underline{B}∩Im(ϕ_{n}^{−}),dim(a)⩽m} R(a)^{⊥}) \ (  ⋃_{b∈\underline{B}∩Im(ϕ_{n}^{−}),dim(b)=m+1} (R(b)^{⊥}\∂^{−}R(b)^{⊥}))

= (  ⋃_{a∈\underline{B},dim(a)⩽m} R(a)^{⊥}) \ (  ⋃_{b∈\underline{B},dim(b)=m+1} (R(b)^{⊥}\∂^{−}R(b)^{⊥}))
= (t_{m}\underline{B})^{⊥}
= (s_{m}\underline{C})^{⊥}
= s_{m−1}(\underline{C}^{⊥})

Consequently, t_{m−1}\underline{B}^{⊥} = s_{m−1}\underline{C}^{⊥}, which proves that \underline{A}^{⊥} is a valid expression of Δ^{n}.

4.8. Corollary. Let \underline{A} and \underline{B} be two valid expressions of I^{n+1} such that s_{0}\underline{A} = s_{0}\underline{B} = R(−_{n+1}) and such that \underline{A} ∗_{m} \underline{B} exists for some m ⩾ 1. Then \underline{A}^{⊥} ∗_{m−1} \underline{B}^{⊥} is a valid expression of Δ^{n} and (\underline{A} ∗_{m} \underline{B})^{⊥} = \underline{A}^{⊥} ∗_{m−1} \underline{B}^{⊥}.

4.9. Theorem. For n ⩾ 0, the isomorphism of ω-categories ℙ_{R(−_{n+1})}^{−}(I^{n+1}) ≅ Δ^{n} holds.

Proof. The proof is threefold : 1) one has to prove that ϕ_{n}^{−} induces an ω-functor ϕ̂_{n}^{−} from Δ^{n} to ℙ^{−}(I^{n+1}) ; 2) afterwards we check that the underlying set map of ϕ̂_{n}^{−} is injective ; 3) finally we prove that the image of ϕ̂_{n}^{−} is the underlying set of ℙ_{R(−_{n+1})}^{−}(I^{n+1}) as a whole.

Step 1. We are going to prove P (n) : “the set map ϕ_{n}^{−} from the set of faces of Δ^{n} to ℙ^{−}(I^{n+1}) induces an ω-functor from Δ^{n} to ℙ^{−}(I^{n+1})” by induction on n ⩾ 0 and using Proposition 4.2. The ω-category ℙ^{−}(I^{1}) is the ω-category 2_{0} generated by one 0-morphism. Therefore P (0) holds. One has the commutative diagrams

\xymatrix{\{Faces of Δ_{i}^{n}\} \ar[r]^{ϕ_{n}^{−}↾_{Δ^{n}_{i}}} & I_{i+1}^{n+1} ⊂ I^{n+1} \\ \{Faces of Δ^{n−1}\} \ar[u]^{≅} \ar[r]^{ϕ_{n−1}^{−}} & I^{n} \ar[u]^{≅}}

for any i = 0, …, n. Therefore by Proposition 4.2 and the induction hypothesis, one sees that ϕ_{n}^{−} induces an ω-functor ϕ̂_{n}^{−} from Δ^{n}\{(01 … n)} to ℙ^{−}(I^{n+1}).

It remains to prove that s_{n}(R(0_{n+1}))^{−} = ϕ̂_{n}^{−}s_{n−1}(0 < ⋯ < n) and that t_{n}(R(0_{n+1}))^{−} = ϕ̂_{n}^{−}t_{n−1}(0 < ⋯ < n) to complete the proof. Let us check the first equality. By Proposition 4.7, (s_{n}R(0_{n+1}))^{⊥} is a valid expression of Δ^{n} in which the (n − 1)-dimensional faces (0 < ⋯ < ˆ2i < ⋯ < n) for 0 ⩽ 2i ⩽ n appear. In the ω-complex Δ^{n}, that means that (s_{n}R(0_{n+1}))^{⊥} contains not only the faces (0 < ⋯ < ˆ2i < ⋯ < n), but also all their subfaces. Since (0 < 1 < ⋯ < n) ∉ (s_{n}R(0_{n+1}))^{⊥}, then necessarily (s_{n}R(0_{n+1}))^{⊥} = s_{n−1}R(0 < 1 < ⋯ < n). Because of the calculation rules in ℙ^{−}(I^{n+1}) described in Theorem 3.5, ϕ_{n}^{−} ((s_{n}R(0_{n+1}))^{⊥}) is necessarily equal to s_{n}(R(0_{n+1}))^{−}. And the desired equality is then proved.

Step 2. The previous paragraph shows that there is a well defined ω-functor ψ_{n} from ℙ_{R(−_{n+1})}^{−}(I^{n+1}) to Δ^{n} characterized by

• if x ∈ Im(ϕ_{n}^{−}) (in particular x is a face of I^{n+1}), then ψ_{n}(R(x))^{−} = R(x^{⊥})

• for x, y ∈ ℙ_{R(−_{n+1})}^{−}(I^{n+1}), if x∗_{r} y exists for some r ⩾ 1, then ψ_{n}(x∗_{r} y) = ψ_{n}(x)∗_{r−1} ψ_{n}(y).

Moreover ψ_{n} ∘ ϕ̂_{n}^{−} = Id and therefore ϕ̂_{n}^{−} is injective.

Step 3. This is an immediate consequence of Theorem 3.5 and of the construction of ϕ̂_{n}^{−}.

4.10. Corollary. For n ⩾ 0,

ℙ^{−}(I^{n+1}) = ⨁_{1⩽p⩽n+1}(Δ^{p−1})^{⊕C_{n+1}^{p}}

where ⊕ is the direct sum in the category of ω-categories (which corresponds for the underlying sets to the disjoint union).

Proof. By Proposition 3.6, the ω-category ℙ^{−}(I^{n+1}) is graded by the vertices of I^{n+1} (however G^{+_{n+1},−}ℙ^{−}(I^{n+1}) = ∅). So this is a consequence of Theorem 4.9.

The isomorphism of Theorem 4.9 is actually more than only an isomorphism of ωcategories. Indeed, let \underline{Δ} be the unique small category such that a presheaf over \underline{Δ} is exactly a simplicial set [11, 18]. The category \underline{Δ} has for objects the finite ordered sets [n] = {0 < 1 < ⋯ < n} for all integers n ⩾ 0 and has for morphisms the nondecreasing monotone functions. One is used to distinguish in this category the morphisms ϵ_{i} : [n − 1] → [n] and η_{i} : [n + 1] → [n] defined as follows for each n and i = 0, …, n:

ϵ_{i}(j) = \{ \begin{matrix}j  if j < i \\ j + 1 if j ⩾ i \end{matrix} \} , η_{i}(j) = \{ \begin{matrix}j  if j ⩽ i \\ j − 1 if j > i \end{matrix} \}

It is well-known ([16]) that the map [n] ↦ Δ^{n} induces a functor Δ^{∗} from \underline{Δ} to ωCat by setting ϵ_{i} ↦ Δ^{ϵ_{i}} and η_{i} ↦ Δ^{η_{i}} where

• for any face (σ_{0} < ⋯ < σ_{s}) of Δ^{n−1}, Δ^{ϵ_{i}}(σ_{0} < ⋯ < σ_{s}) is the only face of Δ^{n} having ϵ_{i}{σ_{0}, …, σ_{s}} as set of vertices ;

• for any face (σ_{0} < ⋯ < σ_{r}) of Δ^{n+1}, Δ^{η_{i}}(σ_{0} < ⋯ < σ_{r}) is the only face of Δ^{n} having η_{i}{σ_{0}, …, σ_{r}} as set of vertices.

For a face σ = {σ_{1}, …, σ_{s}} of Δ^{n} with σ_{1} < ⋯ < σ_{s}, let ϕ_{n}^{−}(σ) := ϕ_{n}^{−}(σ_{1} < ⋯ < σ_{s}). Then one has

4.11. Proposition. Let δ_{i}^{−} : I^{n} → I^{n+1} be the ω-functor corresponding by Yoneda’s lemma to the face map ∂_{i}^{−} : ωCat(I^{n+1}, −) → ωCat(I^{n}, −) and let γ_{i}^{−} : I^{n+2} → I^{n+1} be the ω-functor corresponding by Yoneda’s lemma to the degeneracy maps Γ_{i}^{−} : ωCat(I^{n+1}, −) → ωCat(I^{n+2}, −) for 1 ⩽ i ⩽ n + 1. Then the following diagrams are commutative :

\xymatrix{Δ^{n−1} \ar[r]^{Δ^{ϵ_{i}}} \ar[d]_{ϕ_{n−1}^{−}} & Δ^{n} \ar[d]_{ϕ_{n}^{−}} & Δ^{n+1} \ar[r]^{Δ^{η_{i}}} \ar[d]_{ϕ_{n+1}^{−}} & Δ^{n} \ar[d]_{ϕ_{n}^{−}} \\ I^{n} \ar[r]^{δ_{i+1}^{−}} & I^{n+1} & I^{n+2} \ar[r]^{γ_{i+1}^{−}} & I^{n+1}}

Proof. This is a remake of the proof that the natural morphism h^{−} from the globular to the branching semi-cubical nerve preserves the simplicial structure of both sides (see [8]).

Remember that the geometric explanation of Proposition 4.11 is again that close to a corner, the intersection of an n-cube by an hyperplane is exactly the (n − 1)-simplex.

4.12. Corollary. For 0 ⩽ i ⩽ n, the mapping

k_{1} … k_{n+1} ↦ δ_{i+1}^{−}(k_{1} … k_{n+1}) = k_{1} … k_{i}[−]_{i+1}k_{i+1} … k_{n+1}

induces an ω-functor from ℙ_{R(−_{n})}^{−}(I^{n}) to ℙ_{R(−_{n+1})}^{−}(I^{n+1}). And the mapping

k_{1} … k_{n+2} ↦ γ_{i+1}^{−}(k_{1} … k_{n+2}) = k_{1} … k_{i} max(k_{i+1}, k_{i+2})k_{i+3} … k_{n+2}

induces an ω-functor from ℙ_{R(−_{n+2})}^{−}(I^{n+2}) to ℙ_{R(−_{n+1})}^{−}(I^{n+1}). This way, the mapping [n] ↦ ℙ_{R(−_{n+1})}^{−}(I^{n+1}) induces a functor from \underline{Δ} to ωCat which is isomorphic to the functor Δ^{∗}. In other terms, the family of maps (ϕ_{n})_{n⩾0} induces an isomorphism of functors from \underline{Δ} to ωCat

Δ^{∗} ≅ ℙ_{R(−_{∗+1})}^{−}(I^{∗+1}).

5. Simplicial cut

The branching semi-globular nerve will not match the notion of cut as presented in [8]. A slight modification of that definition is therefore necessary. This is precisely the purpose of this section. The reader does not need to know the previous definition of a cut.

5.1. Definition. A cut is a triple (F, \underline{P} , ev) where \underline{P} is a functor from ωCat_{1} to ωCat, F a functor from ωCat_{1} to Sets_{+}^{Δ^{op}}, and ev = (ev_{n})_{n⩾0} a family of natural transformations ev_{n} : F_{n} ⟶ tr^{n}\underline{P} where F_{n} is the set of n-simplexes of F. A morphism of cuts from (F, \underline{P} , ev) to (G, \underline{Q}, ev) is a pair (ϕ, ψ) such that ϕ is a natural transformation of functors from F to G and ψ a natural transformation of functors from \underline{P} to \underline{Q} which makes the following diagram commutative for any n ⩾ 0 :

\xymatrix{F_{n} \ar[d]_{ϕ_{n}} \ar[r]^{^{ev^{n}}} & tr^{n}\underline{P} \ar[d]_{ψ_{n}} \\ G_{n} \ar[r]^{_{ev_{n}}} & _{tr_{n}\underline{Q}}}

If (F, ev) is a cut in the sense of [8], then (F, ℙ, ev) is a cut in the sense of the above definition. One can omit ev and simply denote the cut (F, \underline{P} , ev) by (F, \underline{P}).

For such a cut, one can define the associated homology theory as in [8]. If (F, \underline{P}) is a cut, let C_{n+1}^{(F,\underline{P})}(C) := C_{n}(F(C)) and let H_{n+1}^{(F,\underline{P})} be the corresponding homology theory for n ⩾ −1.

To illustrate the definition, let us recall now the definition of the branching semi-cubical cut [6, 7]. Let C be a non-contracting ω-category. We set

ωCat(I^{n+1}, C)^{−} := {x ∈ ωCat(I^{n+1}, C), d_{0}^{−}(u) = −_{n+1} and dim(u) = 1 ⟹ dim(x(u)) = 1}

where −_{n+1} is the initial state of I^{n+1}. For all (i, n) such that 0 ⩽ i ⩽ n, the face maps ∂_{i} from ωCat(I^{n+1}, C)^{−} to ωCat(I^{n}, C)^{−} are the arrows ∂_{i+1}^{−} defined by

∂_{i+1}^{−}(x)(k_{1} … k_{n+1}) = x(k_{1} … [−]_{i+1} … k_{n+1})

and the degeneracy maps ϵ_{i} from ωCat(I^{n}, C)^{−} to ωCat(I^{n+1}, C)^{−} are the arrows Γ_{i+1}^{−} defined by setting

Γ_{i}^{−}(x)(k_{1} … k_{n}) := x(k_{1} … max(k_{i}, k_{i+1}) … k_{n})

with the order − < 0 < +.

Let C be a non-contracting ω-category. The ℕ-graded set N_{∗}^{−}(C) = ωCat(I^{∗+1}, C)^{−} together with the convention N_{−1}^{−}(C) = C_{0}, endowed with the maps ∂_{i} and ϵ_{i} above defined with moreover ∂_{−1} = s_{0} and with ev(x) = x(0_{n}) for x ∈ ωCat(I^{n}, C) is an augmented simplicial set and (N^{−}, ℙ) becomes a simplicial cut. It is called the branching simplicial cut associated to C. Set H_{n+1}^{−}(C) := H_{n}(N^{−}(C)) for n ⩾ −1. This homology theory is called the branching semi-cubical homology.

6. Thin elements in simplicial cuts and reduced homology

Let (F, \underline{P}) be a simplicial cut. Let M_{n}^{F} : ωCat_{1} ⟶ Ab be the functor defined as follows : the group M_{n}^{(F,\underline{P})}(C) is the subgroup generated by the elements x ∈ F_{n−1}(C) such that ev(x) ∈ tr^{n−2}\underline{P} C for n ⩾ 2 and with the convention M_{0}^{(F,\underline{P})}(C) = M_{1}^{(F,\underline{P})}(C) = 0 and the definition of M_{n}^{F} is obvious on non-contracting ω-functors.

6.1. Definition. The elements of M_{∗}^{(F,\underline{P})}(C) are called thin.

To illustrate the definition above, let us consider again the case of the branching semicubical cut. A thin element of N_{n−1}^{−}(C) is nothing else but an ω-functor f ∈ ωCat(I^{n}, C)^{−} such that f(0_{n}) ∈ tr^{n−2}ℙC = tr^{n−1}C, that is f(0_{n}) is of dimension at most n − 1. So f corresponds intuitively to a n-cube without volume.

Let us come back now to the general situation. Let CR_{n}^{(F,\underline{P})} : ωCat_{1} ⟶ Comp(Ab) be the functor defined by

CR_{n}^{(F,\underline{P})} := C_{n}^{(F,\underline{P})}/(M_{n}^{(F,\underline{P})} + ∂M_{n+1}^{(F,\underline{P})})

where Comp(Ab) is the category of chain complexes of abelian groups and endowed with the differential map ∂.

6.2. Definition. This chain complex is called the reduced complex associated to the cut (F, \underline{P}) and the corresponding homology is denoted by HR_{∗}^{(F,\underline{P})} and is called the reduced homology associated to (F, \underline{P}).

A morphism of cuts from (F, \underline{P}) to (G, \underline{Q}) yields natural morphisms from H_{∗}^{(F,\underline{P})}

to H_{∗}^{(G,\underline{Q})} and from HR_{∗}^{(F,\underline{P})} to HR_{∗}^{(G,\underline{Q})}. There is also a canonical natural transformation R^{(F,\underline{P})} from H_{∗}^{(F,\underline{P})} to HR_{∗}^{(F,\underline{P})}, functorial with respect to (F, \underline{P}), that makes the following diagram commutative :

\xymatrix{H_{∗}^{(F,\underline{P})} \ar[r]^{R^{(F,\underline{P})}} \ar[d] & HR_{∗}^{(F,\underline{P})} \ar[d] \\ H_{∗}^{(G,\underline{Q})} \ar[r]^{R^{(}G,\underline{Q})} & _{HR{(G,\underline{Q}) \atop ∗}}}

6.3. Notation. The reduced branching semi-cubical complex is denoted by CR^{−} and the reduced branching semi-cubical homology theory is denoted by HR^{−}.

7. Regular cut

The next definition presents the notion of regular cut. It makes the construction of folding operators possible.

7.1. Definition. A cut (F, \underline{P}) is regular if and only if it satisfies the following properties :

1. for any ω-category C, the set F_{−1}(C) only depends on tr^{0}C = C_{0} : i.e. for any ω-categories C and D, C_{0} = D_{0} implies F_{−1}(C) = F_{−1}(D).

2. F_{0} := tr^{0}\underline{P}.

3. ev ∘ ϵ_{i} = ev.

4. for any natural transformation of functors μ from F_{n−1} to F_{n} with n ⩾ 1, and for any natural map □ from tr^{n−1}\underline{P} to F_{n−1} such that ev∘□ = Id_{tr}^{n−1}\underline{P}, there exists one and only one natural transformation μ.□ from tr^{n}\underline{P} to F_{n} such that the following diagram commutes

\xymatrix{tr^{n}\underline{P} \ar[rr]^{Id^{^{tr}^{n}\underline{P}}} \ar[r]^{μ.□} & F_{n} \ar[r]^{^{ev^{n}}} & tr^{n}\underline{P} \\ _{tr_{n−1}\underline{P}} \ar[rr]_{Id_{_{tr}_{n−1}\underline{P}}} \ar[u]^{i_{n}} \ar[r]^{□} & F_{n−1} \ar[r]^{_{ev_{n−1}}} \ar[u]^{μ} & _{tr_{n−1}\underline{P}} \ar[u]^{i_{n}}}

where i_{n} is the canonical inclusion functor from tr^{n−1}\underline{P} to tr^{n}\underline{P}.

5. let □_{1}^{(F,\underline{P})} := Id_{F_{0}} and □_{n}^{(F,\underline{P})} := ϵ_{n−2}…. ϵ_{0}.□_{1}^{(F,\underline{P})} be natural transformations from tr^{n−1}\underline{P} to F_{n−1} for n ⩾ 2 ; then the natural transformations ∂_{i}□_{n}^{(F,\underline{P})} for 0 ⩽ i ⩽ n − 1 from tr^{n−1}\underline{P} to F_{n−2} satisfy the following properties

(a) \{ev∂_{n−2}□_{n}^{(F,\underline{P})}, ev∂_{n−1}□_{n}^{(F,\underline{P})}\} = \{s_{n−1}, t_{n−1}\}.

(b) if for some ω-category C and some u ∈ C_{n}, ev∂_{i}□_{n}^{(F,\underline{P})}(u) = d_{p}^{α}u for some p ⩽ n and for some α ∈ \{−, +\}, then ∂_{i}□_{n}^{(F,\underline{P})} = ∂_{i}□_{n}^{(F,\underline{P})}d_{p}^{α}.

6. let Φ_{n}^{(F,\underline{P})} := □_{n}^{(F,\underline{P})} ∘ev be a natural transformation from F_{n−1} to itself ; then Φ_{n}^{(F,\underline{P})} induces the identity natural transformation on CR_{n}^{(F,\underline{P})}.

7. if x, y and z are three elements of F_{n}(C), and if ev(x) ∗_{p} ev(y) = ev(z) for some 1 ⩽ p ⩽ n, then x + y = z in CR_{n+1}^{(F,\underline{P})}(C) and in a functorial way.

If (F, \underline{P}) is a regular cut, then the natural transformation Φ_{n}^{(F,\underline{P})} is called the n-dimension-al folding operator of the cut (F, \underline{P}). By convention, one sets □_{0}^{(F,\underline{P})} = Id_{F_{−1}} and Φ_{0}^{(F,\underline{P})} = Id_{F_{−1}}. There are no ambiguities to set Φ^{(F,\underline{P})}(x) := Φ_{n+1}^{(F,\underline{P})}(x) for x ∈ F_{n}(C) for some ω-category C. So Φ^{(F,\underline{P})} defines a natural transformation, and even a morphism of cuts, from (F, \underline{P}) to itself. However beware of the fact that there is really an ambiguity in the notation □^{(F,\underline{P})} : so the latter will not be used.

Now here are some trivial remarks about regular cuts :

• Let f be a natural set map from tr^{0}\underline{P} C = C_{1} to itself. Let 2_{1} be the ω-category generated by one 1-morphism A. Then necessarily f(A) = A and therefore f = Id. So the above axioms imply that ev_{0} = Id.

• The map Φ_{n}^{(F,\underline{P})} induces the identity natural transformation on HR_{n}^{(F,\underline{P})}.

• For any n ⩾ 1, there exists non-thin elements x in F_{n−1}(C) as soon as C_{n} ≠ ∅. Indeed, if u ∈ C_{n}, ev □_{n}^{(F,\underline{P})}(u) = u, therefore □_{n}^{(F,\underline{P})}(u) is a non-thin element of F_{n−1}(C).

We end this section by some general facts about regular cuts.

7.2. Proposition. Let f be a morphism of cuts from (F, \underline{P}) to (G, \underline{Q}). Suppose that (F, \underline{P}) and (G, \underline{Q}) are regular. Then the equality Φ^{(G,\underline{Q})} ∘ f = f ∘ Φ^{(F,\underline{P})} holds as natural transformation from (F, \underline{P}) to (G, \underline{Q}). In other terms, the following diagram is commutative :

\xymatrix{(F, \underline{P}) \ar[r]^{f} \ar[d]_{Φ^{(F,\underline{P})}} & (G, \underline{Q}) \ar[d]^{Φ^{(G,\underline{Q})}} \\ (F, \underline{P}) \ar[r]^{f} & (G, \underline{Q})}

Proof. See [8].

7.3. Proposition. If u is a (n + 1)-morphism of C with n ⩾ 1, then □_{n+1}^{(F,\underline{P})}u is an homotopy within the simplicial set F(C) between □_{n}^{(F,\underline{P})}s_{n}u and □_{n}^{(F,\underline{P})}t_{n}u.

Proof. See [8].

7.4. Corollary. If x ∈ CR_{n+1}^{(F,\underline{P})}(C), then ∂x = ∂□_{n+1}^{(F,\underline{P})}x = □_{n}^{(F,\underline{P})}s_{n}x − □_{n}^{(F,\underline{P})}t_{n}x in CR_{n}^{(F,\underline{P})}(C). In other terms, the differential map from CR_{n+1}^{(F,\underline{P})}(C) to CR_{n}^{(F,\underline{P})}(C) with n ⩾ 1 is induced by the map s_{n} − t_{n}.

Now let us come back to the particular example of the branching semi-cubical cut.

7.5. Theorem. [7] The branching semi-cubical cut is regular.

7.6. Notation. The branching semi-cubical folding operators are denoted by Φ^{−} and □_{n}^{−}.

7.7. Definition. [7] Set

• CF_{0}^{−}(C) := ℤC_{0}

• CF_{1}^{−}(C) := ℤC_{1}

• CF_{n}^{−}(C) = ℤC_{n}/{x ∗_{0} y = x, x ∗_{1} y = x + y, …, x ∗_{n−1} y = x + y mod ℤtr^{n−1}C} for n ⩾ 2

with the differential map s_{n−1} − t_{n−1} from CF_{n}^{−}(C) to CF_{n−1}^{−}(C) for n ⩾ 2 and s_{0} from CF_{1}^{−}(C) to CF_{0}^{−}(C). This chain complex is called the formal negative corner complex. The associated homology is denoted by HF^{−}(C) and is called the formal negative corner homology of C. The map CF_{∗}^{−} (resp. HF_{∗}^{−}) induces a functor from ωCat_{1} to the category of chain complexes of groups Comp(Ab) (resp. to the category of abelian groups Ab).

Since the branching semi-cubical cut is regular, then □_{n}^{−}(x ∗_{p} y) = □_{n}^{−}(x) + □_{n}^{−}(y) in CR_{n}^{−}(C) for any non-contracting ω-category C, for any p ⩾ 1 and any x, y ∈ C_{n} as soon as x ∗_{p} y exists. Moreover we have with the same notation □_{n}^{−}(x ∗_{0} y) = □_{n}^{−}(x) as soon as x ∗_{0} y exists [7]. So the folding operators □_{n}^{−} induce a natural morphism of chain complexes from CF^{−} to CR^{−}.

8. The branching semi-globular nerve

Using the functor Δ^{∗} from \underline{Δ} to ωCat, one obtains the well-known simplicial nerve of ω-category N_{∗}(C) := ωCat(Δ^{∗}, C) introduced for the first time in [16]. Now we have the necessary tools in hand to define the branching semi-globular cut of a non-contracting ω-category.

8.1. Definition. Let C be a non-contracting ω-category. Then set

N_{n}^{gl^{−}}(C) = ωCat(Δ^{n}, ℙ^{−}C)

and N_{−1}^{gl^{−}}(C) = C_{0} with ∂_{−1}(x) = s_{0}x. Then N^{gl^{−}} induces a functor from ωCat_{1} to Sets_{+}^{Δ^{op}}. The triple (N^{gl^{−}}, ℙ^{−}, ev) with ev(x) = x(0 < 1 < ⋯ < n) is called the branching semi-globular cut.

8.2. Proposition. If ℙC is a strict globular ω-groupoid, then the branching semi-globu-lar cut of C is Kan.

Proof. This is an immediate corollary of Theorem 3.8.

8.3. Theorem. The branching semi-globular cut is regular.

Proof. Let C be a non-contracting ω-category. Let D be the unique ω-category such that ℙD = ℙ^{−}C and with s_{0}(ℙD) = {α}, t_{0}(ℙD) = {β} and α ≠ β. Then N_{n}^{gl}(D) = N_{n}^{gl^{−}}(C) for any n ⩾ 0. So the regularity of the branching semi-globular nerve comes from that of the globular nerve [8].

The reduced branching semi-globular homology theory is denoted by HR^{gl^{−}}, the branching semi-globular folding operators by Φ^{gl^{−}} and □_{n}^{gl^{−}}.

8.4. Theorem. Let C be a non-contracting ω-category. Then for any n ⩾ 0, CR_{n}^{gl^{−}}(C) is generated by the Φ^{gl^{−}}(h^{−}(x)) for x running over C_{n}. Moreover, one has

• if x, y ∈ C_{n} and if x ∗_{0} y exists, then Φ^{gl^{−}}(h^{−}(x ∗_{0} y)) = Φ^{gl^{−}}(h^{−}(x))

• if x, y ∈ C_{n} and if x ∗_{r} y exists for r ⩾ 1, then Φ^{gl^{−}}(h^{−}(x ∗_{r} y)) = Φ^{gl^{−}}(h^{−}(x)) + Φ^{gl^{−}}(h^{−}(y)) in CR_{n}^{gl^{−}}(C).

Proof. The group CR_{n}^{gl^{−}}(C) is generated by the Φ^{gl^{−}}(X) for X ∈ ℙ^{−}C. By Theorem 3.5, X = Ψ(h^{−}(x_{1}), …, h^{−}(x_{s})) where Ψ is an expression using only the composition laws ∗_{h} for h ⩾ 1 and where x_{1}, …, x_{s} ∈ ℙC. By regularity of the branching semi-globular nerve, one deduces that CR_{n}^{gl^{−}}(C) is generated by the Φ^{gl^{−}}(h^{−}(x)) for x running over C_{n}. The remaining part of the statement is clear.

So, as the family of operators □_{n}^{−} does for the semi-cubical case, the family of operators (□_{n}^{gl^{−}})_{n⩾0} induces a natural morphism of chain complexes from CF_{∗}^{−} to CR_{∗}^{gl^{−}} by Theorem 8.4.

We close this section by the statement of the “thin elements” conjecture for the branching semi-globular nerve :

8.5. Conjecture. Let C be a non-contracting ω-category which is the free ω-category freely generated by a precubical set. Consider a linear combination ∑_{i∈I} λ_{i}x_{i} of elements of M_{n}^{gl^{−}}(C) with ∀i ∈ I, λ_{i} ∈ ℤ. Then this linear combination is a cycle if and only if it is a boundary for the simplicial differential map.

8.6. Conjecture. [7] (The thin elements conjecture) Let K be a precubical set. Then the chain complex morphisms C^{gl^{±}}(F (K)) → CR^{gl^{±}}(F (K)) induce isomorphisms in homology.

\xymatrix{ & N^{gl} \ar[dr]^{h^{+}} \ar[dl]_{h^{−}} \ar[ddr]_{N (ℙC→ℙ^{+}C)} \ar[ddl]^{N (ℙC→ℙ^{−}C)} \\ N^{−} \ar[d]_{f↦f^{−}} &  & N^{+} \ar[d]^{f↦f^{+}} \\ N^{gl^{−}} &  & N^{gl^{+}}}

Figure 2: Recapitulation of all simplicial constructions

8.7. Conjecture. (The extended thin elements conjecture) Let K be a precubical set. Then the chain complex morphisms C^{gl^{±}}({ \atop F (K)}) → CR^{gl^{±}}({ \atop F (K)}) induce isomorphisms in homology.

9. Comparison with the branching semi-cubical nerve

9.1. Theorem. There exists one and only one morphism of cuts from the branching semi-cubical cut to the branching semi-globular cut such that the underlying natural transformation from ℙ to ℙ^{−} is the canonical morphism ℙ → ℙ^{−} appearing in the definition of ℙ^{−}.

Proof. Let f_{1} and f_{2} be two morphisms of cuts from the branching semi-cubical nerve to the branching semi-globular nerve. For any non-contracting ω-category C, (f_{1})_{−1} and (f_{2})_{−1} induce natural set maps from C_{0} to C_{0}. Since the only natural transformation from the identity functor of the category of sets to itself is the identity transformation (to see that, consider the case of a singleton), then (f_{1})_{−1} and (f_{2})_{−1} are both equal to the identity of C_{0}. If C is the free ω-category 2_{1}(A) generated by one 1-morphism A, then C is noncontracting. In that case, N_{0}^{−}(C) = {A} = N_{0}^{gl^{−}}(C). So in that case, (f_{1})_{0}(A) = (f_{2})_{0}(A). For any non-contracting ω-category C and any x ∈ C_{1}, there exists a unique ω-functor \underline{x} from 2_{1}(A) to C such that \underline{x}(A) = x. So by naturality, (f_{1})_{0}(x) = (f_{2})_{0}(x), and therefore (f_{1})_{0} and (f_{2})_{0} coincide everywhere. Notice that in general N_{0}^{gl^{−}}(C) ≠ C_{1} so the reasoning of the 0-th dimension does not apply to dimension 1. Now suppose that we have proved that (f_{1})_{n} = (f_{2})_{n} for n ⩽ n_{0} and n_{0} ⩾ 1. Then (f_{1})_{n_{0}+1} and (f_{2})_{n_{0}+1} are two ω-functors from Δ^{n_{0}+1} to ℙ^{−}C which coincide on the n_{0}-dimensional faces of Δ^{n_{0}+1} and such that (f_{1})_{n_{0}+1}(0 < ⋯ < n_{0}+1) = (f_{2})_{n_{0}+1}(0 < ⋯ < n_{0}+1). Then (f_{1})_{n_{0}+1} and (f_{2})_{n_{0}+1} induce the same labeling of the faces of Δ^{n_{0}+1}, therefore by freeness of Δ^{n_{0}+1}, (f_{1})_{n_{0}+1} = (f_{2})_{n_{0}+1}.

Now let us prove the existence of this natural transformation. Let f ∈ ωCat(I^{n+1}, C)^{−}. Then for any x ∈ G^{R(−_{n+1}),−}ℙI^{n+1}, the morphism f(x) cannot be 0-dimensional otherwise s_{1}f(x) = f(s_{1}x) would be so as well. So the restriction of f to G^{R(−_{n+1}),−}ℙI^{n+1} ⊂ ℙI^{n+1} gives rise to an element of

N_{n}^{1}(C) := ωCat (G^{R(−_{n+1}),−}ℙI^{n+1}, ℙC)

[figure: 𝔽 (𝕌ℙC); 𝔽 (𝕌ℙC/R^{−}); G^{R(−_{n+1}),−}𝔽 (𝕌ℙI^{n+1}); G^{R(−_{n+1}),−}𝔽 (𝕌ℙI^{n+1}/R^{−}); ℙC; ℙ^{−}C; G^{R(−_{n+1}),−}ℙI^{n+1}; ℙ_{R(−_{n+1})}^{−}I^{n+1}; f^{−}]

Figure 3: The canonical morphism from the branching semi-cubical to the branching semi-globular nerve

and therefore to elements of

N_{n}^{2}(C) := ωCat (G^{R(−_{n+1}),−}𝔽 (𝕌ℙI^{n+1}) , 𝔽 (𝕌ℙC))

and of

N_{n}^{3}(C) := ωCat (G^{R(−_{n+1}),−}𝔽 (𝕌ℙI^{n+1}/R^{−}) , 𝔽 (𝕌ℙC/R^{−})) .

The ω-functors δ_{i}^{−} : I^{n} → I^{n+1} and γ_{i}^{−} : I^{n+2} → I^{n+1} for 1 ⩽ i ⩽ n + 1 are all non-contracting. Since the natural maps N_{n}^{−} → N_{n}^{i} for i = 1, 2, 3 arise from restrictions, then one obtains three natural morphisms of simplicial sets N^{−} → N^{i} which yield a cone based on the diagram

\xymatrix{ & N^{3} \ar[d] \\ N^{1} \ar[r] & N^{2}}

Therefore one obtains a natural transformation

N^{−} ⟶ \underleftarrow{lim} N^{i} ≅ ωCat (ℙ_{R(−_{∗+1})}^{−}I^{∗+1}, −) ≅ N^{gl^{−}}

For f ∈ N^{−}(C), the corresponding element f^{−} ∈ N^{gl^{−}} is represented in Figure 3.

Let C be a non-contracting ω-category. The natural transformation N^{−} → N^{gl^{−}} yields a natural morphism of chain complexes CR_{∗}^{−}(C) → CR_{∗}^{gl^{−}}(C) by Section 6.

9.2. Proposition. The following diagram is commutative and the three maps are surjective :

\xymatrix{ & CF_{∗}^{−} \ar@{-->}[dr]^{□_{∗}^{gl^{−}}} \ar[dl]_{□_{∗}^{−}} \\ _{CR− ∗} \ar[rr] &  & _{CR\begin{matrix}gl & ^{−} \\ ∗ \end{matrix}}}

Proof. Let C be a non-contracting ω-category. The only thing one has to prove is the surjectivity of CR_{∗}^{−}(C) → CR_{∗}^{gl^{−}}(C). There is nothing to prove for n = 0 and n = 1. So let us suppose that n ⩾ 2. The group CR_{n}^{gl^{−}}(C) is generated by the elements of the form □_{n}^{gl^{−}}(x) where x ∈ (ℙ^{−}C)_{n−1}. The canonical map ℙC → ℙ^{−}C is generally not surjective on the underlying sets but by Theorem 3.5, any element of (ℙ^{−}C)_{n−1} is a composite of elements of ℙC by only using the composition laws ∗_{r} for r ⩾ 1. Since the branching semi-globular nerve is regular, then □_{n}^{gl^{−}}(x) is therefore equal to a sum of elements of the form □_{n}^{gl^{−}}(h^{−}(z)) where z ∈ (ℙ^{−}C)_{n−1}. Hence the surjectivity.

These three maps are likely to be injective for any non-contracting ω-category C but we have not yet been able to verify it. The latter conjecture together with the thin elements conjecture means that for ω-categories modeling HDA, i.e. freely generated by precubical sets, both simplicial homology theories H_{∗}^{−} and H_{∗}^{gl^{−}} coincide.

Figure 2 is a recapitulation of all constructions made so far (N^{gl^{+}} is the merging semi-globular cut, that is the Kan version of the merging nerve). The figure represents a commutative diagram. The morphisms h^{−} and h^{+} are those defined in [8]. The maps N^{−} → N^{gl^{−}} and N^{+} → N^{gl^{+}} are the maps constructed in Theorem 9.1. The composites N^{gl} → N^{gl^{−}} and N^{gl} → N^{gl^{+}} are induced by the natural transformations ℙ → ℙ^{−} (resp. ℙ → ℙ^{+}).

10. Concluding discussion

Any HDA can be modeled by a precubical set K. The prefix “pre” means that there are no degeneracy maps in the data.

We have worked so far with the strict globular ω-category F (K) freely generated by the precubical set K. This paper shows, hopefully with convincing arguments, that we can deal directly with the non-contracting ω-category { \atop F (K)} obtained by making the path ω-category ℙF (K) a strict globular ω-groupoid in a universal way, without changing the information contained in the homology groups introduced so far. The non-contracting ωcategory { \atop F (K)} is obtained from the non-contracting ω-category F (K) by adding inverses to morphisms of dimension greater than 2 and with respect to all composition laws of dimension greater than 1. This is very satisfactory from the point of view of computerscientific modeling because there are no reasons for an homotopy between non-constant execution paths to be not invertible. In this new setting, the globular nerve N^{gl}({ \atop F (K)}) of { \atop F (K)} becomes a Kan complex.

Starting from a non-contracting ω-category C, we have then introduced in this paper two ω-categories ℙ^{−}C and ℙ^{+}C whose 0-morphisms are the germs of 1-morphisms of C beginning (resp. ending) in the same way and whose higher dimensional morphisms are the germs of homotopies between them. We have then obtained the diagram of noncontracting ω-categories

\xymatrix{ & ℙC \ar[dl]_{h^{−}} \ar[dr]^{h^{+}} \\ ℙ^{−}C &  & ℙ^{+}C}

Applied to the particular case C = { \atop F (K)}, one obtains the diagram of strict globular ω-groupoids

\xymatrix{ & ℙ{ \atop F (K)} \ar@{-->}[dl]_{h^{−}} \ar@{-->}[dr]^{h^{+}} \\ ℙ^{−}{ \atop F (K)} &  & ℙ^{+}{ \atop F (K)}}

whose corresponding simplicial homologies give us the globular homology and the new branching and merging homologies.

Loosely speaking, the strict globular ω-groupoid ℙ{ \atop F (K)} plays the role of the space of non-constant execution paths of the HDA, and the strict globular ω-groupoid ℙ^{−}{ \atop F (K)} (resp. ℙ^{+}{ \atop F (K)} ) plays the role of the space of germs of non-constant execution paths beginning (resp. ending) in the same way. So these results tell us that what matters for the homological study of dihomotopy is to have a set of states (the set of 0-morphisms) and a space of non-constant execution paths, the two other spaces being characterized by the space of non-constant execution paths and the composition law ∗_{0}. This idea is implemented in [4] in a topological context.

11. Acknowledgments

I thank the referee for helpful comments and the editor for his patience.

References

[1] R. Brown and P. J. Higgins. The equivalence of ∞-groupoids and crossed complexes. Cahiers Topologie Géom. Différentielle Catég., 22(4):371–386, 1981.

[2] R. Brown and P. J. Higgins. On the algebra of cubes. J. Pure Appl. Algebra, 21(3):233–260, 1981.

[3] R. Cridlig. Implementing a static analyzer of concurrent programs: Problems and perspectives. In Logical and Operational Methods in the Analysis of Programs and Systems, pages 244–259, 1996.

[4] P. Gaucher. A Convenient Category for The Homotopy Theory of Concurrency. arXiv:math.AT/0201252.

[5] P. Gaucher. From concurrency to algebraic topology. In Electronic Notes in Theoretical Computer Science, volume 39, page 19pp. Elsevier Science Publishers, 2000.

[6] P. Gaucher. Homotopy invariants of higher dimensional categories and concurrency in computer science. Math. Structures Comput. Sci., 10:481–524, 2000.

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

[8] P. Gaucher. About the globular homology of higher dimensional automata. Cahiers Topologie Géom. Différentielle Catég., 43(2):107–156, 2002.

[9] E. Goubault. The Geometry of Concurrency. PhD thesis, École Normale Supérieure, 1995.

[10] S. Mac Lane. Categories for the working mathematician. Springer-Verlag, New York, second edition, 1998.

[11] J. P. May. Simplicial objects in algebraic topology. D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto, Ont.-London, 1967. Van Nostrand Mathematical Studies, No. 11.

[12] J. Pénon. Approche polygraphique des ∞-catégories non strictes. Cahiers Topologie Géom. Différentielle Catég., 40(1):31–80, 1999.

[13] V. Pratt. Modeling concurrency with geometry. In ACM Press, editor, Proc. of the 18th ACM Symposium on Principles of Programming Languages, 1991.

[14] R. Steiner. Tensor products of infinity-categories. University of Glasgow, 1991.

[15] R. Steiner. Pasting in multiple categories. Theory Appl. Categ., 4:No. 1, 1–36 (electronic), 1998.

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

[17] R. Street. The petit topos of globular sets. J. Pure Appl. Algebra, 154(1-3):299–315, 2000. Category theory and its applications (Montreal, QC, 1997).

[18] C. A. Weibel. An introduction to homological algebra. Cambridge University Press, Cambridge, 1994.

Institut de Recherche Mathématique Avancée ULP et CNRS 7 rue René Descartes 67084 Strasbourg Cedex France

Email: gaucher@irma.u-strasbg.fr

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/11/3/11-03.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi, Postscript and PDF. Details will be e-mailed to new subscribers. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh,

rrosebrugh@mta.ca.

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

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org, Associate Managing Editor Lawrence Breen, Université Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of Wales Bangor: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Palo Alto Research Center: paiva@parc.xerox.com Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca