Quasiorders

# Quasiorders

## Definitions

A quasiorder on a set $S$ is a (binary) relation $\lt$ on $S$ that is both irreflexive and transitive. That is:

• $x \nless x$ always;
• If $x \lt y \lt z$, then $x \lt z$.

A quasiordered set, or quoset, is a set equipped with a quasiorder.

## Properties

Unlike with other notions of order, a set equipped with a quasiorder cannot be constructively understood as a kind of enriched category (at least, not as far as I know …). Using excluded middle, however, a quasiorder is the same as a partial order; interpret $x \leq y$ literally to mean that $x \lt y$ or $x = y$, while $x \lt y$ conversely means that $x \leq y$ but $x \ne y$.

Instead, the relation $\lt$ should be defined as an irreflexive comparison when generalising mathematics to other categories and to constructive mathematics.

If a quasiorder satisfies comparison (if $x \lt z$, then $x \lt y$ or $y \lt z$), then it is a strict order, and additionally, if it is a linear relation, it is a linear order.

There are also certainly examples of quasiordered sets that are also partially ordered, where $\lt$ and $\leq$ (while related and so denoted with similar symbols) don't correspond as above. For example, if $A$ is any inhabited set and $B$ is any linearly ordered set, then the function set $B^A$ is partially ordered with $f \leq g$ meaning that $f(x) \leq g(x)$ always and quasiordered with $f \lt g$ meaning that $f(x) \lt g(x)$ always. Except in degenerate cases, it's quite possible to have $f \ne g$, $f \nless g$, and $f \leq g$ simultaneously.

Last revised on December 7, 2022 at 16:10:09. See the history of this page for a list of all contributions to it.