Cuts and endpoint maps in finite orders

Written by GPT-6.1 Sol (OpenAI), Ultra reasoning effort, October 2026. Self-checked by the writing AI (GPT-6.1 Sol, Ultra). Original text: CC0.

A finite linear order can be recovered from its cuts. Moving a point forward moves the evaluation at that point forward, but moving the order itself forward pulls its cuts backward. This reversal turns injections of finite orders into surjections of their cut orders. Adjoining two endpoints gives a second construction: arbitrary monotone maps become endpoint-preserving maps from the enlarged order.

We use finite linear orders with arbitrary monotone maps, including the empty order. We distinguish this augmented category from the nonempty simplicial indexing category used in [Stacks, Finite ordered sets]. The category of nonempty finite orders with endpoint-preserving maps will provide its dual. Prerequisites are the complete opposite-category and functor laws in Relations and cancellation in categories, the equivalence criterion in Equivalences and chosen representatives, and Passing maps across an adjunction. Basic references are [Stacks, Finite ordered sets], [Simplicial sets, nerves and Kan complexes] and these three prerequisite lessons.

Fix a universe \(\mathcal U\), and take orders whose underlying finite sets and order relations belong to it. Their Hom sets are finite and belong to \(\mathcal U\); all object data form ambient sets. The small models in Section 5 have \(\mathcal U\)-small object sets. The cut constructions remain within this universe by its finite-set and function-set closure, proved in Universes and small categories.

1. The chain of all cuts

Write \(\mathsf O\) for the category of finite linear orders, including the empty order, and monotone maps. Write \(\mathsf B\) for the category of nonempty finite linear orders and monotone maps preserving both the least and the greatest element. The least and greatest element of a singleton coincide. Consequently there is no endpoint-preserving map from a singleton to a two-element order. These maps are closed under identities and composition, so \(\mathsf B\) is a subcategory of \(\mathsf O\).

Let \(\mathbf2=\{0<1\}\). For \(P\in\mathsf O\), define

ordered pointwise.

Proposition 1.1. If \(P\) has \(n\) elements, \(S(P)\) is a nonempty linear order with \(n+1\) elements. Its endpoints are the constant functions. Precomposition defines a functor \(S:\mathsf O\to\mathsf B^{\mathrm{op}}\).

Proof. For a finite linear order \(P=\{p_1<\cdots<p_n\}\), every monotone map to \(\mathbf2\) has one initial block of zeros followed by one final block of ones. For \(0\leq c\leq n\), let \(f_c(p_i)=0\) if \(i\leq c\), and \(f_c(p_i)=1\) if \(i>c\). These are all the maps, and for \(n\geq1\) their order is

Thus \(S(P)\) is a nonempty linear order with \(n+1\) elements. Its least and greatest elements are the constant zero and constant one functions. If \(P\) is empty these are the same empty function, and \(S(P)\) is a singleton.

For a monotone \(u:P\to P'\), precomposition gives

It is monotone because pointwise inequalities remain inequalities after substitution. It preserves the two constant functions, hence both endpoints. Identity substitution is the identity, and substitution along \(vu\) is first substitution along \(v\) and then along \(u\). Consequently \(S:\mathsf O\to\mathsf B^{\mathrm{op}}\) is a functor. \(\square\)

For the three-element chain \(a<b<c\), the entire cut order and its point evaluations fit in one table:

Figure 1.1. Rows increase from the least cut to the greatest. Each column is an endpoint-preserving monotone function on that row order. The columns increase in the original point order \(a<b<c\), which Section 2 recovers by evaluation. The displayed array is the editable source of this exact finite diagram.

2. Evaluation recovers the original points

For \(Q\in\mathsf B\), define

again ordered pointwise. If \(Q=\{q_1<\cdots<q_m\}\), an endpoint-preserving map must take \(q_1\) to zero and \(q_m\) to one. For \(m\geq2\), the possible cuts therefore have \(1\leq c\leq m-1\). They form a linear order of size \(m-1\). For \(m=1\), no such map exists and \(T(Q)\) is the empty order. An endpoint-preserving map \(v:Q'\to Q\) induces the monotone map \(T(Q)\to T(Q')\), \(g\mapsto gv\). Substitution proves both functor laws. This defines \(T:\mathsf B^{\mathrm{op}}\to\mathsf O\).

Theorem 2.1. The functors \(S:\mathsf O\to\mathsf B^{\mathrm{op}}\) and \(T:\mathsf B^{\mathrm{op}}\to\mathsf O\) are quasi-inverse equivalences. The two comparisons are given by evaluation.

Proof. Define the evaluation maps

For \(e_P\), evaluation is monotone in \(f\) and takes the constant zero and one functions to zero and one, respectively. Hence \(e_P(p)\) belongs to \(T(S(P))\). As \(p\) increases, every monotone \(f\) has nondecreasing values, so \(e_P\) is monotone. If \(p<p'\), there is a cut with value zero at \(p\) and one at \(p'\), so these evaluations are distinct. Both \(P\) and \(T(S(P))\) have \(n\) elements, including \(n=0\), making \(e_P\) bijective. A monotone injection between linear orders reflects order: if \(p>p'\), its two distinct images have the same strict inequality. A monotone bijection therefore has a monotone inverse. Thus \(e_P\) is an order isomorphism.

For \(d_Q\), evaluation is monotone in \(g\) and in \(q\). If \(m\geq2\), the endpoints of \(Q\) evaluate to the constant zero and one functions on \(T(Q)\), so \(d_Q\) preserves endpoints. Every pair \(q<q'\) can be separated by an endpoint-preserving cut between them. Thus the evaluations are distinct, and \(Q,S(T(Q))\) both have \(m\) elements. For \(m=1\), its target is the singleton set of empty functions; \(d_Q\) is the unique order isomorphism and preserves the coincident endpoints.

For \(u:P\to P'\), evaluate either composite in the first identity below at \(p\in P\) and \(f\in S(P')\). The result is \(f(u(p))\) in both cases. For \(v:Q\to Q'\), evaluate either composite in the second at \(q\in Q\) and \(g\in T(Q')\); the result is \(g(v(q))\):

Here \(S(u):S(P')\to S(P)\) and \(T(v):T(Q')\to T(Q)\) are written in their underlying categories, so both equations have the displayed types. They prove both naturality statements. In \(\mathsf B^{\mathrm{op}}\), the arrow \(d_Q^{\mathrm{op}}\) goes from \(STQ\) to \(Q\). Thus \(e:1_{\mathsf O}\Rightarrow TS\) and the components \(d_Q^{\mathrm{op}}\) of \(ST\Rightarrow1_{\mathsf B^{\mathrm{op}}}\) are natural isomorphisms exhibiting the quasi-inverse functors. We have proved

\(\square\)

The empty order is essential: it corresponds to the singleton endpoint order, whose two endpoints coincide.

The evaluation comparisons also satisfy the two triangle identities. In the underlying categories these read

For \(f\in S(P)\), the first composite evaluated at \(p\) is \(d_{S(P)}(f)(e_P(p))=e_P(p)(f)=f(p)\). For \(g\in T(Q)\), the second evaluated at \(q\) is \(e_{T(Q)}(g)(d_Q(q))=d_Q(q)(g)=g(q)\). Equality at every point proves the identities, including empty function domains. Theorem 2.2 of Passing maps across an adjunction therefore makes these specific comparisons an adjoint equivalence as well.

3. An injection becomes a surjection of cuts

Theorem 3.1. For a monotone \(u:P\to P'\), the endpoint map \(S(u)\) is surjective if and only if \(u\) is injective. The equivalence restricts to injections in \(\mathsf O\) and the opposite of endpoint-preserving surjections in \(\mathsf B\).

Proof. If \(u\) is injective, it identifies \(P\) with an ordered subset of \(P'\). A cut on \(P\) extends to a cut on \(P'\): take the initial zero block in the image, close it downward in \(P'\), and assign one elsewhere. The downward closure intersects \(u(P)\) in exactly the original zero block, since the complementary image points are strictly larger. If the zero block is empty its downward closure is empty. The resulting monotone function therefore restricts to the original cut. Empty \(P\) causes no exception: its one empty cut is the restriction of either constant function on \(P'\).

If \(u\) is not injective, choose \(p<p'\) with \(u(p)=u(p')\). There is a cut on \(P\) taking different values at those points. No function pulled back from \(P'\) can do so. Therefore \(S(u)\) is not surjective.

The quasi-inverse evaluations in Section 2 are order isomorphisms. In particular, their underlying maps are injective and surjective. For every endpoint map \(v:Q\to Q'\), (2.3) gives

Thus \(v\) is surjective exactly when \(S(T(v))\) is. Apply the first assertion to the monotone \(T(v):T(Q')\to T(Q)\): this happens exactly when \(T(v)\) is injective. Consequently both functors restrict to the indicated subcategories. The natural comparisons also restrict, since order isomorphisms are both injective and surjective. They give

with the same objects as before. \(\square\)

4. Adjoin boundaries and then forget them

Let \(J:\mathsf B\to\mathsf O\) be inclusion. For \(P\in\mathsf O\), let \(A(P)\) be the disjoint ordered sum of a new least point, \(P\), and a new greatest point. The two new points are distinct even when \(P\) is empty. Extend a monotone \(u\) by fixing the new endpoint labels; this defines an endpoint-preserving \(A(u)\). Its identity and composition laws hold on each of the three summands.

Theorem 4.1. Adjoining endpoints is left adjoint to inclusion: \(A\dashv J\).

Proof. Restriction and extension give a bijection

Restriction discards the values at the new endpoints. Its inverse sends those endpoints to the least and greatest points of \(Q\), and agrees with the given map on \(P\). This extension is monotone because every value on \(P\) lies between those two endpoints. Restriction after extension returns the given map, while extension after restriction returns the original endpoint-preserving map because its endpoint values were already forced. Composing in \(P\) or \(Q\) commutes with the operations, since maps in \(\mathsf B\) preserve the two endpoint values. Thus the bijection is natural in both variables and proves \(A\dashv J\). \(\square\)

Its unit includes \(P\) in its middle summand; its counit sends the new endpoints of \(A(JQ)\) to the endpoints of \(Q\) and is the identity on its middle summand. In the first triangle, \(A\) of the middle inclusion fixes the new endpoints and includes each old point in the middle of \(A(J(A(P)))\); the counit sends those points back and fixes the two endpoints of \(A(P)\). In the second triangle, middle inclusion followed by the counit is the identity at each point of \(JQ\). This checks both triangles on their whole domains.

Proposition 4.2. The square formed by \(A,S,T^{\mathrm{op}},J^{\mathrm{op}}\) commutes up to a specified natural isomorphism.

Proof. Apply the same restriction to \(Q=\mathbf2\). At each \(P\), it gives an order isomorphism

The inverse is endpoint extension; both preserve pointwise inequalities. For \(u:P\to P'\), restricting \(h A(u)\) to the middle summand gives the restriction of \(h\) followed by \(u\). Hence

The symbol \(T(A(u))\) here means the underlying precomposition arrow \(T(A(P'))\to T(A(P))\). In categorical composition, use \(T^{\mathrm{op}}\circ A:\mathsf O\to\mathsf O^{\mathrm{op}}\). Likewise the other route is \(J^{\mathrm{op}}\circ S\). Reversing (4.2) gives the components in \(\mathsf O^{\mathrm{op}}\) of the natural isomorphism

Equation (4.3) proves its naturality and identifies the particular comparison, rather than only its existence. \(\square\)

5. Small models and extreme objects

Proposition 5.1. The full subcategory of \(\mathsf O\) on \([0,n]\), \(n\geq-1\), is a small model of \(\mathsf O\). Forgetting order is faithful and reflects existence of an isomorphism between objects.

Proof. Every finite linear order has a unique increasing listing: successively take its least remaining element. Its increasing listing identifies it with the chain of the same cardinality; the empty order corresponds to \([0,-1]\). The full subcategory on those standard chains is fully faithful by definition and essentially surjective by this listing. The complete equivalence criterion cited in the introduction makes it equivalent to \(\mathsf O\). Its objects are indexed by the integers \(n\geq-1\), a member of \(\mathcal U\), and its Hom sets are finite, so it is \(\mathcal U\)-small.

The forgetful functor to finite sets is faithful, because equality of underlying functions is equality of monotone maps. If two underlying finite sets have the same cardinality, matching their points in increasing order gives an order isomorphism. Thus this functor reflects existence of an isomorphism between objects. It need not lift a particular permutation: the transposition of a two-element set is not monotone. \(\square\)

The empty order is initial and the singleton is terminal in \(\mathsf O\). In \(\mathsf B\), the two-element order is initial: its endpoint values determine the unique map to every \(Q\), including the singleton. The singleton is terminal because the unique constant map from \(Q\) to it preserves both endpoints. The duality exchanges these initial and terminal objects as required.

6. Four exercises with full solutions

Exercise 1 — read a gap from its dual map

Foundation. Let \(P=\{0<1<2\}\), \(P'=\{0<1<2<3\}\), and let \(u:P\to P'\) have values \((0,2,3)\). List \(S(u)\) on all cuts, in increasing cut order. Identify its only nontrivial fibre. Show that applying \(T\) to this endpoint map recovers \(u\) under the evaluation comparisons.

Solution. A string lists the values of a cut at the points in increasing order. The full map is

Both columns increase pointwise down the table. The first and last cuts map to the corresponding endpoints. Every cut on \(P\) occurs, so \(S(u)\) is surjective. Its only fibre with more than one member is \(\{0011,0111\}\), whose two cuts differ at the omitted point \(1\in P'\).

For \(p\in P\), \(T(S(u))(e_P(p))\) is the function on \(S(P')\) sending \(f\) to \(e_P(p)(S(u)(f))=f(u(p))\). It is therefore \(e_{P'}(u(p))\). Under the increasing evaluation identifications its three values are \(0,2,3\). This recovers the original injection, and explains which omitted point causes the cut fibre.

Exercise 2 — count maps and check the empty cases

Intermediate. Count monotone maps from an \(n\)-element chain to an \(m\)-element chain, allowing \(n,m=0\). Count endpoint-preserving maps from an \(a\)-element nonempty chain to a \(b\)-element nonempty chain. Deduce numerical checks of both the duality and the endpoint adjunction. Finally count injections and the corresponding endpoint-preserving surjections.

Solution. For \(m\geq1\), a monotone map is determined by the nonnegative fibre sizes \(s_1,\ldots,s_m\) with sum \(n\). Conversely such sizes specify one monotone map by its successive constant blocks. To count the vectors, place \(m-1\) separators among a row of \(n\) identical marks: choosing the mark positions in the resulting \(n+m-1\) positions gives

This includes \(n=0\), with its unique empty map. If \(m=0\), there is one map when \(n=0\) and no map when \(n>0\).

For endpoint maps, if \(b=1\) there is exactly one map for every \(a\geq1\). If \(a=1<b\), there is no map because the single source point would have to map to both distinct target endpoints. If \(a,b\geq2\), the endpoint values are fixed. The other \(a-2\) entries may be any nondecreasing list of values in the \(b\)-element target. The preceding count gives

For the duality, the sizes on the endpoint side are \(a=m+1\), \(b=n+1\). If \(n,m\geq1\), (6.3) becomes \(\binom{n+m-1}{m-1}=\binom{n+m-1}{n}\). If \(n=0\), the endpoint target is a singleton and there is exactly one map, as on the order side. If \(m=0<n\), the endpoint source is a singleton with a larger target and there is no map. If both vanish, both Hom sets have one element.

For the adjunction, the endpoint source \(A(P)\) has \(a=n+2\) elements and its target has \(b=m\geq1\). When \(m\geq2\), (6.3) gives exactly (6.2); when \(m=1\), both counts are one.

An injection chooses an \(n\)-element ordered subset of the \(m\)-element target, so there are \(\binom mn\) injections for \(0\leq n\leq m\), and none for \(n>m\). This includes the unique empty injection. A monotone surjection from a chain of size \(m+1\) to one of size \(n+1\) is determined by its \(n+1\) positive fibre sizes summing to \(m+1\). Choosing their \(n\) dividing positions among the \(m\) gaps gives \(\binom mn\), with no choice when \(n>m\). Surjectivity forces endpoint preservation. The counts therefore agree with the restricted duality, including a singleton endpoint target.

Exercise 3 — what breaks for a partially ordered set

Advanced. Let \(P=\{a,b,c\}\), where \(a<c\), \(b<c\), and \(a,b\) are incomparable. For this exercise extend the cut construction to finite partially ordered sets and extend the endpoint-cut construction to bounded finite partially ordered sets. List the cuts on \(P\) and all endpoint-preserving monotone functions on its cut poset. Does point evaluation recover \(P\) as an isomorphism?

Solution. List values in the order \(a,b,c\). The cuts are

The cuts \(011\) and \(101\) are incomparable. The order has least point \(000\), then \(001\), then the two incomparable points \(011,101\), then greatest point \(111\). Thus the cut poset is bounded and not a linear order.

An endpoint-preserving monotone function on it has value zero at \(000\) and one at \(111\). Its set of ones is a nonempty upper set excluding \(000\). There are exactly five:

Indeed, including \(001\) forces both middle points, and each included middle point forces \(111\); these conditions enumerate every choice.

Evaluation at \(a\), \(b\), \(c\) has respectively the sets of ones \(\{101,111\}\), \(\{011,111\}\), and \(\{001,011,101,111\}\). They are distinct and preserve and reflect the order of \(P\). But two of the five functions are not point evaluations: the function with ones \(\{111\}\) is the pointwise meet of evaluation at \(a,b\), and the one with ones \(\{011,101,111\}\) is their pointwise join. Hence evaluation embeds this three-element poset into a five-element one and is not surjective. This example explains why Theorem 2.1 assumes linear orders.

Exercise 4 — compute both routes past new endpoints

Advanced. Take \(P=\{0<1\}\) and \(Q=\{0<1<2\}\). List every map \(P\to JQ\) and its adjoint map \(A(P)\to Q\). Give the unit at \(P\) and counit at \(Q\), and check both triangles in ordered coordinates. For the constant map \(u:P\to\{0\}\), verify the naturality equation (4.3) on every endpoint cut of \(A(\{0\})\).

Solution. The six nondecreasing pairs \((x,y)\) in \(Q\) are

Their adjoint maps have the four successive values \((0,x,y,2)\) on \(A(P)\). Restriction returns \((x,y)\), and extending any endpoint map returns its tuple because its first and last entries were already \(0,2\).

The unit includes the two points in the middle of the four-element order, with values \((1,2)\). The counit at \(Q\) has the five values \((0,0,1,2,2)\). For the first triangle at \(A(P)\), \(A\) of the unit has values \((0,2,3,5)\) in the six-element order \(A(J(A(P)))\). The counit there has values \((0,0,1,2,3,3)\). Composing gives \((0,1,2,3)\), the identity on \(A(P)\). For the second triangle at \(JQ\), the unit has values \((1,2,3)\), and the counit just listed sends them to \((0,1,2)\), the identity on \(Q\).

The three endpoint cuts on \(A(P)\), and their restrictions to \(P\), are

The order \(A(\{0\})\) has three elements and its two endpoint cuts are \(001,011\). The map \(A(u)\) has values \((0,1,1,2)\). Pulling those two cuts back gives \(0001,0111\), whose middle restrictions are \(00,11\). The other route first restricts \(001,011\) to the singleton, giving \(0,1\), then precomposes with the constant \(u\), giving \(00,11\). Both routes agree on every cut, verifying the exact naturality comparison in this example.

7. References

• [Stacks, Finite ordered sets] The Stacks Project authors, Simplicial Methods, “The category of finite ordered sets”. The consulted pinned structured chapter uses the nonempty indexing category. Its licence is GFDL 1.2 or later. No source expression is incorporated here.
• [Simplicial sets, nerves and Kan complexes] Section 1.1, “The indexing category”, a separate course lesson using nonempty standard chains for simplicial objects. Its nerve and homotopy results are not needed for the proofs here.
• [Categorical prerequisites] Relations and cancellation in categories, Equivalences and chosen representatives, and Passing maps across an adjunction, the complete internal functor, equivalence and adjunction interfaces used above.