The Stacks project

14.2 The category of finite ordered sets

The category $\Delta $ is the category with

  1. objects $[0], [1], [2], \ldots $ with $[n] = \{ 0, 1, 2, \ldots , n\} $ and

  2. a morphism $[n] \to [m]$ is a nondecreasing map $\{ 0, 1, 2, \ldots , n\} \to \{ 0, 1, 2, \ldots , m\} $ between the corresponding sets.

Here nondecreasing for a map $\varphi : [n] \to [m]$ means by definition that $\varphi (i) \geq \varphi (j)$ if $i \geq j$. In other words, $\Delta $ is a category equivalent to the “big” category of nonempty finite totally ordered sets and nondecreasing maps. There are exactly $n + 1$ morphisms $[0] \to [n]$ and there is exactly $1$ morphism $[n] \to [0]$. There are exactly $(n + 1)(n + 2)/2$ morphisms $[1] \to [n]$ and there are exactly $n + 2$ morphisms $[n] \to [1]$. And so on and so forth.

Definition 14.2.1. For any integer $n\geq 1$, and any $0\leq j \leq n$ we let $\delta ^ n_ j : [n-1] \to [n]$ denote the injective order preserving map skipping $j$. For any integer $n\geq 0$, and any $0\leq j \leq n$ we denote $\sigma ^ n_ j : [n + 1] \to [n]$ the surjective order preserving map with $(\sigma ^ n_ j)^{-1}(\{ j\} ) = \{ j, j + 1\} $.

Lemma 14.2.2. Any morphism in $\Delta $ can be written as a composition of the morphisms $\delta ^ n_ j$ and $\sigma ^ n_ j$.

Proof. Let $\varphi : [n] \to [m]$ be a morphism of $\Delta $. If $j \not\in \mathop{\mathrm{Im}}(\varphi )$, then we can write $\varphi $ as $\delta ^ m_ j \circ \psi $ for some morphism $\psi : [n] \to [m - 1]$. If $\varphi (j) = \varphi (j + 1)$ then we can write $\varphi $ as $\psi \circ \sigma ^{n - 1}_ j$ for some morphism $\psi : [n - 1] \to [m]$. The result follows because each replacement as above lowers $n + m$ and hence at some point $\varphi $ is both injective and surjective, hence an identity morphism. $\square$

Lemma 14.2.3. The morphisms $\delta ^ n_ j$ and $\sigma ^ n_ j$ satisfy the following relations.

  1. If $0 \leq i < j \leq n + 1$, then $\delta ^{n + 1}_ j \circ \delta ^ n_ i = \delta ^{n + 1}_ i \circ \delta ^ n_{j - 1}$. In other words the diagram

    \[ \xymatrix{ & [n] \ar[rd]^{\delta ^{n + 1}_ j} & \\ [n - 1] \ar[ru]^{\delta ^ n_ i} \ar[rd]_{\delta ^ n_{j - 1}} & & [n + 1] \\ & [n] \ar[ru]_{\delta ^{n + 1}_ i} & } \]

    commutes.

  2. If $0 \leq i < j \leq n - 1$, then $\sigma ^{n - 1}_ j \circ \delta ^ n_ i = \delta ^{n - 1}_ i \circ \sigma ^{n - 2}_{j - 1}$. In other words the diagram

    \[ \xymatrix{ & [n] \ar[rd]^{\sigma ^{n - 1}_ j} & \\ [n - 1] \ar[ru]^{\delta ^ n_ i} \ar[rd]_{\sigma ^{n - 2}_{j - 1}} & & [n - 1] \\ & [n - 2] \ar[ru]_{\delta ^{n - 1}_ i} & } \]

    commutes.

  3. If $0 \leq j \leq n - 1$, then $\sigma ^{n - 1}_ j \circ \delta ^ n_ j = \text{id}_{[n - 1]}$ and $\sigma ^{n - 1}_ j \circ \delta ^ n_{j + 1} = \text{id}_{[n - 1]}$. In other words the diagram

    \[ \xymatrix{ & [n] \ar[rd]^{\sigma ^{n - 1}_ j} & \\ [n - 1] \ar[ru]^{\delta ^ n_ j} \ar[rd]_{\delta ^ n_{j + 1}} \ar[rr]^{\text{id}_{[n - 1]}} & & [n - 1] \\ & [n] \ar[ru]_{\sigma ^{n - 1}_ j} & } \]

    commutes.

  4. If $0 < j + 1 < i \leq n$, then $\sigma ^{n - 1}_ j \circ \delta ^ n_ i = \delta ^{n - 1}_{i - 1} \circ \sigma ^{n - 2}_ j$. In other words the diagram

    \[ \xymatrix{ & [n] \ar[rd]^{\sigma ^{n - 1}_ j} & \\ [n - 1] \ar[ru]^{\delta ^ n_ i} \ar[rd]_{\sigma ^{n - 2}_ j} & & [n - 1] \\ & [n - 2] \ar[ru]_{\delta ^{n - 1}_{i - 1}} & } \]

    commutes.

  5. If $0 \leq i \leq j \leq n - 1$, then $\sigma ^{n - 1}_ j \circ \sigma ^ n_ i = \sigma ^{n - 1}_ i \circ \sigma ^ n_{j + 1}$. In other words the diagram

    \[ \xymatrix{ & [n] \ar[rd]^{\sigma ^{n - 1}_ j} & \\ [n + 1] \ar[ru]^{\sigma ^ n_ i} \ar[rd]_{\sigma ^ n_{j + 1}} & & [n - 1] \\ & [n] \ar[ru]_{\sigma ^{n - 1}_ i} & } \]

    commutes.

Proof. Omitted. $\square$

Lemma 14.2.4. The category $\Delta $ is the universal category with objects $[n]$, $n \geq 0$ and morphisms $\delta ^ n_ j$ and $\sigma ^ n_ j$ such that (a) every morphism is a composition of these morphisms, (b) the relations listed in Lemma 14.2.3 are satisfied, and (c) any relation among the morphisms is a consequence of those relations.

Proof. Omitted. $\square$

Comments (5)

Comment #253 by Keenan Kidwell on

In the definition of morphisms for the category , I think "a morphism is the set of nondecreasing" should be "a morphism is a nondecreasing," since this is introducing the notion of a morphism between two objects, as opposed to talking about the set of morphisms between two objects.

Comment #254 by Keenan Kidwell on

Regarding the lemma with tag 0166, when it says "composition with an identity morphism," isn't this unnecessary? I could very well be misunderstanding, but isn't the lemma just saying that any morphism is a composite of the two kinds of special morphisms just defined?

Comment #3284 by on

The "big" category of finite totally ordered sets -- the empty set is an object of this category, right? And the empty set seems to have no corresponding element of Delta, so perhaps Delta isn't equivalent to this big category the way you wrote it (so maybe you have to choose between adding an empty set to Delta, removing the empty set from your big category, relaxing the assertion that it's an equivalence, or pointing out my error).

Comment #3371 by on

OK, I opted for removing the empty set from the other side. The category definitively shouldn't contain the empty set as an object. Thanks and fixed here.

Post a comment

Your email address will not be published. Required fields are marked.

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).

Unfortunately JavaScript is disabled in your browser, so the comment preview function will not work.

All contributions are licensed under the GNU Free Documentation License.




In order to prevent bots from posting comments, we would like you to prove that you are human. You can do this by filling in the name of the current tag in the following input field. As a reminder, this is tag 0164. Beware of the difference between the letter 'O' and the digit '0'.



View Section 14.2 as pdf