Preorder

related topics
{math, number, function}

In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.

For example, all partial orders and equivalence relations are preorders. The name quasi-order is also common for preorders.

Many order theoretical definitions for partially ordered sets can be generalized to preorders, but the extra effort of generalization is rarely needed.[citation needed]

Contents

Formal definition

Consider some set P and a binary relation ≤ on P. Then ≤ is a preorder, or quasiorder, if it is reflexive and transitive, i.e., for all a, b and c in P, we have that:

Note that an alternate definition of preorder requires the relation to be irreflexive. However, as this article is examining preorders as a logical extension of partial orders, the current definition is more intuitive.

A set that is equipped with a preorder is called a preordered set.

If a preorder is also antisymmetric, that is, ab and ba implies a = b, then it is a partial order.

On the other hand, if it is symmetric, that is, if ab implies ba, then it is an equivalence relation.

A preorder which is preserved in all contexts (i.e. respected by all functions on P) is called a precongruence. A precongruence which is also symmetric (i.e. is an equivalence relation) is a congruence relation.

Equivalently, a preorder on the set P can be defined as a category with object set P where every homset has at most one element (one for objects which are related, zero otherwise).

Examples of preorders

  • Any collection of sets is preordered by their comparative sizes. Thus {3, 7} ≤ {April, June, July}. This applies equally to infinite sets; as one example, Cantor's famous diagonalization result that the real numbers are uncountable (i.e, more numerous than the integers) may be expressed in terms of this preorder as Z < R.
  • Logical implication over sentences.
  • Every finite topological space gives rise to a preorder on its points, in which xy if and only if x belongs to every neighborhood of y, and every finite preorder can be formed as the specialization preorder of a topological space in this way. That is, there is a 1-to-1 correspondence between finite topologies and finite preorders. However, the relation between infinite topological spaces and their specialization preorders is not 1-to-1.
  • A net is a directed preorder, that is, each pair of elements has an upper bound. The definition of convergence via nets is important in topology, where preorders cannot be replaced by partially ordered sets without losing important features.
  • The relation defined by x \le y iff f(x) \le f(y), where f is a function into some preorder.
  • The relation defined by x \le y iff there exists some injection from x to y. Injection may be replaced by surjection, or any type of structure-preserving function, such as ring homomorphism, or permutation.
  • The embedding relation for countable total orderings.
  • The graph-minor relation in graph theory.

Full article ▸

related documents
Presburger arithmetic
Chain rule
Idempotence
Ring (mathematics)
Merkle-Hellman
Boolean ring
ML (programming language)
Trie
Assignment problem
Definable real number
Richard's paradox
Extended real number line
Generalized mean
Splitting lemma
Base (topology)
Meromorphic function
Haar measure
Monster group
Unicity distance
Oracle machine
Queue (data structure)
Axiom of pairing
Legendre symbol
XSL Transformations
Mathematical model
Pigeonhole principle
B-tree
Functional analysis
Elementary group theory
Outer product