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$.

Accordingly, quasiorders in general should usually be replaced by partial orders when generalising mathematics to other categories. However, if a quasiorder satisfies comparison (if $x \lt z$, then $x \lt y$ or $y \lt z$), then it is a linear order (at least on some quotient set), which is an important concept.

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.

Revised on September 2, 2012 10:05:30
by Toby Bartels
(98.23.143.147)