nLab strict preorder

Redirected from "strict preorders".

Contents

Definitions

A strict preorder or strict 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 strictly preordered set, or strict proset, is a set equipped with a strict preorder.

Properties

Theorem

Strict preorders orders are asymmetric.

Proof

Transitivity of <\lt says that for all xSx \in S and ySy \in S, x<yx \lt y and y<xy \lt x implies x<xx \lt x. However, irreflexivity says that for all xx, xxx \leq x is always false. This implies that for all xx and yy, x<yx \lt y and y<xy \lt x is always false, which is precisely the condition of asymmetry.

As a result, sometimes the term strict partial order is used for strict preorders, since they are always asymmetric. However, the term “strict partial order” is also used for other order relations.

In constructive mathematics

Unlike with other notions of order, a set equipped with a strict preorder cannot be constructively understood as a kind of enriched category (at least, not as far as I know …). Using excluded middle, however, a strict preorder 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 strict preorder satisfies comparison (if x<zx \lt z, then x<yx \lt y or y<zy \lt z), then it is a strict weak order, and additionally, if it is a connected relation, it is a strict total order.

There are also certainly examples of strictly preordered 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 strictly preordered 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.

References

Last revised on December 26, 2023 at 05:10:11. See the history of this page for a list of all contributions to it.