{'fraction_non_alphanumeric': 0.0839727030882523, 'fraction_numerical': 0.017041292362262404, 'mean_word_length': 3.207981829980532, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 67, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Kan subdivision and products of simplicial sets

The canonical map from the Kan subdivision of a product of finite simplicial sets to the product of the Kan subdivisions is a simple map, in the sense that its geometric realization has contractible point inverses.


Introduction
Kan's normal subdivision [5, §7] is a functor Sd from simplicial sets to simplicial sets. It agrees with barycentric subdivision when applied to (ordered) simplicial complexes. The maps induced by applying Kan subdivision to the projections X × Y → X and X × Y → Y combine to a canonical map κ : Sd(X × Y ) → Sd X × Sd Y . The theorem follows from the special cases when X = ∆[m] is a standard simplex, for some m ≥ 0, by an induction on the dimension and number of topdimensional cells in the CW complex |X|. A second induction, over the cells of |Y |, allows us to specialize further to the cases when Y = ∆[n], for some n ≥ 0. Hence our real task is to prove the following result. points or closed intervals. Hence |κ| is not a homeomorphism, but all preimages of points are contractible. Note that |κ| does not admit a continuous section.
Remark 1.5. Simple maps have a direction: given a simple map f : A → B there might be no simple map g : B → A. Simple-homotopy theory [2] concerns the equivalence relation on finite simplicial sets (or simplicial complexes) generated by simple maps. Piecewise-linear topology [6] concerns the properties of simplicial complexes that are invariant under linear subdivisions. It is often convenient and sufficient to only consider the linear subdivisions that arise by iterated barycentric subdivision [7, §3.5, §3.6]. Our theorem gives a strong version of the statement that the simple-homotopy type of a product is a well-defined piecewise-linear notion, also with respect to this more restricted notion of subdivision.
The weaker statement that the map κ in the theorem is a simple-homotopy equivalence is easily proved: there is a natural last vertex map d X : Sd X → X, which is simple for all finite X [9, 2.2.17], and (d X × d Y ) • κ = d X×Y . However, this argument does not suffice to prove that κ is a simple map.
In Section 2 we present an application of our main result. In Section 3 we show how to deduce Theorem 1.2 from Proposition 1.3, and outline the proof of the latter result. The details of that proof occupy Sections 4, 5 and 6.
2. An application to the improvement functor A simplicial set X is said to be non-singular [9, 1.2.2] if for each non-degenerate nsimplex x in X the representing mapx : ∆[n] → X is a cofibration, or equivalently, if each non-degenerate n-simplex has n + 1 distinct vertices, for each n ≥ 0. This implies that the geometric realization |X| has a preferred piecewise-linear structure. Let C be the category of finite simplicial sets and simplicial maps, let D be its full subcategory of finite non-singular simplicial sets, and let sC and sD denote the respective subcategories of simple maps.
Our main result has an application to the multiplicative properties of the improvement functor I : C → D constructed in [9, 2.5.2]. This functor associates to each finite simplicial set X a finite non-singular simplicial set I(X), together with a natural simple map s X : I(X) → X. Hence the restricted functor sI : sC → sD induces a homotopy equivalence of classifying spaces, and the localized functor I[s −1 ] : C[s −1 ] → D[s −1 ] (inverting the respective collections of simple maps [4, 1.1]) is an equivalence of categories. This shows that the simple-homotopy theory of finite simplicial sets is equivalent to the simple-homotopy theory of finite non-singular simplicial sets. For a useful relative version of this statement, see [9, 1.2.5]. The application we have in mind concerns the compatibility of this equivalence with the categorical products.
Proposition 2.1. Let X and Y be finite simplicial sets, and let I denote the improvement functor from [9, §2.5]. The canonical map Before showing how to deduce this from our main theorem, we recall some notation and terminology. Each simplex x of a simplicial set X is a degeneration of a unique non-degenerate simplex, which we denote x # . If x is non-degenerate then x = x # . Let X # be the set of non-degenerate simplices in X, partially ordered by letting x ≤ y if x is a face of y. We call the nerve B(X) = N (X # ) of this partially ordered set the Barratt nerve of X, due to its early appearance in [1]. A simplicial map f : X → Y induces an order-preserving function f # : X # → Y # , taking x to f (x) # , and a functorial map of nerves B(f ) = N (f # ) : B(X) → B(Y ). The Kan subdivision Sd(X) is defined as the left Kan extension of [n] → B(∆ n ) along the Yoneda embedding of ∆ into simplicial sets [9, 2.2.7], so there is a natural map b X : Sd(X) → B(X), which is an isomorphism for non-singular X [9, 2.2.11]. The improvement functor I is defined as the composite I(X) = B(Sd(X)) .
(The use of the opposite subdivision in [9] plays no explicit role in our arguments, and will be suppressed.) Remark 2.2. The improvement functor I appears implicitly in the work of Thomason [8], as the composite N • c Sd 2 of the nerve functor N (from small categories to simplicial sets) and the categorified double subdivision c Sd 2 (from simplicial sets to categories). The latter functor is the left adjoint in Thomason's Quillen equivalence between these two (closed) model categories. By [8,Lemma 5.6] the category c Sd 2 (X) is a partially ordered set, for any simplicial set X, and this makes it easy to identify it with the partially ordered set Sd(X) # of non-degenerate simplices in Sd(X).
Proof of Proposition 2.1. There are canonical maps The left hand map, Sd(κ), is simple by our Theorem 1.2, combined with the fact that Kan subdivision preserves simple maps [9, 2.3.3]. The right hand map is simple by the same theorem applied for the finite simplicial sets Sd(X) and Sd(Y ). Hence the composite map is also simple [9, 2.1.3(a)].
The natural map b Sd(X) : Sd(Sd(X)) → B(Sd(X)) is simple by [9, 2.5.5, 2.5.8]. Hence the vertical maps are simple in the commutative square We have just argued that the upper horizontal map is simple, and this implies that the lower horizontal map is simple, by the right cancellation property of simple maps [9, 2.1.3(b)].

Outline of argument
This uses the fact that Sd preserves colimits and cofibrations [ By induction we may assume that κ is simple for ∂∆[n] and Y ′ , so the main theorem follows from the case Y = ∆[n], i.e., from Proposition 1.3.
Outline of proof of Proposition 1.3. To show that the canonical map is simple, it suffices to show that it is simple over the interior of each non-degenerate r-simplex (z, w) = (z 0 ≤ · · · ≤ z r , w 0 ≤ · · · ≤ w r ) of the target, for r ≥ 0, cf. Notation 4.2. By Lemmas 4.3, 4.7 and 4.11, κ agrees with the nerve of the order-preserving function π : P (φ r , . . . , φ 1 ) → [r] over that interior. Here is a diagram of partially ordered sets and order-preserving functions, specified in Notations 4.6 and 4.8, and P (φ r , . . . , be the induced diagram of nerves. According to Definition 5.4, the nerve of π equals the reduced coordinate projection π : . . , f 1 ) is the r-fold iterated reduced mapping cylinder. As we explain in Remark 5.11, there is a commutative diagram where T (f r , . . . , f 1 ) is the r-fold iterated ordinary mapping cylinder, cf. Definition 5.6. The reduction map red : T (f r , . . . , f 1 ) → M (f r , . . . , f 1 ) is simple by Lemma 5.18, and the map red: T r → ∆[r] is simple by Lemma 5.10.
By the composition and right cancellation properties of simple maps [9, 2.1.3], the reduced coordinate projection π will be simple if the ordinary cylinder projection T (f r , . . . , f 1 ) → T r is simple. Each point inverse of the geometric realization |T (f r , . . . , f 1 )| → |T r | is homeomorphic to one of the spaces |N F i |, for 0 ≤ i ≤ r, so it suffices to prove that each of the partially ordered sets F i has contractible classifying space. Using Notation 6.1, each F i is of the form P z ′ ,w ′ for a suitable i-simplex . Hence the required contractibility is a consequence of our final technical result, Proposition 6.7.

Partially ordered sets of paths
As a first step towards the proof of Proposition 1.3, we unravel the definition of the canonical map κ in that special case, and identify the part of κ that sits over a non-degenerate r-simplex in its target. is the nerve of the partially ordered set of its non-degenerate simplices. An r-simplex is a chain γ 0 ≤ γ 1 ≤ · · · ≤ γ r of injective order-preserving functions γ i : The first projection pr 1  . We can display these order-preserving functions in the following diagram, where a feathered arrow denotes an injection and a two-headed arrow denotes a surjection.
The (z i , w i ) are pairwise distinct, so the P i are pairwise disjoint as sets, for 0 ≤ i ≤ r. Let P 0 ∪ · · · ∪ P r denote the union of these sets, partially ordered as a subset of C = (∆[m]× ∆[n]) # , and let λ : P 0 ∪· · ·∪P r → [r] be the order-preserving function taking the elements of P i to i, for each 0 ≤ i ≤ r.
By the restriction of a map f : A → B over a simplicial subset Z ⊆ B, we mean the associated map f −1 (Z) → Z, given by restricting f to f −1 (Z) ⊆ A, and corestricting the target to Z.
Proof. Nerves commute with pullbacks, which means we have a pullback square We now explain how only a part of the union P 0 ∪ · · · ∪ P r plays a role over the interior of the r-cell |∆[r]|.
This terminology (being (µ, ν)-full) will also be important throughout this paper. In general, not every (ζ, η)-path will be (µ, ν)-full. Notation 4.6. For each 0 ≤ i ≤ r, let F i denote the set of (z i , w i )-paths that are (z j , w j )-full for every 0 ≤ j < i. Partially order F i as a subset of P i , and partially order F 0 ∪ · · · ∪ F r as a subset of P 0 ∪ · · · ∪ P r . The F i are pairwise disjoint as sets, since this holds for the P i . Let ξ : F 0 ∪ · · · ∪ F r → [r] be the order-preserving function that takes each element of F i to i.
The notations P i and F i are chosen for their brevity. They always depend on the implicit choice of a non-degenerate r-simplex (z, w), as above. Proof. By the definition of ξ and λ, the triangle commutes. Let x ∈ N (P 0 ∪ · · · ∪ P r ) be a p-simplex that does not lie over the boundary ∂∆[r] of ∆[r]. In other words, x is an order-preserving function such that the composite It follows that |N (F 0 ∪ · · · ∪ F r )| → |N (P 0 ∪ · · · ∪ P r )| restricts to the identity over the interior of |∆[r]|.
As before, these notations depend on the implicit choice of a non-degenerate r-simplex (z, w). To conclude this section, we clarify how the partially ordered set  . Given an order-preserving function ϕ : V → W of partially ordered sets, let P (ϕ) = V ⊔ ϕ W be the disjoint union of the sets V and W , with the partial ordering generated by the relations in V , the relations in W , and the relation ϕ(v) < v for all v ∈ V .
In other words, for v ∈ V and w ∈ W we have w ≤ v in P (ϕ) if and only if w ≤ ϕ(v) in W . We write ϕ ∨ 1 : P (ϕ) → W for the order-preserving function that restricts to ϕ on V and to the identity on W , and π : P (ϕ) → [1] = {0 < 1} for the order-preserving function that maps V to 1 and W to 0.
with the partial ordering generated by the relations in V i for 0 ≤ i ≤ r, and the for the order-preserving function that takes V i to i, for each 0 ≤ i ≤ r.
The order-preserving function ψ j : The partial ordering on P (φ r , . . . , φ j ) = P (ψ j ) agrees with the subset partial ordering when restricted to F j ∪ · · · ∪ F r = P (φ r , . . . , φ j+1 ), and when restricted to F j−1 . It remains to check that, for γ ∈ F j ∪ · · · ∪ F r and β ∈ F j−1 , we have β ≤ γ in the subset partial To summarize what we have learned so far, let κ be as in Proposition 1.3, let (z, w) be as in Notation 4.2, and let π : P (φ r , . . . , φ 1 ) → [r] be as in Notation 4.8 and Definition 4.10.

Mapping cylinders
The (backward) reduced mapping cylinder, as introduced in [9, §2.4], is a functor that to each simplicial map f : X → Y associates a simplicial set M (f ), factoring f as an inclusion in : X → M (f ) followed by a simple projection map pr : There is a natural reduction map red: T (f ) → M (f ) from the ordinary mapping cylinder T (f ) = X × ∆[1] ∪ X Y to the reduced mapping cylinder, and the ordinary coordinate projection T (f ) → ∆[1] factors naturally through a reduced coordinate projection π : More generally, given a sequence X r fr − → . . .

f1
− → X 0 of maps of simplicial sets, there is an r-fold iterated reduced mapping cylinder M (f r , . . . , f 1 ), a reduction map red : T (f r , . . . , f 1 ) → M (f r , . . . , f 1 ) from the r-fold iterated ordinary mapping cylinder, and compatible coordinate projection maps: In this section, we shall recognize the map N π : N (P (φ r , . . . , φ 1 )) → ∆[r] as the reduced coordinate projection map π : M (f r , . . . , f 1 ) → ∆[r] for the sequence of simplicial sets X i = N F i and maps f i = N φ i . Thereafter, we use the second author's criterion [9, 2.4.16] to show that the iterated reduction map T (f r , . . . , f 1 ) → M (f r , . . . , f 1 ) is simple in this case. This reduces the problem of showing that π is simple to the problem of showing that the classifying spaces |N F i | are contractible, which we will address in the following, final, section. . Given an order-preserving function ϕ : V → W of partially ordered sets, let in : V → P (ϕ) = V ⊔ ϕ W and in ′ : W → P (ϕ) be the front and back inclusions, respectively, and let pr = ϕ∨1 : P (ϕ) → W and π : P (ϕ) → [1] be as before. Consider the commutative diagram of order-preserving functions, where i t (v) = (v, t), ρ(v, 1) = in(v) and ρ(v, 0) = in ′ (ϕ(v)). Applying nerves, we get the commutative diagram where the lower left hand square is the pushout defining T (N ϕ) = N V × ∆[1] ∪ N V N W , and the reduction map red is induced by N ρ and in ′ . We define the reduced mapping cylinder of the simplicial map f = N ϕ : N V → N W to be the nerve M (f ) = N (P (ϕ)) of the partially ordered set P (ϕ) = V ⊔ φ W , with inclusion, projection, reduction and coordinate projection maps as in the diagram above. The extra relation [1] ′ , leads to the additional 3-simplex 0 ′ < 1 ′ < 1 < 2 on the right hand side.
The reduced mapping cylinder M (f ) for a general simplicial map f : X → Y can be defined as a left Kan extension from these special cases, essentially as in [9, 2.4.4], but the definition just given suffices for our purposes. See [9, 2.4.12] for the compatibility of the two definitions.
The iterated reduced mapping cylinder M (f r , . . . , f 1 ) of a general sequence X r → · · · → X 0 of simplicial sets and maps can, again, be defined as a left Kan extension from these special cases, but the definition given will suffice for this paper.
Here the left hand map is induced by the (r − 1)-fold iterated reduction map red : T (f r , . . . , f 2 ) → M (f r , . . . , f 2 ) and the identity map of X 0 , while the right hand map is the reduction map for f 1 • pr : M (f r , . . . , f 2 ) → X 0 . The map T r → M r is an isomorphism for r = 0 and 1. To address the case r ≥ 2, the following terminology will be convenient. Proof. By induction, we may assume that r ≥ 2 and that T r−1 → M r−1 is simple. We must prove that the composite is simple. The left hand map is simple by the inductive hypothesis and the gluing lemma for simple maps [9, 2.1.3(d)]. The right hand map is isomorphic to the reduction map for the unique map N ǫ : ∆[r − 1] → ∆[0], which is the canonical map from the pushout to the lower right hand entry in the commutative square By the gluing lemma, and the fact that N ǫ is simple, it suffices to prove that N ρ is simple. There is an order-preserving bijection [ , given by σ(0) = (0, 0) and σ(j) = (j − 1, 1) for 1 ≤ j ≤ r, is a section of θ, and (σ • θ)(i, t) ≤ (i, t) for all (i, t) ∈ [r − 1] × [1]. Hence N σ is a section of N θ, and there is a simplicial homotopy from N σ • N θ to the identity, covering the identity of ∆[r].
Remark 5.11. Naturality of the iterated reduction map, with respect to the terminal morphism in the category of r-tuples of composable maps, leads to the commutative diagram The lower reduction map T r → M r is simple, by the previous lemma. Each point inverse of the geometric realization |T (f r , . . . , f 1 )| → |T r | of the left hand vertical map is homeomorphic to one of the spaces |X 0 |, . . . , |X r |. This is obvious for r = 0 and 1, and follows by an easy induction for r ≥ 2. Hence the map T (f r , . . . , f 1 ) → T r is simple if (and only if) these spaces are contractible. The left hand picture in Example 5.2 illustrates that the point inverses of the map |π| : |M (f r , . . . , f 1 )| → |∆[r]| need not be homeomorphic to one of the spaces |X 0 |, . . . , |X r |. This is why we introduce ordinary mapping cylinders and reduction maps, as technical tools.
In the remainder of this section we shall prove that the upper reduction map T (f r , . . . , f 1 ) → M (f r , . . . , f 1 ) is simple in the case when X i = N F i and f i = N φ i are as in Notation 4.8. In the following section we shall prove that the classifying spaces |N F i | = |X i | are contractible in that case. By the diagram above, and the right cancellation property for simple maps, it will then follow that π : M (f r , . . . , f 1 ) → ∆[r] is simple. In view of Lemma 4.13, this will complete the proof of our main theorem. Definition 5.12. Let V be a partially ordered set. A subset I ⊆ V is called a left ideal if v ∈ I and u ≤ v in V implies u ∈ I. It is called a right ideal if v ∈ I and v ≤ w in V implies w ∈ I. We always give I the subset partial ordering.
Definition 5.13. Suppose given a partially ordered set V and an element v ∈ V . Let V /v denote the left ideal in V consisting of all elements u ∈ V with u ≤ v. Any order-preserving function ϕ : V → W restricts to an order-preserving function Proposition 5.14. Let ϕ : V → W be an order-preserving function of finite partially ordered sets. Then the following conditions are equivalent: (1) The nerve of ϕ/v : (2) The reduction map red: Proof. See [9, 2.4.16].
The nerve of the order-preserving function pr /v : , and pr(v) = ϕ(v), so we can identify pr /v with the orderpreserving function ϕ/v ∨ 1 : P (ϕ/v) → W/ϕ(v). Its nerve is the projection map from the reduced mapping cylinder of N (ϕ/v) to its target, which is simple by [9, 2.4.8], recalled above as Lemma 5.3.
We now return to the context of the previous section, where ( , F i is the set of (z i , w i )-paths that are (z j , w j )-full for every 0 ≤ j < i, and φ i : First, there is an order-preserving function C/γ × C/γ → C/γ that takes two paths α, β ∈ C/γ to the path α ∪ β ∈ C/γ with im(α ∪ β) = im(α) ∪ im(β).
Second, there is an order-preserving function F i → C taking β ∈ F i to the path β \ L i−1 with image im(β) \ L i−1 .
Lemma 5.17. The nerve of the order-preserving function Proof. We prove that N (φ i /γ) is a homotopy equivalence over the target, in the sense of Definition 5.9. Using the operations mentioned above we can define an order-preserving function σ : Hence there is a simplicial homotopy from the identity of N (F i /γ) to N σ •N (φ i /γ), covering the identity of N (F i−1 /φ i (γ)). The second assertion now follows from Proposition 5.14. is simple, for each r ≥ 0.
Proof. This is trivial for r = 0, and was proved in Lemma 5.17 for r = 1. We may therefore suppose r ≥ 2, and assume, for some 1 ≤ i ≤ r, that the (r − i)-fold iterated reduction map red : T (N φ r , . . . , N φ i+1 ) → M (N φ r , . . . , N φ i+1 ) is simple. We must prove that the (r−i+1)-fold iterated reduction map red : T (N φ r , . . . , N φ i ) → M (N φ r , . . . , N φ i ) is simple. By definition, this is the composite of two further maps, each of which will be shown to be simple. The first of the two is the map of ordinary mapping cylinders induced by the (r − i)-fold iterated reduction map and the identity on N F i−1 . It is simple by the inductive hypothesis and the gluing lemma for simple maps. The second of the two is the reduction map The latter map equals the nerve of the composite order-preserving function which we denote as ψ i = φ i • (ψ i+1 ∨ 1). Recall from the proof of Lemma 5.5 that We will use the criterion in Proposition 5.14 to show that red : Consider any γ ∈ P (φ r , . . . , φ i+1 ) = P (ψ i+1 ). We must show that the nerve of ψ i /γ is simple. This order-preserving function is the composite of pr /γ and φ i / pr(γ). The nerve of pr /γ : P (ψ i+1 )/γ → F i / pr(γ) is simple by Lemma 5.15, for the order-preserving function ψ i+1 and the element γ ∈ P (ψ i+1 ). The nerve of φ i / pr(γ) is simple by Lemma 5.17, for the element pr(γ) ∈ F i . Hence the composite N (φ i / pr(γ)) • N (pr /γ) is also simple, as we needed to prove. We consider an r-simplex (z, w) in the target of κ, represented by a chain (z 0 ≤ · · · ≤ z r , w 0 ≤ · · · ≤ w r ), where the z i and w i are faces of ∆[m] and ∆[n], respectively. However, unlike in the previous sections, we no longer assume that (z, w) is non-degenerate. This added generality will be convenient for our inductive proofs. Notation 6.1. For any r-simplex (z, w) = (z 0 ≤ · · · ≤ z r , w 0 ≤ · · · ≤ w r ) in the nerve of the partially ordered set ∆[m] # × ∆[n] # , let P z,w be the partially ordered set of (z r , w r )-paths γ : [k] → [m] × [n] that are (z j , w j )-full for each 0 ≤ j < r, partially ordered as a subset of (∆[m] × ∆[n]) # .

Contracting sets of paths
When (z, w) is non-degenerate, P z,w is equal to the partially ordered set F r from Notation 4.6. More generally, for each 0 ≤ i ≤ r the partially ordered set F i is equal to P z ′ ,w ′ , where (z ′ , w ′ ) = (z 0 ≤ · · · ≤ z i , w 0 ≤ · · · ≤ w i ) is the front i-face of (z, w). As explained in Remark 5.11, the task that remains is to prove that each classifying space |N F i | is contractible. Hence it will suffice to prove that |N P z,w | is contractible, for each simplex (z, w). We shall prove this by induction on the dimension r ≥ 0 of that simplex.
We begin with the case r = 0, when (z, w) = (z 0 , w 0 ) = (µ, ν) for some faces µ ∈ ∆[m] # and ν ∈ ∆[n] # . The proof we present for the following proposition introduces some ideas that will reappear in the cases r ≥ 1. , respectively. Then there is an order-preserving bijection P m1,n1 ∼ = P µ,ν , taking γ : . It will therefore suffice to prove that the classifying space of P m1,n1 is contractible, for each m 1 , n 1 ≥ 0. Changing the notation, we will prove that each partially ordered set P m,n of (m, n)-paths has contractible classifying space. This will be done by induction on m ≥ 0.
Hence the nerve N P 1,n is a union of 2n edges, with alternating orientations, and the classifying space |N P 1,n | is homeomorphic to an interval.
To handle the general case, fix some m ≥ 1 and n ≥ 0, and suppose inductively that |N P m1,n1 | is contractible whenever 0 ≤ m 1 ≤ m and n 1 ≥ 0. We shall prove that the classifying space of P m+1,n is contractible.
In the first case, there is an order-preserving bijection Q j ∼ = P m,j × P 1,n−j for each 0 ≤ j ≤ n, breaking an (m + 1, n)-path γ passing through (m, j) into two pieces: Hence |N Q j | ∼ = |N P m,j | × |N P 1,n−j | is a product of two contractible spaces, by our inductive hypothesis.
In the second case, there is an order-preserving bijection for each 0 ≤ i < j ≤ n, breaking a path γ passing through (m, i) and (m, j) into three pieces: is a product of three contractible spaces, by the inductive hypothesis.
(a) There is an order-preserving bijection There is an order-preserving bijection taking the (z, w)-paths γ that pass through both (p, q) and (p ′ , q ′ ), to the triples Proof. This follows by two applications of the previous lemma, or by a direct proof. In (b), (z ℓ , w ℓ ) = (z ℓ 0 ≤ · · · ≤ z ℓ r , w ℓ 0 ≤ · · · ≤ w ℓ r ) for each 1 ≤ ℓ ≤ 3, where z i corresponds to (z 1 i , z 2 i , z 3 i ) as in (a), and likewise for w i . We can now prove our main technical result.
Proposition 6.7. The classifying space |N P z,w | is contractible, for each simplex Proof. The proof involves a double induction. We begin with an outer induction on the dimension r ≥ 0 of the simplex (z, w). The initial case r = 0 was handled in Proposition 6.2. For the outer inductive step, we fix an r ≥ 0 and assume that |N P z,w | is contractible for each r-simplex (z, w). We shall prove that |N P x,y | is contractible for each (r + 1)-simplex Let the pair (ζ, η) be the 0-th vertex of (x, y), and let the r-simplex (z, w) be the 0-th face of (x, y). In other words, let ζ = x 0 : [s] → [m] and η = y 0 : [t] → [n], for some s, t ≥ 0, and let z i = x i+1 and w i = y i+1 for all 0 ≤ i ≤ r. With this notation, an (x, y)-path is the same as a (z, w)-path that is (ζ, η)-full. We maintain this notational scheme throughout this proof.
We shall prove that the classifying space of P x,y is contractible, by an inner induction on the dimension s ≥ 0 of the face ζ of ∆[m].
Hence P x,y ∼ = P x 1 ,y 1 × P x 2 ,y 2 × P x 3 ,y 3 by Lemma 6.6. Here ( that lands in [ζ(0)] is 0-dimensional, and similarly for the part ζ 3 = x 3 0 . Hence P x 1 ,y 1 and P x 3 ,y 3 have contractible classifying spaces, by the already established case s = 0 of the inner induction. It therefore remains to prove that P x 2 ,y 2 has contractible classifying space. Replacing (x 2 , y 2 ) with (x, y) in the notation, we may and will assume that ζ(0) = 0, ζ(1) = m, η(0) = 0 and η(t) = n, and seek to prove that P x,y has contractible classifying space.
The inner induction ends with the inner inductive step, for s ≥ 2: Assume inductively that |N P x ′ ,y ′ | is contractible for each (r + 1)-simplex (x ′ , y ′ ) such that the dimension of ζ ′ = x ′ 0 is strictly less than s. We must prove that P x,y has contractible classifying space when the dimension of ζ = x 0 , as a face of ∆[m], equals s.