Prost.yaml

id: Prost
name: category of prosets
notation: $\Prost$
objects: preordered sets (aka prosets), i.e. sets equipped with a reflexive, transitive relation
morphisms: order-preserving functions
description: Even though there are many similarities with $\Pos$, the main difference is that the forgetful functor $\Prost \to \Set$ has a right adjoint, mapping $X$ to $(X , X \times X)$ (chaotic preorder).
nlab_link: https://ncatlab.org/nlab/show/Prost

tags:
  - order theory

related_categories:
  - Pos

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

  - property: locally finitely presentable
    proof: The same proof as for <a href="/category/Pos">$\Pos$</a> works, cf. <a href="https://ncatlab.org/nlab/show/Locally+Presentable+and+Accessible+Categories" target="_blank">Adamek-Rosicky</a>, Example 1.10.

  - property: cartesian closed
    proof: For prosets $P,Q$ we endow $\Hom(P,Q)$ with the preorder in which $f \leq g$ holds iff $f(p) \leq g(p)$ for all $p \in P$. The universal evaluation map is $\Hom(P,Q) \times P \to Q$, $(f,p) \mapsto f(p)$, it is order-preserving, and it satisfies the universal property.

  - property: generator
    proof: The singleton proset $1$ is a generator, since morphisms $1 \to P$ correspond to the elements of $P$.

  - property: cogenerator
    proof: Endow the set $\{ 0,1 \}$ with the preorder $0 \leq 1$, $1 \leq 0$ (which is not a partial order). Then every map $P \to \{0,1\}$ is order-preserving. Now the claim follows since the set $\{ 0,1 \}$ is a cogenerator in $\Set$.

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

  - property: infinitary extensive
    proof: '[Sketch] Since <a href="/category/Set">$\Set$</a> is infinitary extensive, a map $f : P \to \coprod_i Q_i$ corresponds to a decomposition $P = \coprod_i P_i$ (as sets) with maps $f_i : P_i \to Q_i$. Endow $P_i$ with the induced order. If $f$ is order-preserving, the elements in different $P_i$ cannot be comparable (since their $f$-images are not comparable), so that $P = \coprod_i P_i$ as prosets, and each $f_i$ is order-preserving.'

  - property: coregular
    proof: See <a href="https://math.stackexchange.com/questions/5130295" target="_blank">MSE/5130295</a>.

  - property: regular subobject classifier
    proof: The set $\{0,1\}$ with the chaotic preorder $(0 \leq 1$, $1 \leq 0)$ is a regular subobject classifier since order-preserving maps $P \to \{0,1\}$ correspond to subsets of $P$.

unsatisfied_properties:
  - property: regular
    proof: See Example 3.14 at the <a href="https://ncatlab.org/nlab/show/regular+category" target="_blank">nLab</a>.

  - property: balanced
    proof: The inclusion $\{0,1\} \to \{0 < 1\}$ provides a counterexample (where in the domain there is no relation between $0$ and $1$).

  - property: skeletal
    proof: This is trivial.

  - property: co-Malcev
    proof: 'See <a href="https://mathoverflow.net/questions/509552">MO/509552</a>: Consider the forgetful functor $U : \Prost \to \Set$ and the relation $R \subseteq U^2$ defined by $R(A) \coloneqq \{(a,b) \in U(A)^2 : a \leq b\}$. Both are representable: $U$ by the singleton preordered set and $R$ by $\{0 \leq 1 \}$. It is clear that $R$ is reflexive, but not symmetric.'

  - property: cofiltered-limit-stable epimorphisms
    proof: We know that <a href="/category/Set">$\Set$</a> does not have this property. Now use the contrapositive of the dual of Lemma 2 <a href="/content/subcategories">here</a> applied to the functor $\Set \to \Prost$ that equips a set with the chaotic preorder.

  - property: effective cocongruences
    proof: 'Consider the proset $E \coloneqq \{ a, b \}$ with the chaotic preorder. This represents the functor which sends a proset to the pairs of elements $x,y$ with $x \le y$ and $y \le x$. Therefore, it defines a cocongruence $1 \rightrightarrows E$, where the maps are the two possible functions. However, this cannot be effective: for any map $h : Z \to 1$ which equalizes the two functions, $Z$ must be empty. But that means the cokernel pair of $h$ is the two-element proset with the trivial preorder.'

special_objects:
  initial object:
    description: empty proset
  terminal object:
    description: singleton proset
  coproducts:
    description: disjoint union with the obvious preorder that leaves the distinct summands incomparable
  products:
    description: direct products with the evident preorder

special_morphisms:
  isomorphisms:
    description: bijective functions that are order-preserving and order-reflecting
    proof: This is easy.
  monomorphisms:
    description: injective order-preserving functions
    proof: The same proof as for <a href="/category/Set">$\Set$</a> can be used.
  epimorphisms:
    description: surjective order-preserving functions
    proof: Clearly, surjective maps are epimorphisms. The converse follows since, as mentioned, the forgetful functor $\Prost \to \Set$ has a right adjoint hence preserves epimorphisms.
  regular monomorphisms:
    description: embeddings
    proof: 'Every regular monomorphism is an embedding by the explicit construction of equalizers. For the converse, let $i : P \to Q$ be an embedding, which we may assume to be an inclusion. Consider the cokernel pair $C \coloneqq Q \cup_P Q$. It exists because the category has pushouts, but we can (and need to) describe it more concretely: As a set, $C$ is a disjoint union of $P$ and two copies of $Q \setminus P$. The elements will be denoted by $p,q_1,q_2$. The $i$th inclusion map $Q \to C$ maps $p \in P$ to itself and $q \in Q \setminus P$ to $q_i$. The ordering is directly induced by $Q$: We have $p \leq p''$ in $C$ iff $p \leq p''$ in $P$, we have $p \leq q_i$ iff $p \leq q$ in $Q$, etc. One verifies that this indeed defines a preorder, and by construction the two maps $Q \rightrightarrows C$ are order-preserving and have equalizer $P$.'