preorder

A preorder (also sometimes called a *quasi-order*, especially if one works with $\lt$ instead of $\leq$) is like a partial order, but without the “antisymmetry” requirement that $x \leq y$ and $y \leq x$ implies $x = y$.

By interpreting the relation $\leq$ as the existence of a unique arrow, preorders may be regarded as certain categories (namely, thin categories); see below for details.

A **preorder** on a set $S$ is a reflexive and transitive relation, generally written $\leq$. A **preordered set**, or **proset**, is a set equipped with a preorder. (This should not be confused with a pro-set, i.e. a pro-object in Set.)

Equivalently, a proset is a (strict) thin category: a strict category such that for any pair of objects $x, y$, there is at most one morphism from $x$ to $y$. In other words, it’s a (strict) category enriched over the cartesian monoidal category of truth values.

Any preordered set is equivalent to a poset. This is a special case of the theorem that every category has a skeleton, but (if you define ‘equivalence’ weakly enough) this case does *not* require the axiom of choice.

In set-theoretic foundations, a preordered set is the same as a thin category (a category in which any two parallel morphisms are equal), and it is partially ordered just when it is skeletal. Thus, asking for a preordered set to be partially ordered may seem to break the principle of equivalence of category theory. However, as remarked above, a thin category always has a skeleton which is a poset; so working with posets up to isomorphism is the same as working with preordered sets up to equivalence. In other words, if $x \le y$ and $y \le x$, so that $x$ and $y$ are isomorphic, we may as well say that they are equal (since they are isomorphic in only one way).

Another way to say this is that the nerve simplicial set of a preorder, which is necessarily a *Segal space* or *category object in an (infinity,1)-category* in $Set \hookrightarrow \infty Grpd$, is in addition a *complete Segal space* or *genuine category object* in $Set$ if the preorder is in fact a partial order. For more on this perspective see at *Segal space – Examples – In Set*.

If we distinguish between isomorphism and equality of elements in a preordered set (hence considering preordered sets up to isomorphism, rather than up to equivalence), then this is equivalent to considering the corresponding thin category to also be a strict category. When treated in this sense, preordered sets are not equivalent to posets.

On the other hand, in non-set-theoretic foundations where not every category need have an underlying set (i.e. need not be a strict category in any canonical way) — such as homotopy type theory or preset theories — a preordered set defined as “a set with a relation $\leq$ …” is automatically a strict category, with a notion of equality of objects coming from the given set. By contrast, in this case a thin category (as opposed to a more general category) does have a canonical structure of strict category in which equality of objects *means* isomorphism, but not every strict thin category is canonical in this sense. In this case, partially ordered sets correspond to thin categories (with canonical strict-category structures), while preordered sets correspond to thin categories with arbitrary strict-category structures.

The 2-category of preorders (more precisely, that of thin categories) is reflective in Cat. The reflector preserves the objects and declares $x \leq y$ if there exists an arrow from $x$ to $y$.

Internal to any regular category every poset is a Cauchy complete category.

This appears as (Rosolini, prop. 2.1).

Internal to any exact category the Cauchy completion of any preorder exists and is its poset reflection?.

This appears as (Rosolini, corollary. 2.3).

Cauchy completion for preorders is discussed in

- G. Rosolini,
*A note on Cauchy completeness for preorders*(pdf)

Revised on May 13, 2017 19:16:29
by Tphyahoo?
(75.82.220.195)