nLab quasiorder

Quasiorders

Quasiorders

Definitions

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

  • xxx \nless x always;
  • If x<y<zx \lt y \lt z, then x<zx \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 xyx \leq y literally to mean that x<yx \lt y or x=yx = y, while x<yx \lt y conversely means that xyx \leq y but xyx \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<zx \lt z, then x<yx \lt y or y<zy \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 AA is any inhabited set and BB is any linearly ordered set, then the function set B AB^A is partially ordered with fgf \leq g meaning that f(x)g(x)f(x) \leq g(x) always and quasiordered with f<gf \lt g meaning that f(x)<g(x)f(x) \lt g(x) always. Except in degenerate cases, it's quite possible to have fgf \ne g, fgf \nless g, and fgf \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.