|
|
|
|
|
|
PREORDER
- This article is about the mathematics concept. For preorder traversal of a tree data structure, see tree traversal. For the marketing tactic, see pre-order.
In mathematics, especially in order theory, preorders are certain kinds of binary relations that are closely related to partially ordered sets. The name quasiorder is also a common expression for preorders. Many order theoretical definitions for partially ordered sets can be generalized to preorders, but the extra effort of generalization is rarely needed.
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:
- a ≤ a (reflexivity)
- if a ≤ b and b ≤ c then a ≤ c (transitivity)
A set that is equipped with a preorder is called a preordered set.
If a preorder is also antisymmetric, that is, a ≤ b and b ≤ a implies a = b, then it is a partial order, on the other hand, if it is also symmetric, that is, a ≤ b implies b ≤ a, then it is an equivalence relation.
A partial order on a set T can be constructed from any preorder on set S by associating members of T with "equivalent" members of S. Formally, one defines an equivalence relation ~ over S such that a ~ b if and only if a ≤ b and b ≤ a. Now let T be the quotient set S / ~, i.e., the set of all equivalence classes of ~. T can easily be ordered by defining [x] ≤ [y] if and only if x ≤ y. By the construction of ~ this definition is independent from the chosen representatives and the corresponding relation is indeed well-defined. It is readily verified that this yields a partially ordered set.
A preorder which is preserved in all contexts is called a precongruence. A precongruence which is also symmetric (i.e. is an equivalence relation) is a congruence relation.
Examples of preorders
See also
|
|
|
|
|
|
|