FinOrd.yaml

id: FinOrd
name: category of finite ordered sets
notation: $\FinOrd$
objects: finite (totally) ordered sets
morphisms: order-preserving maps
description: The finite ordered sets of the form $\{1 < \dotsc < n\}$ for $n \in \IN$ provide a skeleton (including the empty set for $n = 0$), the augmented simplex category.
nlab_link: https://ncatlab.org/nlab/show/total+order

tags:
  - order theory
  - topology

related:
  - Delta
  - FinSet
  - Pos

satisfied_properties:
  - property: locally small
    proof: There is a forgetful functor $\FinOrd \to \Set$ and $\Set$ is locally small.

  - property: locally finite
    proof: There is a faithful functor $\FinOrd \to \FinSet$ and <a href="/category/FinSet">$\FinSet$</a> is locally finite.

  - property: essentially countable
    proof: Every finite ordered set is isomorphic to $\{0 < \cdots < n-1 \}$ for some $n \in \IN$.

  - property: strict initial object
    proof: The empty ordered set is initial and is clearly strict.

  - property: terminal object
    proof: Take the singleton set with the unique ordering.

  - property: semi-strongly connected
    proof: Every non-empty totally ordered set is weakly terminal (by using constant maps).

  - property: generator
    proof: The one-point finite ordered set is a generator since it represents the forgetful functor $\FinOrd \to \Set$.

  - property: cogenerator
    proof: The ordered set $\{0 < 1\}$ is a cogenerator, even for <a href="/category/Pos">$\Pos$</a>.

  - property: equalizers
    proof: Take the equalizer in $\FinSet$ and restrict the order.

  - property: coequalizers
    proof: It suffices to construct quotients by equivalence relations. Let $\sim$ be an equivalence relation on $X$, where $(X,\leq)$ is a finite ordered set. Since $X$ is finite, by induction we may assume that $\sim$ is generated by a single relation $(a,b)$. If $a=b$, there is nothing to prove. If $a < b$ and $X = \{0,1,\dotsc,n-1\}$ with the usual order, the quotient is $\{0,1,\dotsc,a,b+1,\dotsc,n-1\}$ with the usual order.

  - property: mono-regular
    proof: 'Let $i : A \to B$ be a monomorphism of finite ordered sets. If $A$ is empty, then $i$ is clearly regular, so assume it is not. The map $i$ is injective (see below), hence order-reflecting. Define maps $u,v  : B \to A$ by $u(b) \coloneqq \max \{a \in A : i(a) \leq b \}$ and $v(b) \coloneqq \min \{a \in A : b \leq i(a) \}$. These are order-preserving and satisfy $u \circ i = v \circ i$, both sides are $\id_A$. Conversely, if $b \in B$ satisfies $u(b) = v(b) \eqqcolon a$, then $i(a) \leq b$ and $b \leq i(a)$, hence $b = i(a)$. This shows that $i$ is the equalizer of $u,v$.'

  - property: epi-regular
    proof: 'Let $f : A \to B$ be an epimorphism of finite ordered sets. It is surjective (see below). Define $u,v : B \to A$ by $u(b) \coloneqq \min(f^{-1}(b))$ and $v(b) \coloneqq \max(f^{-1}(b))$. One can easily check that $u,v$ are order-preserving maps with $f \circ u = f \circ v$ (both sides are $\id_B$). Let $h : A \to T$ be an order-preserving map with $h \circ u = h \circ v$. Then $h(a)$ only depends on $b \coloneqq f(a)$: We have $u(b) \leq a \leq v(b)$, hence $h(u(b)) \leq h(a) \leq h(v(b)) = h(u(b))$. Therefore, there is a unique map $\tilde{h} : B \to T$ with $\tilde{h}(f(a)) = h(a)$, and one easily checks that it is order-preserving. This shows that $f$ is the coequalizer of $u,v$.'

  - property: core-thin
    proof: 'Let $f : \{1 < \cdots < n \} \to \{1 < \cdots < n \}$ be an automorphism. Then $f(i)$ is the smallest element not contained in $\{f(j) : j < i\}$. From this one can deduce $f(i)=i$ by induction.'

  - property: ℵ₁-cofiltered limits
    proof: 'Let $D : \I \to \FinOrd$ be an $\aleph_1$-cofiltered diagram. Since <a href="/category/FinSet">$\FinSet$</a> is closed under $\aleph_1$-cofiltered limits in $\Set$, the limit of $D$ taken in $\Set$ is a finite set $L$. We define a partial order on $L$ in the obvious way: $x \leq y$ iff $p_i(x) \leq p_i(y)$ for all $i \in \I$. It remains to prove that this is indeed a total order. So assume that $x,y \in L$ satisfy neither $x \leq y$ nor $y \leq x$. Then there exist $i,j \in \I$ such that $p_i(x) \not\leq p_i(y)$ and $p_j(y) \not\leq p_j(x)$. Choose a span $i \leftarrow k \rightarrow j$. Then $p_k(x) \not\leq p_k(y)$ and $p_k(y) \not\leq p_k(x)$ in $D(k)$, which is impossible.'

unsatisfied_properties:
  - property: small
    proof: Even the collection of all singleton orders is not small.

  - property: skeletal
    proof: This is trivial.

  - property: one-way
    proof: There are three different order-preserving maps $\{0 < 1\} \to \{0 < 1\}$.

  - property: countable
    proof: This is trivial.

  - property: strict terminal object
    proof: This is trivial.

  - property: sequential limits
    proof: Consider the (non-empty) ordered set $[n] \coloneqq \{0 < \cdots < n\}$ for $n \in \IN$. The forgetful functor to $\Set$ is representable, hence preserves all limits. Thus, if the diagram of truncation maps $\cdots \twoheadrightarrow [2] \twoheadrightarrow [1] \twoheadrightarrow [0]$ has a limit in $\FinOrd$, its underlying set is isomorphic to the limit taken in $\Set$, which is $\IN \cup \{\infty\}$. But this is not a finite set.

  - property: sequential colimits
    proof: 'Consider the (non-empty) ordered set $[n] \coloneqq \{0 < \cdots < n\}$ for $n \in \IN$. Assume the sequence of inclusion maps $[0] \hookrightarrow [1] \hookrightarrow [2] \hookrightarrow \cdots$ has a colimit $(f_n : [n] \to X)$ in $\FinOrd$. Let $n_0 \geq 0$ be fixed. I claim that $f_{n_0}$ is injective, which will then yield a contradiction by taking $n_0 \geq \card(X)$. For $n \geq 0$ define $g_n : [n] \to [n_0]$ as follows. For $n \leq n_0$ it is the inclusion, and for $n \geq n_0$ it is the surjection which keeps all elements of $[n_0]$ and maps all other elements to $n_0$. Observe that $g_n$ preserves the order and $g_{n+1} |_{[n]} = g_n$. Hence, there is a unique order-preserving map $g : X \to [n_0]$ with $g \circ f_n = g_n$ for all $n$. For $n = n_0$ this shows $g \circ f_{n_0} = \id_{[n_0]}$, and $f_{n_0}$ is injective.'

special_objects:
  initial object:
    description: empty ordered set
  terminal object:
    description: singleton ordered set
  products:
    description: '[finite case] direct products with the evident order'

special_morphisms:
  isomorphisms:
    description: bijective order-preserving maps
    proof: This works as for posets, using that injective order-preserving maps must be order-reflecting.
  monomorphisms:
    description: injective order-preserving maps
    proof: For the non-trivial direction, the forgetful functor to $\Set$ is representable (by the terminal object), hence preserves monomorphisms.
  epimorphisms:
    description: surjective order-preserving maps
    proof: 'The proof is similar to the one for <a href="/category/Set">$\Set$</a>: If $f : X \to Y$ is an epimorphism of (finite) orders, in particular for all morphisms $g,h : Y \to \{0 < 1\}$ with $g \circ f = h \circ f$ we have $g = h$. This means for all upper sets $A,B \subseteq Y$ with $f^*(A) = f^*(B)$ we have $A = B$. If $y \in Y$, apply this to the intervals $A = Y_{\geq y}$ and $B = Y_{> y}$, which are different. Hence, there is some $x \in f^*(A) \setminus f^*(B)$, which means $f(x) \geq y$ but not $f(x) > y$, so that $f(x) = y$.'
  regular monomorphisms:
    description: same as monomorphisms
    proof: This is because the category is mono-regular.
  regular epimorphisms:
    description: same as epimorphisms
    proof: This is because the category is epi-regular.