Draft lesson.

Augmented finite orders and contracting coface complexes

Original text public domain (CC0).

Alternating coface maps produce a complex in any additive category. An extra collapse map can contract it, including its augmentation. The empty order and the endpoint conditions determine whether that lowest-degree contraction exists. We prove the finite-order identities and keep the augmentation in every calculation.

Use the universe conventions of Universes and small categories. The value category \(\mathcal C\) is additive; only finite sums of morphisms are used. Graded complexes, contravariant signs and stupid truncations, Section 1 supplies the actual chain-homotopy equation. We write \([n]=\{0,\ldots,n\}\) for \(n\ge0\), and \([-1]=\varnothing\).

1. Three categories of finite orders

Let \(\Delta_+\) be the category of all finite totally ordered sets, including the empty set, with nondecreasing maps. Identities and composites are nondecreasing. Its injective subcategory \(\Delta_{+,\mathrm{inj}}\) has the same objects and only injective nondecreasing maps. Let \(\mathcal E\) have all nonempty finite totally ordered sets, with nondecreasing maps preserving both the first and last element. Preserving the endpoints is stable under identity and composition, so this too is a category.

Every finite order with \(r\) elements has a unique increasing isomorphism with \([r-1]\). Explicitly send an element to the number of its predecessors. Comparable distinct elements have strictly different predecessor counts, each count lies between zero and \(r-1\), and the \(r\) different counts fill that interval. The empty order corresponds to \([-1]\). Transporting morphisms by these unique rankings gives a functor to the standard orders, inverse to their inclusion up to the ranking isomorphisms. Thus \(\{[n]:n\ge-1\}\) is a skeleton equivalent to \(\Delta_+\). The analogous nonempty skeleton uses \(n\ge0\).

Forgetting the order gives a faithful functor \(\Delta_+\to\mathsf{FinSet}\): the Hom maps are inclusions of subsets of set maps. It also reflects isomorphism classes of objects. Indeed isomorphic underlying finite sets have the same cardinality, so their rankings give an increasing isomorphism. This is the half-full property in Equivalences and chosen representatives, Section 7. It asserts existence of an order isomorphism, not that every chosen underlying bijection preserves order.

The empty order is initial in \(\Delta_+\), because it has one map to every finite order. A singleton is terminal, because every map into it is forced. In \(\mathcal E\), the two-point chain is initial: its two endpoints must go to the prescribed two endpoints of the target, even when those endpoints coincide. A singleton is terminal, by the unique constant map. There is no endpoint-preserving map from a singleton to a chain with two different endpoints.

Adjoin two new endpoints to define a functor

Extend every map by fixing the two new endpoints. The extension is nondecreasing and endpoint-preserving, and respects identities and composition on each of its three parts. In standard coordinates \(\kappa[n]=[n+2]\), including \(\kappa[-1]=[1]\).

2. Cuts give the opposite-category equivalence

For a finite order \(A\), let \(\operatorname{Cut}(A)\) be its initial segments ordered by inclusion. If \(|A|=s\), these are the segments of sizes \(0,1,\ldots,s\); hence this is a nonempty chain with \(s+1\) elements. A nondecreasing map \(f:A\to B\) sends initial segments backwards by inverse image:

Inverse images preserve inclusion, the empty segment and the whole segment. They also obey \((gf)^*=f^*g^*\) and \(1^*=1\). Thus this defines a functor \(\Delta_+^{\mathrm{op}}\to\mathcal E\).

Theorem 2.1. The cut functor is an equivalence.

Proof. Use the rankings to write \(A\) with \(s\) elements and \(B\) with \(t\) elements. A map \(f:A\to B\) gives the nondecreasing endpoint map

Conversely, for any nondecreasing \(g:\{0,\ldots,t\}\to\{0,\ldots,s\}\) with these endpoints, define

The successive intervals partition \(\{0,\ldots,s-1\}\), allowing empty intervals, so the indicated \(j\) exists uniquely. Increasing \(i\) cannot lower \(j\), making \(f\) nondecreasing. For any \(j\), the elements sent below \(j\) are exactly \(0,\ldots,g(j)-1\); hence (2.2) recovers \(g\). Starting from \(f\), its nondecreasing fibers give exactly the intervals in (2.3), so the inverse procedure recovers \(f\).

If \(t=0\), the endpoint equations force \(s=0\), which is exactly the condition for a map from \(A\) to the empty order. If \(s=0\), both constructions give the unique empty-source map and the constant cut map. Thus the Hom bijection includes every empty case. It proves full faithfulness. Finally every nonempty chain with \(r\) elements is isomorphic to the cuts of an order with \(r-1\) elements; for \(r=1\) use the empty order. This proves essential surjectivity, and therefore the equivalence. \(\square\)

The cut functor and \(\kappa\) are different: the first reverses arrows and adds one cut position, while the second keeps the arrow direction and adds two endpoints.

3. Every coface and collapse identity used below

For \(n\ge-1\), define the injective map omitting position \(i\) by

When \(n=-1\) this is the unique empty-source map. For \(n\ge1\), define the surjection identifying positions \(i,i+1\) by

Every collapse preserves the two endpoints. Here \(\mathbf1_P\) is one when \(P\) holds and zero otherwise.

Lemma 3.1. These maps satisfy

and

as well as the three mixed cases, for \(n\ge0\), \(0\le j\le n\), \(0\le i\le n+1\):

The nonidentity cases have \(n\ge1\), so all their displayed collapses exist.

Proof. The two sides of (3.3) are injective increasing maps with image omitting precisely \(i,j\). An increasing bijection to that ordered image is unique, so they agree. This also covers the empty source at \(n=-1\).

For (3.4), both composites have the value \(x-\mathbf1_{x>j}-\mathbf1_{x>i}\). On the left, after the first collapse at \(i\), the test for the collapse at \(j<i\) is still exactly \(x>j\). On the right, after collapsing at \(j\), the test for exceeding \(i-1\) is exactly \(x>i\). This proves the formula for every input.

In (3.5), if \(i<j\), each composite has value \(x+\mathbf1_{x\ge i}-\mathbf1_{x\ge j}\): inserting before \(i\) changes the collapse test to \(x\ge j\), and doing the collapse first leaves the insertion test \(x\ge i\). If \(i=j\) or \(i=j+1\), the insertion and the collapse cancel on every input, giving \(x\). If \(i>j+1\), both composites have value \(x+\mathbf1_{x\ge i}-\mathbf1_{x>j}\); after the first collapse, reaching the shifted insertion position \(i-1\) is exactly the condition \(x\ge i\). Thus every case, including its boundary values, holds. \(\square\)

Endpoint adjoining sends each coface to the interior coface

Both maps preserve the newly adjoined endpoints and omit exactly the interior position \(i+1\); their increasing image maps therefore agree.

4. Alternating cofaces form a complex and an extra collapse contracts it

Let \(F:\Delta_{+,\mathrm{inj}}\to\mathcal C\) be any functor. Set \(F^n=F[n]\) for \(n\ge-1\) and zero otherwise. Define

and use zero differentials below degree minus one. A functor here need not preserve an addition on its domain; the addition is in the Hom groups of \(\mathcal C\).

Theorem 4.1. The differential squares to zero. Suppose there are maps \(h^n:F^n\to F^{n-1}\) for \(n\ge0\) with

Extend \(h\) by zero below degree zero. Then \(h\) is a contracting homotopy for the augmented complex.

Proof. Expanding \(\delta^{n+1}\delta^n\) gives the finite sum of \((-1)^{i+j}F(d_j^{n+1}d_i^n)\), for \(0\le i\le n+1\), \(0\le j\le n+2\). Pair every term with \(i<j\) with the term whose indices are \((j-1,i)\). The latter has its second index at most its first, and every such term arises exactly once. Identity (3.3) makes the two maps equal; their sign exponents differ by one. They cancel. This proves square zero for \(n\ge-1\); below that the differential is zero.

For \(n\ge0\), (4.2) gives

Thus \(h^{n+1}\delta^n+\delta^{n-1}h^n=1\). At degree minus one, the first condition of (4.2) says \(h^0\delta^{-1}=1_{F^{-1}}\), while the other boundary term is zero. Below it the identity of a zero object is zero. These are exactly the homotopy equations in every degree. \(\square\)

A natural transformation of such functors gives a chain map: each coface square commutes, so their finite alternating sum does too. If the extra collapse maps are compatible with the transformation, their homotopies are compatible as well, by the degreewise square.

5. Endpoint adjoining supplies the required extra collapse

Let \(\widetilde F:\mathcal E\to\mathcal C\) be a functor, and first take \(F=\widetilde F\kappa\) on the injective category. Then \(F^n=\widetilde F[n+2]\) for \(n\ge-1\). For \(n\ge0\), put

These collapses belong to \(\mathcal E\), since they preserve both endpoints. Set \(h^{-1}=0\) into the zero term in degree minus two; no collapse to \(\widetilde F[0]\) is substituted for that zero term.

For \(n\ge-1\), (3.5) gives

With (3.6), this is precisely the first equation of (4.2). For \(n\ge0\), \(0\le i\le n\), its third mixed case gives

Applying \(\widetilde F\) identifies this with the second equation of (4.2). Theorem 4.1 therefore contracts the whole augmented complex. In particular its lowest identity is \(\widetilde F(s_0^2d_1^1)=1_{F^{-1}}\).

If only a natural isomorphism \(a:F\to\widetilde F\kappa\) is specified, naturality on all cofaces makes its components a chain isomorphism. Transport the contraction by

and use zero below it. Substituting into (4.3), or conjugating that identity by \(a\), proves the contraction. Hence an isomorphic factorization suffices; equality of the two functors is not required.

6. Two worked augmented complexes

Example 6.1 (the constant functor). Take any object \(A\) and the constant functor with every structural map the identity. Then \(F^n=A\) for \(n\ge-1\), and the alternating sum (4.1) is identity for odd \(n\), including \(n=-1\), and zero for even \(n\). The complex begins

in degrees \(-1,0,1,2,\ldots\). The maps \(h^n=1\) for \(n\ge0\) give the contraction, since exactly one of the two adjacent differentials is identity. If \(A\ne0\), removing degree minus one destroys contractibility: the new degree-zero differential is zero and its incoming term is zero, so its identity cannot be a homotopy boundary.

Example 6.2 (free groups on the adjoined order). In abelian groups let \(\widetilde F(B)\) be the free abelian group on the finite set \(B\), and send a basis element \(e_b\) under a map \(v\) to \(e_{v(b)}\). Checking on the basis proves the identity and composition laws. For \(F=\widetilde F\kappa\), the term \(F^n\) has basis \(e_0,\ldots,e_{n+2}\). A coface omits basis position \(i+1\), while \(h^n\) sends both \(e_0,e_1\) to \(e_0\), and sends \(e_r\) to \(e_{r-1}\) for \(r\ge2\).

The first differential sends the two degree-minus-one generators to the endpoints \(e_0,e_2\) in degree zero. The next differential is zero on those endpoints and sends the internal \(e_1\) to \(e_2-e_1\) in degree one. Theorem 4.1 proves every higher identity as well, with the same explicit collapse rule. Thus this supplies a contracting augmented complex with terms of increasing ranks, rather than a constant one.

7. Four graded exercises with complete solutions

Exercise 1 (foundation: faithfulness and half-fullness). List every endomorphism of the two-point chain in \(\Delta_+\) and in \(\mathcal E\). Explain why the order-forgetting functor is half-full but not full.

Solution. The nondecreasing maps have value lists \((0,0),(0,1),(1,1)\). Preserving both endpoints leaves only \((0,1)\) in \(\mathcal E\). The fourth underlying set map, \((1,0)\), is not nondecreasing, so the forgetful functor is not full. It is faithful because an underlying function determines the map. If two arbitrary finite orders have isomorphic underlying sets, they have equal cardinality and their unique increasing rankings give an order isomorphism. This proves half-fullness in its object-isomorphism sense; it does not require lifting that fourth chosen bijection.

Exercise 2 (intermediate: compute the cut dual). For \(f:[2]\to[1]\) with values \((0,0,1)\), calculate its map on cut counts and recover \(f\) from that map. Also calculate \(\kappa f\), and distinguish its direction and size from the cut map.

Solution. The cuts of \([1]\) have sizes \(0,1,2\). Their preimages have sizes \(0,2,3\), so \(f^*\) is the map \((0,1,2)\mapsto(0,2,3)\), from a three-point chain to a four-point chain. In (2.3), the interval for output zero is \([0,2)\) and the interval for output one is \([2,3)\); hence the recovered list is \((0,0,1)\). By contrast \(\kappa f\) goes from \([4]\) to \([3]\), with value list \((0,1,1,2,3)\). It adjoins two endpoints and keeps the original arrow direction. The cut functor reverses that direction and uses the initial-segment counts instead.

Exercise 3 (advanced: check the two lowest contractions as matrices). In Example 6.2 compute \(\delta^{-1},\delta^0,h^0,h^1\). Verify the homotopy identities in degrees minus one and zero.

Solution. In the increasing basis orders, the matrices are

and

Multiplication gives \(h^0\delta^{-1}=1_{\mathbb Z^2}\). On degree zero, \(\delta^{-1}h^0\) sends \(e_0,e_1,e_2\) to \(e_0,e_0,e_2\), respectively, while \(h^1\delta^0\) sends them to \(0,e_1-e_0,0\). Their sum is the identity. Also \(\delta^0\delta^{-1}=0\). This verifies the augmentation equation and the first cancellation with the actual signs.

Exercise 4 (synthesis: ordinary degeneracies do not supply the extra collapse). Define \(F[-1]=0\), \(F[n]=\mathbb Z\) for \(n\ge0\), with every map between nonempty orders acting as identity and every map from the empty order acting as zero. Show that this defines a functor even on \(\Delta_+\). Can its restriction to the injective category factor, up to natural isomorphism, through \(\kappa\) and a functor on \(\mathcal E\)?

Solution. There is no map from a nonempty order to the empty order. Thus every possible composite is either between nonempty orders, where the assigned maps are identities, or starts at the empty order, where all relevant maps are zero. The identity on the zero group is zero, so identities are preserved there too. This proves functoriality, including its ordinary collapse maps.

The alternating complex has \(F^{-1}=0\), \(F^0=\mathbb Z\), \(\delta^{-1}=0\) and \(\delta^0=1-1=0\). Any contraction would have its degree-zero boundary \(h^1\delta^0+\delta^{-1}h^0=0\), which cannot be the identity of \(\mathbb Z\). So the complex is not contractible. Section 5 would give a contraction for any factorization through \(\kappa\), even an isomorphic one. Hence no such factorization exists. Ordinary degeneracies and the extra endpoint collapse have different consequences at the augmentation.

References

• The Stacks Project Authors, The category of finite ordered sets, for the nonempty-order convention and its coface/collapse maps. Here the augmented category is explicitly denoted \(\Delta_+\), and includes \([-1]\).
• The definitions and boundary equation for actual chain homotopies are proved in Graded complexes, contravariant signs and stupid truncations, Section 1.